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):

Mehlhorn, Kurt
Vishkin, Uzi

dblp
dblp



BibTeX cite key*:

mehlhorn84n

Title

Title*:

Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories

Journal

Journal Title*:

Acta Informatica

Journal's URL:


Download URL
for the article:

http://www.springerlink.com/content/h561414317p36348/fulltext.pdf

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:


Publisher's
Address:

Berlin, Germany

ISSN:

0001-5903 (Print) 1432-0525 (Online)

Vol, No, pp, Date

Volume*:

21

Number:


Publishing Date:

1984

Pages*:

339-374

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

The present paper provides a comprehensive study of the following problem. Consider algorithms which are designed for shared memory models of parallel computation (PRAMs) in which processors are allowed to have fairly unrestricted access patterns to the shared memory. Consider also parallel machines in which the shared memory is organized in modules where only one cell of each module can be accessed at a time. Problem. Give general fast simulations of these algorithms by these parallel machines.
Each of our solutions answers two basic questions. (1) How to initially distribute the logical memory addresses of the PRAM, to be simulated, among the physical locations of the simulating machine? (2) How to compute the physical location of a logical address during the simulation?
We utilize two main ideas for the first question.

(a) Randomization. The logical addresses are randomly distributed among the memory modules. This is done using universal hashing.
(b) Copies. We keep copies of each logical address in several memory modules.

In a typical time cycle of the PRAM some number of memory requests has to be satisfied. As a primary objective, our simulations minimize the maximum number of memory requests which are assigned to the same module. Our solutions also optimize the following computational resources. They minimize the size of the physical memory, the time for computing the mapping from logical to physical addresses and the space for storing this mapping.
We discuss extensions of our solutions to various PRAMs and various shared memory parallel machines. Our solution is also applicable to synchronous distributed machines with no shared memory where the processors can communicate through a bounded degree network.
A preliminary version of this paper was presented at the 9th Workshop on Graphtheoretic Concepts in Computer Science (WG-83), Fachbereich Mathematic, Universität Osnabrück, June 1983

URL for the Abstract:

http://www.springerlink.com/content/h561414317p36348/?p=b86b5ce3824841539ad629e9d8722357&pi=1

Categories,
Keywords:


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{mehlhorn84n,
AUTHOR = {Mehlhorn, Kurt and Vishkin, Uzi},
TITLE = {Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories},
JOURNAL = {Acta Informatica},
PUBLISHER = {Springer},
YEAR = {1984},
VOLUME = {21},
PAGES = {339--374},
ADDRESS = {Berlin, Germany},
ISBN = {0001-5903 (Print) 1432-0525 (Online)},
}


Entry last modified by Anja Becker, 03/02/2010
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
08/09/2006 02:17:03 PM
Revisions
3.
2.
1.
0.
Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
28.02.2008 12:36:45
21.09.2006 15:26:45
08.09.2006 09:15:48
09.08.2006 14:18:50
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section