2010 Poster Sessions : Comparing Parallel Programming Models using GRAMPS

Student Name : Daniel Sanchez
Advisor : Christos Kozyrakis
Research Areas: Computer Systems
The spread of multi-core CPUs and rise in core counts has stimulated interest in parallel programming models. Proposed models use automatic schedulers to manage concurrency and communication without additional burden on the programmer. This work compares four major classes of parallel programming models with respect to their scheduling efficiency for execution time, memory footprint, and scalability on general-purpose x86 multi-cores.

The basis for our comparison is GRAMPS, a recently proposed model that represents parallel programs as a graph of independent stages communicating via queues. We study the trade-offs programming models make in their scheduling strategies by replacing the GRAMPS scheduler with schedulers developed based on three popular parallel models---task-stealing workqueues in the style of Cilk, TBB and OpenMP; breadth-first kernel scheduling in the style of GPU programming models (CUDA and OpenCL); and static/offline scheduling in the style of Stream processing.

The task-stealer's emphasis on individual tasks is its strength and weakness. It handles fine-grained parallelism efficiently, but cannot e.g., exploit an application graph to minimize footprint. The breadth-first approach is simple and highly efficient for data-parallel graphs, but cannot capture pipeline parallelism and has a large data queue footprints. Static scheduling seems poorly suited to a general purpose system: schedules are often workload dependent and hard to generate well while the dynamic schedulers naturally adapt without showing significant overheads.

Daniel Sanchez is a PhD candidate in Electrical Engineering at Stanford University.

Jeremy Sugerman is a PhD candidate in Computer Science at Stanford University.

David Lo is a coterminal student in Electrical Engineering at Stanford University.

Richard M. Yoo is a PhD candidate in Electrical Engineering at Stanford University.