Performance implications of transient loop-carried data dependences in automatically parallelized loops
Open Access
- 17 March 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 23-33
Abstract
Recent approaches to automatic parallelization have taken advantage of the low-latency on-chip interconnect provided in modern multicore processors, demonstrating significant speedups, even for complex workloads. Although these techniques can already extract significant thread-level parallelism from application loops, we are interested in quantifying and exploiting any additional performance that remains on the table. This paper confirms the existence of significant extra thread-level parallelism within loops parallelized by the HELIX compiler. However, improving static data dependence analysis is unable to reach the additional performance offered because the existing loop-carried dependences are true only on a small subset of loop iterations. We therefore develop three approaches to take advantage of the transient nature of these data dependences through speculation, via transactional memory support. Results show that coupling the state-of-the-art data dependence analysis with fine-grained speculation achieves most of the speedups and may help close the gap towards the limit of HELIX-style thread-level parallelism.Keywords
Funding Information
- Engineering and Physical Sciences Research Council (EP/K026399/1 & EP/G033110/1)
This publication has 38 references indexed in Scilit:
- Haswell: The Fourth-Generation Intel Core ProcessorIEEE Micro, 2014
- XIOSim2012
- Interprocedural Analysis with Lazy Propagation2010
- Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model2008
- Chip Multiprocessor Architecture: Techniques to Improve Throughput and LatencySynthesis Lectures on Computer Architecture, 2007
- The STAMPede approach to thread-level speculationACM Transactions on Computer Systems, 2005
- Redundant synchronization elimination for DOACROSS loopsIEEE Transactions on Parallel and Distributed Systems, 1999
- Parallelization of DOALL and DOACROSS Loops—a Survey1997
- Loop-level parallelism in numeric and symbolic programsIEEE Transactions on Parallel and Distributed Systems, 1993
- Dynamic dependency analysis of ordinary programsACM SIGARCH Computer Architecture News, 1992