ROMM routing on mesh and torus networks by Ted Nesson, S Lennart Johnsson
1995 (English)Conference paper (Refereed)
ROMM 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 representative 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.
Place, publisher, year, edition, pages
1995. 275-287 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-64553DOI: 10.1145/215399.215455OAI: oai:DiVA.org:kth-64553DiVA: diva2:483124
Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures
NR 201408052012-01-242012-01-24Bibliographically approved