next up previous contents
Next: Experiment Design and Generation Up: Automating Performance Modeling Previous: Lost Cycles Analysis

Lost Cycles Toolkit

 

In this section we describe the Lost Cycles Toolkit, which automates the process of constructing a performance model for a parallel application, and also serves as infra structure for looking at other issues in performance modeling. The toolkit integrates empirical model-building techniques from statistics [Atkinson and Donev1992, Jain1991] with measurement and modeling techniques for parallel programs.

Creation of a performance model for an application using the Lost Cycles Toolkit involves the following steps:

  1. The user designs an experiment to capture the necessary overhead measurements. Based on user input, the tool expgen determines the necessary application executions and creates a program script for execution.
  2. The user runs the experiments by executing the script; the predicate profiler (pp) automatically extracts the overhead measurements from each execution.
  3. Using the program measurements as input, the lca tool finds the best-fitting default univariate model for each overhead category. If no default model is sufficiently accurate for a category, the user is alerted by the xmodgen interface, and given the ability to suggest an alternative model.
  4. Using the modgen tool, the user combines the univariate models into the final, multivariate performance model of the application. Sources of inaccuracy in the final model can be traced through the xmodgen interface back to particular categories or choices of experiments, allowing the user to adjust models or compensate for noisy data.

As described above, the tool is intended to be used in a highly interactive fashion. At each step in the modeling process, the user may provide information that facilitates or constrains the modeling process, reducing the need for experiments, increasing the accuracy of the models, or improving the descriptive value of the models. Such information may derive from an analysis of the application, or previous experience with application modeling. In those cases where the user cannot provide the appropriate information, the toolkit uses reasonable default settings to produce a model automatically.

To describe the Lost Cycles Toolkit and its utilization, we use one-dimensional FFT (1D FFT) on the KSR1 as an example application to illustrate each of the steps in model development. In our implementation of 1D FFT we use a 2-stage pipeline, where the first stage consists of input generation, matrix transpose, FFT, and matrix scaling, and the second stage consists of matrix transpose, FFT, transpose, and output checking. Each stage is allocated half of the available processors and uses data parallelism to exploit those processors.




next up previous contents
Next: Experiment Design and Generation Up: Automating Performance Modeling Previous: Lost Cycles Analysis

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