NDLI: Can parallel algorithms enhance serial implementation

Please wait, while we are loading the content...

Volume 22, Issue 4, Fall 1991

Commutative regular languages

On the Peeper's Voronoi diagram

Some notions on notations

Can parallel algorithms enhance serial implementation

Volume 22, Issue 3, Summer 1991

Volume 22, Issue 2, Spring 1991

Volume 22, Issue 1, Winter 1991

Issue 14, January 1972

Issue 13, December 1971

Issue 12, October 1971

Issue 11, August 1971

Issue 10, July 1971

Issue 9, April 1971

Issue 8, January 1971

Issue 7, September 1970

Issue 6, June 1970

Issue 4, January 1970

Issue 3, October 1969

Issue 2, July 1969

Issue 1, April 1969

Can parallel algorithms enhance serial implementation

Content Provider	ACM Digital Library
Author	Vishkin, Uzi
Abstract	Consider the serial emulation of a parallel algorithm. The thesis presented in this informal paper is rather broad. It suggests that such a serial emulation has the potential advantage of running on a serial machine faster than a standard serial algorithm for the same problem.The main concrete observation is very simple: just before the serial emulation of a round of the parallel algorithm begins, the whole list of memory addresses needed during this round is readily available; and, we can start fetching these addresses from secondary memories.This enables to prefetch the data that will be needed in the next "time window", perhaps by means of pipelining and have them ready at the fast memories when requested by the CPU. Thereby, utilization of commonly used memory management systems will be theoretically enhanced. Another (considerably less orthodox) implementation approach will result in abandoning locality of references, in favor of a drastically different approach: distribute memory addresses at random over memory modules, as has been proposed in the context of implementing the parallel-random-access machine (PRAM) design space.It is too early to reach conclusions regarding the significance of the thesis of this paper. Serious attempts to follow it up are needed to determine its usefulness. Parts of this paper are intentionally written in an informal way, suppressing issues that will have to be resolved in the context of a concrete implementation. My general intention is to encourage colleagues to: (i) suggest other specific approaches, and (ii) explore opportunities for taking advantage of the fine structure of parallel programs well beyond concrete suggestions made in the paper.The full paper is available as UMIACS TR 91-145, from the Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742--3251.
Starting Page	63
Ending Page	63
Page Count	1
File Format	PDF
ISSN	01635700
DOI	10.1145/126546.126550
Journal	ACM SIGACT News (SIGA)
Volume Number	22
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1992-06-30
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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