More Web Proxy on the site http://driver.im/

research-article

Fast and Efficient Simulations among CRCW PRAMs

Authors:

Y. MatiasAuthors Info & Claims

Journal of Parallel and Distributed Computing, Volume 23, Issue 2

Pages 135 - 148

https://doi.org/10.1006/jpdc.1994.1127

Published: 01 November 1994 Publication History

Abstract

We study the problem of fast leaders election on TOLERANT, a CRCW PRAM model which tolerates concurrent write but does not support symmetry breaking. The leaders election problem is related to the problem of simulating stronger CRCW models, which support leaders election by predefined conflict resolution rules. We give a randomized simulation of MAXIMUM-a very strong CRCW PRAM-on TOLERANT. The simulation is optimal, is reliable, and runs in nearly doubly logarithmic time and linear space. This is the first simulation which is fast, optimal, and space-efficient, and therefore grants true comparison of algorithms running on different CRCW PRAMs. Moreover, it implies that the memory to which concurrent read or concurrent write is allowed should never be more than linear-the rest of the memory can always be addressed under the EREW convention. The techniques presented in this paper tackle fundamental difficulties in the design of fast parallel algorithms.

References

[1]

Awerbuch, B., and Shiloach, Y. New connectivity and MSF algorithms for Ultracomputer and PRAM. Proc. of the International Conference on Parallel Processing and Applications. 1983, pp. 175-179.

[2]

Beame, P., and Håstad, J. Optimal bounds for decision problems on the CRCW PRAM. J. Assoc. Comput. Mach. 36, 3 (July 1989). 643-670.

Digital Library

[3]

Berkman, O., Breslauer, D., Galil, Z., Schieber, B., and Vishkin, U. Highly parallelizable problems. Proc. of the 21st Annual ACM Symposium on Theory of Computing. 1989, pp. 309-319.

[4]

Berkman, O., and Vishkin, U. Recursive star-tree parallel data structure. SIAM J. Comput. 22, 2 (1993), 221-242.

Digital Library

[5]

Bhatt, P. C., Diks, K., Hagerup, T., Prasad, V. C., Radzik. T., and Saxena, S. Improved deterministic parallel integer sorting. Inform and Comput. 94 (Nov. 1991), 29-47.

Digital Library

[6]

Boppana, R. B. Optimal separations between concurrent-write parallel machines. Proc. of the 21st Annual ACM Symposium on Theory of Computing. 1989, pp. 320-326.

[7]

Borodin, A., Hopcroft, J. E., Paterson, M. S., Ruzzo, W. L., and Tompa, M. Observations concerning synchronous parallel models of computation. Manuscript, 1980.

[8]

Chernoff, H. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. of Math. Statist. 23 (1952), 493-507.

[9]

Chlebus, B. S., Diks, K., Hagerup, T., and Radzik, T. Efficient simulations between concurrent-read concurrent-write PRAM models. In Proc. of 13th Symposium on Mathematical Foundations of Computer Science. Springer-Verlag, Berlin/New York, 1988. Lecture Notes in Computer Science. Vol. 324, pp. 231-239.

[10]

Chlebus, B. S., Diks, K., Hagerup, T., and Radzik, T. New simulations between CRCW PRAMs. Proc. of 7th International Conference on Fundamentals of Computation Theory. Springer-Verlag, Berlin/New York, 1989, Lecture Notes in Computer Science, Vol. 380, pp. 95-104.

[11]

Cook, S. A., Dwork, C and Reischuk, R. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput. 15 (1986), 87-97.

Digital Library

[12]

Dietzfelbinger, M., Gil, J., Matias, Y., and Pippenger. N. Polynomial hash functions are reliable. Proc. of 19th International Colloquium on Automata Languages and Programming. Springer-Verlag, Berlin/New York, July 1992, Lecture Notes in Computer Science, Vol. 623, pp. 235-246.

[13]

Dietzfelbinger, M., Kutylowski, M., and Reischuk, R. Exact time bounds for computing boolean functions on PRAMs without simultaneous writes. 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990, pp. 125-135.

Digital Library

[14]

Eppstein, D., and Galil, Z. Parallel algorithmic techniques for combinatorial computation. Ann. Rev. Comput. Sci. 3 (1988), 233-283.

[15]

Fich, F. E., Meyer auf der Heide, F., and Wigderson, A. Lower bounds for parallel random-access machines with unbounded shared memory. In Advances in Computing Research. JAI Press, 1986.

[16]

Fich, F. E., Ragde, P. L., and Wigderson, A. Relations between concurrent-write models of parallel computation. SIAM J. Comput. 17 (June 1988), 606-627.

Digital Library

[17]

Fich, F. E., Ragde, P. L., and Wigderson, A. Simulations among concurrent-write PRAMs. Algorithmica 3 (1988), 43-51.

Digital Library

[18]

Fredman, M. L., Komlos, J., and Szemeredi, E. Storing a sparse table with O(1) worst case access time. J. Assoc. Comput. Mach. 31, 3 (July 1984), 538-544.

Digital Library

