next up previous contents
Next: Decomposition by source of Up: Decomposition in Analytic Modeling Previous: Horizontal Decomposition

Vertical Decomposition

 

In vertical decomposition, high-level operations (e.g., communication routines, vector operations) are the modeling units. We call this approach vertical decomposition because the focus is on application-level operations, and the models capture characteristics of a parallel system's components at multiple levels.

PERFSIM, which predicts the running time of CM-5 programs, is presented in [Toledo1995]. His approach mixes experimental and statically estimated information. More specifically, all the vector operations, which are usually expensive, are estimated, and the control flow, which is cheap but complicated, is executed. In practice, PERFSIM analyzes a compiler-generated code block and determines the amortized number of cycles it takes to operate on one element in each array. The main source of inaccuracies in the PERFSIM estimations is the occurrence of data-dependent operations, whose execution time depends on the configuration of the data that is processed by the operation. Another possible source of problems is the assumption that the network load is always low and the data network is never a bottleneck.

The main caveat of vertical decomposition is that inaccuracies in the predictions are proportional to the behavior variations in an operation. Such variations can be caused by different data distributions at the moment the operation is activated. Although it is easier to understand the various operations in isolation rather than whole programs, it can be very hard to identify and understand the interactions among those operations. Also, since these approaches consider all levels of the parallel system together, it is hard to determine the influence of each level on the operation's behavior.



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