✦ LIBER ✦

Deterministic Permutation Routing on Meshes

✍ Scribed by Jop F. Sibeyn; Bogdan S. Chlebus; Michael Kaufmann

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 248 KB
Volume: 22
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1995.0804

No coin nor oath required. For personal study only.

✦ Synopsis

New deterministic algorithms for routing permutations on two-dimensional meshes are developed. On an n = n array, one algorithm runs in the optimal 2 и n y 2 steps, with maximum queue length 32. Another algorithm runs in near-Ž . optimal time, 2 и n q O O 1 steps, with a maximum queue length of only 12. ᮊ 1997

📜 SIMILAR VOLUMES

Broadcasting on Meshes with Wormhole Rou

Broadcasting on Meshes with Wormhole Routing

✍ Mike Barnett; David G. Payne; Robert A. van de Geijn; Jerrell Watts 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 333 KB

The two-dimensional (2D) mesh architecture with wormhole routing is an attractive interconnection architecture for distributed-memory multicomputers. A mesh can be scaled to arbitrarily large configurations while retaining high link bandwidth. Moreover, the number of nodes in a mesh does not inheren

Routing with Locality on Meshes with Bus

Routing with Locality on Meshes with Buses

✍ Steven Cheung; Francis C.M. Lau 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 232 KB

Routing with locality is studied for meshes with buses. In this problem, packets' distances are bounded by a value, d, which is less than the diameter of the network. This problem arises naturally when specific known algorithms are implemented on meshes. Solving this problem in ordinary meshes requi

Optimally Scaling Permutation Routing on

Optimally Scaling Permutation Routing on Reconfigurable Linear Arrays with Optical Buses

✍ Jerry L. Trahan; Anu G. Bourgeois; Yi Pan; Ramachandran Vaidyanathan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 171 KB

We present an optimal and scalable permutation routing algorithm for three reconfigurable models based on linear arrays that allow pipelining of information through an optical bus. Specifically, for any P N, our algorithm routes any permutation of N elements on a P-processor model optimally in O( N

A Lower Bound for Elementary Oblivious R

A Lower Bound for Elementary Oblivious Routing on Three-Dimensional Meshes

✍ Kazuo Iwama; Eiji Miyano 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 434 KB

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 twodim

Routing Problems on the Mesh of Buses

✍ Kazuo Iwama; Eiji Miyano; Yahiko Kambayashi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 175 KB

The mesh of buses MBUSs is a parallel computation model which consists of n = n processors, n row buses, and n column buses, but no local connections between neighboring processors. An n lower bound for the permutation routing on this model is shown. The proof does not depend on common predetermined

Routing Permutations on Hypercube Machin

Routing Permutations on Hypercube Machines with Half-Duplex Links

✍ C.S. Raghavendra; M.A. Sridhar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 466 KB

Algorithms are presented for realizing permutations on a less restrictive hypercube model called the S-MIMD (synchronous MIMD), which allows at most one data transfer on a given communication link at a given time instant, and where data movements are not restricted to a single dimension at a given t