No Access

SORTING AND ROUTING ON OTIS-MESH OF TREES

KENY T. LUCAS

Department of Information Management, Xavier Institute of Social Service, Ranchi 834001, India

Search for more papers by this author

and

PRASANTA K. JANA

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

Search for more papers by this author

https://doi.org/10.1142/S0129626410000119Cited by:6 (Source: Crossref)

Abstract

OTIS (optical transpose interconnection system) is a popular model of optoelectronic parallel computers that has gained enormous attention in the recent years. Several parallel algorithms have been published for many fundamental problems on this architecture. In this paper, first we propose a parallel algorithm for sparse enumeration sort on OTIS-Mesh of Trees (OTIS-MOT). For N (= n²) data elements, our sorting algorithm requires 4 log N electronic moves + 3 OTIS moves. We next present a shortest path routing algorithm that runs also in logarithmic time.

Keywords:

References

S. G. Akl , Parallel Sorting Algorithms ( Academic Press , Orlando, Florida , 1985 ) . Google Scholar
D. Barth, An algorithm for broadcasting in the Mesh of trees, LNCS 634 (Springer, Heidelberg, 1992) pp. 843–844. Crossref, Google Scholar
K. Batcher , Sorting networks and their applications , AFIPS Spring Joint Computing Conf. ( 1968 ) . Google Scholar
R. Cole , Parallel merge sort , 27th IEEE Symposium FOCS . Google Scholar
J. Davila and S. Rajasekaran, Intl. J. Found. Comput. Sci. 16, 105 (2005), DOI: 10.1142/S0129054105002899. Link, Web of Science, Google Scholar
K. Dayet al., IEEE Trans. Parall. Distri. Syst. 13, 359 (2002), DOI: 10.1109/71.995816. Crossref, Web of Science, Google Scholar
K. Day, J. System. Archit. 50, 697 (2004), DOI: 10.1109/71.995816. Crossref, Web of Science, Google Scholar
M. Deet al., IEEE Trans. Comput. 46, 1132 (1997), DOI: 10.1109/12.628397. Crossref, Web of Science, Google Scholar
K. Efe, IEEE Trans. Parall. Distri. Syst. 7, 1281 (1996), DOI: 10.1109/71.553283. Crossref, Web of Science, Google Scholar
E. Horowitz , S. Sahni and S. Rajasekaran , Fundamentals of Computer Algorithms ( Galgotia Publications Pvt. Ltd. , New Delhi , 2002 ) . Google Scholar
H. M. Hussain and V. K. Prasanna, J. of Parall. Distri. Comput. 20, 121 (1994). Web of Science, Google Scholar
P. K. Jana, Parallel Computing 32, 301 (2006), DOI: 10.1016/j.parco.2006.01.001. Crossref, Web of Science, Google Scholar
P. K. Jana, J. System. Archi. 50, 193 (2004), DOI: 10.1016/j.sysarc.2003.08.006. Crossref, Web of Science, Google Scholar
P. K. Jana and B. P. Sinha, Parallel Processing Letters 16, 429 (2006), DOI: 10.1142/S0129626406002757. Link, Google Scholar
F. T. Leighton, IEEE Trans. Comput. 34, 344 (1995), DOI: 10.1142/S0129626406002757. Web of Science, Google Scholar
F. T. Leighton , Introduction to Parallel Algorithms and Architectures: Array, Trees and Hypercubes ( Morgan Kaufman , San Mateo, CA , 1992 ) . Google Scholar
Y. Lee, S. Horng and T. Kao, Comput. Visio. Image Understand 68, 109 (1997), DOI: 10.1006/cviu.1997.0539. Crossref, Web of Science, Google Scholar
K. T. Lucas, D. K. Mallick and P. K. Jana, Lecture Notes in Computer Science, LNCS 4904 (Springer, Heidelberg, 2008) pp. 274–279. Google Scholar
K. T. Lucas and P. K. Jana , An efficient parallel sorting algorithm on OTIS-mesh of trees , Intl. Advance Computing Conf. (IACC'09) . Google Scholar
G. C. Marsdenet al., Optic. Letter 18, 1083 (1993), DOI: 10.1364/OL.18.001083. Crossref, Web of Science, Google Scholar
D. Nassimi and S. Sahni, J. ACM 29, 642 (1982), DOI: 10.1145/322326.322329. Crossref, Web of Science, Google Scholar
A. Osterloh , Sorting on OTIS-Mesh , Proc. of IPDPS . Google Scholar
B. Parhami, Informat. Process. Letters 19, 441 (2005). Google Scholar
B. Parhami, J. Parall. Distri. Comput. 65, 1443 (2005), DOI: 10.1016/j.jpdc.2005.05.002. Crossref, Web of Science, Google Scholar
D. K. Pradhan , Fault-Tolerant Computing: Theory and Techniques ( Englewood Cliffs , Prentice Hall , 1986 ) . Google Scholar
S. Rajasekaran and S. Sahni, IEEE Trans. Parall. Distri. Syst. 9, 833 (1998), DOI: 10.1109/71.722217. Crossref, Web of Science, Google Scholar
J. Reif and L. Valiant, J. ACM 34, 60 (1987), DOI: 10.1145/7531.7532. Crossref, Web of Science, Google Scholar
P. Salinger and P. Tvrdik, J. Parall. Distri. Comput. 62, 1272 (2002), DOI: 10.1006/jpdc.2002.1848. Crossref, Web of Science, Google Scholar
C. P. Schnorr and A. Shamir , An optimal sorting algorithm for mesh connected computers , Proc. of 18th ACM STOC . Google Scholar
B. P. Sinha and A. Mukherjee, J. Parall. Distri. Comput. 60, 891 (2000), DOI: 10.1006/jpdc.2000.1636. Crossref, Web of Science, Google Scholar
B. P. Sinha and S. Bandyopadhyay , OMULT:An Optical Interconnection System for Parallel Computing , Proc. of ICCDC . Google Scholar
C. D. Thompson and H. T. Kung, Comm. ACM 20, 263 (1977), DOI: 10.1145/359461.359481. Crossref, Web of Science, Google Scholar
C.-F. Wang and S. Sahni, IEEE Trans. Parall. Distri. Syst. 9, 1226 (1998), DOI: 10.1145/359461.359481. Crossref, Web of Science, Google Scholar
C.-F. Wang and S. Sahni, IEEE Trans. Comput. 50, 635 (2001). Crossref, Web of Science, Google Scholar
C.-F. Wang and S. Sahni, IEEE Trans. Parallel Distr. Syst. 11, 97 (2000). Crossref, Web of Science, Google Scholar
F. Zaneet al., J. Parall. Distr. Comput. 60, 521 (2000), DOI: 10.1006/jpdc.2000.1627. Crossref, Web of Science, Google Scholar
N. Deo and C. Pang, Networks 14, 275 (1984), DOI: 10.1002/net.3230140208. Crossref, Web of Science, Google Scholar
K. Efe, IEEE Trans. Parallel and distributed Systems 3, 513 (1992), DOI: 10.1109/71.159036. Crossref, Web of Science, Google Scholar
X. Yu, M. Wu and G. J. Wang, Chinese Journal of Computers 30, 615 (2007), DOI: 10.1109/71.159036. Google Scholar
Xin Yu and Tao-shen Li, On shortest path routing algorithm in crossed cube-connected ring networks, Proc. of CyberC '09 pp. 348–354. Google Scholar
Jyh-Wen Mao and Chang-Biau Yang, Journal of Networks 35, 207 (2000). Crossref, Web of Science, Google Scholar
Ngoc Chi Nguyen, Thanh Vu Dinh and Tuan Dang Anh, Improving shortest path routing in hyper-de Bruijn networks, Proc. of IFOST 2000 pp. 288–292. Google Scholar
Ming-Yang Su, Gen-Huey Chen and Dyi-Rong Duh, IEEE Transactions on Parallel and Distributed Systems 8, 367 (1997). Web of Science, Google Scholar
Xiaofan Yang, Graham M. Megson and David J. Evans, J. Parallel Distrib. Comput. 66, 1294 (2006), DOI: 10.1016/j.jpdc.2006.03.008. Crossref, Web of Science, Google Scholar
R. K. C. Chang and H. Y. Wang, J. Parallel Distributed Comput. 61, 838 (2001), DOI: 10.1006/jpdc.2001.1729. Crossref, Web of Science, Google Scholar
Tomaz Dobravec, Janez Z. erovnik and Borut Robic, J. of Systems Architecture 52, 298 (2006), DOI: 10.1016/j.sysarc.2005.12.003. Crossref, Web of Science, Google Scholar
Ke Qiu , An Efficient Disjoint Shortest Paths Routing Algorithm for the Hypercube , Proc. of 14th IEEE Intl. Conf. on Parallel and Distributed Systems . Google Scholar