Routing, merging and sorting on parallel models of computation

ABSTRACT

A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. We distinguish two classes of models, fixed connection networks and models based on a shared memory. Routing is the prototype problem for the networks. In particular, routing provides the basis for simulating the more powerful shared memory models. We show 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 a deterministic O(logn) routing or sorting algorithm for an n processor fixed connection network remains open. However, if we consider the more powerful class of shared memory models, we are -&-ldquo;almost-&-rdquo; able to achieve such an efficient sort via Valiant's parallel merging algorithm. Within a spectrum of models, we show that log log n - log log r is asymptotically optimal for rn processors to merge two sorted lists of n elements.

REFERENCES

• 1: Stephen Cook , Cynthia Dwork, Bounds on the time for parallel RAM's to compute simple functions, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.231-233, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802196]
• 2: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 3: Furst, M., J.B. Saxe, and M. Sipser, Parity, Circuits and the Polynomial Time Hierarchy, Proc. of 22nd Annual Symposium on Foundations of Computer Science, Oct. 1981, 260-270.
• 4: Zvi Galil , Wolfgang J. Paul, An efficient general purpose parallel computer, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.247-262, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802478]
• 5: Leslie M. Goldschlager, A unified approach to models of synchronous parallel machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.89-94, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804336]
• 6: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 7: Haagvist, R. and P. Hell, Parallel Sorting with Constant Time for Comparisons, SIAM J. on Computing 10:3, 1981, 465-472.
• 8: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 9: Kruskal, C., Personal Communication, 1982.
• 10: Lang, T., Interconnections between PE and MBs using the Shuffle-Exchange, IEEE Transactions on Computers, vol. C25, 1976, 496.
• 11: Lev, G., N. Pippenger and L.G. Valiant, A Fast Parallel Algorithm for Routing in Permutation Networks, IEEE Transactions on Computers, 1981.
• 12: Preparata, F.P., New Parallel-Sorting Schemes, IEEE Transactions on Computers, C27:7, 1978, 669-673.
• 13: Preparata, F.P., and J. Vuillemin, The Cube-Connected Cycles, Proceedings 20th Symposium on Foundations of Computer Science, 1979, 140-147.
• 14: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 15: Shiloach, Y., and U. Vishkin, Finding the Maximum, Merging and Sorting in a Parallel Computation Model, Department of Computer Science, Technion Israel, TR173, March 1980.
• 16: Snir, M., On Parallel Search (Extended Abstract), Preprint-Courant Institute, 1982.
• 17: Stockmeyer, L.,and Vishkin, U., Simulation of Parallel Random Access Machines by Circuits, IBM Yorktown Heights, Preprint, 1982.
• 18: Stone, H., Parallel Processing with the Perfect Shuffle, IEEE Transactions on Computers, C20:2, 1971, 153-161.
• 19: Valiant, L.G., Parallelism in Comparison Problems, SIAM J. on Computing 4, 1975, 348-355.
• 20: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]