Efficient PRAM simulation on a Distributed Memory Machine

作     者：Karp, RM Luby, M Heide, FMAD 

作者机构：UNIV CALIF BERKELEY BERKELEY CA 94720 USA INT COMP SCI INST BERKELEY CA 94704 USA UNIV PADERBORN HEINZ NIXDORF INST D-33095 PADERBORN GERMANY UNIV PADERBORN DEPT COMP SCI D-33095 PADERBORN GERMANY 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：1996年第16卷第4-5期

页      面：517-542页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：PRAM simulation distributed memory machine universal hashing stochastic modeling balls and bins 

摘      要：We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the same cell, whereas the memory of a DMM is divided into modules, one for each processor, and concurrent accesses to the same module create a conflict. The delay of a simulation is the time needed to simulate a parallel memory access of the PRAM. Any general simulation of an m processor PRAM on an n processor DMM will necessarily have delay at least min. A randomized simulation is called time-processor optimal if the delay is O(m/n) with high probability. Using a novel simulation scheme based on hashing we obtain a time-processor optimal simulation with delay O(log log(n) log*(n)). The best previous simulations use a simpler scheme based on hashing and have much larger delay: Theta(log(n)/log log(n)) for the simulation of an n processor PRAM on an n processor DMM, and Theta(log(n)) in the case where the simulation is time-processor optimal. Our simulations use several (two or three) hash functions to distribute the shared memory among the memory modules of the PRAM. The stochastic processes modeling the behavior of our algorithms and their analyses based on powerful classes of universal hash functions may be of independent interest.