next up previous contents
Next: Model Generation Up: Lost Cycles Toolkit Previous: Lost Cycles Toolkit

Experiment Design and Generation

 

In developing performance models from measured data, there is a tradeoff between the time and effort required to gather the data and the accuracy of the resulting models. Our approach is based on the optimum experimental design techniques presented in [Atkinson and Donev1992, Jain1991].

Our starting point is an instrumented program for 1D FFT. The performance of the program can be characterized by two factors: P (the number of processors) and D (the size of the input array). The levels for these factors (that is, the valid values each factor can assume) are defined by the program and the architecture. Since we use a two-stage pipeline in the implementation of 1D FFT, P can be any even number of processors up to the limit of the architecture. The levels for D as used in the program have the form tex2html_wrap_inline1997 , where N ranges from 4 to 9 (i.e., 16, 32, 64, 128, 256 and 512).

The first step in experimental design is to choose the experiment levels for each factor; that is, the subset of possible levels for each factor that are representative of the experimental design space as a whole. In general, we should choose at least four levels for each factor, because our formulae are at most second-order (requiring 3 points for a unique fit) and because we want some goodness-of-fit feedback (provided by the fourth point). Additional points give a more accurate measure of goodness-of-fit. We chose P=[4, 8, 16, 24] and D =[64, 128, 256, 512].

The actual experiments to be performed correspond to some combination of the various levels for each factor. In factorial design [Atkinson and Donev1992], an experiment is performed for all possible combinations of the levels for P and D, which would require 16 experiments in our example. While this approach provides broad coverage of the experiment space, it can be very time-consuming. A fractional (or reduced) factorial design attempts to provide reasonable coverage of the experiment space, while requiring significantly fewer experiments. In our case we use a cross-tuple approach based on a subset of the levels for each factor, called instance levels. For each instance level, we generate experiments containing that instance level and all other possible levels for the other factors. In our example, this cross-tuple approach requires 12 experiments instead of 16. gif

In order to generate experiments using the expgen tool, the user must supply the factors of interest, and the levels for each factor. The user may choose to supply the instance levels, which determine the actual experiments to be performed, or simply the number of experiments desired. The user can also supply a replication count, which determines the number of times each experiment is performed. The toolkit assumes a default replication count of 2; more redundancy in experiments increases the accuracy of the results. From these values, the experiment generation tool (expgen) generates the actual experiments.

In our example, expgen used instance levels P=[8, 24] and D =[128, 512], and a default replication count of 2. The output of expgen is a set of program scripts, one for each of the 12 experiments to be performed. Each of these scripts is executed twice (possibly overnight, if the experiments are time-consuming), producing predicate profiling information that is stored for use during model generation.


next up previous contents
Next: Model Generation Up: Lost Cycles Toolkit Previous: Lost Cycles Toolkit

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