[19]

Gil, J. Lower Bounds and Algorithms for Hashing and Parallel Processing. Ph.D. thesis. The Hebrew University of Jerusalem, Nov. 1990.

[20]

Gil, J. Fast load balancing on a PRAM. Proc. of the 3rd IEEE Symposium on Parallel and Distributed Computing. Dec. 1991, pp. 10-17.

Digital Library

[21]

Gil, J., and Matias, Y. Fast hashing on a PRAM--Designing by expectation. Proc. of the Second Annual ACM-SIAM Symposium on Discrete Algorithms. 1991, pp. 271-280.

Digital Library

[22]

Gil, J., and Matias, Y. Simple fast parallel hashing. Manuscript, 1992.

[23]

Gil, J., and Matias, Y. Leaders election without a conflict resolution rule--fast and efficient randomized simulations among CRCW PRAMs. Proc. of the 1st Latin American Informatics Symposium. Springer-Verlag, Berlin/New York, 1992. Lecture Notes in Computer Science, Vol. 583, pp. 204-218.

[24]

Gil, J., Matias, Y., and Vishkin. U. Towards a theory of nearly constant time parallel algorithms. Proc. of the 32nd IEEE Annual Symposium on Foundations of Computer Science. Oct. 1991, pp. 698-710.

Digital Library

[25]

Gil, J., and Rudolph, L. Counting and packing in parallel. Proc. of the International Conference on Parallel Processing and Applications. 1986, pp. 1000-1002.

[26]

Goldschlager, L. M. A universal interconnection pattern for parallel computers. J. Assoc. Comput. Mach. 29, 4 (Julv 1982). 1073-1086.

Digital Library

[27]

Greenberg, A. G., Flajolet, P., and Ladner, R. E. Estimating the multiplicity of conflicts to speed their resolution in multiple access channels. J. Assoc. Comput. Mach. 34, 2 (1987), 289-325.

Digital Library

[28]

Grolmusz, V., and Ragde, P. L. Incomparability in parallel computation. Proc. of the 28th IEEE Annual Symposium on Foundations of Computer Science. 1987, pp. 89-98.

Digital Library

[29]

Grolmusz, V., and Ragde, P. L. Incomparability in parallel computation. Discrete Appl. Math. 29 (1990), 63-78.

Digital Library

[30]

Hagerup, T. Self-simulation on the PRAM. Manuscript, Oct. 1990.

[31]

Hagerup, T., and Radzik, T. Every robust CRCW PRAM can efficiently simulate a priority PRAM. In 2nd Annual ACM Symposium on Parallel Algorithms and Architectures. 1990, pp. 117-124.

Digital Library

[32]

JáJá, J. Introduction to Parallel Algorithms. Addison-Wesley, Reading, MA, 1992.

Digital Library

[33]

Karp, R. M., and Ramachandran, V. Parallel algorithms for shared-memory machines. In J. van Leeuwen (Ed.). Handbook of Theoretical Computer Science. North-Holland, Amsterdam. 1990, Vol. A, pp. 869-941.

[34]

Kruskal, C. P. Searching, merging, and sorting in parallel computation. IEEE Trans. Comput. C-32 (1983), 942-946.

Digital Library

[35]

Kruskal, C. P., Rudolph, L., and Snir, M. A complexity theory of efficient parallel algorithms. Theoret. Comput. Sci. 71 (1990), 95-132.

Digital Library

[36]

Kucera, L. Parallel computation and conflicts in memory access. Inform. Process. Lett. 14 (1982). 93-96.

[37]

MacKenzie, P. D., and Stout, Q. F. Ultra-fast expected time parallel algorithms. Proc. of the Second Annual ACM-SIAM Symposium on Discrete Algorithms. 1991. pp. 414-423.

Digital Library

[38]

Martel, C. U., and Gusfield, D. A fast parallel quicksort algorithm. Inform. Process. Lett. 30 (1989), 97-102.

Digital Library

[39]

Matias, Y. Highly Parallel Randomized Algorithmics. Ph.D. thesis, Tel Aviv University, Dec. 1992.

[40]

Matias, Y., and Vishkin, U. Converting high probability into nearly-constant time--With applications to parallel hashing. Proc. of the 23rd Annual ACM Symposium on Theory of Computing. May 1991, pp. 307-316.

[41]

Matias, Y., and Vishkin, U. On parallel hashing and integer sorting. J. Algorithms 12, 4 (1991), 573-606.

Digital Library

[42]

Ragde, P. L. The parallel simplicity of compaction and chaining. Proc. of 17th International Colloquium on Automata Languages and Programming. Springer-Verlag, Berlin/New York, 1990, Lecture Notes in Computer Science, Vol. 443. pp. 744-751. To appear in J. Algorithms.

[43]

Ragde, P. L., Steiger, W. L., Szemerédi, E., and Wigderson, A. The parallel complexity of element distinctness if ¿(¿lg n). SIAM J. Discrete Math. 1, 3 (Aug. 1988), 399-410.

Digital Library

[44]

