next up previous contents
Next: Integrating WT explanation techniques Up: Research Plan Previous: Research Plan

Extending WT explanation techniques

 

Our primary goal in developing explanation techniques is to correlate performance phenomena to the implementation decisions that cause the phenomena.

Waiting Time Analysis is an example of a first step in this direction, since it identifies dynamic factors that are causing waiting time. However, we still have to complete the explanation process by correlating waiting time characterizations with implementation decisions, such as the data distribution. In our SPMD scenario, it is usually the case that the data distributions adopted in a program are responsible for any waiting time, and an explanation such as your program is performing poorly because of the data distribution is not particularly helpful. We want to know which implementation decisions are responsible for each instance of waiting time, and how much of that waiting time can be attributed to each decision. With this information, the programmer can decide whether it is necessary to change a data distribution or otherwise modify the program.

As a next step in extending WTA, we need to determine what additional information is necessary to conclude the inference process. How to obtain this information is also an issue. We can identify two basic types of additional information: (1) parallelization details, and (2) symbolic analysis information.

Parallelization details include loop scheduling, communication and synchronization points, and any information exchanged by the processors at those points. This information can be exported by the compiler or obtained by properly instrumenting the code. Adaptor [Brandes1995] is a parallel compiler that is freely distributed and can be instrumented to export these parallelization details.

Symbolic analysis [Haghigat1995] may be used to perform timing analysis (i.e., derive cost estimates of the program execution). Although this analysis is unsolvable in the general case, there are many instances that can be solved. For example, we can derive the execution cost of loop iterations as a function of the loop index variable using symbolic analysis. Conditional statements are an obstacle to this analysis, since it may not be possible to determine statically the branch probability of the conditional statement. We can solve this problem by measuring that probability during execution, and thereby enhance the applicability of symbolic analysis by providing execution information that is not available at analysis time. For example, if an unknown loop boundary prevents the timing analysis of a loop, we can insert instrumentation to capture that value, allowing a more accurate and complete timing analysis. There are some tools available that provide symbolic analysis facilities along these lines, including Polaris [Faigin et al. 1994] and Parafrase-2 [Polychronopoulos et al. 1989].

We can classify information about an application according to how it is obtained, from strictly static to completely dynamic. The data distribution is determined statically and an event's time of occurrence is determined dynamically. However, there is other information that can be obtained either dynamically, or statically, or even both. For example, the data structures that are transmitted in a communication exchange can be obtained from the compiler or by instrumentation of the run-time library.

We plan to use this additional information (i.e., parallelization details and cost estimates) to design and implement the remaining WT explanation techniques using Carnival resources.

After we conclude the development of explanation techniques for waiting time, we plan to validate WTA with real applications that are parallelized using the data-parallel paradigm and are publically available. Two examples are the HPF-2 and HPFA program suites [Hawick and Havlak1995].


next up previous contents
Next: Integrating WT explanation techniques Up: Research Plan Previous: Research Plan

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