For multicomputer or distributed systems that use circuit switching, wormhole routing, or virtual cut-through (the last two are collectively called the cut-through switching), the communication overhead and the message delivery time depend largely upon link contention rather than upon the distance between the source and the destination. That is, a larger communication overhead or a longer delivery delay occurs to a message when it traverses a route with heavier traffic than the one with a longer distance and lesser traffic. This characteristic greatly affects the selection of routes for interprocessor communication and/or load balancing. We consider the load-balancing problem in these types of systems. Our objective is to find the maximum load imbalance that can be eliminated without violating the (traffic) capacity constraint and the route to eliminate the imbalance while keeping the maximum link traffic as low as possible. We investigate the load-balancing problem under various conditions. First, we consider the case in which the excess load on each overloaded node is divisible. We devise a network flow algorithm to solve this type of load balancing problem optimally in polynomial time. Next, we impose the realistic assumption that the system uses a specific routing scheme so that the excess load transferred from an overloaded node to an underloaded node must use the route found by the routing scheme. For this case, we use a graph transformation technique to transform the system graph to another graph to which the same network flow algorithm can be applied to solve the load balancing problem optimally. Finally, we consider the case in which the excess load on each overloaded node is indivisible, i.e., the excess load must be transferred as an entity. We show that the load-balancing problem of this type becomes NP-complete and propose a heuristic algorithm as a solution.

Modern parallel and distributed applications have a wide range of communication characteristics and performance requirements. These diverse characteristics affect the performance and suitability of particular routing and switching policies in multihop point-to-point networks. In this paper, we identify a core set of architectural features necessary for flexible selection and implementation of multiple routing and switching schemes. Using this, we present a flexible router whose routing and switching policies can be tailored to the application, allowing the network to meet these diverse needs. By dedicating a small programmable processor to each incoming link, we can implement wormhole, virtual cut-through, and packet switching, as well as hybrid switching schemes, each under a variety of unicast and multicast routing algorithms. In addition, a flexible router can support several applications or traffic types simultaneously, enabling better support of applications with multiple traffic classes. We have designed, implemented, and fabricated the Programmable Routing Controller (PRG). Cycle-level simulations of mesh-connected PRCs also demonstrate that flexible routing and switching can significantly enhance application performance.

Ghose and Desai (1995) introduced a new interconnection for large-scale distributed memory multiprocessors called the Hierarchical Cubic Network (HCN). The HCN is topologically superior to a comparable hypercube. They also proposed optimal routing algorithms for the HCN and obtained its diameter, which is about three-fourths the diameter of a comparable hypercube. However, their routing algorithm is not distance-optimal. In this paper, we propose an optimal routing algorithm for the HCN and show that HCN has about two-thirds the diameter of a comparable hypercube.