TY - JOUR
T1 - Simple, Efficient, Asynchronous Parallel Algorithms for Maximization
AU - Greenberg, Albert G.
AU - Lubachevsky, Boris D.
AU - Odlyzko, Andrew M.
PY - 1988/4/1
Y1 - 1988/4/1
N2 - 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.
AB - 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.
KW - Asynchronous algorithms
KW - maximization
KW - response times
UR - http://www.scopus.com/inward/record.url?scp=0023999968&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0023999968&partnerID=8YFLogxK
U2 - 10.1145/42190.42278
DO - 10.1145/42190.42278
M3 - Article
AN - SCOPUS:0023999968
SN - 0164-0925
VL - 10
SP - 313
EP - 337
JO - ACM Transactions on Programming Languages and Systems (TOPLAS)
JF - ACM Transactions on Programming Languages and Systems (TOPLAS)
IS - 2
ER -