Accession Number:

ADA327912

Title:

How to Share Memory in a Distributed System.

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Upfal, Eli
• Wigderson, Avi

Report Date:

1984-10-01

Pagination or Media Count:

21.0

Abstract:

We study the power of shared memory in models of parallel computation. We describe a novel distributed data structure that eliminates the need for shared memory without significantly increasing the run time of the parallel computation. More specifically we show how a complete network of processors can deterministicly simulate one PRAM step in Olog nloglog n2 time, when both models use n processors, and the size of the PRAMs shared memory is polynomial in n. The best previously known upper bound was the trivial On. We also establish that this upper bounds is nearly optimal. We prove that an online simulation of T PRAM steps by a complete network of processors requires omegaT log n timeloglog n. A simple consequence of the upper bound is that an Ultracomputer the only currently feasible general purpose parallel machine, can simulate one step of a PRAM the most convenient parallel model to program, in log n loglog n2 steps.

Descriptors:

• *DISTRIBUTED DATA PROCESSING
• *PARALLEL PROCESSING
• *TIME SHARING
• DATA BASES
• SIMULATION
• COMPUTATIONS
• MODELS
• NETWORKS
• PROCESSING EQUIPMENT
• MEMORY DEVICES
• POLYNOMIALS
• POWER
• PARALLEL ORIENTATION
• ONLINE SYSTEMS

Subject Categories:

• Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE