Portability of performance with the BSPLib communications library
Jonathan M. D. Hill, Stephen R. Donaldson, David B. Skillicorn · 2002
The BSP cost model makes a new level of power available for designing parallel algorithms. First, it models the actual behaviour of today's parallel computers, and so can be used to choose appropriate algorithms without completely implementing them. Second, it becomes possible to characterise the range of architecture performance over which a particular algorithm is the best choice. This provides the foundations for developing software that is both portable at the source code level, and in its expectation of performance. We illustrate this by comparing three possible implementations of broadcast, and show that a two-phase broadcast algorithm outperforms other techniques whenever the size of the data is large relative to the cost of synchronisation, and that broadcasting using trees is never a good technique (despite its continued popularity). We carry out a similar analysis for samplesort, and show that samplesort cannot perform well on networks of workstations unless the network bandwidth exceeds a certain threshold.