We presented an overview of Lost Cycles Analysis (LCA) in
Section 2.2.2. In this section we describe the approach in
more detail
. LCA comprises two main phases: predicate profiling
and modeling.
During the predicate profiling phase, the various overheads that affect the performance of the parallel application are measured. Overheads include time spent in tasks not directly related to the problem or time wasted due to some parallel system characteristic. Overheads are divided into categories that meet three criteria: completeness, orthogonality and meaningfulness. The categories are defined via performance predicates [Crovella and LeBlanc1993], which are logical statements that represent the occurrence conditions of the categories.
The modeling phase assigns models to overhead categories. These models are functions of environment variables that rule the application's execution. Data structure dimensions, the number of processors used, and the number of iterations performed are examples of environment variables. The models are fittings of the measured data to default models. One assumption of the LCA approach is that the default models are simple and limited in number for each category, and they can be determined based on previous experience or user knowledge about the application.
The modeling process can be divided into two steps: one-dimensional and
multi-dimensional model generation. The tool lca is used to find
the model's coefficients in both cases. lca finds the best model
for a category using a direct method of general linear least squares
minimization based on Singular Value Decomposition (SVD)
[Press et al.
1992]. The metric used for fitting is the determination
coefficient (
), which ranges between 0 to 1, with 1 being the best
possible fitting. The determination coefficient is the fraction of the
total variance that is explained by the fit [Jain1991].
During the one-dimensional modeling step, the user generates models for each environment variable and overhead category separately. lca fits the default models for each category to one environment variable at a time. The LCA methodology assumes that the user is able to come up with meaningful models for each overhead category. Although this assumption is reasonable in some cases, it may not be applicable in all cases [Meira Jr.1995].
To generate the multi-dimensional models, the user combines the one-dimensional models related to each overhead category. This combination can express interactions or a lack of interactions among the environment variables. The tool lca fits the combined models to the multivariate data. There are no default models in this case.
To produce the program's overall model, the user simply adds the multivariate models of the overhead categories, exploiting the orthogonality of the categories.
Note that a significant portion of the modeling work is performed manually by the user. Generating experiments, validating measurements, and combining models are among the tasks the user must perform. The automation of these and other tasks, making the performance modeling process easier, more efficient, and less error-prone is the main motivation for the Lost Cycles Toolkit, described in the section that follows.