RETRIEVAL OF SCATTERED INFORMATION BY EREW, CREW, AND CRCW PRAMS

The k-compaction problem arises when k out of n cells in an array are non-empty and the contents of these cells must be moved to the first k locations in the array. Parallel algorithms for k-compaction have obv ious applications in processor allocation and load balancing; k-compac tion is also an important subroutine in many recently developed parall el algorithms. We show that any EREW PRAM that solves the k-compaction problem requires Ohm(root log n) time, even if the number of processo rs is arbitrarily large and k = 2. On the CREW PRAM, we show that ever y n-processor algorithm for k-compaction problem requires Ohm(log log n) time, even if k = 2. Finally, we show that O(log k) time can be ach ieved on the ROBUST PRAM, a very weak CRCW PRAM model.