Network topologies can have signicant eect on the costs of
algorithms due to inter-processor communication. Parallel
algorithms that ignore network topology can suer from con-
tention along network links. However, for particular combi-
nations of computations and network topologies, costly net-
work contention may inevitably become a bottleneck, even
for optimally designed algorithms. We obtain a novel con-
tention lower bound that is a function of the network and
the computation graph parameters. To this end, we com-
pare the communication bandwidth needs of subsets of pro-
cessors and the available network capacity (as opposed to
per-processor analysis in most previous studies). Applying
this analysis we improve communication cost lower bounds
for several combinations of fundamental computations on
common network topologies.
Technical Report No. UCB/EECS-2014-147