next up previous contents
Next: Communication vs. Replicated Computation Up: Applications of WT Analysis Previous: Load Imbalance vs. Communication

Processor Allocation in Radar

 

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.

  1. Generate a 3-D input array ( tex2html_wrap_inline1903 ) of complex numbers: tex2html_wrap_inline1905 .

  2. Corner turn the input array to an array of size tex2html_wrap_inline1907 : tex2html_wrap_inline1905 .

  3. Perform 1-D FFT on columns in the turned array: tex2html_wrap_inline1911 .

  4. Scale and reduce the array to a tex2html_wrap_inline1913 array (where k = 40): tex2html_wrap_inline1917 .

  5. Threshold process the new array: tex2html_wrap_inline1917 .

  6. Check and print results of one channel: tex2html_wrap_inline1921 .

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 tex2html_wrap_inline1923 and tex2html_wrap_inline1925 , respectively. Our experimental space consists of the sets of values that tex2html_wrap_inline1923 and tex2html_wrap_inline1925 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 tex2html_wrap_inline1923 from 1 to 4 and tex2html_wrap_inline1925 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 ( tex2html_wrap_inline1937 ), the time spent waiting in each task ( tex2html_wrap_inline1939 ), and the total number of processors ( tex2html_wrap_inline1941 ) as follows:

displaymath1893

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 tex2html_wrap_inline1943 and tex2html_wrap_inline1945 increase as a linear function of tex2html_wrap_inline1923 and tex2html_wrap_inline1925 respectively (due to additional communication), and tex2html_wrap_inline1951 is constant (since it is a sequential task). The method also produces the constants for each analytic form.

Given these functions for tex2html_wrap_inline1937 , we only need functions for tex2html_wrap_inline1939 to produce the model for E. Applying WT analysis to the same experiments used to produce the models for tex2html_wrap_inline1937 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 tex2html_wrap_inline1939 .

According to our WT analysis, for each pair tex2html_wrap_inline1963 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 tex2html_wrap_inline1963 is the maximum of these waiting time characterizations.

Let tex2html_wrap_inline1967 be the average computation time per processor of task i when task 0 and 1 are allocated tex2html_wrap_inline1971 and tex2html_wrap_inline1973 processors respectively. Then the waiting time model for task 2 (based on the characterizations produced by WT analysis) is

displaymath1894

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 tex2html_wrap_inline1975 and tex2html_wrap_inline1977 . 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 tex2html_wrap_inline1981 and tex2html_wrap_inline1983 , 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.

   figure440
Figure 4.4: Average computation time per processor for tasks 0 and 1.


next up previous contents
Next: Communication vs. Replicated Computation Up: Applications of WT Analysis Previous: Load Imbalance vs. Communication

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