In this section, we use WT analysis to solve the processor allocation problem for a parallel application. The problem is to determine an assignment of processors to parallel tasks that provides the best performance. A brute-force approach to this problem is to evaluate the performance of all possible processor configurations to determine the best processor allocation. This approach may be prohibitive in terms of the number of executions required. Furthermore the results of exhaustive experimentation would be useless if there were a change in execution parameters other than the allocation of processors. A better approach is to generate a model for the execution time that accounts for allocation of processors, and any other execution parameters that affect performance (such as the problem size). Given such a model, we need only determine the model parameters that provide the minimum execution time for a given problem size.
Generating a model for the execution time of a parallel application is quite difficult however, due to our limited understanding of program behavior. In particular, waiting time is a complex performance phenomenon that is hard to understand because it results from process interactions. There are no general models for waiting time, and changes in execution parameters can generate diverse waiting time characterizations, further complicating the modeling task.
WT analysis facilitates modeling by breaking down the complexity associated with execution delays. Rather than capture complex interactions by blindly fitting observed behavior to analytic forms, we derive models for waiting time from its sources. To illustrate this use of WT, we consider the processor allocation problem for the narrow-band radar tracking benchmark in the CMU Task Parallel Program Suite [Dinda et al. 1994] on the SGI Challenge.
We recoded the initial Fortran implementation of Radar into C, ported it to our SGI Challenge, and instrumented it by hand. The application is a six-stage task-parallel pipeline, where each stage is a data-parallel shared-memory task. There are three data-related parameters: (1) c, the number of channels, (2) r, the number of rows in the radar image, and (3) d, the number of columns in the radar image. The six stages are described below.
In our implementation we grouped stages 1 and 2 into one task (task 0), isolated stage 3 within one task (task 1), and grouped the remaining stages into one task (task 2). We chose this grouping based on the simplicity of the last three stages, and the complexity of the FFT stage.
Our goal is an execution-time model that is a function of the assignment of processors to tasks. Since the processing time of task 2 in our parallelization is very small, we assign one processor to that task and study the effects of varying the number of processors allocated to tasks 0 and 1.
Let the number of processors assigned to task 0 and 1
be
and
, respectively.
Our experimental space consists of the sets of values that
and
can assume.
Our SGI machine has 12 processors, one of which performs most system tasks,
and another of which we reserve for monitoring the execution.
We therefore allocate one processor to task 2,
and vary
from 1 to 4 and
from 1 to 5
(since task 1 has greater asymptotic complexity than task 0).
The execution time (E) of the program depends on the time spent
computing (and communicating) within each task (
),
the time spent waiting in each task (
),
and the total number of processors (
) as follows:
To generate a model for the execution time of the Radar application,
we first execute the program over representative portions of the
experimental space using a reduced-factorial
experimental design [Atkinson and Donev1992].
During each execution, we record the information used for WT analysis
and measure the computation time of each task
(which includes shared memory references).
Using a direct method of general linear least squares minimization
based on singular value decomposition [Press et al.
1992],
we fit the observed measurements for computation
to analytic forms for each task.
This process shows that
and
increase as a linear function
of
and
respectively (due to additional communication),
and
is constant (since it is a sequential task).
The method also produces the constants for each analytic form.
Given these functions for
,
we only need functions for
to produce the model for E.
Applying WT analysis to the same experiments used to produce the
models for
shows that for some portions of the experimental space
task 0 causes waiting time for tasks 1 and 2,
while in other portions of the experimental space,
task 1 causes waiting time for tasks 0 and 2.
This phenomenon is illustrated in figure 4.4,
where the white surface gives the average computation time per
processor for task 1, and the shaded surface gives
the average computation time per processor for task 0.
As seen in the figure, task 1 is dominant for most of our experimental space.
Nonetheless, when we use 1 or 2 processors for task 0,
and more than 2 processors for task 1, task 0 dominates.
It is exactly this variation in the dominant task
that makes is difficult to generate models for
.
According to our WT analysis,
for each pair
there is one waiting time characterization
for each task, and that characterization is based on the dominant stage
for that allocation of processors.
Over the entire space we see two waiting time characterizations
for the synchronization step in each task:
one where task 0 is the longer path,
and another where task 1 is the longer path.
The waiting time for a task at point
is the maximum
of these waiting time characterizations.
Let
be the average computation time per processor of task i
when task 0 and 1 are allocated
and
processors respectively.
Then the waiting time model for task 2
(based on the characterizations produced by WT analysis) is
This model is simply the maximum of the waiting time characterizations
for task 2 produced by WT analysis.
This same approach yields comparable models for
and
.
Substituting these models into the equation for E
results in a model for the execution time of the application.
We produced this model by sampling 14 points in the experimental space.
To validate the model, we used it to predict the execution times
of Radar under processor allocations that were not used in generating
the model.
The average error in the model over an additional 6 points in the
space is only 7%.
Using the model, we found the best processor allocation strategy
to be
and
, and confirmed this result via experimentation.
In is important to note that WT analysis does not require knowledge of the structure of the application, and in particular, our use of WT analysis in this example did not depend on the pipeline structure of Radar. Although the pipeline structure assures us that there is only one waiting time characterization for each point in the experimental space, we do not require that to be true in general, and did not exploit it in developing our model. In fact, our next example (Nagurney) has multiple waiting time characterizations for each point in the experimental space.
Figure 4.4: Average computation time per processor for tasks 0 and 1.