Design space exploration of a software speculative parallelization scheme
Authors:
- 2 May 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 16 (6) , 562-576
Abstract
With speculative parallelization, code sections that cannot be fully analyzed by the compiler are optimistically executed in parallel. Hardware schemes are fast but expensive and require modifications to the processors and/or memory system. Software schemes require no changes to the hardware of existing shared-memory systems, but can suffer from significant overheads involved with the speculative execution. In fact, the performance of software schemes is highly dependent on application characteristics, the design and implementation of the scheme, and the system configuration and size. This paper explores the design space of a recently proposed software speculative parallelization scheme. In the process, we gain insight into the most beneficial features of software schemes for speculative parallelization, as well as the most influential application characteristics. For instance, experimental results show that, contrary to intuition, checking for data dependence violations on every speculative store, as opposed to at commit time, leads to little performance degradation in the worst case and to significantly better performance with large configurations. Also, scheduling policies based on windows can perform very close to fully dynamic policies with a fraction of the memory overhead. Finally, experimental results show consistent speedups in the execution of loops that cannot be parallelized at compile time, both with and without RAW data dependences, for 4 to 32 processors.Keywords
This publication has 24 references indexed in Scilit:
- Toward efficient and robust software speculative parallelization on multiprocessors2003
- Speculative synchronization2002
- Clustered speculative multithreaded processors1999
- The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelizationIEEE Transactions on Parallel and Distributed Systems, 1999
- The superthreaded processor architectureIEEE Transactions on Computers, 1999
- Shared memory consistency models: a tutorialComputer, 1996
- Run-time parallelization and scheduling of loopsIEEE Transactions on Computers, 1991
- The Perfect Club Benchmarks: Effective Performance Evaluation of SupercomputersThe International Journal of Supercomputing Applications, 1989
- Efficient and correct execution of parallel programs that share memoryACM Transactions on Programming Languages and Systems, 1988
- On optimistic methods for concurrency controlACM Transactions on Database Systems, 1981