next up previous contents
Next: Analysis Up: Implementation Previous: Implementation

Instrumentation

 

During instrumentation, Carnival inserts calls to the trace library and collects static information that is used for post-processing. Both tasks are performed automatically by tools that use the code manipulation facilities provided by the Sage++ package [Bodin et al.1994].

The instrumentation's goal is to expose the semantic structure of the code and parallelization details that are not explicit in the original HPF code. Thus, Carnival instruments subroutine entry and exit points, loops, function calls, and run-time library calls. All instrumentation routines occur in pairs (e.g., start and end subroutine, start and end loop) that can be nested; each pair delimits a code segment, which receives an identifier that is unique for the application and is used for correlating static and dynamic data (as discussed in Section 3.3.2).

We can instrument programs at various granularities. In choosing the instrumentation granularity, we must address a trade-off between the amount of information provided and the monitoring cost of the instrumentation. Fine-grain instrumentation (e.g., instruction level) provides a detailed description of the execution, but its cost, and therefore intrusion, is very high. On the other hand, coarse-grain instrumentation (e.g., scope level) has significantly less cost, but does not provide important details. Information collected at the scope level, for example, is not precise enough for performance understanding, since non-contiguous segments of a scope are treated as a whole, even though they are distinct and executed at different times. Figure 3.2 presents a simple program that has four scopes A, B, C, and D. Scopes B and C are within A, and scope D, which is a function, is called from both B and C. We can see that scope A is divided into three non-contiguous segments of code: (1) a segment that precedes scope B, (2) a segment that is executed after B and before C, and (3) a segment that is executed after C. Using only static scope information, these three segments are treated as one contiguous segment. A compromise solution is to instrument basic blocks, which provides detailed information with reasonable cost. The three segments that compose scope A are examples of basic blocks. To obtain performance information at the basic block level, we can instrument each basic block using a compiler, or we can use dynamic information about the application, by instrumenting only at the scope level and characterizing the basic block by its static scope and the last scope that was closed. The second option has the advantage of requiring less instrumentation, since instrumentation at the scope level suffices. Also, to generate cumulative timings, which must reflect the dynamic structure of the application, we also consider the call chain to the basic block in the characterization (as described in Section 3.3.2) and separate the measurements of a basic block according to its call chain. Thus, thereafter we refer to a basic block with its call chain as simply a basic block. There are seven basic blocks in the example program depicted in Figure 3.2. Blocks 1, 3, and 5 are subdivisions of scope A. For instance, block 3, which is the portion of code from scope A that is between scopes B and C, is distinguished from 1 and 5 by considering the preceding scope (B). Blocks 2 and 4 comprise the code executed within scopes B and C, respectively. Blocks 6 and 7 refer to the same static scope (D), but they have a different dynamic history (i.e., the scope from which D was called), and therefore are accounted separately.

   figure207
Figure 3.2: Analysis of Dynamic Information

We adopted the second strategy in Carnival, since we collect dynamic information and want to reduce the instrumentation intrusion as much as possible. Thus, dynamic information is collected at the scope level only and the dynamic basic blocks are determined during analysis (as described in Section 3.3.2).

Also, during instrumentation, each scope is assigned a processing category gif, which is also recorded as part of the static information that is used for analysis. The processing categories in the current implementation are:

Scopes are assigned only to the first three categories. All scopes containing calls to the run-time library are categorized as extra computation, since these calls are not part of the original code. The other scopes are assigned either the local or parallel category, depending on the nature of the data they access (local or distributed, respectively) gif. The remaining categories are not generated by instrumentation calls, but inherit the identifiers from the nearest enclosing scope. Send, receive and barrier categories, for example, always happen inside the run-time library and the scope identifier of the callee is used. System calls and multiprogramming may happen inside any other category, and are measured directly by the UTE trace facility. Waiting time, which may happen within barrier or receive operations, is not measured, being determined by analysis of the execution trace file, as described in Chapter 4.

In this implementation of Carnival , the static information recorded is the source code of the application annotated with scope information, which includes starting and ending line numbers, processing category, and the scope identifier. This annotated code is used in the generation of the visual interface of Carnival . The annotations, for example, are used to correlate dynamic and static information.


next up previous contents
Next: Analysis Up: Implementation Previous: Implementation

Wagner Meira
Wed Feb 28 15:37:47 EST 1996