ROMM routing on mesh and torus networks

Abstract

is a class of Randomized, Oblivious, Multi-phase, Minimal routing algorithms. ROMM routing offers a potential for improved performance compared to both fully randomized algorithms and deterministic oblivious algorithms, under both light and heavy loads. ROMM routing also offers close to best case performance for many common routing problems. In previous work, these claims were supported by extensive simulations on binary cube networks [30, 31], Here we present analytical and empirical results for ROMM routing on wormhole routed mesh and torus networks. Our simulations show that ROMM algorithms can perform several represent ative routing tasks 1,5 to 3 times faster than fully randomized algorithms, for medium-sized networks. Furthermore, ROMM algorithms are always competitive with deterministic, oblivious routing, and in some cases, up to 2 times faster. 1 Any viable routing algorithm must ensure freedom from deadlock and livelock. The minimum buffer capacity in the nodes and the buffer management required to achieve these properties depend on whether zoormhole [10], virtual cutthrough [22], or store-and-forward [44] routing is used. The requirements for store-and-forward and virtual cut-through routing have been studied extensively [6, 7, 16, 29]. For concurrent use of all channels of a node, wormhole routing requires a buffer for each virtual channel, which is a more stringent requirement than what is required for virtual cutthrough and store-and-forward routing. For these routing techniques deadlock and livelock can be guaranteed even if buffers are shared between channels. The atomic unit being routed is however typically considerably smaller in wormhole routing than in the other two techniques, and the totaf