Reischuk, R. Probabilistic parallel algorithms for sorting and selection. SIAM J. Comput. 14, 2 (May 1985), 396-409.

[45]

Shiloach, Y., and Vishkin, U. Finding the maximum, merging, and sorting in a parallel computation model. J. Algorithms 2 (1981), 88-102.

[46]

Shiloach, Y., and Vishkin, U. An O(lg n) parallel connectivity algorithm. J. Algorithms 3 (1982), 57-67.

[47]

Valiant, L. G. Parallelism in comparison problems. SIAM J. Comput. 4 (1975), 348-355.

Digital Library

[48]

Vishkin, U. On choice of a model of parallel computation. Tech. Rep. 61, Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, New York, NY, 1983.

[49]

Vishkin, U. Synchronous parallel computation--A survey. Tech. Rep. 71, Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, New York, NY, 1983. Also in Annual Paper Collection of "Datalogforeningen" (The Computer Science Association of Aarhus, Denmark), 1987, pp. 76-89.

[50]

Vishkin, U. Research on parallel algorithms. UMIACS 1989 Annual Report, 1990.

[51]

Willard, D. E. Log-logarithmic selection resolution protocols in a multiple access channel. SIAM J. Comput. 15 (1986), 468-477.

Digital Library

Cited By

Ghanim FElwasif WBernholdt D(2021)Implementing Arbitrary/Common Concurrent Writes of CRCW PRAM50th International Conference on Parallel Processing Workshop10.1145/3458744.3474041(1-9)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3458744.3474041
Agrawal KHe YHsu WLeiserson CTorrellas JChatterjee S(2006)Adaptive scheduling with parallelism feedbackProceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/1122971.1122988(100-109)Online publication date: 29-Mar-2006
https://dl.acm.org/doi/10.1145/1122971.1122988
Fujiwara TIwama KIwamoto C(2004)Partially effective randomization in simulations between arbitrary and common PRAMsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2003.12.00164:3(319-326)Online publication date: 1-Mar-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2003.12.001
Show More Cited By

Index Terms

Fast and Efficient Simulations among CRCW PRAMs
1. Computing methodologies
  1. Modeling and simulation
2. Theory of computation
  1. Logic
  2. Models of computation

Recommendations

Parallel integer sorting and simulation amongst CRCW models
Abstract
In this paper a general technique for reducing processors in simulation without any increase in time is described. This results in an O(√logn) time algorithm for simulating one step of PRIORITY on TOLERANT with processor-time product of O(n log ...
Leaders Election Without a Conflict Resolution Rule - Fast and Efficient Randomized Simulations among CRCW PRAMs
Partially effective randomization in simulations between arbitrary and common PRAMs

It is known that Θ(log n/log log n) steps are needed to simulate one step of ARBITRARY CRCW PRAMs by COMMON CRCW PRAMs, but it was open whether there is a faster simulation when randomization is allowed. This paper gives both positive and negative ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Parallel and Distributed Computing

Journal of Parallel and Distributed Computing Volume 23, Issue 2

Nov. 1994

143 pages

ISSN:0743-7315

Editors:
Allan Gottlieb
New York Univ., New York, NY
,
Kai Hwang
Univ. of Southern California, Los Angeles
,
Sartaj Sahni
Univ. of Florida, Gainesville

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 November 1994

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghanim FElwasif WBernholdt D(2021)Implementing Arbitrary/Common Concurrent Writes of CRCW PRAM50th International Conference on Parallel Processing Workshop10.1145/3458744.3474041(1-9)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3458744.3474041
Agrawal KHe YHsu WLeiserson CTorrellas JChatterjee S(2006)Adaptive scheduling with parallelism feedbackProceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/1122971.1122988(100-109)Online publication date: 29-Mar-2006
https://dl.acm.org/doi/10.1145/1122971.1122988
Fujiwara TIwama KIwamoto C(2004)Partially effective randomization in simulations between arbitrary and common PRAMsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2003.12.00164:3(319-326)Online publication date: 1-Mar-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2003.12.001
Greiner JBlelloch G(1999)A provably time-efficient parallel implementation of full speculationACM Transactions on Programming Languages and Systems10.1145/316686.31669021:2(240-285)Online publication date: 1-Mar-1999
https://dl.acm.org/doi/10.1145/316686.316690
Greiner JBlelloch GBoehm HSteele G(1996)A provably time-efficient parallel implementation of full speculationProceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/237721.237797(309-321)Online publication date: 1-Jan-1996
https://dl.acm.org/doi/10.1145/237721.237797
Blelloch GGreiner J(1996)A provable time and space efficient implementation of NESLACM SIGPLAN Notices10.1145/232629.23265031:6(213-225)Online publication date: 15-Jun-1996
https://dl.acm.org/doi/10.1145/232629.232650
Blelloch GGreiner JHarper R(1996)A provable time and space efficient implementation of NESLProceedings of the first ACM SIGPLAN international conference on Functional programming10.1145/232627.232650(213-225)Online publication date: 15-Jun-1996
https://dl.acm.org/doi/10.1145/232627.232650

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents