Networks of workstations are emerging as a cost-effectivealternative to parallel computers. The interconnection betweenworkstations usually relies on switch-based networks with irregulartopologies. This irregularity makes routing and deadlock avoidance quitecomplicated. Current proposals avoid deadlock by removing cyclicdependencies between channels and therefore, many messages are routedalong non-minimal paths, increasing latency and wasting resources. Wepropose a general methodology for the design of adaptive routingalgorithms for networks with irregular topology that improves apreviously proposed one by reducing the probability of routing overnon-minimal paths. The resulting routing algorithms allow messages tofollow minimal paths in most cases, reducing message latency andincreasing network throughput. As an example of application, we proposean improved adaptive routing algorithm for Autonet
展开▼