Name
Abstract | ||
|---|---|---|
With the rise of Chip multiprocessors (CMPs), the amount of parallel computing power will increase significantly in the near future. However, most programs are sequential in nature and have not been explicitly parallelized, so they cannot exploit these parallel resources. Automatic 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 detected automatically and if so, how much parallelism there is. In this paper, we propose a framework for extracting potential 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 appropriate 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, respectively. We apply our framework on the SPECcpu2000 bzip2 benchmark, achieving a speedup of 3.74 of the compression part and a global speedup of 2.45 on a quad processor system. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1241601.1241612 | SIGARCH Computer Architecture News |
Keywords | Field | DocType |
chip multiprocessors,new graph representation,potential parallelism,function level parallelism,global speedup,parallel resource,appropriate parallel,interprocedural data flow graph,data dependency,parallel computing power,sequential program,data structure,data flow,parallel computer,data flow graph,graph representation | Instruction-level parallelism,Data structure,Implicit parallelism,Computer science,Task parallelism,Parallel computing,Data-flow analysis,Theoretical computer science,Data parallelism,Speedup,Automatic parallelization | Journal |
Volume | Issue | Citations |
35 | 1 | 16 |
PageRank | References | Authors |
0.83 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sean Rul | 1 | 102 | 4.89 |
| Hans Vandierendonck | 2 | 629 | 54.43 |
| Koen De Bosschere | 3 | 1659 | 117.74 |