HELIX
Authors:
Open Access
- 31 March 2012
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 84-93
Abstract
We describe and evaluate HELIX, a new technique for automatic loop parallelization that assigns successive iterations of a loop to separate threads. We show that the inter-thread communication costs forced by loop-carried data dependences can be mitigated by code optimization, by using an effective heuristic for selecting loops to parallelize, and by using helper threads to prefetch synchronization signals. We have implemented HELIX as part of an optimizing compiler framework that automatically selects and parallelizes loops from general sequential programs. The framework uses an analytical model of loop speedups, combined with profile data, to choose loops to parallelize. On a six-core Intel® Core i7-980X, HELIX achieves speedups averaging 2.25 x, with a maximum of 4.12x, for thirteen C benchmarks from SPEC CPU2000.Keywords
Funding Information
- Division of Information and Intelligent Systems (IIS-0926148)
This publication has 26 references indexed in Scilit:
- Performance scalability of decoupled software pipeliningACM Transactions on Architecture and Code Optimization, 2008
- Parallel-stage decoupled software pipelining2008
- Time stamp algorithms for runtime parallelization of DOACROSS loops with dynamic dependencesIEEE Transactions on Parallel and Distributed Systems, 2001
- Tolerating memory latency through software-controlled pre-execution in simultaneous multithreading processorsACM SIGARCH Computer Architecture News, 2001
- Redundant synchronization elimination for DOACROSS loopsIEEE Transactions on Parallel and Distributed Systems, 1999
- Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreadingACM Transactions on Computer Systems, 1997
- On effective execution of nonuniform DOACROSS loopsIEEE Transactions on Parallel and Distributed Systems, 1996
- Shared memory consistency models: a tutorialComputer, 1996
- Spin-block synchronization algorithm in the shared memory multiprocessor systemACM SIGOPS Operating Systems Review, 1994
- Validity of the single processor approach to achieving large scale computing capabilities1967