✦ LIBER ✦

Routing with Locality on Meshes with Buses

✍ Scribed by Steven Cheung; Francis C.M. Lau

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 232 KB
Volume: 33
Category: Article
ISSN: 0743-7315
DOI: 10.1006/jpdc.1996.0027

No coin nor oath required. For personal study only.

✦ Synopsis

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 requires at least a routing time of d steps. To do better than this, we propose adding a kind of short bus to ordinary meshes. By using a technique which we call iterative walk-and-ride, we show how the routing time can be reduced by approximately one-third for solving the problem (including the multipacket version) on one-and two-dimensional short-bus meshes. The bounds we develop are tight.

📜 SIMILAR VOLUMES

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

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

Oblivious Routing Algorithms on the Mesh

Oblivious Routing Algorithms on the Mesh of Buses

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

An optimal W1.5N 1Â2 X lower bound is shown for oblivious routing on the mesh of buses: a two-dimensional parallel model consisting of N 1Â2 \_N 1Â2 processors and N 1Â2 row and N 1Â2 column buses but no local connections between neighboring processors. Many lower bound proofs for routing on mesh-st

Selection on Mesh Connected Computers wi

Selection on Mesh Connected Computers with Fixed and Reconfigurable Buses

✍ Sanguthevar Rajasekaran 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 227 KB

Mesh connected computers have become attractive models of computing because of their varied special features. In this paper we consider two variations of Ž . Ž . the mesh model: 1 a mesh with fixed buses and 2 a mesh with reconfigurable buses. Both these models have been the subject of extensive pr

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

Minimal Adaptive Routing on the Mesh wit

Minimal Adaptive Routing on the Mesh with Bounded Queue Size

✍ Donald D. Chinn; Tom Leighton; Martin Tompa 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 388 KB

An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing packets around ''hot spots.'' Minimal adaptive routing algorithms have the additional a