Advanced search
1 file | 982.13 KB

Function level parallelism driven by data dependencies

Sean Rul (UGent) , Hans Vandierendonck (UGent) and Koen De Bosschere (UGent)
(2007) COMPUTER ARCHITECTURE NEWS. 35(1). p.55-62
Author
Organization
Abstract
With the rise of Chip multiprocessors (CMPs), the amount of parallel computing power will increase signif- icantly in the near future. However, most programs are sequential in nature and have not been explicitly paral- lelized, so they cannot exploit these parallel resources. Au- tomatic parallelization of sequential, non-regular codes is very hard, as illustrated by the lack of solutions after more than 30 years of research on the topic. The question remains if there is parallelism in sequential programs that can be de- tected automatically and if so, how much parallelism there is. In this paper, we propose a framework for extracting poten- tial parallelism from programs. Applying this framework to sequential programs can teach us how much parallelism is present in a program, but also tells us what the most appro- priate parallel construct for a program is, e.g. a pipeline, master/slave work distribution, etc. Our framework is profile-based, implying that it is not safe. It builds two new graph representations of the profile-data: the interprocedural data flow graph and the data sharing graph. This graphs show the data-flow between functions and the data structures facilitating this data-flow, respec- tively. We apply our framework on the SPECcpu2000 bzip2 bench- mark, achieving a speedup of 3.74 of the compression part and a global speedup of 2.45 on a quad processor system.

Downloads

  • peper
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 982.13 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Rul, Sean, Hans Vandierendonck, and Koen De Bosschere. 2007. “Function Level Parallelism Driven by Data Dependencies.” Computer Architecture News 35 (1): 55–62.
APA
Rul, S., Vandierendonck, H., & De Bosschere, K. (2007). Function level parallelism driven by data dependencies. COMPUTER ARCHITECTURE NEWS, 35(1), 55–62.
Vancouver
1.
Rul S, Vandierendonck H, De Bosschere K. Function level parallelism driven by data dependencies. COMPUTER ARCHITECTURE NEWS. 2007;35(1):55–62.
MLA
Rul, Sean, Hans Vandierendonck, and Koen De Bosschere. “Function Level Parallelism Driven by Data Dependencies.” COMPUTER ARCHITECTURE NEWS 35.1 (2007): 55–62. Print.
@article{1148370,
  abstract     = {With the rise of Chip multiprocessors (CMPs), the amount of parallel computing power will increase signif- icantly in the near future. However, most programs are sequential in nature and have not been explicitly paral- lelized, so they cannot exploit these parallel resources. Au- tomatic parallelization of sequential, non-regular codes is very hard, as illustrated by the lack of solutions after more than 30 years of research on the topic. The question remains if there is parallelism in sequential programs that can be de- tected automatically and if so, how much parallelism there is. In this paper, we propose a framework for extracting poten- tial parallelism from programs. Applying this framework to sequential programs can teach us how much parallelism is present in a program, but also tells us what the most appro- priate parallel construct for a program is, e.g. a pipeline, master/slave work distribution, etc. Our framework is profile-based, implying that it is not safe. It builds two new graph representations of the profile-data: the interprocedural data flow graph and the data sharing graph. This graphs show the data-flow between functions and the data structures facilitating this data-flow, respec- tively. We apply our framework on the SPECcpu2000 bzip2 bench- mark, achieving a speedup of 3.74 of the compression part and a global speedup of 2.45 on a quad processor system.},
  author       = {Rul, Sean and Vandierendonck, Hans and De Bosschere, Koen},
  issn         = {1943-5851},
  journal      = {COMPUTER ARCHITECTURE NEWS},
  language     = {eng},
  number       = {1},
  pages        = {55--62},
  title        = {Function level parallelism driven by data dependencies},
  url          = {http://dx.doi.org/10.1145/1241601.1241612},
  volume       = {35},
  year         = {2007},
}

Altmetric
View in Altmetric