For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Recent Developments in Mesh Routing Algorithms
Kazuo IWAMA Eiji MIYANO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Parallel and Distributed Algorithms
parallel computation, meshes, packet routing,
Full Text: PDF>>
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.