TBDA: Trace Based Dependence Analyzer

http://www4.ncsu.edu/~rramase/CSC548/TBDA.html

Ravi Ramaseshan rramase@ncsu.edu

Abstract

Dependence graphs can be used as a vehicle for formulating and implementing compiler optimizations. Static compiler analysis of a program may lead to conservative dependence graphs, some of whose edges might be exercised with extremely low probability during most execution runs. Also, imprecise pointer analysis may add may-dependence edges that might prevent aggressive compiler optimizations from being applied on the program. TBDA proposes building a dynamic dependence graph (DDG) based on memory reference traces obtained during a typical run of the program. TBDA also proposes annotating the edges in the dependence graph with distance vectors, direction vectors and probability of the dependence edge being exercised, which can be used by a compiler to base heuristics for speculative or user-directed parallelization.

Framework

The figure below shows the overall framework of the trace based analyzer with the interaction of the various systems and the flow of information through the framework.

The trace based dependence analyzer operates in two distinct phases. The first phase is the tracing phase in which the target program is instrumented to generate a memory trace, loop iteration and function call markers. The instrumented program is then compiled with the tracing library and run with training input to generate a trace file of the memory references. In the second phase, the trace file is given as input to the dependence analyzer which builds the dynamic dependence graph of the program.

Timeline

Date Milestone
26 Oct 2006 Project Statement:
Problem description and set up a webpage.
07 Nov 2006 Project Report I:
Generate trace based dependence graph with ILOADs, ISTOREs, LDIDs, STIDs and CALLs for micro-benchmarks.
13 Nov 2006 Tested the tool over micro-benchmarks and the tracing tool over the equake benchmark. Tracing using binary packed files instead of ASCII.
20 Nov 2006 Converted the tracing tool into the reference ID strategy thereby making each tracing record just two integers.
30 Nov 2006 Code cleanup. Tracing into functions containing no loops by hacking the PreOptimizer to generate DU information for non-loop functions. First draft of final comprehensive project report.
7 Dec 2006 Final Project Report:
Ran tool on equake. Updated website. Updated final project report. Handled method level parallelism. Created tarballs for final project submission.
14 Dec 2006 Final Project Demo

Reports

References