RT info:eu-repo/semantics/article
T1 New Scheduling Strategies for Randomized Incremental Algorithms in the Context of Speculative Parallelization
A1 Llanos Ferraris, Diego Rafael
A1 Orden, David
A1 Palop del Río, Belén
K1 Informática
K1 Parallelism and concurrency
K1 Load balancing and task assignment
K1 Scheduling and task partitioning
K1 Geometrical problems and computations
K1 1203 Ciencia de Los Ordenadores
K1 3304
AB In this work, we address the problem of scheduling loops with dependences in the context of speculative parallelization. We show that the scheduling alternatives are highly influenced by the dependence violation pattern the code presents. We center our analysis in those algorithms where dependences are less likely to appear as the execution proceeds. Particularly, we focus on randomized incremental algorithms, widely used as a much more efficient solution to many problems than their deterministic counterparts. These important algorithms are, in general, hard to parallelize by hand and represent a challenge for any automatic parallelization scheme. Our analysis led us to the development of MESETA, a new scheduling strategy that takes into account the probability of a dependence violation to determine the number of iterations being scheduled. MESETA is compared with existing techniques, including fixed-size chunking (FSC), the only scheduling alternative used so far in the context of speculative parallelization. Our experimental results show a 5.5 percent to 36.25 percent speedup improvement over FSC, leading to a better extraction of the parallelism inherent to randomized incremental algorithms. Moreover, when the cost of dependence violations is too high to obtain speedups, MESETA curves the performance degradation.
PB IEEE
SN 0018-9340
YR 2007
FD 2007
LK https://uvadoc.uva.es/handle/10324/70439
UL https://uvadoc.uva.es/handle/10324/70439
LA eng
NO IEEE Transactions on Computers, vol. 56, no. 6, pp. 839-852, June 2007, ISSN 0018-9340.
NO Producción Científica
DS UVaDOC
RD 20-ene-2025