zbMATH — the first resource for mathematics

Retrieval of scattered information by EREW, CREW, and CRCW PRAMs. (English) Zbl 0838.68052
Summary: The \(k\)-compaction problem arises when \(k\) out of \(n\) cells in an array are on-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(\log\log 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.

68W15 Distributed algorithms
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] H. Bast and T. Hagerup, Fast and Reliable Parallel Hashing. InProc. 3rd Ann. ACM Symp. Parallel Algorithms and Architectures, 1991, 50–61.
[2] P. Beame,Lower Bounds in Parallel Machine Computation. Ph.D. thesis, University of Toronto, 1986.
[3] P. Beame, M. Kik, andM. Kutyłowski, Information Broadcasting by Exclusive Read PRAMs.Parallel Processing Letters 4.1&2 (1994), 159–169. · doi:10.1142/S012962649400017X
[4] C. Berge,Graphs and Hypergraphs. North-Holland, Amsterdam, 1976.
[5] R. Cole, Parallel Merge Sort.SIAM J. Comput. 17 (1988), 770–785. · Zbl 0651.68077 · doi:10.1137/0217049
[6] S. Cook, C. Dwork, andR. Reischuk, Upper and Lower Time Bounds for Parallel Random Access Machines Without Simultaneous Writes.SIAM J. Comput. 15 (1986), 87–97. · Zbl 0591.68049 · doi:10.1137/0215006
[7] M. Dietzfelbinger, M. Kutyłowski, andR. Reischuk, Exact Time Bounds for Computing Boolean Functions on PRAMs Without Simultaneous Writes.J. Comput. System Sci. 48 (1994), pp. 231–254. · Zbl 0822.68049 · doi:10.1016/S0022-0000(05)80003-0
[8] F. E. Fich, R. Impagliazzo, B. Kapron, V. King, andM. Kutyłowski, Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. InProc. 10th Ann. Symp. Theoret. Aspects Comput. Sci., Lecture Notes in Computer Science665, Springer-Verlag, Berlin, 1993, 386–397. · Zbl 0842.68033
[9] F. E. Fich, P. Ragde, andA. Wigderson, Relations Between Concurrent-Write Models of Parallel Computation.SIAM J. Comput. 17 (1988), 606–627. · Zbl 0652.68065 · doi:10.1137/0217037
[10] J. Gil and Y. Matias, Fast Hashing on a PRAM-Designing by Expectation. InProc. 2nd Ann. ACM Symp. Discrete Algorithms, 1991, 271–280. · Zbl 0800.68457
[11] J. Gil, Y. Matias, and U. Vishkin, Towards a Theory of Nearly Constant Parallel Time Algorithms. InProc. 32nd Ann. IEEE Symp. Found. Comput. Sci., 1991, 698–710.
[12] J. Gil and L. Rudolph, Counting and Packing in Parallel. InProc. 1986 Int. Conf. Parallel Processing, IEEE Comput. Soc. Press, 1986, 1000–1002.
[13] M. Goodrich, Using Approximation Algorithms to Design Parallel Algorithms that may Ignore Processor Allocation. InProc. 32nd Ann. IEEE Symp. Found. Comput. Sci., 1991, 711–722.
[14] T. Hagerup. Personal communication.
[15] T. Hagerup, Fast and Optimal Simulations between CRCW PRAMs. InProc. 9th Symp. Theoret. Aspects Comput. Sci., Lecture Notes in Computer Science577, Springer-Verlag, Berlin, 1992, 45–56.
[16] T. Hagerup, The Log-Star Revolution. InProc. 9th Symp. Theoret. Aspects Comput. Sci., Lecture Notes in Computer Science578, Springer-Verlag, Berlin, 1992, 259–278.
[17] T. Hagerup andM. Nowak, Parallel Retrieval of Scattered Information. InProc. 16th Int. Colloq. Automata Languages and Programming, Lecture Notes in Computer Science372, Springer-Verlag, Berlin, 1989, 439–450.
[18] T. Hagerup and T. Radzik, Every ROBUST CRCW PRAM can Efficiently Simulate a PRIORITY PRAM. InProc. 2nd ACM Symp. Parallel Algorithms and Architectures, 1990, 125–135.
[19] M. Kutyłowski, Time Complexity of Boolean Functions on CREW PRAMs.SIAM J. Comput. 20 (1991), 824–833. · Zbl 0732.68053 · doi:10.1137/0220051
[20] P. D. MacKenzie, Lower Bounds for Randomized Exclusive Write PRAMs InProc. 7th Ann. ACM Symp. Parallel Algorithms and Architectures, 1995, pp 254–263.
[21] Y. Matias andU. Vishkin, On Parallel Hashing and Integer Sorting.J. Algorithms 12 (1991), 573–606. · Zbl 0767.68051 · doi:10.1016/0196-6774(91)90034-V
[22] J. B. Rosser andL. Schoenfeld, Approximate Formulas for Some Functions of Prime Numbers.Illinois J. Math. 6 (1962), 64–94. · Zbl 0122.05001
[23] P. Ragde, The Parallel Simplicity of Compaction and Chaining.J. Algorithms 14 (1993), 371–380. · Zbl 0793.68072 · doi:10.1006/jagm.1993.1019
[24] L. Rudolph and W. Steiger, Subset Selection in Parallel. InProc. 1985 Int. Conf. Parallel Processing, IEEE Comput. Soc. Press, 1985, 11–14.
[25] M. Snir, On Parallel Searching.SIAM J. Comput. 14 (1985), 688–708. · Zbl 0607.68047 · doi:10.1137/0214051
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.