de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones

MPG-Autoren

Alt,  Helmut
Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Preparata,  Franco P.
Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-AEAA-8
Zusammenfassung
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.