Recent Developments in Mesh Routing Algorithms

Kazuo IWAMA; Eiji MIYANO

Recent Developments in Mesh Routing Algorithms

Kazuo IWAMA, Eiji MIYANO

Full Text Views

0

Cite this

Summary :

The two dimensional mesh is widely considered to be a promising parallel architecture in its scalability. In this architecture, processors are naturally placed at intersections of horizontal and vertical grids, while there can be three different types of communication links: (i) The first type is the most popular model, called a mesh-connected computer: Each processor is connected to its four neighbours by local connections. (ii) Each processor of the second type is connected to a couple of (row and column) buses. The system is then called a mesh of buses. (iii) The third model is equipped with both buses and local connections, which is called a mesh-connected computer with buses. Mesh routing has received considerable attention for the last two decades, and a variety of algorithms have been proposed. This paper provides an overview of lower and upper bounds for algorithms, with pointers to the literature, and suggests further research directions for mesh routing.

Publication: IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.530-540

Publication Date: 2000/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: INVITED SURVEY PAPER

Category: Parallel and Distributed Algorithms

Cite this

Copy

Kazuo IWAMA, Eiji MIYANO, "Recent Developments in Mesh Routing Algorithms" in IEICE TRANSACTIONS on Information, vol. E83-D, no. 3, pp. 530-540, March 2000, doi: .
Abstract: The two dimensional mesh is widely considered to be a promising parallel architecture in its scalability. In this architecture, processors are naturally placed at intersections of horizontal and vertical grids, while there can be three different types of communication links: (i) The first type is the most popular model, called a mesh-connected computer: Each processor is connected to its four neighbours by local connections. (ii) Each processor of the second type is connected to a couple of (row and column) buses. The system is then called a mesh of buses. (iii) The third model is equipped with both buses and local connections, which is called a mesh-connected computer with buses. Mesh routing has received considerable attention for the last two decades, and a variety of algorithms have been proposed. This paper provides an overview of lower and upper bounds for algorithms, with pointers to the literature, and suggests further research directions for mesh routing.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_530/_p

Copy

@ARTICLE{e83-d_3_530,
author={Kazuo IWAMA, Eiji MIYANO, },
journal={IEICE TRANSACTIONS on Information},
title={Recent Developments in Mesh Routing Algorithms},
year={2000},
volume={E83-D},
number={3},
pages={530-540},
abstract={The two dimensional mesh is widely considered to be a promising parallel architecture in its scalability. In this architecture, processors are naturally placed at intersections of horizontal and vertical grids, while there can be three different types of communication links: (i) The first type is the most popular model, called a mesh-connected computer: Each processor is connected to its four neighbours by local connections. (ii) Each processor of the second type is connected to a couple of (row and column) buses. The system is then called a mesh of buses. (iii) The third model is equipped with both buses and local connections, which is called a mesh-connected computer with buses. Mesh routing has received considerable attention for the last two decades, and a variety of algorithms have been proposed. This paper provides an overview of lower and upper bounds for algorithms, with pointers to the literature, and suggests further research directions for mesh routing.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - Recent Developments in Mesh Routing Algorithms
T2 - IEICE TRANSACTIONS on Information
SP - 530
EP - 540
AU - Kazuo IWAMA
AU - Eiji MIYANO
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - The two dimensional mesh is widely considered to be a promising parallel architecture in its scalability. In this architecture, processors are naturally placed at intersections of horizontal and vertical grids, while there can be three different types of communication links: (i) The first type is the most popular model, called a mesh-connected computer: Each processor is connected to its four neighbours by local connections. (ii) Each processor of the second type is connected to a couple of (row and column) buses. The system is then called a mesh of buses. (iii) The third model is equipped with both buses and local connections, which is called a mesh-connected computer with buses. Mesh routing has received considerable attention for the last two decades, and a variety of algorithms have been proposed. This paper provides an overview of lower and upper bounds for algorithms, with pointers to the literature, and suggests further research directions for mesh routing.
ER -