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......Page 12 Acknowledgments......Page 14 Note to the Reader......Page 16 Introduction......Page 18 Beowulf: The Cluster is Born......Page 20 Overview of Parallel Programming Models......Page 21 Putting it all together......Page 22 Quality of Service (QoS) requirements......Page 23 Lossy flow control......Page 24 Lossless flow control......Page 25 Summary......Page 26 Technology trends......Page 30 Communication Stack......Page 33 Introduction......Page 36 Mesh, Torus, and Hypercubes......Page 37 k-ary n-cube tradeoffs......Page 39 Towards High-radix Topologies......Page 42 Pin Bandwidth......Page 43 Economical Optical Signaling......Page 46 Butterfly......Page 47 High-Radix Folded-Clos......Page 48 Dragonfly......Page 51 HyperX......Page 54 Routing Basics......Page 56 Deterministic Routing......Page 57 Non-minimal Routing......Page 58 Universal Global Adaptive Load-Balancing (UGAL)......Page 59 Indirect Adaptive Routing......Page 60 Routing Algorithm Examples......Page 61 Example 2: Flattened Butterfly......Page 62 Example 3: Dragonfly......Page 66 Router Microarchitecture Basics......Page 68 Scaling baseline microarchitecture to high radix......Page 69 Fully Buffered Crossbar......Page 71 Hierarchical Crossbar Architecture......Page 72 Cray YARC Router......Page 74 Mellanox InfiniScale IV......Page 76 Power delivery and cooling......Page 80 Topology and Packaging Locality......Page 85 BlackWidow Node Organization......Page 90 High-radix Folded-Clos Network......Page 91 System Packaging......Page 92 High-radix Fat-tree......Page 93 Packet Format......Page 94 Data-link Layer Protocol......Page 95 Cray XT Multiprocessor......Page 97 3-D torus......Page 98 Routing......Page 99 SeaStar Router Microarchitecture......Page 101 Summary......Page 105 Wire protocols......Page 108 Opportunities......Page 109 Bibliography......Page 110 Authors' Biographies......Page 116 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.