next up previous contents
Next: Summary Up: Decomposition in Analytic Modeling Previous: Vertical Decomposition

Decomposition by source of overhead

 

In general, we can define overheads as execution delays that appear because of parallelization and prevent the full utilization of the potential parallelism of the system. In the models presented above, these overheads appear implicitly as parameters of the architecture (e.g., latency, cache miss time) or as a natural consequence of the software parallelization (e.g., load imbalance, contention for resources). Decomposition by overhead divides these overheads into meaningful categories that help both the user and the modeling task.

In [Sivasubramaniam et al. 1994], they divide the overheads into two broad classes: algorithmic and architectural. Algorithmic overhead functions are intrinsic to the algorithm and arise due to factors like load imbalance and serial fraction. These overheads correspond to the difference between a theoretical perfect parallelization (i.e., a parallelization that exhibits linear speedup) and the execution of the algorithm on an ideal machine like the PRAM. The interactions between algorithm and architecture (e.g., latency and contention in the network) characterize the second class of overheads. An execution-driven simulation platform is used to capture this overhead. The simulation also separates contention from other interaction overheads. This methodology is used to evaluate the scalability of parallel systems and to help users in identifying the bottlenecks of the algorithm or architecture.

Crovella and LeBlanc developed lost cycles analysis (LCA) [Crovella1994] to automate the construction of performance models of an application as a function of runtime factors. The first interesting characteristic is that LCA is not limited to predefined runtime factors (e.g., number of processors and data size). The second characteristic is the decomposition of parallel overhead into a set of categories that are intuitively meaningful, mutually exclusive, and complete. This decomposition facilitates the generation of performance models for two reasons: the decomposed overheads can be modeled more easily than the total overhead, and each overhead category has certain characteristic behaviors it often follows (called default models), resulting in simple models. The overhead categories are measured via predicate profiling. Predicate profiling assigns measured overhead to categories based on a set of recognizers called performance predicates. The final models are calculated using least squares minimization of the default models and the goodness of the fitting is evaluated via determination coefficients.

The key point of decomposition by overhead is the selection of the categories. More specifically, the trade-offs involved in this selection can be divided into two types: qualitative and quantitative. The meaning and purpose (in the modeling context) of each category are examples of qualitative issues. The ability to measure the category is also qualitative. The quantitative issue (i.e., the number of categories in the model) affects the complexity and cost of the modeling task.

The approaches presented here basically focus on the same kinds of overheads using different methodologies: simulation, analytical, and experimental. We should also note that decomposition by overhead helps in understanding performance, but does not improve the techniques used for modeling each category.

Another difference among the examples presented above is regarding the significance of the models adopted. In the LCA methodology, the models used to characterize the overheads must be provided by the user or derived from real applications, and these models are embedded in a tool in LCA. In other cases [Sivasubramaniam et al. 1994], they are not worried about the descriptive value of the models. We have seen a similar contrast among the approaches presented in section 2.2.1.

Decomposition by source of overhead is helpful in terms of performance understanding. By dividing the parallel overhead into an initial set of categories, a first level of explanation is provided. However, the root causes of performance phenomena (i.e., implementation decisions) cannot be determined from explanations at this level.


next up previous contents
Next: Summary Up: Decomposition in Analytic Modeling Previous: Vertical Decomposition

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