A DEADLOCK-FREE ADAPTIVE ROUTING ALGORITHM ON DIAGONAL MESH

Mesh is a popular topology of multiprocessor interconnected network. A new topology, that is, diagonal mesh, and a new adaptive deadlock free routing algorithm based on it, are proposed in this paper. Diagonal mesh is a planar graph with fixed connection number per node.It allows a simple VLSI layout as well as scalability. The algorithm requires simple hardware. And, it do not need virtual channel to support adaptivity and deadlock freeness.