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

On Multidimensional Packet Routing for Meshes with Buses

โœ Scribed by J.Y.T. Leung; S.M. Shende

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
1006 KB
Volume
20
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

Routing problems on the (r)-dimensional (n \times n \times \cdots \times n) mesh architecture, enhanced with independent buses along each dimension, are investigated. We analyze several different kinds of routing problems, among them off-line routing, and provide routing algorithms for the one-dimensional, two-dimensional, and (r)-dimensional meshes. Asymptotically, we show that, queuesize being equal, the bus-equipped mesh architecture outperforms the classical mesh by speeding up the routing time by a factor of 12/7. 1994 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

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

Routing Problems on the Mesh of Buses
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

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

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