๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Routing Problems on the Mesh of Buses

โœ Scribed by Kazuo Iwama; Eiji Miyano; Yahiko Kambayashi

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
175 KB
Volume
20
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 assumptions such as ''if a packet has to move horizontally then it has to ride on a horizontal bus at least once.'' As for upper bounds, a 1.5n algorithm is shown.

๐Ÿ“œ SIMILAR VOLUMES

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

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

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

On the Power of Segmenting and Fusing Bu
On the Power of Segmenting and Fusing Buses
โœ Jerry L. Trahan; Ramachandran Vaidyanathan; Ratnapuri K. Thiruchelvan ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 328 KB

Reconfigurable bus-based models of parallel computation have been shown to be extremely powerful, capable of solving several problems in constant time that require nonconstant time on conventional models such as the PRAM. The primary source of the power of reconfigurable bus-based models is their ab