ABSTRACT
This chapter provides an overview of network interconnection for multiprocessors. It describes some desired routing properties and routing flow control schemes, e.g., store-and-forward, wormhole, and so on. The chapter introduces the virtual channel concept and different classes of routing algorithms: deterministic, fully adaptive, and partially adaptive algorithms. It discusses some representative routing algorithms proposed and shows how they prevent deadlock. There are several network properties which are directly related to network performance and complexity. The network diameter is the maximum shortest path between any two nodes in the network. A network is symmetric if it is isomorphic to itself with any node as the origin. In a symmetric network, the network is the same seen from any node. A multi-stage interconnect network consists of more than one stage of switch elements which can be set up dynamically according to traffic requests.
