SORTING AND ROUTING ON OTIS-MESH OF TREES
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 (= n2) 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.
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 - Intl. J. Found. Comput. Sci. 16, 105 (2005), DOI: 10.1142/S0129054105002899. Link, ISI, Google Scholar
- IEEE Trans. Parall. Distri. Syst. 13, 359 (2002), DOI: 10.1109/71.995816. Crossref, ISI, Google Scholar
- J. System. Archit. 50, 697 (2004), DOI: 10.1109/71.995816. Crossref, ISI, Google Scholar
- IEEE Trans. Comput. 46, 1132 (1997), DOI: 10.1109/12.628397. Crossref, ISI, Google Scholar
- IEEE Trans. Parall. Distri. Syst. 7, 1281 (1996), DOI: 10.1109/71.553283. Crossref, ISI, Google Scholar
-
E. Horowitz , S. Sahni and S. Rajasekaran , Fundamentals of Computer Algorithms ( Galgotia Publications Pvt. Ltd. , New Delhi , 2002 ) . Google Scholar - J. of Parall. Distri. Comput. 20, 121 (1994). ISI, Google Scholar
- Parallel Computing 32, 301 (2006), DOI: 10.1016/j.parco.2006.01.001. Crossref, ISI, Google Scholar
- J. System. Archi. 50, 193 (2004), DOI: 10.1016/j.sysarc.2003.08.006. Crossref, ISI, Google Scholar
- Parallel Processing Letters 16, 429 (2006), DOI: 10.1142/S0129626406002757. Link, Google Scholar
- IEEE Trans. Comput. 34, 344 (1995), DOI: 10.1142/S0129626406002757. ISI, Google Scholar
-
F. T. Leighton , Introduction to Parallel Algorithms and Architectures: Array, Trees and Hypercubes ( Morgan Kaufman , San Mateo, CA , 1992 ) . Google Scholar - Comput. Visio. Image Understand 68, 109 (1997), DOI: 10.1006/cviu.1997.0539. Crossref, ISI, 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 - Optic. Letter 18, 1083 (1993), DOI: 10.1364/OL.18.001083. Crossref, ISI, Google Scholar
- J. ACM 29, 642 (1982), DOI: 10.1145/322326.322329. Crossref, ISI, Google Scholar
-
A. Osterloh , Sorting on OTIS-Mesh , Proc. of IPDPS . Google Scholar - Informat. Process. Letters 19, 441 (2005). Google Scholar
- J. Parall. Distri. Comput. 65, 1443 (2005), DOI: 10.1016/j.jpdc.2005.05.002. Crossref, ISI, Google Scholar
-
D. K. Pradhan , Fault-Tolerant Computing: Theory and Techniques ( Englewood Cliffs , Prentice Hall , 1986 ) . Google Scholar - IEEE Trans. Parall. Distri. Syst. 9, 833 (1998), DOI: 10.1109/71.722217. Crossref, ISI, Google Scholar
- J. ACM 34, 60 (1987), DOI: 10.1145/7531.7532. Crossref, ISI, Google Scholar
- J. Parall. Distri. Comput. 62, 1272 (2002), DOI: 10.1006/jpdc.2002.1848. Crossref, ISI, Google Scholar
-
C. P. Schnorr and A. Shamir , An optimal sorting algorithm for mesh connected computers , Proc. of 18th ACM STOC . Google Scholar - J. Parall. Distri. Comput. 60, 891 (2000), DOI: 10.1006/jpdc.2000.1636. Crossref, ISI, Google Scholar
-
B. P. Sinha and S. Bandyopadhyay , OMULT:An Optical Interconnection System for Parallel Computing , Proc. of ICCDC . Google Scholar - Comm. ACM 20, 263 (1977), DOI: 10.1145/359461.359481. Crossref, ISI, Google Scholar
- IEEE Trans. Parall. Distri. Syst. 9, 1226 (1998), DOI: 10.1145/359461.359481. Crossref, ISI, Google Scholar
- IEEE Trans. Comput. 50, 635 (2001). Crossref, ISI, Google Scholar
- IEEE Trans. Parallel Distr. Syst. 11, 97 (2000). Crossref, ISI, Google Scholar
- J. Parall. Distr. Comput. 60, 521 (2000), DOI: 10.1006/jpdc.2000.1627. Crossref, ISI, Google Scholar
- Networks 14, 275 (1984), DOI: 10.1002/net.3230140208. Crossref, ISI, Google Scholar
- IEEE Trans. Parallel and distributed Systems 3, 513 (1992), DOI: 10.1109/71.159036. Crossref, ISI, Google Scholar
- 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- Journal of Networks 35, 207 (2000). Crossref, ISI, 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- IEEE Transactions on Parallel and Distributed Systems 8, 367 (1997). ISI, Google Scholar
- J. Parallel Distrib. Comput. 66, 1294 (2006), DOI: 10.1016/j.jpdc.2006.03.008. Crossref, ISI, Google Scholar
- J. Parallel Distributed Comput. 61, 838 (2001), DOI: 10.1006/jpdc.2001.1729. Crossref, ISI, Google Scholar
- J. of Systems Architecture 52, 298 (2006), DOI: 10.1016/j.sysarc.2005.12.003. Crossref, ISI, 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


