✦ LIBER ✦
An O(N) Oblivious Routing Algorithm for Two-Dimensional Meshes of Constant Queue-Size
✍ Scribed by Kazuo Iwama; Eiji Miyano
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 151 KB
- Volume
- 41
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
An O
√ N oblivious permutation-routing algorithm for two-dimensional meshes is presented. The model is a standard mesh where √ N × √ N processors are connected via point-to-point connections and each processor has four queues, one per each outgoing link, which can hold only a constant number of temporal packets. The previous bound was O N 0 75 (K.