Plenary Lecture

Efficient Parallel Prefix Algorithms on the Multicomputer and Circuit Models

Professor Yen-Chun Lin
Department of Computer Science and Information Engineering
National Taiwan University of Science and Technology
Taipei, Taiwan

Abstract: Prefix computation has been extensively studied for its wide application in fields such as biological sequence comparison, cryptography, design of silicon compilers, job scheduling, image processing, loop parallelization, polynomial evaluation, processor allocation, and sorting. Because of its importance and usefulness, it has been proposed as a primitive operation. In fact, prefix computation is a built-in operation for Message-Passing Interface parallel programming. Many parallel prefix algorithms for various parallel computing models have been proposed. In this lecture, we consider computation-efficient parallel prefix algorithms for message-passing multicomputers and fast prefix algorithms on the combinational circuit model. Precisely, families of new computation-efficient parallel prefix algorithms are first introduced. Fast parallel prefix circuits, including waist-size optimal ones and depth-size optimal ones, are then presented. Properties and merits of these parallel prefix algorithms are also described.

Brief Biography of the Speaker:
Yen-Chun Lin received his BS degree in electrical engineering from National Taiwan University in 1977, MS degree in computer engineering from National Chiao Tung University in 1983, and PhD degree in electrical engineering from National Taiwan University in 1988. Since 1988 he has been on the faculty at National Taiwan University of Science and Technology. Dr. Lin has been a full professor since February 1993, in Department of Electronic Engineering before August 2001 and then in Department of Computer Science and Information Engineering. He served as Program Chair of the 2001 International Conference on Parallel and Distributed Computing, Applications, and Technologies and as Guest Editor of The Journal of Supercomputing, March 2003. Dr. Lin received Honorable Mention of Annual Best Paper Award of Journal of Information Science and Engineering in 2001. He was a Visiting Scientist at the IBM Almaden Research Center, San Jose, California, from 1993 to 1994. His research interests include parallel computing and Web-based systems. Dr. Lin is a member of the ACM and the IEEE Computer Society.