Just-In-Time Scheduling for Loop-based Speculative Parallelization

Abstract

Scheduling for speculative parallelization is a problem that remained unsolved despite its importance. Simple methods such as Fixed-Size Chunking (FSC) need several 'dry-runs' before an acceptable chunk size is found. Other traditional scheduling methods were originally designed for loops with no dependences, so they are primarily focused in the problem of load balancing. In general, all these methods perform poorly when used for speculative parallelization, where loops may present unexpected dependences that adversely affect performance. In this work we address the problem of scheduling loops with and without dependences for speculative execution. We have found that a trade-off between minimizing the number of re-executions and reducing overheads can be found if the size of the scheduled block of iterations is calculated at runtime. We introduce here a scheduling method called Just-In- Time (JIT) scheduling that uses the information available during the execution of the loop in order to dynamically compute the size of the next block to be scheduled. The results show a 10% to 26% speedup improvement in real applications with dependences with respect to a carefully- tuned FSC strategy, and a 9% to 39% speedup improvement in real applications without dependences. With our proposal, the number of dependence violations that lead to squashes can be reduced by up to 62%. Moreover, in applications where the cost of dependence violations is too high to obtain speedups with FSC, our runtime scheduling mechanism avoids performance degradation.