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:
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.