English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 DetailsSummary
  Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones

Alt, H., Hagerup, T., Mehlhorn, K., & Preparata, F. P. (1987). Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones. SIAM Journal on Computing, 16, 808-835.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AEAA-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AEAB-6
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Alt, Helmut1, Author
Hagerup, Torben2, Author           
Mehlhorn, Kurt2, Author           
Preparata, Franco P.1, Author
Affiliations:
1Max Planck Society, ou_persistent13              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: The authors describe a nonuniform deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number $n$ of processors as the simulated PRAM, and if the size of the PRAM's shared memory is polynomial in $n$, each PRAM step is simulated by $O(\log n)$ MPC steps or by $O((\log n)^2)$ steps of the bounded-degree network. This improves upon a previous result by Upfal and Wigderson (1984). The authors prove an $\Omega((\log n)^2/\log\log n)$ lower bound on the number of steps needed to simulate one PRAM step on a bounded-degree network under the assumption that the communication in the network is point to point. As an important part of the simulation of PRAMs on MPCs, a new technique for dynamically averaging out a given work load among a set of processors operating in parallel is used.

Details

show
hide
Language(s): eng - English
 Dates: 2006-11-101987
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 344590
Other: Local-ID: C1256428004B93B8-E25297A1C6B06A65C125714A00588CF3-SICOMP::AltHMP1987
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: SIAM Journal on Computing
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 16 Sequence Number: - Start / End Page: 808 - 835 Identifier: -