November 2006 B
High Productivity Computing Systems and the Path Towards Usable Petascale Computing
Pedro C. Diniz, Information Sciences Institute, University of Southern California
Tejus Krishna, Information Sciences Institute, University of Southern California

2. Technical Approach

We now describe in more detail the use of compiler analyses and source-level code instrumentation to extract as much information about the program behavior as possible and with the least amount of run-time overhead.

2.1. System Architecture

Figure 2 depicts the overall system architecture. We use the Open64 infrastructure for program internal representation and transformation.12 Given a source file, the compiler performs a series of analyses and generates a set of static information files. These files have some of the information about the program structure such as basic blocks and loop organization, and about the program structure the compiler can determine statically. Next, the compiler instruments the source code with library function calls to capture at run-time the missing pieces of information. At run-time the execution collects these missing pieces of information in internal data structures to be output to selected files when the program executes with real input data. These instrumented files are then compiled with the native compiler to generate an executable that is linked against the instrumentation library.

2.2. Compiler Analyses

We have implemented the following basic compiler analyses in Open64 that form the basis for our instrumentation:

  • Basic Block Recognition: The analysis uses the basic control flow information in the Open64 intermediate representation (Whirl) to recognize basic blocks and loop structure in addition to call graph;
  • Induction Variable Recognition: We derive induction variables, in some cases capturing induction variables across multiple control flow branches, and as always focusing on scalar variables only;
  • Loop Invariants and Symbolic Constant Loop Bounds: Using induction variables and loop index variables (in Fortran) we recognize which bounds of the inner loops are symbolically constant, i.e., their value is unknown at compile time but does not change through the execution of the loop they control;
  • Data Access Patterns in Array Expressions: We focus on affine index function recognition to determine, either statically or with the help of run-time information, the stride of the array accesses for a given array reference.

Figure 2

Figure 2. Overall system architecture.

Using the basic information from these analyses the compiler instruments the code to determine the following program execution properties:

  • Basic Block Execution Frequency: the absolute number of times a given basic block is executed. In many cases with symbolically constant expression, we hoist the expression that evaluates the number of executions outside the loop that encloses the corresponding basic block.
  • Loop Bounds: The actual values of the loop bounds and thus the number of loop iterations across all invocations of a given loop construct.
  • Virtual Array Address Ranges. For each array reference, the instrumentation keeps track of the range of addresses accessed for each invocation of the loop.
  • Array stride Information: Determine stride of consecutive accesses for each given reference measured in terms of array index function and not the virtual address accessed.

Pages: 1 2 3 4 5 6

Reference this article
"A Compiler-guided Instrumentation for Application Behavior Understanding," CTWatch Quarterly, Volume 2, Number 4B, November 2006 B. http://www.ctwatch.org/quarterly/articles/2006/11/a-compiler-guided-instrumentation-for-application-behavior-understanding/

Any opinions expressed on this site belong to their respective authors and are not necessarily shared by the sponsoring institutions or the National Science Foundation (NSF).

Any trademarks or trade names, registered or otherwise, that appear on this site are the property of their respective owners and, unless noted, do not represent endorsement by the editors, publishers, sponsoring institutions, the National Science Foundation, or any other member of the CTWatch team.

No guarantee is granted by CTWatch that information appearing in articles published by the Quarterly or appearing in the Blog is complete or accurate. Information on this site is not intended for commercial purposes.