Recent Developments in Mesh Routing Algorithms

Kazuo IWAMA  Eiji MIYANO  

IEICE TRANSACTIONS on Information and Systems   Vol.E83-D    No.3    pp.530-540
Publication Date: 2000/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Parallel and Distributed Algorithms
parallel computation,  meshes,  packet routing,  

Full Text: PDF>>
Buy this Article

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.