CSE 291: Interconnection Networks (Winter 2007)

Lectures: MW 5:00-6:20PM, Warren Lecture Hall 2110
Office Hours: MW 4:00-4:50PM, CSE2130

Course Instructor: CK Cheng


Interconnection Architectures and designs including network topologies, wire styles, packaging technologies, routing strategies, flow control methods, deadlock and deadlock avoidance, congestion controls, and router architectures. We will examine applications of networks to parallel computer interconnect, main memory interconnect in multiprocessors, and switching fabric in internet routers.


  • Appendix E, Interconnection Networks, Computer Architecture: A Quantitative Approach, 4th edition, Hennessy and Patterson
  • Principles and Practices of Interconnection Networks, Elsevier, William James Dally and Brian Patrick Towles
  • High Speed Signal Propagation: Advanced Black Magic, Prentice Hall, Howard Johnson, Martin Graham


  • Mathematical Theory of Connecting Networks and Telephone Traffic, V.E. Benes, Mathematics in Science and Engineering, Vol. 17, 1965, Academic Press
  • Topological Structure and Analysis of Interconnection Networks, Junming Xu, 2001, Kluwer Academic Pub.


  • January 15: Holiday
  • January 22, 24: ASPDAC 2007
  • February 19: Holiday


  • Class participation
  • Homeworks
  • Projects
  • Presentations
  • Reports


    Letcture 1 Introduction
    Letcture 2 Projects
    Letcture 2 Introduction from Appendix E of architecture book
    Letcture 3 Topology Construction
    Letcture 4 Hypercube and De Bruijn Networks
    Letcture 5 De Bruijn and Kautz Networks
    Letcture 6 Circulant, Pyramid, Butterfly Networks
    Letcture 7 Circuit Switching: Clos Networks
    Letcture 8.0 BlueGene Example
    Letcture 8 Slicing and Dicing
    Letcture 9 Routing
    Letcture 10 Flow Control
    Letcture 11 Deadlock and Livelock
    Letcture 12 Deadlock (cont.) and Router Architecture
    Letcture 15 Router Control Subsystem and Datapath
    BlackWidow: High-Radix Clos Network S. Scott, D. Abts, J. Kim, W.J. Dally