Albert G. Greenberg
Boris D. Lubachevsky
Abstract
The problem of computing the maximum of n inputs on an asynchronous parallel computer is considered. In general, the inputs may arrive staggered in time, the number of processors available to the maximization algorithm may vary during its execution, and the number of inputs, n, may be initially unknown. Two simple, efficient algorithms to compute the maximum are presented. Each algorithm may be invoked asynchronously, as new inputs and processors arrive. Performance measures that account for the response times of the invocations are introduced, and the algorithms are analyzed under these measures.
- 1 BENDER, E.A. Central and local limit theorems applied to asymptotic enumeration. J. Comb. Theory 15 (1973), 91-111.Google Scholar
- 2 FRIEZE, A., AND RUDOLPH, L. A parallel algorithm for all pairs shortest paths in a random graph. In Proceedings of the 22nd Annual Allerton Conference on Communication, Control, and Computation (Monticello, Ill., Oct. 1984). University of Illinois, Urbana-Champaign, pp. 663-670.Google Scholar
- 3 GOODMAN, J. R. Cache memory optimization to reduce processor/memory traffic. J. VLS{ Comput. Syst. 2, i (1987), 61-86. Google Scholar
- 4 GOTTLIEB, A., GRISHMAN, R., KRUSKAL, C. P., MCAULIFFE, K. P., RUDOLPH, L., AND S~IR, M. The NYU ultracomputer--Designing an MIMD shared memory parallel machine. IEEE Trans. Comput. C-32, 2 (Feb. 1983).Google Scholar
- 5 GOTTLIEB, A., AND KRUSKAL, C. P. Coordinating parallel processors: A partial unification. ACM SIGARCH, Comput. Architecture News (Oct. 1981), 16-24. Google Scholar
- 6 GOTTLIEB, A., LUBACHEVSKY, B. D., AND RUDOLPH, L. Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. ACM Trans. Program. Lang. Syst. 5, 2 (April 1983), 164-189. Google Scholar
- 7 HOLT, R. C., GRAHAM, G. S., LAZOWSKA, E. D., AND SCOTT, M. A. Structured Concurrent Programming with Operating Systems Applications. Addison-Wesley, Reading, Mass., 1978.Google Scholar
- 8 KALOS, M. Private communication, 1980.Google Scholar
- 9 LEVITAN, S. P., AND FOSTER, C.F. Finding an extremum in a network. In Proceedings of the 9th International Symposium on Computer Architecture (Austin, Tex., April 1982). IEEE, New York, 1982, pp. 321-325. Also in ACM SIGARCH Comput. Architecture News 10, 3. Google Scholar
- 10 LUBACHEVSKY, B.D. An approach to automating the verification of compact parallel coordination programs I. Acta Inf. 21 (1984), 125-169.Google Scholar
- 11 LUBACHEVSKY, B.D. Verification of several parallel coordination programs based on descriptions of their reachability sets. Ultracomputer Note 33, Courant Institute, New York Univ., New York, July 1981.Google Scholar
- 12 LUBACHEVSKY, B. D., AND GREENBERG, A.G. Simple, efficient asynchronous parallel prefix algorithms. In Proceedings of the 16th International Conference on Parallel Processing (1987), pp. 66-69.Google Scholar
- 13 MEGIODO, N. Parallel algorithms for finding the maximum and the median almost surely in constant time. Preliminary manuscript, GSIA, Carnegie-Mellon Univ., Pittsburgh, Pa., 1982.Google Scholar
- 14 REIF, J. H., AND SPIRAKIS, P.G. Real-time synchronization of interprocess communications. ACM Trans. Program. Lang. Syst. 6, 2 (April 1984), 215-238. Google Scholar
- 15 RUDOLPH, L. Software structures for ultraparallel computing. Ph.D. thesis, Courant Institute, New York Univ., New York, Dec. 1981. Google Scholar
- 16 RUDOLPH, L., AND SEGALL, Z. Dynamic decentralized cache schemes for MIMD parallel processors. In Proceedings of the 11th International Symposium on Computer Architecture (June 1984), pp. 340-347. Also in ACM SIGARCH Comput. Architecture News 12, 3. Google Scholar
Index Terms
- Simple, efficient, asynchronous parallel algorithms for maximization
Recommendations
Highly efficient asynchronous execution of large-grained parallel programs
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer ScienceAn n-thread parallel program p is large-grained if in every parallel step the computations on each of the threads are complex procedures requiring numerous processor instructions. This practically relevant style of programs differs from PRAM programs in ...
Simple and parallel proximity algorithms for general polygonal models
CASA' 2010 Special IssueWe present simple and fast parallel proximity algorithms for rigid polygonal models. Given two polygon-soup models in space, if they overlap, our algorithm can find all the intersected primitives between them; otherwise, it reports their Euclidean ...
Reviews
David Malcolm Nicol
This paper constructs performance models for asynchronous parallel algorithms that determine the maximum value in a set. The fundamental idea behind the algorithms is that a processor compares its own value with a shared variable that holds the tentative maximum. If the processor's value is larger, the processor enters a critical section where it checks again and updates the tentative maximum if needed. The value of this paper is not in proposing such simple algorithms. Its real interest lies in two particular areas. The first follows from the paper's implicit assumption that the processor-memory switching network performs “combining.” Under this condition all processors can simultaneously read a shared variable. This paper shows how asynchronous requests can be bunched together to take advantage of this architectural feature. The second point of interest lies in the paper's performance analysis. Asynchronous algorithms are generally difficult to analyze; algorithm analysts may be able to increase their repertoire of tricks by studying the techniques developed in this paper. The generic parallel programmer will not be interested in more than the first two pages of this paper. It is an academic paper—no commercially available machine offers the architecture needed to make the proposed algorithms attractive. However, the paper offers interesting insights into a difficult performance-modeling problem; those who are interested in such analyses should look at this work.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments