Presentation
D2P: From Recursive Formulations to Distributed-Memory Codes
SessionFrameworks & Tools
Event Type
Paper
TP
Algorithms
Data Analytics
GPUs
Heterogeneous Systems
MPI
Parallel Application Frameworks
Parallel Programming Languages, Libraries, and Models
Performance
Productivity
Programming Systems
Runtime Systems
Scalable Computing
Task-based programming
Tools
TimeTuesday, 19 November 20194pm - 4:30pm
Location301-302-303
DescriptionRecursive formulations of programs are straightforward to reason about and write, often have good locality properties, and readily expose parallelism. We observe that it is easier to automatically generate distributed-memory codes for recursive formulations with certain properties: i) inclusive—a recursive method’s parameters summarize the data access done within the method body. ii) Intersection—data-set intersection tests among method invocations can be computed efficiently.
In this paper we present D2P, a system that automatically generates distributed-memory codes for recursive divide-conquer algorithms with these properties. D2P produces MPI-based implementations starting from shared-memory specifications of the recursive algorithms. We evaluate D2P with recursive Dynamic Programming (DP) algorithms, since these algorithms have the desired properties and are well known. We show that the generated implementations are scalable and efficient: D2P generated implementations execute faster than implementations generated by recent distributed DP frameworks, and are competitive with (and often faster than) hand-written implementations.
In this paper we present D2P, a system that automatically generates distributed-memory codes for recursive divide-conquer algorithms with these properties. D2P produces MPI-based implementations starting from shared-memory specifications of the recursive algorithms. We evaluate D2P with recursive Dynamic Programming (DP) algorithms, since these algorithms have the desired properties and are well known. We show that the generated implementations are scalable and efficient: D2P generated implementations execute faster than implementations generated by recent distributed DP frameworks, and are competitive with (and often faster than) hand-written implementations.
Download PDF
Archive