Recent developments in mesh routing algorithms

Citation
K. Iwama et E. Miyano, Recent developments in mesh routing algorithms, IEICE T INF, E83D(3), 2000, pp. 530-540
Citations number
35
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
ISSN journal
09168532 → ACNP
Volume
E83D
Issue
3
Year of publication
2000
Pages
530 - 540
Database
ISI
SICI code
0916-8532(200003)E83D:3<530:RDIMRA>2.0.ZU;2-5
Abstract
The two dimensional mesh is widely considered to be a promising parallel ar chitecture in its scalability. In this architecture, processors are natural ly placed at intersections of horizontal and vertical grids, while there ca n be three different types of communication links: (i) The first type is th e most popular model, called a mesh-connected computer: Each processor is c onnected to its four neighbours by local connections. (ii) Each processor o f the second type is connected to a couple of (row and column) buses. The s ystem is then called a mesh of buses. (iii) The third model is equipped wit h both buses and local connections, which is called a mesh-connected comput er with buses. Mesh routing has received considerable attention for the las t two decades, and a variety of algorithms have been proposed. This paper p rovides an overview of lower and upper bounds for algorithms, with pointers to the literature, and suggests further research directions for mesh routi ng.