Name
Abstract | ||
|---|---|---|
For more than thirty years, the parallel programming community has used the dependence graph as the main abstraction for reasoning about and exploiting parallelism in "regular" algorithms that use dense arrays, such as finite-differences and FFTs. In this paper, we argue that the dependence graph is not a suitable abstraction for algorithms in new application areas like machine learning and network analysis in which the key data structures are "irregular" data structures like graphs, trees, and sets. To address the need for better abstractions, we introduce a data-centric formulation of algorithms called the operator formulation in which an algorithm is expressed in terms of its action on data structures. This formulation is the basis for a structural analysis of algorithms that we call tao-analysis. Tao-analysis can be viewed as an abstraction of algorithms that distills out algorithmic properties important for parallelization. It reveals that a generalized form of data-parallelism called amorphous data-parallelism is ubiquitous in algorithms, and that, depending on the tao-structure of the algorithm, this parallelism may be exploited by compile-time, inspector-executor or optimistic parallelization, thereby unifying these seemingly unrelated parallelization techniques. Regular algorithms emerge as a special case of irregular algorithms, and many application-specific optimization techniques can be generalized to a broader context. These results suggest that the operator formulation and tao-analysis of algorithms can be the foundation of a systematic approach to parallel programming. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1993498.1993501 | PLDI |
Keywords | Field | DocType |
optimistic parallelization,dependence graph,unrelated parallelization technique,data-centric formulation,suitable abstraction,operator formulation,better abstraction,key data structure,main abstraction,data structure,machine learning,network analysis,algorithms,languages,finite difference,structure analysis | Analysis of parallel algorithms,Programming language,Computer science,Analysis of algorithms,Theoretical computer science,Operator (computer programming),Network analysis,Special case,Data structure,Task parallelism,Parallel computing,Algorithm,Data parallelism | Conference |
Volume | Issue | ISSN |
46 | 6 | 0362-1340 |
Citations | PageRank | References |
158 | 5.09 | 40 |
Authors | ||
12 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keshav Pingali | 1 | 3056 | 256.64 |
| Donald Nguyen | 2 | 419 | 17.94 |
| Milind Kulkarni | 3 | 744 | 45.29 |
| Martin Burtscher | 4 | 1444 | 86.02 |
| M. Amber Hassaan | 5 | 190 | 6.75 |
| Rashid Kaleem | 6 | 214 | 7.07 |
| Tsung-Hsien Lee | 7 | 245 | 9.93 |
| Andrew Lenharth | 8 | 456 | 19.94 |
| Roman Manevich | 9 | 353 | 16.16 |
| Mario Méndez-Lojo | 10 | 272 | 10.20 |
| Dimitrios Prountzos | 11 | 246 | 9.42 |
| Xin Sui | 12 | 340 | 31.49 |