Approximate compaction and padded-sorting on exclusive write PRAMs

Author

Kutylowski, Miroslaw ; Wierzbicki, Tomasz

Author_Institution

Heinz Nixdorf Inst., Univ. Gesamthochschule Paderborn, Germany

fYear

1996

fDate

15-19 Apr 1996

Firstpage

174

Lastpage

181

Abstract

Padded-sorting is a task of placing input items in an array in a nondecreasing order, but with free space between consecutive elements allowed. For many applications, padded-sorting is as useful as sorting. Approximate compaction and compression are closely related problems. It is known that the time complexity of padded-sorting on randomized CRCW PRAMs is considerably lower than the time complexity of sorting. We analyze the time complexity of these problems on CREW and EREW PRAMs (deterministic and randomized) and get tight lower and upper bounds depending on the size of free space. We extend our lower bounds to approximate compaction and compression. Some of the algorithms presented are very rare examples of randomized EREW PRAMs that are much faster than their deterministic counterparts

Keywords

computational complexity; deterministic algorithms; parallel algorithms; parallel machines; random-access storage; randomised algorithms; sorting; EREW PRAM; approximate compaction; array; compression; deterministic algorithm; exclusive write PRAM; free space; nondecreasing order; padded-sorting; parallel random access memory; randomized CRCW PRAM; randomized algorithm; tight lower bounds; time complexity; upper bounds; Compaction; Phase change random access memory; Polynomials; Runtime; Sorting; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1996., Proceedings of IPPS '96, The 10th International

Conference_Location

Honolulu, HI

Print_ISBN

0-8186-7255-2

Type

conf

DOI

10.1109/IPPS.1996.508054

Filename

508054