Abstract | ||
---|---|---|
Data parallelism has proven to be an effective technique for high-level programming of a certain class of parallel applications, but it is not well suited to irregular parallel computations. Blelloch and others proposed nested data parallelism (NDP) as a language mechanism for programming irregular parallel applications in a declarative data-parallel style. The key to this approach is a compiler transformation that flattens the NDP computation and data structures into a form that can be executed efficiently on a wide-vector SIMD architecture. Unfortunately, this technique is ill suited to execution on today's multicore machines. We present a new technique, called data-only flattening, for the compilation of NDP, which is suitable for multicore architectures. Data-only flattening transforms nested data structures in order to expose programs to various optimizations while leaving control structures intact. We present a formal semantics of data-only flattening in a core language with a rewriting system. We demonstrate the effectiveness of this technique in the Parallel ML implementation and we report encouraging experimental results across various benchmark applications. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1145/2442516.2442525 | PPOPP |
Keywords | Field | DocType |
parallel application,data-only flattening,ndp computation,effective technique,parallel computation,nested data parallelism,nested data structure,data parallelism,data structure,new technique,flattening,compilers,multicore | Data structure,Programming language,Implicit parallelism,NESL,Computer science,Task parallelism,Parallel computing,Compiler,Data parallelism,Rewriting,Multi-core processor | Conference |
Volume | Issue | ISSN |
48 | 8 | 0362-1340 |
Citations | PageRank | References |
10 | 0.49 | 13 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lars Bergstrom | 1 | 81 | 5.23 |
Matthew Fluet | 2 | 296 | 20.32 |
Mike Rainey | 3 | 183 | 10.69 |
John H. Reppy | 4 | 899 | 84.36 |
Stephen Rosen | 5 | 15 | 0.94 |
Adam Shaw | 6 | 93 | 4.77 |