White paper draft. June, 1997.

Assigning PEs to Loosely Synchronous Computations at Runtime

David R. O’Hallaron

1 Overview

This note describes the runtime information that we will need from Remulac in order to assign PEs to loosely synchronous computations such as the sparse matrix vector product (SMVP).

A simple model characterizes the performance of PEs participating in an SMVP. The model relies on application and system properties, and it characterizes the local �oating point performance as well as the communication performance across the network interface. The key system parameters in the model are:

(1) average time per SMVP �op (T_{f}), (2) the overhead per communicated block (T_{l}), (3) the overhead per additional communicated word (T_{w}), and (4) the amount of available memory (M).

Our aim is to use the model to allocate PEs at runtime in order to satisfy certain performance objectives. These objectives might be expressed in relative or absolute terms. For example, we might want the program to spend at least 20% of its time computing (rather than communicating). Or we may require each SMVP to �nish in under 1 second. In either case, a key requirement is getting accurate runtime estimates of the system properties T_{f}, T_{l}, T_{w}, and M.

Section 2 summarizes the performance model. Section 3 sketches an approach for using the model to allocate compute resources.

2 Performance model

Running time for the SMVP is given by

T_{mv} = T_{comp} + T_{comm} ≤ F T_{f} + (B_{max}T_{l} + C_{max}T_{b})  (1)

where T_{comp} is the time required for all processors to �nish their computation phases and T_{comm} is the time required for all PEs to �nish their communication phases. (For reference, the symbols in the writeup are summarized in Figure 1). Equation 1 makes a conservative simplifying assumption that the PE with the most communicated blocks is also the PE with the most communicated words. It can be shown that this assumption overestimates the running time of the communication phase by at most

β = 1 + min_{i is a processor}[max\{\frac{(B_{max} − B_{i})C_{max}}{B_{max}C_{i}} , \frac{(C_{max} − C_{i})B_{max}}{B_{i}C_{max}} \}]  (2)

where 1 ≤ β ≤ 2. For the Quake applications, β is usually 1 and the largest value we have seen is 1.15.

The relationship between the average time for a �oating point operation and the average time for a communicated word is given precisely by

T_{c} = \frac{F}{C_{max}} (\frac{1 − E}{E} ) T_{f}.  (3)

The average time per communicated word can be approximated in terms of the application parameters and lower-level communication parameters in the system:

T_{c} ≤ \frac{B_{max}}{C_{max}} T_{l} + T_{w}  (4)

T_{comm} is overestimated by at most a factor of β, and since T_{c} = T_{comm}/C_{max}, T_{c} is also overestimated by at most a factor β.

Symbol Description
T_{SMV P} running time for SMVP
T_{comp}  running time for SMVP computation phase
T_{comm} running time for SMVP communication phase
F  �ops per processing element (PE)
C_{i}  communicated words for PE i
C_{max}  max number of communicated words per PE
B_{i}  communicated blocks for PE i
B_{max}  max number of communicated blocks per PE
T_{f}  time per �op (inverse of sustained FLOPS)
T_{c}  time per communication word (inverse of sustained bandwidth)
T_{l}  time per block (block latency)
T_{w}  time per additional block word (inverse of block bandwidth)
M  amount of available memory
β  error bound on communication time
E  ef�ciency (T_{comp}/T_{mv})

Figure 1: Symbols.

3 Assigning PEs to the Quake application

Consider the following scenario. The application is dominated by the SMVP and is static in the sense that mesh is does not change over time and there is a �xed amount of work per node per timestep. However, the computing platform does change over time as PEs come online and of�ine, as PE’s become busy and idle, and as available memory is allocated and deaxllocated. The problem is to automatically assign PEs to the Quake application, based on the current con�guration of the computing platform, so as to achieve some performance goal.

Given a basic capability to determine T_{f}, T_{l}, T_{w}, and M at runtime, then this problem is fairly straightforward, as a couple of examples illustrate. For each example, assume that we have precompiled instances of the application for a range of partitions and that we have also precomputed the set of application properties F, B_{max}, C_{max} for each of these partitions.

Example 1. Suppose that the absolute performance goal is for each SMVP to run in under 1 second on the fewest number of PEs. Then we can plug runtime values of T_{l} and T_{w} into Equation 4 for different partitions to determine the appropriate set of PEs. Of course, we must also ensure that the SMVP will �t in the available memory of these processors, so we must also know the system parameter M.

Example 2. Suppose that the relative performance goal is to �nd a collection of PEs that will run the code at 80% ef�ciency. Then we can plug the runtime value of T_{f} into Equation 3 for different partitions to arrive at a partition with the appropriate ef�ciency.