NDLI: Work-time optimal k-merge algorithms on the PRAM

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

Work-time optimal k-merge algorithms on the PRAM

Content Provider	IEEE Xplore Digital Library
Author	Hayashi, T. Nakano, K. Olariu, S.
Copyright Year	1990
Abstract	For 2/spl les/k/spl les/n, the k-merge problem is to merge a collection of ksorted sequences of total length n into a new sorted sequence. The k-merge problem is fundamental as it provides a common generalization of both merging and sorting. The main contribution of this work is to give simple and intuitive work-time optimal algorithms for the k-merge problem on three PRAM models, thus settling the status of the k-merge problem. We first prove that /spl Omega/(n log k) work is required to solve the k-merge problem on the PRAM models. We then show that the EREW-PRAM and both the CREW-PRAM and the CRCW require /spl Omega/(log n) time and /spl Omega/(log log n+log k) time, respectively, provided that the amount of work is bounded by O(n log k). Our first k-merge algorithm runs in /spl Theta/(log n) time and performs /spl Theta/(n log k) work on the EREW-PRAM. Finally, we design a work-time optimal CREW-PRAM k-merge algorithm that runs in /spl Theta/(log log n+log k) time and performs /spl Theta/(n log k) work. This latter algorithm is also work-time optimal on the CREW-PRAM model. Our algorithms completely settle the status of the k-merge problem on the three main PRAM models.
Sponsorship	IEEE Computer Society
Starting Page	275
Ending Page	282
Page Count	8
File Size	351280
File Format	PDF
ISSN	10459219
Volume Number	9
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1998-03-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Phase change random access memory Merging Sorting Parallel algorithms Information retrieval Databases Memory management Read-write memory Writing Query processing
Content Type	Text
Resource Type	Article
Subject	Signal Processing Computational Theory and Mathematics Hardware and Architecture

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

Efficient EREW PRAM algorithms for parentheses-matching

Parallel binary search

Parallel median splitting and k-splitting with application to merging and sorting

An optimal implementation of broadcasting with selective reduction

Efficient geometric algorithms on the EREW PRAM

Time-space optimal parallel merging and sorting

Scans as primitive parallel operations

An optimal linked list prefix algorithm on a local memory computer

Parallel algorithms for the longest common subsequence problem

Work-time optimal k-merge algorithms on the PRAM

Similar Documents

Efficient EREW PRAM algorithms for parentheses-matching

Parallel binary search

Parallel median splitting and k-splitting with application to merging and sorting

An optimal implementation of broadcasting with selective reduction

Efficient geometric algorithms on the EREW PRAM

Time-space optimal parallel merging and sorting

Scans as primitive parallel operations

An optimal linked list prefix algorithm on a local memory computer

Parallel algorithms for the longest common subsequence problem

Work-time optimal k-merge algorithms on the PRAM