Recognizing Opportunities for Thread Level Parallelism Through Trace Analysis

Posted in Conferences, Companies, Science, Development on March 30, 2007

Recognizing Opportunities for Thread Level Parallelism Through Trace Analysis
Google Tech Talks
March 15, 2007


With the rise of chip-multiprocessors (CMPs) as the high-performance architecture of choice, programmers must now find and extract parallelism from their applications to see continued performance improvements. Previous analysis of long-running non-scientific (e.g., SPECint like) program trace data has shown that a fair amount of parallelism is present in modern sequential applications, but this parallelism cannot be exploited via the classic instruction-level parallel approach. Despite the promise of extracting this parallelism for CMPs, no work characterizes which code sequences are parallelizable because these large traces (e.g., terabytes in size, uncompressed) are difficult to mine for useful information.

This talk will present an approach to mining large dynamic execution traces of sequential applications with an emphasis on finding opportunities for construction of parallel codes. The key challenge in this work is representing the relationships between computations in a dynamic trace with billions of operations. Worse, the most useful trace analyses, such as data-dependence visualization, program slicing, and heap variable liveness techniques, require global access to this data. This talk will focus on the novel observation that traces stored as Binary Decision Diagrams (BDDs) are compact and can be analyzed so that the analysis has complexity that is a function of the compressed size. The talk will discuss how to represent trace data in BDD form, how this data can be used for global analysis and visualization, and present some initial results.

Speaker: Manish Vachharajani

Manish is on the faculty of University of Colorado at Boulder

Watch Video

Tags: Techtalks, Google, Conferences, Science, Lectures, Computer Science, Broadcasting, Development, Companies