Bulk Synchronous to Asynchronous Parallelism: Using Loop Chains and Full Sparse Tiling to Get There

Michelle Mills Strout (Colorado State University)

COMPUTER SYSTEMS SEMINAR

DATE: 2013-08-16
TIME: 15:15:00 - 16:00:00
LOCATION: CSIT N228
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
Scientific computing applications contain a significant amount of loop-level parallelism. Executing the iterations of a loop in parallel and then performing a communication step between neighboring processors (i.e. bulk synchronous parallelism) is a common parallel computing paradigm for these applications. There are many parallel programming languages and libraries that support this model by providing parallel loops and in some cases even handling the communication phase for the programmer. Unfortunately, due to memory bandwidth bottlenecks, synchronization overhead, and reliability issues, a bulk synchronous approach can lead to parallel scaling issues. Task-graph-based programming models have become a popular way of exposing asynchronous parallelism, which can often hide synchronization and access delays with the execution of other tasks. However, the use of task-graph programming models can require significant rewrites of large code bases.

In this talk, I will present loop chaining, an approach for annotating typical bulk synchronous parallel code with data access information, and general full sparse tiling, a run-time scheduling approach for loop chains. The loop chaining parallel programming construct provides compilers and/or run-time systems the information they need schedule across loops. With the loop chain abstraction, scheduling techniques such as generalized full sparse tiling can be used to turn bulk synchronous schedules into asynchronous schedules based on task graphs. All this leads to computations with parallel performance that scales to more cores in a multicore processor.

BIO:
Michelle is on a one-year sabbatical from Colorado State University, where she is an Associate Professor in the High Performance Computing Research Group. She was previously an Enrico Fermi Postdoctoral Scholar at Argonne National Laboratory and the University of Chicago, and holds a PhD from the University of California, San Diego.