| |
| |
| |
| Introduction to Interconnection Networks | |
| |
| |
| |
| Three Questions About Interconnection Networks | |
| |
| |
| |
| Uses of Interconnection Networks | |
| |
| |
| |
| Network Basics | |
| |
| |
| |
| History | |
| |
| |
| |
| Organization of this Book | |
| |
| |
| |
| A Simple Interconnection Network | |
| |
| |
| |
| Network Specifications and Constraints | |
| |
| |
| |
| Topology | |
| |
| |
| |
| Routing | |
| |
| |
| |
| Flow Control | |
| |
| |
| |
| Router Design | |
| |
| |
| |
| Performance Analysis | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Topology Basics | |
| |
| |
| |
| Nomenclature | |
| |
| |
| |
| Traffic Patterns | |
| |
| |
| |
| Performance | |
| |
| |
| |
| Packaging Cost | |
| |
| |
| |
| Case Study: The SGI Origin 2000 | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Butterfly Networks | |
| |
| |
| |
| The Structure of Butterfly Networks | |
| |
| |
| |
| Isomorphic Butterflies | |
| |
| |
| |
| Performance and Packaging Cost | |
| |
| |
| |
| Path Diversity and Extra Stages | |
| |
| |
| |
| Case Study: The BBN Butterfly | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Torus Networks | |
| |
| |
| |
| The Structure of Torus Networks | |
| |
| |
| |
| Performance | |
| |
| |
| |
| Building Mesh and Torus Networks | |
| |
| |
| |
| Express Cubes | |
| |
| |
| |
| Case Study: The MIT J-Machine | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Non-Blocking Networks | |
| |
| |
| |
| Non-Blocking vs. Non-Interfering Networks | |
| |
| |
| |
| Crossbar Networks | |
| |
| |
| |
| Clos Networks | |
| |
| |
| |
| Benes Networks | |
| |
| |
| |
| Sorting Networks | |
| |
| |
| |
| Case Study: The Velio VC2002 (Zeus) Grooming Switch | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Slicing and Dicing | |
| |
| |
| |
| Concentrators and Distributors | |
| |
| |
| |
| Slicing and Dicing | |
| |
| |
| |
| Slicing Multistage Networks | |
| |
| |
| |
| Case Study: Bit Slicing in the Tiny Tera | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Routing Basics | |
| |
| |
| |
| A Routing Example | |
| |
| |
| |
| Taxonomy of Routing Algorithms | |
| |
| |
| |
| The Routing Relation | |
| |
| |
| |
| Deterministic Routing | |
| |
| |
| |
| Case Study: Dimension-Order Routing in the Cray T3D | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Oblivious Routing | |
| |
| |
| |
| Valiant's Randomized Routing Algorithm | |
| |
| |
| |
| Minimal Oblivious Routing | |
| |
| |
| |
| Load-Balanced Oblivious Routing | |
| |
| |
| |
| Analysis of Oblivious Routing | |
| |
| |
| |
| Case Study: Oblivious Routing in the Avici Terabit Switch Router(TSR) | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Adaptive Routing | |
| |
| |
| |
| Adaptive Routing Basics | |
| |
| |
| |
| Minimal Adaptive Routing | |
| |
| |
| |
| Fully Adaptive Routing | |
| |
| |
| |
| Load-Balanced Adaptive Routing | |
| |
| |
| |
| Search-Based Routing | |
| |
| |
| |
| Case Study: Adaptive Routing in the Thinking Machines CM-510.7 Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Routing Mechanics | |
| |
| |
| |
| Table-Based Routing | |
| |
| |
| |
| Algorithmic Routing | |
| |
| |
| |
| Case Study: Oblivious Source Routing in the IBM Vulcan Network | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Flow Control Basics | |
| |
| |
| |
| Resources and Allocation Units | |
| |
| |
| |
| Bufferless Flow Control | |
| |
| |
| |
| Circuit Switching | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Buffered Flow Control | |
| |
| |
| |
| Packet-Buffer Flow Control | |
| |
| |
| |
| Flit-Buffer Flow Control | |
| |
| |
| |
| Buffer Management and Backpressure | |
| |
| |
| |
| Flit-Reservation Flow Control | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Deadlock and Livelock | |
| |
| |
| |
| Deadlock | |
| |
| |
| |
| Deadlock Avoidance | |
| |
| |
| |
| Adaptive Routing | |
| |
| |
| |
| Deadlock Recovery | |
| |
| |
| |
| Livelock | |
| |
| |
| |
| Case Study: Deadlock Avoidance in the Cray T3E | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Quality of Service | |
| |
| |
| |
| Service Classes and Service Contracts | |
| |
| |
| |
| Burstiness and Network Delays | |
| |
| |
| |
| Implementation of Guaranteed Services | |
| |
| |
| |
| Implementation of Best-Effort Services | |
| |
| |
| |
| Separation of Resources | |
| |
| |
| |
| Case Study: ATM Service Classes | |
| |
| |
| |
| Case Study: Virtual Networks in the Avici TSR | |
| |
| |
| |
| Bibliographic Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Router Architecture | |
| |
| |
| |
| Basic Router Architecture | |
| |
| |
| |
| Stalls | |
| |
| |
| |