next up previous contents
Next: Modeling with Static Analysis Up: Structural Modeling Previous: Structural Modeling

Description-based Models

 

 

For description-based models, the modeling process is based on descriptive information provided by the user about the structure and behavior of the parallel system.

Zhang, Xu and Sun [Zhang et al. 1994] describe a semi-empirical methodology for multiprocessor performance prediction. The model is described via a ``thread'' graph that describes the application program and architecture parameters obtained via experiments. Thread graphs are enhanced task graphs that represent not only the precedence relations among tasks, but also the explicit communication dependences and operations. With a thread graph, different types of communication events in an application can be classified and treated differently. To estimate the parallel execution time, the user must define the thread graph and obtain the elapsed time of all segments, as defined by the thread graph, the application, and the number of processors. The parallel execution time is calculated via a graph algorithm, which is based on the underlying semantics of the parallel system and takes into account the processor allocation strategy. The main idea is to use analytical models for deterministic factors and determine the remaining non-deterministic parameters experimentally. Although the applicability of the model is restricted by the use of the task graph structure, this model differs from the approaches presented above in the sense that it embeds communication information in the application description. It resembles PAMELA [van Gemund1993], but the thread graph representation is more flexible and intuitive. However, the model is not able to handle implicit communication caused by data sharing, for example.

The description-based models are characterized by a program description that consists of a task graph (or equivalent) describing the application parallelization and some parameters that express the hardware features. The main advantage in using task graphs is that they are more amenable to modeling. However, some programming models cannot be precisely characterized via task graphs, a fact that limits the applicability of the technique. Regarding parameters that characterize the hardware, the trade-offs are the same as in parameter-based analytical approaches: the level of abstraction of the parameters, and the difficulty of obtaining them.

Since these techniques rely on thread graphs, the amount of understanding provided is restricted by the parallel-system model adopted by the technique. If the application is simple and can be fully described using the representation provided, we can understand it by considering the resultant model, otherwise many important characteristics are disconsidered, and the model is incomplete, inaccurate, and thus inadequate for performance understanding.


next up previous contents
Next: Modeling with Static Analysis Up: Structural Modeling Previous: Structural Modeling

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