Goodness of Time-Processor Optimal PRAM Simulations

We address the question 'how to measure goodness of time-processor optimal PRAM simulations'. Instead of measuring only the asymptotic complexity of simulation time, we attempt to take into account all aspects of simulations exactly. We present a goodness

Goodness of Time-Processor Optimal PRAM SimulationsVille LeppanenDepartment of Computer Science, University of Turku Lemminkaisenkatu 14, FIN-20520 Turku, FINLAND Email: Ville.Leppanen@cs.utu.

Turku Centre for Computer Science TUCS Technical Report No 89 December, 1996 ISBN 951-650-936-3 ISSN 1239-1891

We address the question 'how to measure goodness of time-processor optimal PRAM simulations'. Instead of measuring only the asymptotic complexity of simulation time, we attempt to take into account all aspects of simulations exactly. We present a goodness

AbstractWe address the question 'how to measure goodness of time-processor optimal PRAM simulations'. Instead of measuring only the asymptotic complexity of simulation time, we attempt to take into account all aspects of simulations exactly. We present a goodness function framework and propose a generic function for measuring the goodness.

Keywords: Time-processor optimal, PRAM, simulation, goodness

TUCS Research GroupAlgorithmics group

We address the question 'how to measure goodness of time-processor optimal PRAM simulations'. Instead of measuring only the asymptotic complexity of simulation time, we attempt to take into account all aspects of simulations exactly. We present a goodness

1

Introduction

A simulation of an N -processor PRAM on a P -processor distributed memory machine (DMM) is time-processor optimal, if simulation of a PRAM step succeeds in time O(N=P ) (with high probability). The simulation time is lower bounded by the diameter of the routing machinery and the expected memory congestion . If the DMM is symmetric and memory requests can be satis ed by only one memory module (one hash function), expected length of memory request route is= ( ). If the total routing capacity is P ( packets per physical processor per step), two necessary conditions for timeprocessor optimality are that the load`= N=P (parallel slackness factor) is`= (maxf; g) and= ( ). Many such solutions can be derived 3, 4, 5, 6, 9]. Often when simulation results are reported, the asymptotic complexity of simulation time is highlighted while other aspects are almost ignored.\Better" results can be obtained by assuming stronger graph theoretical properties (larger degree, smaller ) and/or stronger (shared resource) contention resolution protocols. Comparison of PRAM simulations should account for implementation of routing machinery properties, since a PRAM simulation is basically a routing problem! How to account for routing machinery implementation? Using the VLSI cost model to implement communication graphs has been studied extensively. The basic VLSI components are transistors and wires, and the success in modeling the cost leans on the fact that the size of basic components is approximately the same. Extension to processor&memory modules and connections between them is possible, but the size issue can be severely o balance. Using optics instead of VLSI to implement communication has been suggested in 7, 10]{ more or less in the form of static multichannel mesh of optical buses. A SMcMOB (s; d; ) consists of a d-dimensional mesh of optical buses{ the side length along each axis is s nodes. Each node is connected to a bus along each axis with receivers and transmitters. Each transmitter (receiver) connected to a bus is assumed to have a xed unique channel. (In 8], a hardware con guration capable of supporting 250 channels per bus is discussed. Each of them operates at rate 1 Gbit/s. The con gur

ation is claimed to be able to support up to 5000 channels.) We assume that a PRAM simulation S is implemented on a logical architectural model (of a routing machinery) which in turn is implemented by embedding it into a SMcMOB . Our goodness function parameters come from simulation, architectural model and embedding of the communication graph. An embedding E= (G; H ) of graph G into H= SMcMOB (s; d; ) assigns nodes of G on nodes of H; maps a channel for each transmitter and receiver 1

We address the question 'how to measure goodness of time-processor optimal PRAM simulations'. Instead of measuring only the asymptotic complexity of simulation time, we attempt to take into account all aspects of simulations exactly. We present a goodness

properly; and sets a path to each directed edge of G. A stepwise emulation F assigns a collision-free schedule for the movement of packets according to the paths. Let 't denote the length of schedule. Besides 't, we are interested of stretch 's, which is the largest stretch of a channel in H . If a channel connects nodes hx1;:::; xi;:::; xdi and hx1;:::; xi?1; yi; xi+1;:::; xdi, the stretch of channel is jxi? yij. Above kind of embedding and emulation has been studied in 7, 10].

2

Goodness functions

Let I be an implementation of an EREW simulation S running on a distributed memory machine M so that I is based on an emulation F on an embedding E=(M; SMcMOB (s; d; )). Informally our goodness functions map a certain set of PRAM implementation related parameters to scalar values. The best value a goodness function can give for an implementation is 1. Besides 't and 's, we see the following parameters of M and S relevant: the number of processors and memory modules P; the number of routing machinery nodes Q; the routing machinery communication capacity (expressed in packets); the logical diameter; the maximum degree of nodes and processor&memory modules; the size of queues q; the size of packets z; and the load-cost function of simulation C . The function C measures simulation cost per simulated PRAM processor on load`. If S uses at most T (N …… 此处隐藏：12676字，全部文档内容请下载后查看。喜欢就下载吧 ……