MPI-INF D1 Publications: Journal Article: Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Goto entry point

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

Edit History (please click the blue arrow to see the details)

	Editor(s) Christine Kiesel	Created 04/08/2006 18:07:12
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

Attachment Section