next up previous contents
Next: Summary Up: Structural Modeling Previous: Description-based Models

Modeling with Static Analysis

 

Static analysis differs from the descriptive approach in that it requires much less information and effort from the user. Performance information is produced automatically from the original source code. This information is used for parallelization and data partition selection or to help tune the application.

In [Fahringer and Zima1993, Fahringer et al. 1992, Fahringer1995] they presented a prediction tool that is part of the Vienna Fortran Compilation System (VFCS). This tool statically computes a set of parameters that characterize the behavior of the parallel program. These parameters include work distribution, the amount of data transferred, transfer times, network contention, and number of cache misses. Most of these parameters are machine independent and therefore highly portable. The goal of the tool is to rank the performance of different parallel program versions without running them. The computation of the parameters is based on a general loop model in which the bounds expressions may linearly depend on the loop variables of the enclosing loops. Experiments on an iPSC/860 exhibit a strong correlation between the estimated and measured timings. A restriction of this approach is the assumption that parallelizations are based on loops. They also adopt a simplified communication model: to calculate its parameters, the tool assumes worst-case scenarios of traffic and contention that can never occur.

In [Gupta and Banerjee1992] they describe a methodology for statically estimating communication time as a function of the array sizes and the number of processors used in a distributed computation. This estimation is useful for determining automatically the best data partitioning. Their estimates are based on costs associated with library communication routines (e.g., multicast, shift, reduction). The array reference patterns of the application define the routines that are involved in the data movements required by the algorithm. They have used a number of simplifying assumptions that should be relaxed in order to build a truly automated system. In particular, loop bounds in the program and the probabilities of executing different branches are assumed to be known by the compiler. This information can be obtained via profiling of the original code, accounting for importance and cost of basic blocks. It is interesting to note that the estimation of the amount of communication is easier in distributed-memory machines than in shared-memory environments, because all communication is explicit. However, contention in the communication network is not captured in the models, causing inaccuracies as in the shared-memory environments.

Static analysis modeling tools are usually part of compiling environments, where they provide performance information about parallelizations and data partitions of applications. These tools are expensive to develop and implement, because they embed sophisticated techniques. However, their use is trivial and the computational costs for producing predictions are negligible. Regarding accuracy, they are not accurate in absolute values, but they are usually precise in ranking different parallelizations.

The limitations of static-analysis and description-based techniques for performance understanding are similar. In the static-analysis case, the use of the models for performance understanding is limited by the amount of information about the application behavior that can be obtained by static analysis techniques, especially interactions and other dynamic behaviors.


next up previous contents
Next: Summary Up: Structural Modeling Previous: Description-based Models

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