The Parallel Simplicity of Compaction and Chaining

✍ Scribed by P. Ragde

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 459 KB
• Volume: 14
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1993.1019

✦ Synopsis

Given a set of values (x_{1}, x_{2}, \ldots, x_{n}), of which (k) are nonzero, the compaction problem is the problem of moving the nonzero elements into the first (k) consecutive memory locations. The chaining problem asks that the nonzero elements be put into a linked list. One can in addition require that the elements remain in the same order, leading to the problems of ordered compaction and ordered chaining, respectively. This paper introduces a technique involving perfect hash functions that leads to a deterministic algorithm for ordered compaction running on a CRCW PRAM in time (O(\log k / \log \log n)) using (n) processors. A matching lower bound for unordered compaction is given. The ordered chaining problem is shown to be solvable in time (O(\alpha(k))) with (n) processors (where (\alpha) is a functional inverse of Ackermann's function) and unordered chaining is shown to be solvable in constant time with (n) processors when (k<n^{1 / 4-\xi}). 1943 Academic Press. Inc.