Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

¡@

Journal of Information Science and Engineering, Vol.19 No.1, pp.75-83 (January 2003)


Optimal Parallel Prefix on the Postal Model*

Yen-Chun Lin and Ching-Sung Yeh+
 Department of Computer Science and Information Engineering
+Department of Electronic Engineering
National Taiwan University of Science and Technology
*Worldwide Semiconductor Corporation
Taipei, 106 Taiwan
E-mail: yclin@computer.org

This paper explores the prefix operation on a message-passing fully connected multicomputer with multiport postal communication. We present an exact communication lower bound for the prefix operation on the model. Two efficient parallel prefix algorithms are also presented; they are optimal in terms of the number of communication steps. For an input of size n, one of the algorithms using n processors is also time-optimal; the other algorithm using p < n processors can be cost-optimal and can achieve linear speedup.

Keywords: exact communication lower bound, message-passing multicomputer, parallel algorithms, postal model, prefix operation

Full Text (¥þ¤åÀÉ) Retrieve PDF document (200301_05.pdf)

Received December 19, 2000; revised April 11 & October 24, 2001; accepted November 13, 2001.
Communicated by Chu-Sing Yang.
* A preliminary version of the paper was presented at the 1999 National Computer Symposium, Taipei, Dec. 1999.