Minimal‐distance routing for KYKLOS II

We propose a new routing strategy for the KYKLOS II multiprocessor interconnection network that achieves minimum distance for the path between any two processors. For KYKLOS II with 2ⁿ processors, the average distance is shorter than those of previous routing strategies by approximately 2 log₂n. The traffic density, a measure of traffic concentration, is better than previous strategies for up to 2000 processors, though asymptotically inferior to a strategy proposed by Jenevein and Menezes. © 1994 by John Wiley & Sons, Inc.