Cost modelling and performance prediction

A cost model helps to guide the choice of programming algorithm.

The separation of communication from synchronisation and the inherent simplicity of the superstep structure make it relatively easy to find a suitable cost-model. The cost is expressed in terms of steps or floating point operations (FlOps) for each portion of the program. The cost parameters are the BSP parameters for the machine and parameters determined by the choice of algorithm and their implementation.

As a BSP program consists of a sequence of supersteps, the ``cost'' of an entire program is the sum of the contributions from its supersteps.

What are the key parameters that determine performance? Extensive research by the originators of the BSPlib showed that the following four key parameters are sufficient (cf. Hill and McColl, 1996):

• the number of processors, $p$;
• processor speed, $s$ (number of steps per second);
• the cost $l$ (steps), of achieving barrier synchronisation (which depends on network latency, which is a measurement of delay from one end of a network to another). Basically $l$ is the cost of telling all processors to wait till all communication has been performed; and
• the cost $g$ (steps per word), of delivering message data. This captures the interprocess communication speed.

Since the processor speed $s$ is essentially a normalising factor, there are only three independent parameters: $p$, $l$ and $g$.

The cost of one superstep is

$$\max (w_{i})+g \cdot \max (h_{i})+l$$ (59)

where $i$ ranges over processors ( $i=1,\dots ,p$), $w_{i}$ is the time for the local computation in processor $i$ and $h_{i}$ is the number of incoming or outcoming messages per processor. The values of the parameters are determined by measurement using suitable benchmarks that mimic average computation and communication loads (cf. Hill, 1996).

The dependence on a specific platform enters the cost function only through the parameters $p$, $l$ and $g$.

We follow convention and count every floating point operation as 1.

The BSP approach offers a simple cost model. In general, cost-modeling applications give a rough ball-park figure of the cost on any parallel machine and configuration size. The role of profiling tools like bsprof aids simplistic pencil and paper cost modeling, and it effectively predicts the cost of an algorithm on any parallel machine (cf. Hill, Crumpton and Burgess, 1996).