Efficient parallel prefix algorithms on multiport message-passing systems

Authors
Lin, YC Yeh, CS
Citation
Yc. Lin et Cs. Yeh, Efficient parallel prefix algorithms on multiport message-passing systems, INF PROCESS, 71(2), 1999, pp. 91-95
Citations number
17
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
71
Issue
2
Year of publication
1999
Pages
91 - 95
Database
ISI
SICI code
0020-0190(19990730)71:2<91:EPPAOM>2.0.ZU;2-#
Abstract
We present the communication lower bound for the prefix problem on a multip ort message-passing fully connected multicomputer. Two efficient parallel p refix algorithms are also presented. Both are optimal in the number of comm unication steps. One of them is also time-optimal; the other is cost-optima l when n = Omega(p log p), where n is the input size and p < n is the numbe r of processors used. (C) 1999 published by Elsevier Science B.V. All right s reserved.