Dynamic Tracing for Legion

Abstract

Dependence analysis is a key ingredient to implicit parallelism. Since analyzing dependencies in a program is costly and even intractable at compile time, most of implicitly parallel programming systems limit the dependence structure of programs to be structural and data independent. This approach reduces the runtime overhead at the cost of expressivity of the system. On the other hand, Legion pursues expressivity of its programming model by providing flexible, data-dependent partitioning primitives and customizable mapping of data, which makes any attempts to optimize the dependence analysis challenging. We have explored a dynamic tracing technique for Legion that significantly reduces the cost of dependence analysis without sacrificing the expressivity. The key observation is that programs' dependence structure, though unstructured and data dependent, is often static, and the dependence analysis discovers the same result repeatedly in most cases. By exploiting this property, the technique we developed first records the results of dependence analysis for a given set of tasks and then replays the results when the same set of tasks are executed again. In this talk, we will present the design and implementation of the dynamic tracing technique and discuss the preliminary experiment results.

Short bio

Wonchan Lee is a 5th year Ph.D. student in the computer science department at Stanford. His research interest is applying programming language theory to high-performance computing. He has been actively contributing to Legion (http://legion.stanford.edu/), a data-centric parallel programming system for portable high performance programs.