We use a simple model to analyze the performance of our parallel algorithms. Our model is based on the fact that current hardware platforms can be viewed as a collection of powerful processors connected by a communication network that can be modeled as a complete graph on which communication is subject to the restrictions imposed by the latency and the bandwidth properties of the network. We view a parallel algorithm as a sequence of local computations interleaved with communication steps, where we allow computation and communication to overlap. We account for communication costs as follows.
Assuming no congestion, the transfer of a block consisting of m
contiguous words between two processors takes 
time,
where 
is the latency of the network and 
is the time per word at which a processor can inject or receive data from
the network. Note that the bandwidth per processor is inversely
proportional to . We assume that the bisection bandwidth is
sufficiently high to support block permutation routing amongst the p
processors at the rate of 
. In particular, for any
subset of q processors, a block permutation amongst the q processors
takes time, where m is the size of the largest block.
Using this cost model, we can evaluate the communication time
of an algorithm as a function of the input size n, the number
of processors p , and the parameters and . The coefficient
of gives the total number of times
collective communication primitives are used, and the coefficient of
gives the maximum total amount of data exchanged between a
processor and the remaining processors.
This communication model is close to a number of similar models (e.g. [16, 33, 1]) that have recently appeared in the literature and seems to be well-suited for designing parallel algorithms on current high performance platforms.
We define the computation time 
as the maximum time it takes a
processor to perform all the local computation steps. In general, the
overall performance 
involves a tradeoff between
and 
. In many cases, it is possible to minimize both
and simultaneously, and sorting is such a case.