Bisection bandwidth

In computer networking, if the nodes of a network are bisected into two partitions, the bisection bandwidth is the bandwidth available between the two partitions.[1] Generally, this refers to the worst-case bisection, so long as there are the same number of nodes in each partition.

Theoretical support for the importance of this measure of network performance was developed in the PhD research of Clark Thomborson (formerly Clark Thompson).[2] Thomborson proved that important algorithms for sorting, fast Fourier transformation, and matrix-matrix multiplication become communication-limited—as opposed to CPU-limited or memory-limited—on computers with insufficient bisection width. F. Thomson Leighton's PhD research[3] tightened Thomborson's loose bound [4] on the bisection width of a computationally-important variant of the De Bruijn graph known as the shuffle-exchange graph. Bill Dally analyzed the latency, average case throughput, and hot-spot throughput of k-ary n-cube networks for various k, determining that low-dimensional networks (e.g., tori) have lower latency and higher hot-spot throughput than high-dimensional networks (e.g., binary n-cubes) with the same bisection width.[5]

References

  1. ↑ John L. Hennessy and David A. Patterson (2003). Computer Architecture: A Quantitative Approach (Third ed.). Morgan Kaufmann Publishers, Inc. p. 789. ISBN 1-55860-596-7.
  2. ↑ C. D. Thompson (1980). A complexity theory for VLSI (PDF) (Thesis). Carnegie-Mellon University.
  3. ↑ F. Thomson Leighton (1983). Complexity Issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks (Thesis). MIT Press. ISBN 0-262-12104-2.
  4. ↑ Clark Thompson (1979). Area-time complexity for VLSI. Proc. Caltech Conf. on VLSI Systems and Computations. pp. 81–88.
  5. ↑ Bill Dally (1990). "Performance analysis of k-ary n-cube interconnection networks". IEEE Transactions on Computers 39 (6). doi:10.1109/12.53599.


This article is issued from Wikipedia - version of the Wednesday, February 03, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.