next up previous contents
Next: Incorporating the Lost Cycles Up: Lost Cycles Toolkit Previous: Experiment Design and Generation

Model Generation

We use the measurements produced by the experiment design and generation steps as input to the model generation tool modgen to create a model for the application's performance. Model generation takes place in two steps. We first generate a univariate model for each category of overhead that captures the effects of varying each factor in isolation. We then generate a multivariate model for each overhead category that captures the effects of varying all factors in the experimental design space. The model for the application is simply the sum of these overhead models.

Univariate model generation is straightforward. The lca tool generates a model for each category of overhead by fitting measured data to standard models of overheads. For each cross-tuple, modgen generates a univariate model for each factor by calling lca. For example, one of the univariate models we generate describes how load imbalance varies as a function of P when D=128. Another univariate model describes how contention varies as a function of D when P=8. modgen determines which models to generate, and calls lca to fit a model to a subset of the measured data points.

In multivariate model generation, modgen combines and refits the univariate models. Each multivariate model expresses interactions (or lack thereof) among the various factors. If two factors do not interact, then a reasonable form for the multivariate model is the sum of the univariate models. If two factors do interact, then the multivariate model includes the product of the univariate models. modgen compares the fit for these alternative combinations of univariate models to the measured data to determine the form of the resulting combined model.

Using this approach, we are able to produce a model for each cross-tuple, by combining all the univariate models for that tuple according to the best fit for their interactions. Since the number of cross-tuples is the product of the number of instance levels for each factor (and therefore usually greater than one), this approach will produce several multivariate models that must be combined into one. We incrementally combine these models as they are generated within modgen, using the best fit among the two models or their sum. modgen uses all the measured data points in determining this fit.

The user can evaluate and improve the models generated by the toolkit using an X interface produced by the xmodgen tool. The toolkit supports hierarchical viewpoints of the performance modeling process; some windows describe the model itself, others describe the detailed information used to generate the model. We illustrate the interface and the hierarchical viewpoints using our FFT example, as shown in Figure 5.1.

   figure550
Figure: Tool display for 1D FFT illustrating insufficient experiment replication and inadequate default models.

The Fitting Overview window (Figure 5.1a) is the starting point of the evaluation. This window shows the average determination coefficient for each univariate model representing a factor and overhead category pair (along the top row of values), and for the multivariate model (the bottom row of values). Values close to 1.0 (e.g., insufficient parallelism as a function of D or P, communication loss as a function of P) represent accurate models; smaller values (e.g., synchronization loss as a function of D) represent inaccurate models. (Note that in this display we treat the time remaining after subtracting out all sources of overhead, rt, as simply another category for modeling purposes.)

In this example, the user first wants to know the cause of the low tex2html_wrap_inline1995 value for synchronization loss (0.35) as a function of D. Clicking the mouse on the determination coefficient of interest produces the Fitting window (Figure 5.1b). This window shows the tex2html_wrap_inline1995 values associated with each of the instances of P used to generate the univariate model. From this window we can see that the results for P=8 are poor, and the results for P=24 are terrible (0.54 and 0.17, respectively).

Clicking on the determination coefficient button for P=24 in this window produces the Fit window for synchronization loss when P=24 (Figure 5.1c). This new window shows the two default linear models for synchronization loss, the constants for those models produced by fitting the measured data to the models, and the corresponding tex2html_wrap_inline1995 values. From the poor tex2html_wrap_inline1995 values, we can conclude that the default models for synchronization loss stored in the toolkit are inadequate for modeling synchronization loss in this application.

Clicking on the ``Graph'' button at the bottom of this window produces the Ghostview graph (Figure 5.1d) of these two models and the measured data. This graph not only confirms that the default formulae are inadequate, but also indicates that the measurements exhibit significant variance. The user can reduce the variance by increasing the replication count to 5 (recall the default is 2) and repeating the experiment generation step.

By clicking the ``Formulae'' button at the bottom of the Fit window, the user can edit the standard models file to include additional models of overhead for a given category. These additional models may be derived by exploiting knowledge of the source code, application structure, or by a visual fit of the measured data points. The editor window (Figure 5.1e) at the bottom of the figure illustrates this process. In this case, we added the formula tex2html_wrap_inline2009 based on the observation that the 1D FFT program applies the transform log(d) times to a matrix of size tex2html_wrap_inline2013 .

After performing a similar type of analysis in each of the cases where the generated model has a low determination coefficient, we can repeat the whole process from the experiment generation step. Continuing with our example, the next iteration of modeling produces the results in Figure 5.2. As can be seen in this figure, the variance in the data in the graph is now much smaller (as expected, based on the larger replication count), and the new model for synchronization loss accurately captures the measured data. At this point all but one of the determination coefficients are 0.97 or better, and the remaining coefficient (resource contention as a function of P) is 0.93.

   figure567
Figure: Tool display for 1D FFT illustrating the final stage in the modeling process.

The user can use modgen to verify the accuracy of the model by having the tool use the model to calculate various measured data points. Once again, we use tex2html_wrap_inline1995 as a metric to define how well the model captures the data points used in verification. The user can also use the model to predict values for data points that were not measured.


next up previous contents
Next: Incorporating the Lost Cycles Up: Lost Cycles Toolkit Previous: Experiment Design and Generation

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