Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Alt, Helmut
Hagerup, Torben
Mehlhorn, Kurt
Preparata, Franco P.

dblp
dblp
dblp
dblp



BibTeX cite key*:

SICOMP::AltHMP1987

Title

Title*:

Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones

Journal

Journal Title*:

SIAM Journal on Computing

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Society for Industrial and Applied Mathematics

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

16

Number:

5

Publishing Date:

1987

Pages*:

808-835

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:

parallel RAM, parallel algorithms, computational complexity idealized parallel computers, nonuniform deterministic simulation, PRAM, lower bound, bounded-degree network

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{SICOMP::AltHMP1987,
AUTHOR = {Alt, Helmut and Hagerup, Torben and Mehlhorn, Kurt and Preparata, Franco P.},
TITLE = {Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones},
JOURNAL = {SIAM Journal on Computing},
PUBLISHER = {Society for Industrial and Applied Mathematics},
YEAR = {1987},
NUMBER = {5},
VOLUME = {16},
PAGES = {808--835},
}


Entry last modified by Christine Kiesel, 11/10/2006
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel
Created
04/08/2006 06:07:12 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Uwe Brahm
Christine Kiesel
Edit Dates
10.11.2006 15:13:39
08.08.2006 10:58:29
08-04-2006 17:51:56
06.04.2006 12:53:48
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section