×
Borodin, A.; Hopcroft, J. E.

Routing, merging, and sorting on parallel models of computation. (English) Zbl 0603.68065

J. Comput. Syst. Sci. 30, 130-145 (1985).
A variety of models have been proposed for the study of synchronous parallel computation. These models are reviewed and some prototype problems are studied further. Two classes of models are recognized, fixed connection networks and models based on a shared memory. Routing and sorting are prototype problems for the networks; in particular, they provide the basis for simulating the more powerful shared memory models. It is shown that a simple but important class of deterministic strategies (oblivious routing) is necessarily inefficient with respect to worst case analysis. Routing can be viewed as a special case of sorting, and the existence of an O(log n) sorting algorithm for some n processor fixed connection network has only recently been established by M. Ajtai, J. Komlos, and E. Szemeredi [15th ACM Symp. on Theory of Comput., Boston, Mass., 1-9 (1983)]. If the more powerful class of shared memory models is considered then it is possible to simply achieve an O(log n loglog n) sort via Valiant’s parallel merging algorithm, which it is shown can be implemented on certain models. Within a spectrum of shared memory models, it is shown that loglog n is asymptotically optimal for n processors to merge two sorted lists containing n elements.

Cited in 54 Documents

MSC:

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

Keywords:

synchronous parallel computation; fixed connection networks; shared memory models
PDF BibTeX XML Cite
\textit{A. Borodin} and \textit{J. E. Hopcroft}, J. Comput. Syst. Sci. 30, 130--145 (1985; Zbl 0603.68065)
Full Text: DOI

References:

