Experimental Results on Simulating EREW PRAM

Work-Optimally on Mesh of Trees

Ville Leppanen

Department of Computer Science

University of Turku, FINLAND

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

Research Report R-94-10

University of Turku, Computer Science

July 14, 1994

Abstract

In this paper we provide experimental evidence that 2-dimensional and 3-dimensional mesh of trees can simulate EREW PRAM models with simulation cost 2{3 routing steps per simulated PRAM processor. Previously, we have proven the cost to be at most roughly 2{3-fold larger. We provide a lot of simulation results with various parameter values.

1 Introduction

1.1 Definition of mesh of trees

Definition 1.1 The n-sided d-dimensional Mesh of Trees (MT) is a graph that is based on an n-sided d-dimensional mesh of nodes (without grid edges). For each tower of mesh nodes fVi1;:::ij?1;0;ij+1;:::;id ; : : : ; Vi1;:::ij?1;n?1;ij+1;:::;id g, it contains a complete binary tree

T ji1 ;:::;ij?1;ij+1;:::;id , whose leaves are the nodes of the tower. The edges of complete binary trees are bi-directional. The MT contains no other edges. The degree of MT is max(3; d), and the number of nodes is jV j = (d+1)nd ?dnd?1. Respectively, the diameter is 2d log n.

In the 2-dimensional case (see Figure 1), we call T 1i the i'th row tree RTi, and T 2i the i'th column tree CTi. We assume that there is a processor Pi2;:::;id in the root of T 1i2 ;:::;id for each i2; : : : ; id 2 f0; : : : ; n ? 1g. Similarly, we assume the memory module Mi1;:::;id?1 to reside at the root of T di1 ;:::;id?1 . Thus, the n-sided d-dimensional mesh of trees consists

of N = nd?1 processors and memory modules.

1.2 Results

In [1] we proved that with high probability an n-sided 2-dimensional and an n-sided 3- dimensional mesh of trees can simulate EREW PRAM work-optimally with cost at most (4 + 5`)=` and (6 + 11`)=` steps per simulated PRAM processor, if each real processor is simulating ` ? log n PRAM processors. The bounds given by our analysis in [1] were claimed to be too high in practice. In this paper we report the results of approximately 2400 routing experiments, which show that this is indeed the case.

In the 2-dimensional case, the simulation cost (in terms of routing steps) can be pushed below 1:5, if there is sufficient load. Even on quite moderate load 4 ? logn the cost seems