Improved Virtual Leveled Routing Strategy for Meshes

Ville Leppanen?

Department of Computer Science

University of Turku, FINLAND

E-mail: Ville.Leppanen@cs.utu.fi

Research Report R-94-8

University of Turku, Computer Science

May 16, 1994

Abstract

We present an improved version of the virtual leveled network routing strategy for mesh connected computers. This improvement achieves a speedup of approximately 2, and requires practically no additional hardware. We confirm this by providing experimental results concerning time to accomplish CRCW PRAM simulation influenced routing situations.

1 Introduction

Combining messages during a routing process is the method to avoid performance degradation in the presence of hot-spots. Especially, combining on the route provides a practical method to accomplish the memory reference primitives of strong CRCW PRAM (as well as CREW) models. Several methods have been proposed to accomplish combining [1, 3, 6, 8, 10], which all can be applied to mesh connected computers. These methods can be applied to other interconnection structures as well, but here we deal only with the 2-dimensional and the 3-dimensional mesh structure, since it is simple, regular, modularly extendible, well scalable, and in general it is very fair with respect to our 3-dimensional world.

Definition 1.1 A d-dimensional n1 ? n2 ? : : : ? nd mesh is a graph Gn1?n2?:::?nd mesh =
(V; E), where

V =
n
Vx1;x2;:::;xd <= xi <= ni ? 1; 1 <= i <= d
o

is a set of N = n1n2 : : : nd (almost) identical nodes, and

E =
n
(Vx1;x2;:::;xd ; Vy1;y2;:::;yd )
d
X

i=1
jxi ? yij = 1; <= xi; yi <= ni ? 1; 1 <= i <= d
o

defines the connections between nodes. The degree is 2d, and the diameter is Pdi=1(ni?1).

?This work was financially supported by the Academy of Finland.