Subsections in the current document:

• 5.1 Crossbar Revisited
• 5.2 Hypercube
• 5.3 Banyan
• 5.4 Benes: Rearrangeably Non-Blocking Fabric
• 5.5 Batcher Sorting Networks
• 5.6 Self-Routing Non-Blocking Fabrics based on Sorting Networks
• 5.7 Clos Networks

Reading Assignments:

• F. Thomson Leighton: "Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes", Morgan Kaufmann, 1992, ISBN 1-55860-117-1:
  • Section 3.2.1: The Benes Network; pp. 451-456.
• T. Cormen, C. Leiserson, R. Rivest: "Introduction to Algorithms", 1990, MIT Press, ISBN 0-262-03141-8, or McGraw-Hill, ISBN 0-07-013143-0:
  • Section 28.3: A Bitonic Sorting Network; pp. 642-645.
• V. Kumar, A. Grama, A. Gupta, G. Karypis: "Introduction to Parallel Computing", Benjamin/Cummings, 1994, ISBN 0-8053-3170-0:
  • Section 6.2.1: Bitonic Sorting; pp. 214-216.
• C. Partridge: "Gigabit Networking", Addison-Wesley, 1994, ISBN 0-201-56333-9:
  • Section 5.6: Batcher-Banyan Switches; pp. 110-123.
• J. Walrand, P. Varaiya: "High Performance Communication Networks", Morgan Kaufmann, 2nd edition, Oct. 1999, ISBN 1-55860-574-6:
  • Sec. 12.1: Switch Performance Measures; pp. 576-579;
  • Sec. 12.2: Time- and Space-Division Switching; pp. 580-582;
  • Sec. 12.3: Modular Switch Designs; pp. 582-588.
• M. Marcus: "The Theory of Connecting Networks and their Complexity: a Review", IEEE Proceedings, vol. 65, no. 9, Sep. 1977, pp. 1263-1271.

5.1 Crossbar Revisited

5.2 Hypercube

5.3 Banyan

5.4 Benes: Rearrangeably Non-Blocking Fabric

5.5 Batcher Sorting Networks

5.6 Self-Routing Non-Blocking Fabrics based on Sorting Networks

5.7 Clos Networks