A complexity theory of efficient parallel algorithms. (English) Zbl 0699.68069

Kruskal, Clyde P.; Rudolph, Larry; Snir, Marc

Theor. Comput. Sci. 71, No. 1, 95-132 (1990).

See the review in Zbl 0657.68044.

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q05	Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

PE PRAM model; parallel algorithms; complexity; classes; models of computation; efficient simulation

Citations:

Zbl 0639.00042; Zbl 0657.68044

References:

[1]	Aggarwal, A.; Anderson, R. J., A random NC algorithm for depth first search, Combinatorica, 8, 1-12 (1988) · Zbl 0647.68060
[2]	Aggarwal, A.; Chandra, A., Virtual memory algorithms, Chicago, IL, U.S.A.. Chicago, IL, U.S.A., Proc. 20th ACM Symp. on Theory of Computing, 173-185 (1988)
[3]	Aggarwal, A.; Chandra, A. K., Communication complexity of PRAM’s, (Lepistö, T.; Salomaa, A., Proc. 15th Int. Colloquium on Automata, Languages and Programming. Proc. 15th Int. Colloquium on Automata, Languages and Programming, Tampere, Finland. Proc. 15th Int. Colloquium on Automata, Languages and Programming. Proc. 15th Int. Colloquium on Automata, Languages and Programming, Tampere, Finland, Lecture Notes in Computer Science, 317 (1988), Springer: Springer Berlin), 1-17
[4]	Aggarwal, A.; Chandra, A. K.; Snir, M., On communication latency in PRAM computations, Santa Fe, New Mexico, USA. Santa Fe, New Mexico, USA, Proc. ACM Symp. on Parallel Algorithms and Architectures, 11-21 (1989)
[5]	Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0207.01701
[6]	Ajtal, M.; Komlos, J.; Steiger, W. L.; Szemeredi, E., Optimal parallel selection has complexity O(log log \(n)\), J. Comput. System Sci., 38, 125-133 (1989) · Zbl 0668.68044
[7]	Ajtal, M.; Komlos, J.; Szemeredi, E., Sorting in \(c\) log \(n\) parallel steps, Combinatorica, 3, 1-19 (1983) · Zbl 0523.68048
[8]	Alt, H.; Hagerup, T.; Mehlhorn, K.; Preparata, F. P., Deterministic simulation of idealized parallel computers on more realistic ones, SIAM J. Comput., 16, 808-835 (1987) · Zbl 0635.68015
[9]	Arjomandi, E.; Fisher, M.; Lynch, N., Efficiency of synchronous versus asynchronous distributed systems, J. Assoc. Comput. Mach., 30, 449-456 (1983) · Zbl 0627.68025
[10]	Batcher, K. E., Sorting networks and their applications, Proc. AFIPS, 32, 307-314 (1968)
[11]	Baudet, G.; Stevenson, G., Optimal sorting algorithms for parallel computers, IEEE Trans. Comput., 27, 84-87 (1978) · Zbl 0369.68021
[12]	Bertoni, A.; Goldwurn, M.; Mauri, G.; Sabatini, N., Parallel algorithms and the classification of problems, (Becker, J. D.; Eisele, I., Proc. Workshop on Parallel Processing: Logic Organization and Technology (WOPPLOT 86). Proc. Workshop on Parallel Processing: Logic Organization and Technology (WOPPLOT 86), Neubiberg, FRG. Proc. Workshop on Parallel Processing: Logic Organization and Technology (WOPPLOT 86). Proc. Workshop on Parallel Processing: Logic Organization and Technology (WOPPLOT 86), Neubiberg, FRG, Lecture Notes in Computer Science, 253 (1986), Springer: Springer Berlin), 206-226
[13]	Bilardi, G.; Nicolau, A., Adaptive bitonic sorting: an optimal parallel algorithm for shared memory machines, SIAM J. Comput., 18, 216-228 (1989) · Zbl 0677.68070
[14]	Blum, M., A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach., 14, 322-336 (1967) · Zbl 0155.01503
[15]	Borodin, A.; Hopcroft, J. E., Routing, merging and sorting on parallel models of computation, San Francisco, CA, U.S.A.. San Francisco, CA, U.S.A., Proc. 14th ACM Symp. on Theory of Computing, 338-344 (1982)
[16]	Borodin, A.; Munro, I., The Computational Complexity of Algebraic and Numeric Problems (1975), Elsevier: Elsevier New York · Zbl 0404.68049
[17]	Brent, R. P., The parallel evaluation of general arithmetic expressions, J. Assoc. Comput. Mach., 21, 201-206 (1974) · Zbl 0276.68010
[18]	Carter, L.; Wegman, M., New hash functions and their use in authentication and set equality, J. Comput. System Sci., 22, 265-279 (1981) · Zbl 0461.68074
[19]	Chin, F. Y.; Lam, J.; Chen, I.-N., Efficient parallel algorithms for some graph problems, Comm. ACM, 25, 659-665 (1982) · Zbl 0485.68056
[20]	Cole, R., Parallel merge sort, SIAM J. Comput., 17, 770-785 (1988) · Zbl 0651.68077
[21]	Cole, R.; Vishkin, U., Approximate and exact parallel scheduling with applications to list, tree and graph problems, Toronto, Canada. Toronto, Canada, Proc. 27th Ann. Symp. on Foundations of Computer Science, 478-491 (1986)
[22]	Cook, S. A., Toward a complexity theory of synchronous parallel computations, Enseign. Math., XXVII, 99-124 (1981) · Zbl 0473.68041
[23]	Cook, S. A.; Dwork, C.; Reischuk, R., Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM J. Comput., 15, 87-97 (1986) · Zbl 0591.68049
[24]	Csanky, L., Fast parallel inversion algorithms, SIAM J. Comput., 5, 618-623 (1976) · Zbl 0353.68063
[25]	Cypher, R.; Sanz, J. L.C., Cubesort: an optimal sorting algorithm for feasible parallel computers, (Reif, J. H., 3rd Aegean Workshop on Computing, AWOC 88. 3rd Aegean Workshop on Computing, AWOC 88, Corfu, Greece. 3rd Aegean Workshop on Computing, AWOC 88. 3rd Aegean Workshop on Computing, AWOC 88, Corfu, Greece, Lecture Notes in Computer Science, 319 (1988), Springer: Springer Berlin), 456-464 · Zbl 0652.68047
[27]	Driscoll, J. R.; Gabow, H. N.; Shrairman, R.; Tarjan, R. E., Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation, Comm. ACM, 31, 1343-1354 (1988)
[28]	Dymond, P. W.; Ruzzo, W. L., Parallel random access machines with owned global memory and deterministic context free language recognition, (Kott, L., Proc. 13th Int. Colloquium on Automata, Languages and Programming. Proc. 13th Int. Colloquium on Automata, Languages and Programming, Rennes, France. Proc. 13th Int. Colloquium on Automata, Languages and Programming. Proc. 13th Int. Colloquium on Automata, Languages and Programming, Rennes, France, Lecture Notes in Computer Science, 226 (1986), Springer: Springer Berlin), 95-104 · Zbl 0596.68047
[29]	Eckstein, D. M.; Alton, D., Parallel graph processing using depth-first search, Conf. on Theoretical Computer Science at the University of Waterloo, 21-29 (1977) · Zbl 0408.68060
[30]	Fortune, S.; Wyllie, J., Parallelism in random access machines, San Diego, CA, U.S.A.. San Diego, CA, U.S.A., Proc. 10th ACM Symp. Theory of Computing, 114-118 (1978) · Zbl 1282.68104
[31]	Furer, M., Generalized iterative arrays, (Technical Report TR 79-07-03 CS (1979), Univ. of Washington: Univ. of Washington Seattle, WA, U.S.A)
[32]	Gazit, H., An optimal randomized parallel algorithm for finding connected components in a graph, Toronto, Canada. Toronto, Canada, Proc. 27th Ann. Symp. on Foundations of Computer Science, 492-501 (1986)
[33]	Goldberg, A. V.; Plotkin, S. A.; Vaidya, P. M., Sublinear-time parallel algorithms for matching and related problems, White Plains, New York. White Plains, New York, 29th Ann. Symp. on Foundations of Computer Science, 432-443 (1988)
[34]	Goldschlager, L., A unified approach to models of synchronous parallel machines, San Diego, CA, U.S.A.. San Diego, CA, U.S.A., Proc. 10th ACM Symp. on Theory of Computing, 89-94 (1978) · Zbl 1282.68105
[35]	Gottlieb, A.; Grishman, R.; Kruskal, C. P.; McAuliffe, K. P.; Rudolph, L.; Snir, M., The NYU Ultracomputer—designing an MIMD parallel machine, IEEE Trans. Comput., 32, 175-189 (1983)
[36]	Gottlieb, A.; Kruskal, C. P., Complexity results for permuting data and other computations on parallel processots, J. Assoc. Comput. Mach., 31, 193-204 (1984) · Zbl 0631.68045
[37]	Gustafson, J. L.; Montry, G. R.; Benner, R. E., Development of parallel methods for a 1024-processor hypercube, SIAM J. Sci. Statist. Comput., 9, 609-638 (1988) · Zbl 0652.65091
[38]	Han, Y., An optimal linked list prefix algorithm on local memory computer TR 111-88 (Nov. 1987), Dept. of Computer Science, Univ. of Kentucky: Dept. of Computer Science, Univ. of Kentucky Lexington, KY, U.S.A
[39]	Hoover, H. J.; Klawe, M. M.; Pippenger, N. J., Bounding fan-out in logical networks, J. Assoc. Comput. Mach., 31, 13-18 (1984) · Zbl 0626.94015
[41]	Karlin, A. K.; Uptal, E., Parallel hashing—an efficient implementation of shared memory, Berkeley, CA, U.S.A.. Berkeley, CA, U.S.A., Proc. 18th ACM Symp. on Theory of Computing, 160-168 (1986)
[43]	Karp, R. M.; Upfal, E.; Widgerson, A., The complexity of parallel search, J. Comput. System Sci., 36, 225-253 (1988) · Zbl 0651.68048
[44]	Karp, R. M.; Upfal, E.; Widgerson, A., Constructing a maximum matching is in random NC, Combinatorica, 6, 35-48 (1986) · Zbl 0646.05051
[46]	Kosaraju, S. R.; Delcher, A. L., Optimal parallel evaluation of tree-structured computations for raking (extended abstract), (Proc. 3rd Aegaen Workshop in Computing, AWOC 88. Proc. 3rd Aegaen Workshop in Computing, AWOC 88, Lecture Notes in Computer Science, 319 (1988), Springer: Springer Berlin), 101-110
[47]	Kruskal, C. P., Algorithms for replace-add based paracomputers, Michigan, U.S.A.. Michigan, U.S.A., Proc. Int. Conf. on Parallel Processing, 219-223 (1982)
[48]	Kruskal, C. P., Searching, merging, and sorting in parallel computation, IEEE Trans. Comput., 32, 942-946 (1983) · Zbl 0525.68039
[49]	Kruskal, C. P., Performance bounds on parallel processors: an optimistic view, (Control Flow and Data Flow: Concepts of Distributed Programming. Control Flow and Data Flow: Concepts of Distributed Programming, NATO ASI series, Series F: Computer and System Sciences, 14 (1985), Springer: Springer Berlin), 331-344
[50]	Kruskal, C. P.; Madej, T.; Rudolph, L., Parallel prefix on fully connected direct connection machine, Illinois, U.S.A.. Illinois, U.S.A., Proc. Int. Conf. on Parallel Processing, 278-283 (1986)
[51]	Kruskal, C. P.; Rudolph, L.; Snir, M., Efficient synchronization in multiprocessors with shared memory, ACM Trans. Programming Languages and Systems, 10, 579-601 (1988) · Zbl 0663.68011
[52]	Kruskal, C. P.; Rudolph, L.; Snir, M., Efficient parallel algorithms for graph problems, Illinois, U.S.A.. Illinois, U.S.A., Proc. Int. Conf. on Parallel Processing, 869-876 (1986)
[53]	Kucera, L., Parallel computation and conflicts in memory accesses, Inform. Process. Lett., 14, 93-96 (1982) · Zbl 0498.68029
[54]	Kuck, D. J., The Structure of Computers and Computations (1978), John Wiley: John Wiley New York
[55]	Leighton, T., Tight bounds on the complexity of parallel sorting, IEEE Trans. Comput., 34, 965-968 (1985)
[56]	Lev, G.; Pippenger, N.; Valiant, L. G., A fast parallel algorithm for routing in permutation networks, IEEE Trans. Comput., 30, 93-100 (1981) · Zbl 0455.94047
[57]	Lynch, N. A.; Fisher, M. J., On describing the behavior an implementation of distributed systems, Theoret. Comput. Sci., 13, 17-43 (1981) · Zbl 0441.68020
[58]	Meertens, L., Recurrent Ultracomputers are not log N-Fast, (Ultracomputer Note 2 (March 1979), New York University: New York University New York, NY, U.S.A) · Zbl 0415.68011
[59]	Mehlhorn, K.; Vishkin, U., Randomized and deterministic simulations of PRAMs by parallel machines with restricted granualarity of parallel memories, Acta Inform., 21, 339-374 (1984) · Zbl 0548.68044
[60]	Mulmuley, K.; Vazirani, U. V.; Vazirani, V. V., Matching is as easy as matrix inversion, Combinatorica, 7, 105-114 (1987) · Zbl 0632.68041
[61]	Nassimi, D.; Sahni, S., Data broadcasting in SIMD computers, IEEE Trans. Comput., 30, 101-107 (1981)
[62]	Pease, M. C., An adaptation of the fast Fourier transform for parallel processing, J. Assoc. Comput. Mach., 15, 252-264 (1968) · Zbl 0165.51502
[63]	Pippenger, N., Sorting and selecting in rounds, SIAM J. Comput., 6, 1032-1038 (1986) · Zbl 0654.68068
[64]	Ranade, A. G., How to emulate shared memory, Los Angeles, California. Los Angeles, California, Proc. 28th Ann. Symp. on Foundations of Computer Science, 185-194 (1987)
[65]	Reif, J. H., Depth-first search is inherently sequential, Inform. Process. Lett., 20, 229-234 (1985) · Zbl 0572.68051
[66]	Reif, J. H., An optimal parallel algorithm for integer sorting, Portland, Oregon. Portland, Oregon, Proc. 26th Ann. Symp. on Foundations of Computer Science, 496-504 (1985)
[67]	Rudolph, L., Software structures for ultraparallel computing, (Ph.D. Thesis (1982), New York University: New York University New York, NY, U.S.A)
[68]	Schwartz, J., Ultracomputers, ACM Trans. Programming Languages and Systems, 2, 484-521 (1980) · Zbl 0468.68027
[69]	Shiloach, Y.; Vishkin, U., An O(log \(n)\) parallel connectivity algorithm, J. Algorithms, 3, 57-67 (1982) · Zbl 0494.68070
[70]	Snir, M., On parallel searching, SIAM J. Comput., 14, 688-708 (1985) · Zbl 0607.68047
[72]	Snir, M., Size depth trade-offs for monotone arithmetic circuits, (IBM Tech. Rep. RC 13742 (May 1988), IBM Research Division: IBM Research Division Yorktown Heights, NY, U.S.A) · Zbl 0727.68049
[73]	Upfal, E.; Wigderson, A., How to share memory in a distributed system, J. Assoc. Comput. Mach., 34, 116-127 (1987) · Zbl 0629.68028
[74]	Valiant, L. G., Parallelism in comparison problems, SIAM J. Comput., 4, 348-355 (1975) · Zbl 0311.68033
[75]	Valiant, G., Structures for highly parallel computing, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. A (1990), North-Holland: North-Holland Amsterdam), to appear.
[76]	Valiant, L. G.; Skyum, S.; Berkowitz, S.; Rackoff, C., Fast parallel computation of polynomials using few processors, SIAM J. Comput., 12, 641-644 (1983) · Zbl 0524.68028
[77]	Vitter, J. S.; Simons, R. A., New classes for parallel complexity: a study of unification and other complete problems for P, IEEE Trans. Comput., 35, 403-418 (1986) · Zbl 0613.68023
[78]	Vuillemin, J., A combinatorial limit to the computing power of VLSI circuits, Buffalo, New York. Buffalo, New York, Proc. 21st Ann. Symp. on Foundations of Computer Science, 294-300 (1980)
[79]	Vishkin, U.; Widgerson, A., Dynamic parallel memories, Inform. and Control, 56, 174-182 (1983) · Zbl 0536.68026
[80]	Wagner, R. A.; Han, Y., Parallel algorithms for bucket sorting and the data dependent prefix problem, Illinois, U.S.A.. Illinois, U.S.A., Proc. Int. Conf. on Parallel Processing, 924-930 (1986)
[81]	Wagner, R. A.; Han, Y., An efficient and fast parallel connected component algorithm (1986), Duke University: Duke University Raleigh, NC, U.S.A, Manuscript