[1] Aleliunas, R., Randomized parallel communications, (Proc. of ACM Sympos. on Principles of Distributed Computing. Proc. of ACM Sympos. on Principles of Distributed Computing, Ottawa Canada (1982)), 60-72
[2] Aitai, M.; Komlos, J.; Szemeredi, E., An \(O(n\) log \(n)\) sorting network, (15th Annual ACM Sympos. on Theory of Comput. 15th Annual ACM Sympos. on Theory of Comput, Boston, Mass. (1983)), 1-9
[3] Borodin, A.; Hopcroft, J., Routing, merging, and sorting in parallel models of computation, (Proc. 14th Annual ACM Sympos. on Theory of Comput.. Proc. 14th Annual ACM Sympos. on Theory of Comput., San Francisco, Calif (1982)), 338-344 · Zbl 0603.68065
[4] Chandra, A. K.; Stockmeyer, L. J.; Vishkin, U., Complexity theory for unbounded fan-in parallelism, (Proc. 23rd Annual IEEE Sympos. on Found. of Comput. Sci. (1982)), 1-13
[5] Cook, S. A., Towards a complexity theory of synchronous parallel computation, Enseign. Mathi., 27, 2, 99-124 (1981) · Zbl 0473.68041
[6] Cook, S. A.; Dwork, C., Bounds on the time of parallel RAM’s to compute simple functions, (Proc. 14th Annual ACM Sympos. on Theory of Comput. (1982)), 231-233
[7] Cook, S. A.; Dymond, P., Hardware complexity and parallel computation, (Proc. 21st Annual IEEE Sympos. on Found. of Comput. Sci. (1980)), 360-372
[8] Fortune, S.; Wyllie, J., Parallelism in random access machines, (Proc. 10th Annual ACM Sympos. on Theory of Comput.. Proc. 10th Annual ACM Sympos. on Theory of Comput., San Diego, Calif. (1978)), 114-118 · Zbl 1282.68104
[9] Furst, M.; Saxe, J. B.; Sipser, M., Parity, circuits and the polynomial-time hierarchy, (Proc. 22nd Annual IEEE Sympos. on Found. of Comput. Sci. (1981)), 260-270
[10] Galil, Z.; Paul, W. J., An efficient general purpose parallel computer, (Proc. 13th Annual ACM Sympos. on Theory of Comput.. Proc. 13th Annual ACM Sympos. on Theory of Comput., Milwaukee, Wisc. (1981)), 247-256
[11] Goldschlager, L., A unified approach to models of synchronous parallel machines, (Proc. 10th Annual ACM Sympos. on Theory of Comput.. Proc. 10th Annual ACM Sympos. on Theory of Comput., San Diego, Calif. (1978)), 89-94 · Zbl 1282.68105
[12] Gottlieb, A.; Lubachevsky, B. D.; Rudolph, L., Coordinating large number of processors, (Proc. of Int. Conf. on Parallel Processing (1981)), 341-349
[13] Haggkvist, R.; Hell, P., Parallel sorting with constant time for comparisons, SIAM J. Comput., 10, 3, 465-472 (1981) · Zbl 0461.68062
[14] Haggkvist, R.; Hell, P., Sorting and Merging in Rounds, (Computing Science technical report TR81-9 (1981), Simon Fraser University: Simon Fraser University Burnaby, B.C., Canada) · Zbl 0493.68060
[15] Knuth, D. E., (The Art ofComputer Programming, Vol. 3:Sorting and Searching (1972), Addison-Wesley: Addison-Wesley Reading, Mass)
[16] Kruskal, C. P., Searching, merging, and sorting in parallel computation, IEEE Trans. Comput. (1983), in press · Zbl 0525.68039
[17] Lang, T., Interconnections between PE and MBs using the shuffle-exchange, IEEE Trans. Comput., C-25, 496 (1976)
[18] Lev, G.; Pippenher, N.; Valiant, L. G., A fast parallel algorithm for routing in permutation networks, IEEE Trans. Comput., C-30, 93-100 (1981) · Zbl 0455.94047
[19] Preparata, F. P., New parallel-sorting schemes, IEEE Trans. Comput., C-27, 7, 669-673 (1978) · Zbl 0379.68025
[20] Preparata, F. P.; Viullemin, J., The cube-connected cycles, (Proc. 20th Sympos. on Found. of Comput. Sci. (1979)), 140-147
[21] Reif, J.; Valiant, L. G., A Logarithmic Time Sort for Linear Size Networks, (Aiken Computation Laboratory, TR13-82 (1982), Harvard University)
[22] Schwartz, J. T., Ultracomputers, ACM Trans. Programming Lang. Systems, 2, 484-521 (1980) · Zbl 0468.68027
[23] Shiloach, Y.; Vishkin, U., Finding the maximum, merging, and sorting in a parallel computation model, J. Algorithms, 2, 1, 88-102 (1981) · Zbl 0456.68062
[24] Snir, M., On Parallel Searching, (Department of Computer Science technical teport TR045 (June 1982), Courant Institute, New York University) · Zbl 0607.68047
[25] Stockmeyer, L. J.; Vishkin, U., Simulation of Parallel Random Access Machines by Circuits (1982), IBM T. J. Watson Research Center: IBM T. J. Watson Research Center Yorktown Heights, N.Y, RC-9362
[26] Stone, H., Parallel processing with the perfect shuffle, IEEE Trans. Comput., C-20, 2, 153-161 (1971) · Zbl 0214.42703
[27] Upfal, E., Efficient schemes for parallel communication, (Proc. of ACM Sympos. on Principles of Distributed Computing. Proc. of ACM Sympos. on Principles of Distributed Computing, Ottawa, Canada (1982)) · Zbl 0628.68021
[28] Valiant, L. G., Parallelism in comparison problems, SIAM J. Comput., 4, 348-355 (1975) · Zbl 0311.68033
[29] Valiant, L. G.; Brebner, G. J., Universal schemes for parallel computation, (Proc. 13th Annual ACM Sympos. on Theory of Comput.. Proc. 13th Annual ACM Sympos. on Theory of Comput., Milwaukee, Wisconsin (1981)), 263-277
[30] Vishkin, U., A Parallel-Design Space Distributed-Implementation Space (PDDI) General Purpose Computer (1983), IBM T. J. Watson Research Center: IBM T. J. Watson Research Center Yorktown Heights, N.Y, RC-9541
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.