A VLSI router design for hypercube multiprocessors

An efficient interprocessor communication mechanism is essential to the performance of hypercube multiprocessors. All existing hypercube multiprocessors only support one-to-one (unicast) communication. Multi-destination communication (multicast), which is highly demanded in many application areas, is not supported. Moreover, a store-and-forward routing scheme is usually used at each intermediate node, which further increases the communication delay. In this paper we present the hardware design of a VLSI router which is versatile in the sense that it supports unicast communication as well as multicast and broadcast communications. The router can handle messages with variable length and arbitrary number of destinations. For any type of communication, each destination will receive the source message in the minimum number of time steps. The total amount traffic created for message routing is minimum in the case of unicast and broadcast, and is very close to the optimal solution for multicast. Message passing is done in a distributed manner. The router handles message routing in a relay approach in which the routing decision is made immediately after the destination addresses are received. Architectural description of the router design is presented. A VLSI prototype design of the Message Handling Unit, an essential part of the router, is detailed.