2026-03-13T02:46:06Zhttps://uvadoc.uva.es/oai/request

oai:uvadoc.uva.es:10324/708652024-10-16T19:00:53Zcom_10324_1165com_10324_931com_10324_894col_10324_1337

2024-10-16T15:35:16Z urn:hdl:10324/70865 Meseta: A new scheduling strategy for speculative parallelization of randomized incremental algorithms Llanos Ferraris, Diego Rafael Orden, David Palop del Río, Belén Informática Producción Científica In this work the authors addressed the problem of scheduling loops with dependencies in the context of speculative parallelization. It is shown that scheduling alternatives are highly influenced by the dependence violation pattern presented in the code. The analysis was centered in those algorithms where dependencies are less likely to appear as the execution proceeds, like incremental randomized algorithms. These algorithms are, in general, hard to parallelize by hand, and represent a challenge for any automatic parallelization scheme. The analysis led 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, among others, with fixed-size chunking (FSC), the only scheduling alternative used so far in the context of speculative parallelization. The experimental results showed a 3% to 22% speedup improvement over FSC for the same incremental randomized algorithm. 2024-10-16T15:35:16Z 2024-10-16T15:35:16Z 2005 info:eu-repo/semantics/conferenceObject 2005 ICPP Workshops (HPSEC-05, 7th Workshop on High Performance Scientific and Engineering Computing), Norway, 14-17 June 2005 https://uvadoc.uva.es/handle/10324/70865 10.1109/ICPPW.2005.49 eng https://ieeexplore.ieee.org/document/1488685 info:eu-repo/semantics/openAccess IEEE