  The bisection width of interconnection networks has always been important in
parallel computing, since it bounds the amount of information that can be moved
from one side of a network to another, i.e., the bisection bandwidth. Finding
its exact value has proven to be challenging for some network families. For
instance, the problem of finding the exact bisection width of the
multidimensional torus was posed by Leighton and has remained open for almost
20 years. In this paper we provide the exact value of the bisection width of
the torus, as well as of several d-dimensional classical parallel topologies
that can be obtained by the application of the Cartesian product of graphs. To
do so, we first provide two general results that allow to obtain upper and
lower bounds on the bisection width of a product graph as a function of some
properties of its factor graphs. We also apply these results to obtain bounds
for the bisection bandwidth of a d-dimensional BCube network, a recently
proposed topology for data centers.
