NDLI: Improved optimal shared memory simulations, and the power of reconsideration

Content Provider	IEEE Xplore Digital Library
Author	Czumaj, A. Meyer auf der Heide, F. Stemann, V.
Copyright Year	1995
Description	Author affiliation: Heinz Nixdoft Inst., Paderborn Univ., Germany (Czumaj, A.; Meyer auf der Heide, F.; Stemann, V.)
Abstract	We present time-processor optimal randomized algorithms for simulating a shared memory machine (EREW PRAM) on, a distributed memory machine (DMM). The first algorithm simulates each step of an n-processor EREW PRAM on an n-processor DMM with O(log log n/log log log n) delay with high probability. This simulation is work optimal and can be made time-processor optimal. The best previous optimal simulations require O(log log n) delay. We also study reconfigurable DMMs which are a "complete network version" of the well studied reconfigurable meshes. We show an algorithm that simulates each step of an n-processor EREW PRAM DMM an n-processor reconfigurable DMM with only O(log* n) delay with high probability. We further show how to make this simulation time-processor optimal.
Starting Page	11
Ending Page	19
File Size	869882
Page Count	9
File Format	PDF
ISBN	0818669152
DOI	10.1109/ISTCS.1995.377051
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1995-01-04
Publisher Place	Israel
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Phase change random access memory Computational modeling Computer simulation Computer science Parallel machines Parallel algorithms Costs Delay effects Routing Broadcasting
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimal parallel merging algorithms on BSR

Implementing shared memory on clustered machines

Optimal and efficient parallel algorithms for summing and prefix summing

A hierarchical computation model for distributed shared-memory machines

On the power of the mesh with hybrid buses

Bulk synchronous parallel without barriers

Efficient simulations of small shared memories on bounded degree networks

Optimal mesh computer algorithms for simple polygons

The Parallel Asynchronous Recursion model

Improved optimal shared memory simulations, and the power of reconsideration

Similar Documents

Optimal parallel merging algorithms on BSR

Implementing shared memory on clustered machines

Optimal and efficient parallel algorithms for summing and prefix summing

A hierarchical computation model for distributed shared-memory machines

On the power of the mesh with hybrid buses

Bulk synchronous parallel without barriers

Efficient simulations of small shared memories on bounded degree networks

Optimal mesh computer algorithms for simple polygons

The Parallel Asynchronous Recursion model

Improved optimal shared memory simulations, and the power of reconsideration