Parallel integer sorting and simulation amongst CRCW models
type: Item
instance of: scholarly article
title: Parallel integer sorting and simulation amongst CRCW models
zbMATH Open document ID: 0849.68052
author: Sanjeev Saxena
published in: Acta Informatica
publication date: 1995-11-16T00:00:00Z
review text: A general technique for reducing processors in simulation without any increase in time is described. This results in an \(O(\sqrt {\log n})\) time algorithm for simulating one step of PRIORITY on TOLERANT with processor-time product \(O (n \log \log n)\); the same as that for simulating PRIORITY on ARBITRARY. This is used to obtain an \(O \left( {\log n \over \log \log n} + \sqrt {\log n} \cdot (\log \log m \log \log n) \right)\) time algorithm for sorting \(n\) integers from the set \(\{0, \cdots, m - 1\}\), \(m \geq n\) with a processor-time product of \(O(\log \log m \log \log n)\) on a TOLERANT CRCW PRAM. New upper and lower bounds for ordered chaining problem on an allocated COMMON CRCW model are also obtained. The algorithm for ordered chaining takes \(O\left({ \log n\over \log \log n} \right)\) time on an allocated PRAM of size \(n\). It is shown that this result is best possible (upto a constant multiplicative factor) by obtaining a lower bound of \(\Omega \left( {r \log n \over \log r + \log \log n}\right)\) for finding the first (leftmost one) live processor on an allocated-COMMON PRAM of size \(n\) of \(r\)-slow virtual processors (one processor simulates \(r\) processors of allocated PRAM). As a result, for ordered chaining problem, ``processor-time product'' has to be at least \(\Omega \left( {n \log n\over \log \log n} \right)\) for any poly-logarithmic time algorithm. Algorithm for ordered-chaining problem results in an \(O\left( {\log N \over \log \log N}\right)\) time algorithm for (stable) sorting of \(n\) integers from the set \(\{0, \dots, m - 1\}\) with \(n\)-processors on a COMMON CRCW PRAM; here \(N = \max (n,m)\). In particular if, \(m = n^{O(1)}\), then sorting takes \(\Theta \left( {\log n\over \log \log n}\right)\) time on both TOLERANT and COMMON CRCW PRAMs. Processor-time product for TOLERANT is \(O(n (\log \log n)^2)\). Algorithm for COMMON uses \(n\) processors.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 814165
zbMATH Keywords: parallel integer sorting
zbMATH Keywords: stable sorting
zbMATH Keywords: ordered chaining
zbMATH Keywords: CRCW PRAM
MaRDI profile type: Publication
full work available at URL: s002360050061
OpenAlex ID: W4243665620
DOI: 10.1007/S002360050061
description: scientific article; zbMATH DE number 814165