No Access

AN IMPROVED PARALLEL PREFIX ALGORITHM ON OTIS-MESH

PRASANTA K. JANA

Department of Computer Science and Engineering, Indian School of Mines, Dhanbad - 826 004, India

IEEE MEMBER.

Search for more papers by this author

and

BHABANI P. SINHA

Advanced Computing and Microelectronics Unit, Indian Statistical Institute, 203 B.T. Road, Calcutta - 700 035, India

IEEE FELLOW.

Search for more papers by this author

https://doi.org/10.1142/S0129626406002757Cited by:20 (Source: Crossref)

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 N^1/4 - 1) electronic moves and 2 OTIS moves. This was further reduced to (7 N^1/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 N^1/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].

Keywords:

References

O. Egecioglu and A. Srinivasan, Parallel Algorithms and Applications 1, 191 (1993). Crossref, Google Scholar
P. K. Janaet al., Information Processing Letters 84, 295 (2002), DOI: 10.1016/S0020-0190(02)00317-4. Crossref, Web of Science, Google Scholar
S. G. Akl , The Design and Analysis of Parallel Algorithms ( Prentice Hall , Englewood Cliffs, NJ , 1989 ) . Google Scholar
C. F. Wang and S. Sahni, IEEE Trans. on Parallel and Distributed Systems 9, 1226 (1998), DOI: 10.1109/71.737698. Crossref, Web of Science, Google Scholar
G. C. Marsdenet al., Optics Letters 18, 1083 (1993). Crossref, Web of Science, 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
F. Zaneet al., J. of Parallel and Distributed Computing 60, 521 (2000), DOI: 10.1006/jpdc.2000.1627. Crossref, Web of Science, Google Scholar
S. Rajasekaran and S. Sahni, IEEE Trans. on Parallel and Distributed Systems 9(9), 833 (1998), DOI: 10.1109/71.722217. Crossref, Web of Science, Google Scholar
C. F. Wang and S. Sahni, IEEE Trans. on Parallel and Distributed Systems 11, 97 (1998), DOI: 10.1109/71.841747. Crossref, Web of Science, Google Scholar
C. F. Wang and S. Sahni, IEEE Trans. on Computers 50, 635 (2001), DOI: 10.1109/12.936231. Crossref, Web of Science, Google Scholar
C. F. Wang and S. Sahni , 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 Scholar
C. 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 Scholar
A. 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
R. Lander and M. J. Fisher, J. ACM 27, 831 (1980). Web of Science, Google Scholar
D. A. Carlson and B. Sugla, J. Supercomputing 4, 107 (1990), DOI: 10.1007/BF00127876. Crossref, Web of Science, 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
M. Snir, J. of Algorithms 7, 185 (1986), DOI: 10.1016/0196-6774(86)90003-9. Crossref, Web of Science, Google Scholar
C. P. Krushkal, L. Rudolh and M. Snir, IEEE Transactions on Computers C 34, 965 (1985). Web of Science, Google Scholar