A Lower Bound for Elementary Oblivious Routing on Three-Dimensional Meshes
✍ Scribed by Kazuo Iwama; Eiji Miyano
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 434 KB
- Volume
- 39
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
This paper shows an important exception to the common perception that three-dimensional meshes are more powerful than two-dimensional ones. Let N be the total number of processors. Then permutation routing over three-dimensional mesh computers needs N 2/3 steps while it takes N 1/2 steps over twodimensional ones under the following conditions: (1) The path of each packet must be determined solely by its initial position and destination, i.e., the algorithm must be oblivious. (2) Each path must be "elementary," i.e., it must be shortest and as straight as possible. Thus the conditions, under which, somewhat surprisingly, three-dimensional meshes are significantly less powerful than two-dimensional ones for the fundamental network operation, are quite reasonable in practice. © 2001 Academic Press 1 A preliminary version of this paper was presented at the 5th European Symposium on Algorithms (ESA '97) [9].