Preface
Interconnection networks are becoming increasingly pervasive in many different applications, with the operational costs and characteristics of these networks depending considerably on the application. For some applications, interconnection networks have been studied in depth for decades. This is the case for telephone networks, computer networks (telecommunications), and backplane buses. The design and operation of these networks are covered in many excellent books. However, in the last 15 years we have seen a rapid evolution of the interconnection network technology that is currently being infused into a new generation of multiprocessor systems. The technology is mature enough to find its way into commercial products, while constantly presenting new avenues for growth and application. This is the case for the interconnection networks used in multicomputers and distributed shared-memory multiprocessors. At the current time, the basic design issues governing this new generation of multiprocessor network technology are diffused over a large number of technical papers. This book is an attempt to present a coherent description of this technology in a form that emphasizes the engineering aspects of their construction and use.
The lack of standards and the need for very high performance and reliability have been primarily responsible for pushing the development of interconnection networks for multicomputers. This technology was transferred to distributed shared-memory multiprocessors. More recently, this network technology began to be transferred to local area networks (LANs). Also, it has been proposed as a replacement for backplane buses, creating the concept of a system area network (SAN). Hence, the advances in interconnection networks for multicomputers are becoming the basis for the development of interconnection networks for other architectures and environments. Therefore, there is a need for formally stating the basic concepts, the alternative design choices, and the design tradeoffs for most of those networks. In this book, we address this challenge and present in a structured way the basic underlying concepts of most interconnection networks, and representative solutions that have currently been implemented or proposed in the literature.
Style of the Book
The literature on routing algorithms and architectures for multiprocessors is extensive. It is not our intent to serve as a resource for a comprehensive review of this area, although we hope that the bibliography will serve as a good starting point for the interested reader.
With the fast pace of development in this area, any such attempt would have a rather short lifetime. Rather we hope to bring together the basic issues and results, and present them from a practical perspective. We hope such a presentation will have a more lasting value. As a result, selections from the literature for inclusion have been guided more by the nature of the problems they address and the authors’ familiarity with the work. We hope to be as comprehensive as possible in the treatment of fundamental issues rather than extent.
This book follows an engineering approach. It only considers those issues that should be taken into account by the designer. However, for each of those issues, we present a broad set of solutions proposed in the literature. Most of these solutions have been proposed very recently (1991–1996). These solutions are described and compared in an informal but rigorous way. We explicitly avoided including complex mathematical descriptions, making the text clear and easier to understand. The reader can certainly find the detailed mathematical treatment in the associated journal and conference papers. We have striven to ensure that the vast majority of material is from refereed journal and conference proceedings, presented from an engineering perspective. However, descriptions are precise. Moreover, we define some new concepts and structure the knowledge on interconnection networks. A considerable effort has been made to establish new and more accurate classifications for different issues (topologies, switching techniques, routing algorithms, problems that prevent message delivery, etc). Also, we introduce new views that make concepts easier to understand, like the unified view of direct and indirect networks, the unified theory of deadlock avoidance and recovery, and so on. In addition to structuring the knowledge on interconnection networks, this book also describes several recently proposed routers. Also, it presents very detailed performance evaluation results.
Intended Audience
This book is intended to be used by engineers, network designers, faculty, and students. A considerable effort was made to select the material in this book and structure the organization and presentation in a manner that would be useful to all of these very different communities. For engineers, this book provides an overall view of what we feel are the most important issues concerning interconnection networks. Descriptions rely on concepts rather than detailed design specifications and as a result are easy to understand even for people who have had relatively little prior exposure to computer architecture and multiprocessor interconnection networks. For network designers, this book addresses the main issues facing the design of interconnection networks. All the chapters have been written with an engineering approach in mind. Moreover, a section on engineering issues at the end of most chapters focuses on the practical aspects of the issues described in the chapter. Designers will find the description of routers in Chapter 7 and the performance results in Chapter 9 particularly useful. Those issues have been grouped into separate chapters for easier access.
For students, this book provides thorough classifications, clear descriptions, accurate definitions, and unified views, thus structuring the knowledge on interconnection networks. Most of those classifications, definitions, and unified views are new and have not been previously published. The frequent figures contribute to improved understanding of concepts, while detailed descriptions of many routing algorithms provide more accurate descriptions. The book also provides numerous examples throughout the text, helping students to understand the concepts, mechanisms, and algorithms explained in the book. A set of solved and unsolved exercises complements most chapters. Finally, a section on commented references provides pointers to more than 300 papers for further reading. For faculty, this book arranges material on interconnection networks in several well-defined chapters, making it easy to design quarter or semester system courses. Liberal use of examples and figures provides a convenient way to explain the main issues.
Organization of the Book
The book is organized to serve as a reference as well as a source of learning. Therefore each chapter is self-contained in many respects.
Chapter 1: Introduction.
The introductory Chapter provides a presentation of the various classes of interconnection networks and seeks to present them in the context of recent advances in engineering high-performance interconnection networks.
Chapter 2: Message Switching Layer.
This Chapter describes the components that comprise the switching layer, including flow control protocols and buffering mechanisms that have been proposed in recent years. The major mechanisms employed in all currently available routers are covered.
Chapter 3: Deadlock, Livelock, and Starvation.
This Chapter is the heart of the basic issues covered in this book. Descriptions are provided for developing deadlock-free routing protocols and ensuring livelock-free routing. The emphasis is on constructive principles rather than formal proofs.
Chapter 4: Routing Algorithms.
This chapter presents a taxonomy of routing protocols and descriptions of representative routing algorithms in each class. Methodologies are presented for constructing deadlock-free routing algorithms for different switching techniques.
Chapter 5: Collective Communication Support.
Modern algorithms for collective communication are described that exploit the properties of pipelined networks. Hardware and software support for broadcast, multicast, barrier synchronization, and other collective communication operations is described.
Chapter 6: Fault-Tolerant Routing.
As parallel computing architectures grow in size and find their way into mission-critical applications, the need for robust and reliable communication grows. Chapter 6 covers the current generation of fault-tolerant routing algorithms. Particular attention is paid to paradigms, fault models, and network features in support of such routing algorithms.
Chapter 7: Network Architectures.
Optimizing the design of networks is a process of optimizing performance in the presence of physical constraints such as wiring density, pin-out, and chip area. This chapter covers models for optimizing the network topology as well as the design of router architectures to date.
Chapter 8: Messaging Layer Software.
As “time on the wire” continues to drop, the software overheads start becoming an increasingly large portion of the overall message latency. This chapter covers the issues facing the design of the software messaging layer, and the implementation of two current lightweight message layers: active messages and fast messages. A brief introduction and pointers to the Message Passing Interface (MPI) standard are also provided as an example of a user-level application programming interface.
Chapter 9: Performance Evaluation.
Accurate and reliable estimates of the network performance are crucial in developing and assessing design approaches. This chapter takes a detailed walk through evaluation of routing algorithms, network design parameters, and switching techniques. Network interfaces and support for collective communication and fault tolerance are evaluated as well. Emphasis is placed on evaluation techniques and interpretation of simulation results.
Two appendices and a list of references complete the book. The first appendix contains a formal version of the theory of deadlock avoidance described in Chapter 3. The second appendix lists the acronyms used in this book.
Course Organization
This text has been used in an advanced graduate course on multiprocessor interconnection networks taught in a 10-week quarter. For such quarter-long courses, recommended coverage is Chapters 1, 2, 3, 4, 7, 8, and the corresponding part of Chapter 9. Chapters 5 and 6 represent specialized areas that build on the remaining material. These two chapters can easily be covered in a traditional semester course, possibly augmented with recent papers in the last week or two to further the engineering aspect of the book.
Acknowledgments
Trying to selectively integrate as much material as we have attempted to do would not have been feasible without the generous support of many of our colleagues. We would like to thank all those people who contributed to this effort. First of all, we thank Dr. P. López, who contributed most of the performance plots in Chapter 9. He ran the simulations and plotted the performance results presented in Sections 9.3 through 9.10. Some of those plots were prepared for his Ph.D. dissertation [218], but many others were specially developed for this book. We gratefully acknowledge Dr. T. M. Pinkston for reviewing several chapters, rewriting some sections, and providing two new sections, including figures and performance plots. We also thank Dr. D. K. Panda for reviewing Chapter 5 and supplying some figures in Chapters 5 and 7 as well as the performance plots in Sections 9.11.3 through 9.11.6. Also, we thank Dr. J. Miguel, Dr. R. Beivide, Dr. A. Arruabarrena, and Dr. J. A. Gregorio for supplying some of the performance results in Section 9.12. We gratefully acknowledge the time taken by Dr. K. Bolding and Dr. C. Stunkel in discussing details of their work, and Dr. S. Scott, Dr. M. Galles, Dr. J. Carbonaro, and Dr. S. Mukherjee for providing advance copies of papers describing state of the art advances so that the material could be included in this text. We hope we have accurately described their excellent work. We are also grateful to the Ohio State Supercomputing Center for allowing us to use their MPI example. We would also like to thank Dr. W. J. Dally for writing an excellent foreword for this book. And last but not least, we would like to thank Mr. V. Garg, Mr. J. M. Martínez, and Mr. J. Martínez for reading early drafts of some chapters and providing useful suggestions.
This book would not have been possible without the indulgence and infinite patience of our families during what often appeared to be an overwhelming task. They graciously accommodated the lost time during evenings, weekends, and vacations. As a small measure of our appreciation, we dedicate this book to them.