Figure 3: Comparison of one- and two-phase personalized communication algorithms
It has been widely believed that an efficient algorithm for
personalized communication is a single-phase algorithm in which
data travels directly from source to destination with no intermediate
routing. These single-phase algorithms generally partition messages
into contention-free routing steps separated by global
synchronizations. As far as we can tell, this algorithm was first
reported (in Japanese) by Take ([40]) for the hypercube
network topology. Later, several variations of this algorithm were
developed (still dependent upon network topology) such as the Optimal
Circuit Switched, Hypercube, or Mesh Algorithm
([38,10,25,37,12,13,14,1,32,23,34,19,24]),
the Pairwise-Exchange (PEX) algorithm ([43,41,42]), and
the general Linear Permutation algorithm ([45]). For our
comparison, we consider the standard algorithm consisting of p
steps, such that during step i, 
, processor j
sends data labelled for processor 
directly to 
.
Figure 3 presents the results of our comparison,
providing empirical support for the notion that our two-phase
personalized communication scheme is faster than the single-phase
communication algorithm described above.