Principles and Practices of Interconnection Networks

Principles and Practices of Interconnection Networks

by William James Dally, Brian Patrick Towles
Released March 2004
Publisher(s): Morgan Kaufmann
ISBN: 9780080497808

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

One of the greatest challenges faced by designers of digital systems is optimizing the communication and interconnection between system components. Interconnection networks offer an attractive and economical solution to this communication crisis and are fast becoming pervasive in digital systems. Current trends suggest that this communication bottleneck will be even more problematic when designing future generations of machines. Consequently, the anatomy of an interconnection network router and science of interconnection network design will only grow in importance in the coming years.This book offers a detailed and comprehensive presentation of the basic principles of interconnection network design, clearly illustrating them with numerous examples, chapter exercises, and case studies. It incorporates hardware-level descriptions of concepts, allowing a designer to see all the steps of the process from abstract design to concrete implementation.
  • Case studies throughout the book draw on extensive author experience in designing interconnection networks over a period of more than twenty years, providing real world examples of what works, and what doesn't.
  • Tightly couples concepts with implementation costs to facilitate a deeper understanding of the tradeoffs in the design of a practical network.
  • A set of examples and exercises in every chapter help the reader to fully understand all the implications of every design decision.

Table of contents

  1. Cover
  2. Contents
  3. Acknowledgments
  4. Preface
  5. About the Authors
  6. Chapter 1. Introduction to Interconnection Networks
    1. 1.1 Three Questions About Interconnection Networks
    2. 1.2 Uses of Interconnection Networks
    3. 1.3 Network Basics
    4. 1.4 History
    5. 1.5 Organization of this Book
  7. Chapter 2. A Simple Interconnection Network
    1. 2.1 Network Specifications and Constraints
    2. 2.2 Topology
    3. 2.3 Routing
    4. 2.4 Flow Control
    5. 2.5 Router Design
    6. 2.6 Performance Analysis
    7. 2.7 Exercises
  8. Chapter 3 .Topology Basics
    1. 3.1 Nomenclature
    2. 3.2 Traffic Patterns
    3. 3.3 Performance
    4. 3.4 Packaging Cost
    5. 3.5 Case Study: The SGI Origin 2000
    6. 3.6 Bibliographic Notes
    7. 3.7 Exercises
  9. Chapter 4. Butterfly Networks
    1. 4.1 The Structure of Butterfly Networks
    2. 4.2 Isomorphic Butterflies
    3. 4.3 Performance and Packaging Cost
    4. 4.4 Path Diversity and Extra Stages
    5. 4.5 Case Study: The BBN Butterfly
    6. 4.6 Bibliographic Notes
    7. 4.7 Exercises
  10. Chapter 5. Torus Networks
    1. 5.1 The Structure of Torus Networks
    2. 5.2 Performance
    3. 5.3 Building Mesh and Torus Networks
    4. 5.4 Express Cubes
    5. 5.5 Case Study: The MIT J-Machine
    6. 5.6 Bibliographic Notes
    7. 5.7 Exercises
  11. Chapter 6. Non-Blocking Networks
    1. 6.1 Non-Blocking vs. Non-Interfering Networks
    2. 6.2 Crossbar Networks
    3. 6.3 Clos Networks
    4. 6.4 Beneˇs Networks
    5. 6.5 Sorting Networks
    6. 6.6 Case Study: The Velio VC2002 (Zeus) Grooming Switch
    7. 6.7 Bibliographic Notes
    8. 6.8 Exercises
  12. Chapter 7. Slicing and Dicing
    1. 7.1 Concentrators and Distributors
    2. 7.2 Slicing and Dicing
    3. 7.3 Slicing Multistage Networks
    4. 7.4 Case Study: Bit Slicing in the Tiny Tera
    5. 7.5 Bibliographic Notes
    6. 7.6 Exercises
  13. Chapter 8. Routing Basics
    1. 8.1 A Routing Example
    2. 8.2 Taxonomy of Routing Algorithms
    3. 8.3 The Routing Relation
    4. 8.4 Deterministic Routing
    5. 8.5 Case Study: Dimension-Order Routing in the Cray T3D
    6. 8.6 Bibliographic Notes
    7. 8.7 Exercises
  14. Chapter 9. Oblivious Routing
    1. 9.1 Valiant’s Randomized Routing Algorithm
    2. 9.2 Minimal Oblivious Routing
    3. 9.3 Load-Balanced Oblivious Routing
    4. 9.4 Analysis of Oblivious Routing
    5. 9.5 Case Study: Oblivious Routing in the Avici Terabit Switch Router(TSR)
    6. 9.6 Bibliographic Notes
    7. 9.7 Exercises
  15. Chapter 10. Adaptive Routing
    1. 10.1 Adaptive Routing Basics
    2. 10.2 Minimal Adaptive Routing
    3. 10.3 Fully Adaptive Routing
    4. 10.4 Load-Balanced Adaptive Routing
    5. 10.5 Search-Based Routing
    6. 10.6 Case Study: Adaptive Routing in the Thinking Machines CM-5
    7. 10.7 Bibliographic Notes
    8. 10.8 Exercises
  16. Chapter 11. Routing Mechanics
    1. 11.1 Table-Based Routing
    2. 11.2 Algorithmic Routing
    3. 11.3 Case Study: Oblivious Source Routing in the IBM Vulcan Network
    4. 11.4 Bibliographic Notes
    5. 11.5 Exercises
  17. Chapter 12. Flow Control Basics
    1. 12.1 Resources and Allocation Units
    2. 12.2 Bufferless Flow Control
    3. 12.3 Circuit Switching
    4. 12.4 Bibliographic Notes
    5. 12.5 Exercises
  18. Chapter 13. Buffered Flow Control
    1. 13.1 Packet-Buffer Flow Control
    2. 13.2 Flit-Buffer Flow Control
    3. 13.3 Buffer Management and Backpressure
    4. 13.4 Flit-Reservation Flow Control
    5. 13.5 Bibliographic Notes
    6. 13.6 Exercises
  19. Chapter 14. Deadlock and Livelock
    1. 14.1 Deadlock
    2. 14.2 Deadlock Avoidance
    3. 14.3 Adaptive Routing
    4. 14.4 Deadlock Recovery
    5. 14.5 Livelock
    6. 14.6 Case Study: Deadlock Avoidance in the Cray T3E
    7. 14.7 Bibliographic Notes
    8. 14.8 Exercises
  20. Chapter 15. Quality of Service
    1. 15.1 Service Classes and Service Contracts
    2. 15.2 Burstiness and Network Delays
    3. 15.3 Implementation of Guaranteed Services
    4. 15.4 Implementation of Best-Effort Services
    5. 15.5 Separation of Resources
    6. 15.6 Case Study: ATM Service Classes
    7. 15.7 Case Study: Virtual Networks in the Avici TSR
    8. 15.8 Bibliographic Notes
    9. 15.9 Exercises
  21. Chapter 16. Router Architecture
    1. 16.1 Basic Router Architecture
    2. 16.2 Stalls
    3. 16.3 Closing the Loop with Credits
    4. 16.4 Reallocating a Channel
    5. 16.5 Speculation and Lookahead
    6. 16.6 Flit and Credit Encoding
    7. 16.7 Case Study: The Alpha 21364 Router
    8. 16.8 Bibliographic Notes
    9. 16.9 Exercises
  22. Chapter 17. Router Datapath Components
    1. 17.1 Input Buffer Organization
    2. 17.2 Switches
    3. 17.3 Output Organization
    4. 17.4 Case Study: The Datapath of the IBM Colony Router
    5. 17.5 Bibliographic Notes
    6. 17.6 Exercises
  23. Chapter 18. Arbitration
    1. 18.1 Arbitration Timing
    2. 18.2 Fairness
    3. 18.3 Fixed Priority Arbiter
    4. 18.4 Variable Priority Iterative Arbiters
    5. 18.5 Matrix Arbiter
    6. 18.6 Queuing Arbiter
    7. 18.7 Exercises
  24. Chapter 19. Allocation
    1. 19.1 Representations
    2. 19.2 Exact Algorithms
    3. 19.3 Separable Allocators
    4. 19.4 Wavefront Allocator
    5. 19.5 Incremental vs. Batch Allocation
    6. 19.6 Multistage Allocation
    7. 19.7 Performance of Allocators
    8. 19.8 Case Study: The Tiny Tera Allocator
    9. 19.9 Bibliographic Notes
    10. 19.10 Exercises
  25. Chapter 20. Network Interfaces
    1. 20.1 Processor-Network Interface
    2. 20.2 Shared-Memory Interface
    3. 20.3 Line-Fabric Interface
    4. 20.4 Case Study: The MIT M-Machine Network Interface
    5. 20.5 Bibliographic Notes
    6. 20.6 Exercises
  26. Chapter 21. Error Control
    1. 21.1 Know Thy Enemy: Failure Modes and Fault Models
    2. 21.2 The Error Control Process: Detection, Containment, and Recovery
    3. 21.3 Link Level Error Control
    4. 21.4 Router Error Control
    5. 21.5 Network-Level Error Control
    6. 21.6 End-to-end Error Control
    7. 21.7 Bibliographic Notes
    8. 21.8 Exercises
  27. Chapter 22. Buses
    1. 22.1 Bus Basics
    2. 22.2 Bus Arbitration
    3. 22.3 High Performance Bus Protocol
    4. 22.4 From Buses to Networks
    5. 22.5 Case Study: The PCI Bus
    6. 22.6 Bibliographic Notes
    7. 22.7 Exercises
  28. Chapter 23. Performance Analysis
    1. 23.1 Measures of Interconnection Network Performance
    2. 23.2 Analysis
    3. 23.3 Valldation
    4. 23.4 Case Study: Efficiency and Loss in the BBN Monarch Network
    5. 23.5 Bibliographic Notes
    6. 23.6 Exercises
  29. Chapter 24. Simulation
    1. 24.1 Levels of Detail
    2. 24.2 Network Workloads
    3. 24.3 Simulation Measurements
    4. 24.4 Simulator Design
    5. 24.5 Bibliographic Notes
    6. 24.6 Exercises
  30. Chapter 25. Simulation Examples
    1. 25.1 Routing
    2. 25.2 Flow Control Performance
    3. 25.3 Fault Tolerance
  31. Appendix A. Nomenclature
  32. Appendix B. Glossary
  33. Appendix C. Network Simulator
  34. Bibliography
  35. Index
  36. Topology

Product information

  • Title: Principles and Practices of Interconnection Networks
  • Author(s): William James Dally, Brian Patrick Towles
  • Release date: March 2004
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080497808