Parallel integer sorting and simulation amongst CRCW models (Q1901715)

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.