AN IMPROVED PARALLEL PREFIX ALGORITHM ON OTIS-MESH
Abstract
Wang and Sahni [4] reported two parallel algorithms for N-point prefix computation on an N-processor OTIS-Mesh optoelectronic computer. The overall time complexity for both SIMS and MIMD models of their first algorithm was shown to be (8 N1/4 - 1) electronic moves and 2 OTIS moves. This was further reduced to (7 N1/4 - 1) electronic moves and 2 OTIS moves in their second algorithm. We present here an improved parallel algorithm for N-point prefix computation on an N-processor OTIS-Mesh, which needs (5.5 N1/4 + 3) electronic moves and 2 OTIS moves. Our algorithm is based on the general theme of parallel prefix algorithm proposed in [4] but following the data distribution and local prefix computation similar to that of [1].
References
- Parallel Algorithms and Applications 1, 191 (1993). Crossref, Google Scholar
- Information Processing Letters 84, 295 (2002), DOI: 10.1016/S0020-0190(02)00317-4. Crossref, ISI, Google Scholar
-
S. G. Akl , The Design and Analysis of Parallel Algorithms ( Prentice Hall , Englewood Cliffs, NJ , 1989 ) . Google Scholar - IEEE Trans. on Parallel and Distributed Systems 9, 1226 (1998), DOI: 10.1109/71.737698. Crossref, ISI, Google Scholar
- Optics Letters 18, 1083 (1993). Crossref, ISI, Google Scholar
S. Sahni and C. F. Wang , BPC permutations on the OTIS-Mesh optoelectronic computer, Proc. 4th Intl. Conference on Massively Parallel Processing Using Optical Interconnections (1997) pp. 130–135. Google Scholar- J. of Parallel and Distributed Computing 60, 521 (2000), DOI: 10.1006/jpdc.2000.1627. Crossref, ISI, Google Scholar
- IEEE Trans. on Parallel and Distributed Systems 9(9), 833 (1998), DOI: 10.1109/71.722217. Crossref, ISI, Google Scholar
- IEEE Trans. on Parallel and Distributed Systems 11, 97 (1998), DOI: 10.1109/71.841747. Crossref, ISI, Google Scholar
- IEEE Trans. on Computers 50, 635 (2001), DOI: 10.1109/12.936231. Crossref, ISI, Google Scholar
- , Parallel Computation Using Optical Interconnections , eds.
K. Li , Y. Pan and S. Q. Zhang ( Kluwer Academic , 1998 ) . Google Scholar A. Osterloh , Sorting on the OTIS-Mesh, Proc. 14th Int. Parallel and Distributed Processing Symposium (2000) pp. 269–274. Google ScholarC. P. Krushkal , T. Madege and L. Rudolph , Parallel prefix on fully connected direct connection machines, Proc. Int. Conf on Parallel Processing (1986) pp. 278–284. Google Scholar-
S. Lakshmivarahan and S. K. Dhall , Parallel computing using the prefix problem ( Oxford University Press , 1994 ) . Crossref, Google Scholar Y. C. Lin and C. M. Lin , Efficient parallel prefix algorithms on fully connected message passing computers, Proc. of Third Int. Conference on High Performance Computing (1996) pp. 19–22. Google ScholarA. Nicolan and H. Hwang , Optimal schedule for parallel prefix computation with bounded resources, Proc. Third ACM SIGPLAN Sym. on Principles and Practice Parallel Programming (1991) pp. 1–10. Google Scholar- J. ACM 27, 831 (1980). ISI, Google Scholar
- J. Supercomputing 4, 107 (1990), DOI: 10.1007/BF00127876. Crossref, ISI, Google Scholar
F. E. Fich , New bounds for parallel prefix circuits, Proc. Fifteenth Sym. on the Theory of Computing (1993) pp. 100–109. Google Scholar- J. of Algorithms 7, 185 (1986), DOI: 10.1016/0196-6774(86)90003-9. Crossref, ISI, Google Scholar
- IEEE Transactions on Computers C 34, 965 (1985). ISI, Google Scholar


