Ghent University Academic Bibliography

Advanced

Detecting the Existence of Coarse-Grain Parallelism in General-Purpose Programs

Sean Rul UGent, Hans Vandierendonck UGent and Koen De Bosschere UGent (2008) p.1-12
abstract
With the rise of chip-multiprocessors, the problem of parallelizing general-purpose programs has once again been placed on the research agenda. In the 1980s and early 1990s, great successes were obtained to extract parallelism from the inner loops of scientific computations. General-purpose programs, however, stayed out-of-reach due to the complexity of their control flow and data dependences.More recently, thread-level speculation (TLS) has been tauted as the definitive solution for general-purpose programs. TLS again targets inner loops. The program complexity issue is handled by checking and resolving dependences at runtime using complex hardware support. However, results so far have been disappointing and limit studies predict very low potential speedups, in one study just 18%.In this paper we advocate a completely different approach. We show that significant amounts of coarse-grain parallelism exists in the outer program loops, even in general-purpose programs. This coarse-grain parallelism can be exploited efficiently on CMPs without additional hardware support.This paper presents a technique to extract coarse-grain parallelismfrom the outer program loops. Application of this technique to the MiBench and SPEC CPU2000 benchmarks shows that significant amounts of outer-loop parallelism exist. This leads to a speedup of 5.18 for bzip2 compression and 11.8 for an MPEG2 encoder on a Sun UltraSPARC T1 CMP. The parallelization effort was limited to 10 to 20 person-hours per benchmark while we had no prior knowledge of the programs.
Please use this url to cite or link to this publication:
author
organization
year
type
conference
publication status
published
subject
keyword
general-purpose programs, coarse-grain parallelism
pages
12 pages
conference name
First Workshop on Programmability Issues for Multi-Core Computers, MULTIPROG-1
conference location
Goteborg, Sweden
conference start
2008-01-27
language
English
UGent publication?
yes
classification
C1
copyright statement
I have transferred the copyright for this publication to the publisher
id
679091
handle
http://hdl.handle.net/1854/LU-679091
date created
2009-06-05 10:12:57
date last changed
2009-07-03 08:37:34
@inproceedings{679091,
  abstract     = {With the rise of chip-multiprocessors, the problem of parallelizing general-purpose programs has once again been placed on the research agenda. In the 1980s and early 1990s, great successes were obtained to extract parallelism from the inner loops of scientific computations. General-purpose programs, however, stayed out-of-reach due to the complexity of their control flow and data dependences.More recently, thread-level speculation (TLS) has been tauted as the definitive solution for general-purpose programs. TLS again targets inner loops. The program complexity issue is handled by checking and resolving dependences at runtime using complex hardware support. However, results so far have been disappointing and limit studies predict very low potential speedups, in one study just 18\%.In this paper we advocate a completely different approach. We show that significant amounts of coarse-grain parallelism exists in the outer program loops, even in general-purpose programs. This coarse-grain parallelism can be exploited efficiently on CMPs without additional hardware support.This paper presents a technique to extract coarse-grain parallelismfrom the outer program loops. Application of this technique to the MiBench and SPEC CPU2000 benchmarks shows that significant amounts of outer-loop parallelism exist. This leads to a speedup of 5.18 for bzip2 compression and 11.8 for an MPEG2 encoder on a Sun UltraSPARC T1 CMP. The parallelization effort was limited to 10 to 20 person-hours per benchmark while we had no prior knowledge of the programs.},
  author       = {Rul, Sean and Vandierendonck, Hans and De Bosschere, Koen},
  keyword      = {general-purpose programs,coarse-grain parallelism},
  language     = {eng},
  location     = {Goteborg, Sweden},
  pages        = {1--12},
  title        = {Detecting the Existence of Coarse-Grain Parallelism in General-Purpose Programs},
  year         = {2008},
}

Chicago
Rul, Sean, Hans Vandierendonck, and Koen De Bosschere. 2008. “Detecting the Existence of Coarse-Grain Parallelism in General-Purpose Programs.” In , 1–12.
APA
Rul, S., Vandierendonck, H., & De Bosschere, K. (2008). Detecting the Existence of Coarse-Grain Parallelism in General-Purpose Programs (pp. 1–12). Presented at the First Workshop on Programmability Issues for Multi-Core Computers, MULTIPROG-1.
Vancouver
1.
Rul S, Vandierendonck H, De Bosschere K. Detecting the Existence of Coarse-Grain Parallelism in General-Purpose Programs. 2008. p. 1–12.
MLA
Rul, Sean, Hans Vandierendonck, and Koen De Bosschere. “Detecting the Existence of Coarse-Grain Parallelism in General-Purpose Programs.” 2008. 1–12. Print.