O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Interconnection Networks

Interconnection Networks

by Lionel Ni, Sudhakar Yalamanchili, Jose Duato
Publisher: Morgan Kaufmann
Release Date: August 2002
ISBN: 9781558608528
View table of contents
Start reading

Book Description



The performance of most digital systems today is limited by their communication or interconnection, not by their logic or memory. As designers strive to make more efficient use of scarce interconnection bandwidth, interconnection networks are emerging as a nearly universal solution to the system-level communication problems for modern digital systems.


Interconnection networks have become pervasive in their traditional application as processor-memory and processor-processor interconnect. Point-to-point interconnection networks have replaced buses in an ever widening range of applications that include on-chip interconnect, switches and routers, and I/O systems.


In this book, the authors present in a structured way the basic underlying concepts of most interconnection networks and provide representative solutions that have been implemented in the industry or proposed in the research literature.

* Gives a coherent, comprehensive treatment of the entire field
* Presents a formal statement of the basic concepts, alternative design choices, and design trade-offs
* Provides thorough classifications, clear descriptions, accurate definitions, and unified views to structure the knowledge on interconnection networks
* Focuses on issues critical to designers

Table of Contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. About the Authors
  5. Copyright
  6. Dedication
  7. Foreword
  8. Foreword to the First Printing
  9. Preface
  10. Chapter 1: Introduction
    1. 1.1 Parallel Computing and Networks
    2. 1.2 Parallel Computer Architectures
    3. 1.3 Network Design Considerations
    4. 1.4 Classification of Interconnection Networks
    5. 1.5 Shared-Medium Networks
    6. 1.6 Direct Networks
    7. 1.7 Indirect Networks
    8. 1.8 Hybrid Networks
    9. 1.9 A Unified View of Direct and Indirect Networks
  11. Chapter 2: Message Switching Layer
    1. 2.1 Network and Router Model
    2. 2.2 Basic Concepts
    3. 2.3 Basic Switching Techniques
    4. 2.4 Virtual Channels
    5. 2.5 Hybrid Switching Techniques
    6. 2.6 Optimizing Switching Techniques
    7. 2.7 A Comparison of Switching Techniques
    8. 2.8 Engineering Issues
    9. 2.9 Commented References
  12. Chapter 3: Deadlock, Livelock, and Starvation
    1. 3.1 A Theory of Deadlock Avoidance
    2. 3.2 Extensions
    3. 3.3 Alternative Approaches
    4. 3.4 Deadlock Avoidance in Switch-Based Networks
    5. 3.5 Deadlock Prevention in Circuit Switching and PCS
    6. 3.6 Deadlock Recovery
    7. 3.7 Livelock Avoidance
    8. 3.8 Engineering Issues
    9. 3.9 Commented References
  13. Chapter 4: Routing Algorithms
    1. 4.1 Taxonomy of Routing Algorithms
    2. 4.2 Deterministic Routing Algorithms
    3. 4.3 Partially Adaptive Algorithms
    4. 4.4 Fully Adaptive Algorithms
    5. 4.5 Maximally Adaptive Routing Algorithms
    6. 4.6 Nonminimal Routing Algorithms
    7. 4.7 Backtracking Protocols
    8. 4.8 Routing in MINs
    9. 4.9 Routing in Switch-Based Networks with Irregular Topologies
    10. 4.10 Resource Allocation Policies
    11. 4.11 Engineering Issues
    12. 4.12 Commented References
  14. Chapter 5: Collective Communication Support
    1. 5.1 Collective Communication Services
    2. 5.2 System Support for Collective Communication
    3. 5.3 Preliminary Considerations
    4. 5.4 Models for Multicast Communication
    5. 5.5 Hardware Implementations of Multicast
    6. 5.6 Hardware Support for Barrier Synchronization and Reduction
    7. 5.7 Software Implementations of Multicast
    8. 5.8 Engineering Issues
    9. 5.9 Commented References
  15. Chapter 6: Fault-Tolerant Routing
    1. 6.1 Fault-Induced Deadlock and Livelock
    2. 6.2 Channel and Network Redundancy
    3. 6.3 Fault Models
    4. 6.4 Fault-Tolerant Routing in SAF and VCT Networks
    5. 6.5 Fault-Tolerant Routing in Wormhole-Switched Networks
    6. 6.6 Fault-Tolerant Routing in PCS and Scouting Networks
    7. 6.7 Dynamic Fault Recovery
    8. 6.8 Engineering Issues
    9. 6.9 Commented References
  16. Chapter 7: Network Architectures
    1. 7.1 Network Topology and Physical Constraints
    2. 7.2 Router Architectures
    3. 7.3 Engineering Issues
    4. 7.4 Commented References
  17. Chapter 8: Messaging Layer Software
    1. 8.1 Functionality of the Messaging Layer
    2. 8.2 Impact of Message Processing Delays
    3. 8.3 Implementation of the Messaging Layer
    4. 8.4 Application Programming Layer: The Message Passing Interface
    5. 8.5 Engineering Issues
    6. 8.6 Commented References
  18. Chapter 9: Performance Evaluation
    1. 9.1 Performance Metrics and Normalized Results
    2. 9.2 Workload Models
    3. 9.3 Comparison of Switching Techniques
    4. 9.4 Comparison of Routing Algorithms
    5. 9.5 Effect of Message Length
    6. 9.6 Effect of Network Size
    7. 9.7 Impact of Design Parameters
    8. 9.8 Comparison of Routing Algorithms for Irregular Topologies
    9. 9.9 Injection Limitation
    10. 9.10 Impact of Router Delays on Performance
    11. 9.11 Performance of Collective Communication
    12. 9.12 Software Messaging Layer
    13. 9.13 Performance of Fault-Tolerant Algorithms
    14. 9.14 Conclusions
    15. 9.15 Commented References
  19. Appendix A: Formal Definitions for Deadlock Avoidance
  20. Appendix B: Acronyms
  21. References
  22. Index