Recent developments in mesh routing algorithms

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.