RT info:eu-repo/semantics/conferenceObject
T1 Moody Scheduling for Speculative Parallelization
A1 Estébanez López, Álvaro
A1 Llanos Ferraris, Diego Rafael
A1 Orden, David
A1 Palop del Río, Belén
AB Scheduling is one of the factors that most directly affect performance in Thread-Level Speculation (TLS). Since loops may present dependences that cannot be predicted before runtime, Finding a good chunk size is not a simple task. The most used mechanism, Fixed-Size Chunking (FSC), requires many \dry-runs" to set the optimal chunk size. If the loop does not present dependence violations at runtime, scheduling only needs to deal with load balancing issues. For loops where the general pattern of dependences is known, as is the case with Randomized Incremental Algorithms, specialized mechanisms have been designed to maximize performance. To make TLS available to a wider community, a general scheduling algorithm that does not require a-priori knowledge of the expected pattern of dependences nor previous dry-runs to adjust any parameter is needed. In this paper, we present an algorithm that estimates at runtime the best size of the next chunk to be scheduled.This algorithm takes advantage of our previous knowledge in the design and test of other scheduling mechanisms, and it has a solid mathematical basis. The result is a method that, using information of the execution of the previous chunks, decides the size of the next chunk to be scheduled. Our experimental results show that the use of the proposed schedulingfunction compares or even increases the performance that can be obtained by FSC, greatly reducing the need of a a costly and careful search for the best fixed chunk size.
PB Springer
SN 978-3-662-48095-3
YR 2015
FD 2015
LK http://uvadoc.uva.es/handle/10324/29117
UL http://uvadoc.uva.es/handle/10324/29117
LA eng
NO Euro-Par 2015, 24-28 August, Vienna, Austria
NO Producción Científica
DS UVaDOC
RD 24-abr-2024