High Performance Datacenter Networks: Architectures, Algorithms, and Opportunities (Synthesis Lectures on Computer Architecture)

Datacenter networks provide the communication substrate for large parallel computer systems that form the ecosystem for high performance computing (HPC) systems and modern Internet applications. The design of new datacenter networks is motivated by an array of applications ranging from communication intensive climatology, complex material simulations and molecular dynamics to such Internet applications as Web search, language translation, collaborative Internet applications, streaming video and voice-over-IP. For both Supercomputing and Cloud Computing the network enables distributed applications to communicate and interoperate in an orchestrated and efficient way. This book describes the design and engineering tradeoffs of datacenter networks. It describes interconnection networks from topology and network architecture to routing algorithms, and presents opportunities for taking advantage of the emerging technology trends that are influencing router microarchitecture. With the emergence of "many-core" processor chips, it is evident that we will also need "many-port" routing chips to provide a bandwidth-rich network to avoid the performance limiting effects of Amdahl's Law. We provide an overview of conventional topologies and their routing algorithms and show how technology, signaling rates and cost-effective optics are motivating new network topologies that scale up to millions of hosts. The book also provides detailed case studies of two high performance parallel computer systems and their networks. Table of Contents: Introduction / Background / Topology Basics / High-Radix Topologies / Routing / Scalable Switch Microarchitecture / System Packaging / Case Studies / Closing Remarks Preface Acknowledgments Note to the reader 1. Introduction From supercomputing to cloud computing Beowulf: the cluster is born Overview of parallel programming models Putting it all together Quality of service (QoS) requirements Flow control Lossy flow control Lossless flow control The rise of ethernet Summary 2. Background Interconnection networks Technology trends Topology, routing and flow control Communication stack 3. Topology basics Introduction Types of networks Mesh,torus, and hypercubes Node identifiers K-ary n-cube tradeoffs 4. High-radix topologies Towards high-radix topologies Technology drivers Pin bandwidth Economical optical signaling High-radix topology High-dimension hypercube, mesh, torus Butterfly High-radix folded-clos Flattened butterfly Dragonfly HyperX 5. Routing Routing basics Objectives of a routing algorithm Minimal routing Deterministic routing Oblivious routing Non-minimal routing Valiant's algorithm (VAL) Universal global adaptive load-balancing (UGAL) Progressive adaptive routing (PAR) Dimensionally-adaptive, load-balanced (DAL) routing Indirect adaptive routing Routing algorithm examples Example 1: Folded-clos Example 2: Flattened butterfly Example 3: Dragonfly 6. Scalable switch microarchitecture Router microarchitecture basics Scaling baseline microarchitecture to high radix Fully buffered crossbar Hierarchical crossbar architecture Examples of high-radix routers Cray YARC router Mellanox InfiniScale IV 7. System packaging Packaging hierarchy Power delivery and cooling Topology and packaging locality 8. Case studies Cray BlackWidow multiprocessor BlackWidow node organization High-radix folded-clos network System packaging High-radix fat-tree Packet format Network layer flow control Data-link layer protocol Serializer/deserializer Cray XT multiprocessor 3-D torus Routing Flow control SeaStar router microarchitecture Summary 9. Closing remarks Programming models Wire protocols Opportunities Bibliography Authors' biographies. Preface Acknowledgments Note to the Reader Introduction From Supercomputing to Cloud Computing Beowulf: The Cluster is Born Overview of Parallel Programming Models Putting it all together Quality of Service (QoS) requirements Flow control Lossy flow control Lossless flow control The rise of ethernet Summary Background Interconnection networks Technology trends Topology, Routing and Flow Control Communication Stack Topology Basics Introduction Types of Networks Mesh, Torus, and Hypercubes Node identifiers k-ary n-cube tradeoffs High-Radix Topologies Towards High-radix Topologies Technology Drivers Pin Bandwidth Economical Optical Signaling High-Radix Topology High-Dimension Hypercube, Mesh, Torus Butterfly High-Radix Folded-Clos Flattened Butterfly Dragonfly HyperX Routing Routing Basics Objectives of a Routing Algorithm Minimal Routing Deterministic Routing Oblivious Routing Non-minimal Routing Valiant's algorithm (VAL) Universal Global Adaptive Load-Balancing (UGAL) Progressive Adaptive Routing (PAR) Dimensionally-Adaptive, Load-balanced (DAL) Routing Indirect Adaptive Routing Routing Algorithm Examples Example 1: Folded-Clos Example 2: Flattened Butterfly Example 3: Dragonfly Scalable Switch Microarchitecture Router Microarchitecture Basics Scaling baseline microarchitecture to high radix Fully Buffered Crossbar Hierarchical Crossbar Architecture Examples of High-Radix Routers Cray YARC Router Mellanox InfiniScale IV System Packaging Packaging hierarchy Power delivery and cooling Topology and Packaging Locality Case Studies Cray BlackWidow Multiprocessor BlackWidow Node Organization High-radix Folded-Clos Network System Packaging High-radix Fat-tree Packet Format Network Layer Flow Control Data-link Layer Protocol Serializer/Deserializer Cray XT Multiprocessor 3-D torus Routing Flow Control SeaStar Router Microarchitecture Summary Closing Remarks Programming models Wire protocols Opportunities Bibliography Authors' Biographies Describes the design and engineering tradeoffs of datacenter networks. This book describes interconnection networks from topology and network architecture to routing algorithms, and presents opportunities for taking advantage of the emerging technology trends that are influencing router microarchitecture.