Skip navigation
Please use this identifier to cite or link to this item:
Title: Moody Scheduling for Speculative Parallelization
Authors: Estebanez, Alvaro
Llanos, Diego R.
Orden, David
Palop, Belen
Conference: Euro-Par
Issue Date: 2015
Publisher: Springer
Description: Producción Científica
Citation: Euro-Par 2015, 24-28 August, Vienna, Austria
Abstract: 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 scheduling function 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.
ISBN: 978-3-662-48095-3
DOI: 10.1007/978-3-662-48096-0_11
Sponsor: Castilla-Leon (VA172A12- 2), MICINN (Spain) and the European Union FEDER (MOGECOPP project TIN2011-25639, HomProg-HetSys project, TIN2014-58876-P, CAPAP-H5 net- work TIN2014-53522-REDT), Madrid Regional Government through the TIGRE5- CM program (S2013/ICE-2919), and by the MICINN Project MTM2011-22792. Belen Palop is partially supported by MINECO MTM2012-30951.
Publisher Version:
Rights Owner: Springer
Language: eng
Rights: info:eu-repo/semantics/restrictedAccess
Appears in Collections:DEP41 - Comunicaciones a congresos, conferencias, etc.

Files in This Item:
File Description SizeFormat 
moody.pdf357,09 kBAdobe PDFThumbnail

This item is licensed under a Creative Commons License Creative Commons

University of Valladolid
Powered by MIT's. DSpace software, Version 5.5