BSP machine parameters (table of contents)

1. Summary of machines profiled
2. Table of the BSP machine parameters
3. What is the BSP parameter s?
4. What is the BSP parameter l?
5. What is the BSP parameter g?

Summary of machines profiled

Table of the BSP machine parameters

The benchmark program that was used to calculate the BSP machine parameters can be found here. A more detailed list of the BSP machine parameters, including communication rates in usecs (which are useful for comparing the absolute performance of communication across architectures) can be found here.

The following description of the BSP parameters s, l, and g is taken from the paper:

``Questions and answers about BSP'' David B. Skillicorn, Jonathan M. D. Hill and W. F. McColl. Journal of Scientific Programming, to appear 1997. (See also Technical Report 15-96, Programming Research Group, Oxford University Computing Laboratory, August 1996.. Compressed Postscript, 193K)

What is the BSP parameter s?

1. Lower-bound for s: measures the cost of an inner product, where O(n) operations are performed on a data structure of size n. The value of n is chosen to be far greater than the cache size on each processor. This benchmark therefore gives a lower-bound megaflop rate for the processor as each arithmetic operation induces a cache miss.
2. Upper-bound for s: measures the cost of a dense matrix multiplication, where O(n^3) operations are performed on a data structures of size n^2. Because a large percentage of the computation can be kept in cache, this benchmark gives an upper-bound megaflop rate for the processor.

The values of s given in the table above is an average of the upper and lower bound values for s.

What is the BSP parameter l?

The cost of a barrier synchronisation comes in two parts:

• The cost caused by the variation in the completion times of the computation steps that participate. There is not much that an implementation can do about this, but it does suggest that balance in the computation parts of a superstep is a good thing.
• The cost of reaching a globally-consistent state in all of the processors. This depends, of course, on the communication network, but also on whether or not special-purpose hardware is available for synchronising, and on the way in which interrupts are handled by processors.

The parameter l captures the latter of these costs. The diameter of the communication network, or at least the length of the longest path that allows state to be moved from one processor to another clearly imposes a lower bound on l. However, it is also affected by many other factors, so that, in practice, an accurate value of l for each parallel architecture is obtained empirically.

What is the BSP parameter g?

The ability of a communication network to deliver data is captured by a BSP parameter, g, that measures the permeability of the network to continuous traffic addressed to uniformly-random destinations. As we have seen, BSP programs approximate such traffic. The parameter g is defined such that an h-relation will be delivered in time hg. Subject to some small provisos, hg is an accurate measure of communication performance over a large range of architectures. The value of g is normalised with respect to the clock rate of each architecture so that it is in the same units as the time for executing sequences of instructions.

Sending a message of length m clearly takes longer than sending a message of size 1. BSP does not distinguish between a message of length m and m messages of length 1 --- the cost in either case is mhg (refer to the Q&A paper to see why this isn't a problem). So messages of varying lengths may either be costed using the form mhg where h is the number of messages, or the message lengths can be folded into h, so that it becomes the number of units of data to be transferred.

The parameter g is related to the bisection bandwidth of the communication network but they are not equivalent --- g also depends on factors such as:

• the protocols used to interface with and within the communication network,
• buffer management by both the processors and the communication network,
• the routing strategy used in the communication network, and
• the BSP runtime system.

So g is bounded below by the ratio of p to the bisection bandwidth, suitablly normalised, but may be much larger because of these other factors. Only a very unusual network would have a bisection bandwidth that grew faster than p, so g is a monotonically increasing function of p. The precise value of g is, in practice, determined empirically for each parallel computer, by running suitable benchmarks.

Note that g is not the single-word delivery time, but the single-word delivery time under continuous traffic conditions. This difference is subtle but crucial.

An example of the BSP parameters being used in the analysis of a broadcasting algorithm can be found here.