Retrieval of scattered information by EREW, CREW and CRCW PRAMs,
Faith Fich, Miroslaw Kowaluk, Miroslaw Kutylowski,
Krzysztof Lorys, Prabhakar Ragde,
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
obvious applications in processor allocation and load balancing;
k-compaction is also an important subroutine in many recently developed
parallel algorithms. We show that any EREW PRAM that solves the
k-compaction problem requires Omega(sqrt(log n)) time, even if the
number of processors is arbitrarily large and k=2. On the CREW PRAM, we
show that every n-processor algorithm for k-compaction problem requires
Omega(loglog n) time, even if k=2. Finally, we show that O(log k) time
can be achieved on the ROBUST PRAM, a very weak CRCW PRAM model.