Programming Languages Lunch - M. Amber Hassaan, UT ECE, "Parallelizing Ordered Computations using Kinetic Dependence Graph"

Contact Name: 
John Thywissen
GDC 6.302
Feb 11, 2014 12:00pm - 1:30pm

Talk Audience: UTCS Faculty, Grads, Undergrads, Other Interested Parties

Talk Abstract: Efficient parallelization of a computation becomes more challenging when "tasks" (atomic activities or work items) have precedence constraints among them. We call such computations "ordered", as opposed to "unordered" computations where tasks can complete in any order. Existing literature proposes Dependence Graphs (aka DAG-based Scheduling) to parallelize ordered computations. A dependence graph is used to capture the precedence constraints among tasks. This abstraction finds its applications in linear algebra and signal processing domains. 

However, dependence graph becomes inadequate if the set of tasks in an ordered computation, or their dependences change as a result of completing a task. Such dynamic task-sets and dynamic dependences exhibit themselves in ordered computations as simple as computing a minimum-weight spanning tree of a graph to sophisticated techniques for simulating physical phenomena, e.g., elastic deformations, molecular collisions, and multi-agent systems. 

We propose the Kinetic Dependence Graph (KDG), which makes generalizes classic dependence graph by making it dynamic in nature. An update rule incrementally updates the graph upon completion of a task so that it reflects the new set of tasks and their dependences. We have implemented a programming model to express ordered computations at a high level of abstraction, and, a runtime that provides their efficient parallelization using KDGs. Our KDG-based runtime system achieves speedups of up to 21x on 24 cores (against efficient sequential baseline) on a wide range of ordered programs that each had its own domain-specific parallelization strategy. Our work shows how some of these domain-specific strategies emerge as specializations of a general KDG-based parallelization model.

Speaker Bio: M. Amber Hassaan is a PhD student in Dr. Pingali's research group. His research focuses on efficient parallelization of  ordered programs. He also contributes to the development of Galois system (