Topological properties of OTIS bijective connection graphs

Articles in Press

Document Type : Original paper

Authors

School of Advanced Sciences, Vellore Institute of Technology, Chennai, 600 127, India

Abstract

In the ever-evolving landscape of parallel computing architectures, the demand for innovative interconnection networks is paramount. This paper introduces Optical Transpose Interconnection System (OTIS) - Bijective connection graphs, a subclass of interconnection network designed to address the challenges on scalability, efficiency, and fault tolerance. By merging the strengths of networks, namely, OTIS networks and Bijective connection graphs (BC graphs in brief), we aim to overcome the limitations inherent in individual architectures. This paper presents a comprehensive analysis of Optical Transpose Interconnection System - Bijective connection graphs. We demonstrate superiority over traditional interconnection networks, showcasing their potential to emerge as an interesting candidate for parallel computing.
Precisely, in this work, we compute few basic graph theoretical parameters, explored the embedding properties, solved the edge isoperimetric problem, and many associated properties of the proposed class of network.

Keywords

Main Subjects

References

[1] A.A. Al-Adwan, A. Sharieh, and B.A. Mahafzah, Parallel heuristic local search algorithm on OTIS hyper hexa-cell and OTIS mesh of trees optoelectronic architectures, Appl. Intell. 49 (2019), no. 2, 661–688.  https://doi.org/10.1007/s10489-018-1283-2
[2] A.A. Al-Adwan, R. Zaghloul, B.A. Mahafzah, and A. Sharieh, Parallel quicksort algorithm on OTIS hyper hexa-cell optoelectronic architecture, J. Parallel Distrib. Comput. 141 (2020), 61–73.  https://doi.org/10.1016/j.jpdc.2020.03.015
[3] J. Al-Sadi, A. Awwad, and B. AlBdaiwi, Efficient routing algorithm on OTIS-star network, Proceedings of the IASTED International Conference on Advances in Computer Science and Technology, 2004, pp. 157–162.
[4] S.L. Bezrukov, Edge isoperimetric problems on graphs, Graph theory and combinatorial biology 7 (1999), 157–197.
[5] J.M. Chang, X.R. Chen, J.S. Yang, and R.Y. Wu, Locally exchanged twisted cubes: connectivity and super connectivity, Inform. Process. Lett. 116 (2016),  no. 7, 460–466.  https://doi.org/10.1016/j.ipl.2016.03.003
[6] W. Chen, W. Xiao, and B. Parhami, An efficient construction of node disjoint paths in OTIS networks, Advanced Parallel Processing Technologies (Berlin, Heidelberg) (M. Xu, Y. Zhan, J Cao, and Y. Liu, eds.), Springer Berlin Heidelberg, 2007, pp. 180–189.
[7] E. Cheng, K. Qiu, and Z. Shen, Structural properties of generalized exchanged hypercubesgeneralized exchanged hypercube, pp. 215–232, Springer International Publishing, Cham, 2017.
[8] S.A. Choudum and V. Sunitha, Augmented cubes, Networks 40 (2002), no. 2, 71–84. https://doi.org/10.1002/net.10033
[9] P. Cull and S.M. Larson, The mobius cubes, IEEE on Trans. Comput. 44 (1995), no. 5, 647–659. https://doi.org/10.1109/12.381950
[10] K. Day and A.E. Al-Ayyoub, Topological properties of OTIS-networks, IEEE Trans. Parallel Distrib. Syst. 13 (2002), no. 4, 359–366.  https://doi.org/10.1109/71.995816
[11] K. Efe, The crossed cube architecture for parallel computation, IEEE Trans. Parallel Distrib. Syst. 3 (1992), no. 5, 513–524.  https://doi.ieeecomputersociety.org/10.1109/71.159036
[12] J. Fan and X. Jia, Edge-pancyclicity and path-embeddability of bijective connection graphs, Inf. Sci. 178 (2008), no. 2, 340–351.  https://doi.org/10.1016/j.ins.2007.08.012
[13] J.X. Fan and L.Q. He, Bc interconnection networks and their properties, Chinese  J. Comput. 26 (2003), no. 1, 84–90.
[14] M.R. Garey, D.S. Johnson, and L. Stockmeyer, Some simplified NP-complete problems, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing (New York, NY, USA), Association for Computing Machinery, 1974,
pp. 47–63.
[15] B. Greeni, R. Sundara Rajan, and P. Immanuel, Embedding augmented cube into certain trees and windmill graphs, Internat. J. Found. Comput. Sci. 35 (2023), no. 4, 409–434.  https://doi.org/10.1142/S0129054123500090
[16] L. Guo and C.W. Lee, Reliability analysis of the bijective connection networks for components, Mathematics 7 (2019), no. 6, Article ID: 546.  https://doi.org/10.3390/math7060546
[17] A. Gupta and B.K. Sarkar, Biswapped–torus network: a new efficient node-symmetrical optoelectronic network, Natl. Acad. Sci. Lett. 44 (2021), no. 1, 27–31. https://doi.org/10.1007/s40009-020-00942-y
[18] A. Gupta and B.K. Sarkar, BSN MOT: a fast and cost-efficient optoelectronic architecture, IETE Tech. Rev. 39 (2022), no. 1, 37–48.  https://doi.org/10.1080/02564602.2020.1823251
[19] L.H. Harper, Optimal assignments of numbers to vertices, J. Society Industrial  Appl. Math. 12 (1964), no. 1, 131–135. https://doi.org/10.1137/0112012
[20] M.R. Hoseinyfarahabady and H. Sarbazi-Azad, On pancyclicity properties of otis  networks, High Performance Computing and Communications (Berlin, Heidelberg) (R. Perrott, B.M. Chapman, J. Subhlok, R.F. de Mello, and L.T. Yang,
eds.), Springer Berlin Heidelberg, 2007, pp. 545–553. https://doi.org/10.1007/978-3-540-75444-2_52
[21] I.F. Hussain, S. Afridi, A.M. Qureshi, G. Ali, and U. Ali, Fault-tolerant resolvability of swapped optical transpose interconnection system, J. Math. 2022 (2022),  no. 1, Article ID: 8200046.  https://doi.org/10.1155/2022/8200046
[22] P.K. Jana and D.K. Mallick, OTIS-MOT: an efficient interconnection network  for parallel processing, J. Supercomput. 59 (2012), no. 2, 920–940.  https://doi.org/10.1007/s11227-010-0479-y
[23] X. Jiang, Q. Liu, N. Parthiban, and R.S. Rajan, A note on minimum linear  arrangement for BC graphs, Discrete Math. Algorithms Appl. 10 (2018), no. 2,  Article ID: 1850023.  https://doi.org/10.1142/S1793830918500234
[24] J.S. Kim, M.H. Kim, and H.O. Lee, Analysis and design of a half hypercube  interconnection network, Multimedia and Ubiquitous Engineering (Dordrecht)  (James J. Park, J. Kee-Yin Ng, H.Y. Jeong, and B. Waluyo, eds.), Springer Netherlands, 2013, pp. 537–543.
[25] A.V. Krishnamoorthy, P.J. Marchand, F.E. Kiamilev, and S.C. Esener, Grain-size considerations for optoelectronic multistage interconnection networks, Appl. Opt. 31 (1992), no. 26, 5480–5507.  https://doi.org/10.1364/AO.31.005480
[26] K. Li, Y. Mu, and G. Min, Exchanged crossed cube: a novel interconnection  network for parallel computation, IEEE Trans. Parallel Distrib. Syst. 24 (2012),  no. 11, 2211–2219.  https://doi.org/10.1109/TPDS.2012.330
[27] Y. Li and S. Peng, Dual-cubes:  a new interconnection network for high-performance computer clusters, 2000.
[28] P.K.K. Loh, W.J. Hsu, and Y. Pan, The exchanged hypercube, IEEE Trans. Parallel Distrib. Syst. 16 (2005), no. 9, 866–874.
https://doi.org/10.1109/TPDS.2005.113
[29] K.T. Lucas and P.K. Jana, Sorting and routing on OTIS-mesh of trees, Parallel Process. Lett. 20 (2010), no. 2, 145–154.
https://doi.org/10.1142/S0129626410000119
[30] B.A. Mahafzah, A.A. Al-Adwan, and R.I. Zaghloul, Topological properties assessment of optoelectronic architectures, Telecommun. Syst. 80 (2022), no. 4,  599–627.  https://doi.org/10.1007/s11235-022-00910-5
[31] B.A. Mahafzah, M. Alshraideh, T.M. Abu-Kabeer, E.F. Ahmad, and N.A.  Hamad, The optical chained-cubic tree interconnection network: topological structure and properties, Comput. Electr. Eng. 38 (2012), no. 2, 330–345. https://doi.org/10.1016/j.compeleceng.2011.11.023
[32] B.A. Mahafzah and B.A. Jaradat, The load balancing problem in OTIS-hypercube  interconnection networks, J. Supercomput. 46 (2008), no. 3, 276–297.  https://doi.org/10.1007/s11227-008-0191-3
[33] B.A. Mahafzah, A. Sleit, N.A. Hamad, E.F. Ahmad, and T.M. Abu-Kabeer, The  OTIS hyper hexa-cell optoelectronic architecture, Computing 94 (2012), no. 5,  411–432.  https://doi.org/10.1007/s00607-011-0177-5
[34] B.A. Mahafzah, R.Y. Tahboub, and O.Y. Tahboub, Performance evaluation of  broadcast and global combine operations in all-port wormhole-routed otis-mesh interconnection networks, Clust. Comput. 13 (2010), no. 1, 87–110.
https://doi.org/10.1007/s10586-009-0117-8
[35] G.C. Marsden, P.J. Marchand, P. Harvey, and S.C. Esener, Optical transpose  interconnection system architectures, Opt. Lett. 18 (1993), no. 13, 1083–1085.  https://doi.org/10.1364/OL.18.001083
[36] B. Parhami, The Hamiltonicity of swapped (OTIS) networks built of Hamiltonian  component networks, Inform. Process. Lett. 95 (2005), no. 4, 441–445.  https://doi.org/10.1016/j.ipl.2005.05.009
[37] S. Rajasekaran and S. Sahni, Randomized routing, selection, and sorting on the  OTIS-mesh, IEEE Trans. Parallel Distrib. Syst. 9 (1998), no. 9, 833–840.  https://doi.org/10.1109/71.722217
[38] S. Sahni and C.F. Wang, BPC permutations on the OTIS-hypercube optoelectronic  computer, Informatica 22 (1998), 263–270.
[39] J.h. Seo and H.O. Lee, Petersen-star networks modeled by optical transpose interconnection system, Int. J. Distrib. Sens. Netw. 17 (2021), no. 11, Article ID:  15501477211033115.  https://doi.org/10.1177/15501477211033115
[40] F. Shahrokhi, O. S`ykora, L.A. Sz´ekely, and I. Vrto, On bipartite drawings and the linear arrangement problem, SIAM J. Comput. 30 (2001), no. 6, 1773–1789.  https://doi.org/10.1137/S0097539797331671
[41] X. Tan, S.Z. Yu, and J.H. Park, A note about some properties of BC graphs, Inform. Process. Lett. 108 (2008), no. 6, 398–401.  https://doi.org/10.1016/j.ipl.2008.07.014
[42] A.S. Vaidya, P.S.N. Rao, and S.R. Shankar, A class of hypercube-like networks, Proceedings of 1993 5th IEEE Symposium on Parallel and Distributed Processing,  IEEE, 1993, pp. 800–803.
[43] C.F. Wang and S. Sahni, Basic operations on the OTIS-mesh optoelectronic computer, IEEE Trans. Parallel Distrib. Syst. 9 (1998), no. 12, 1226–1236.  https://doi.org/10.1109/71.737698
[44] G. Wang, C.K. Lin, J. Fan, B. Cheng, and X. Jia, A novel low cost interconnection  architecture based on the generalized hypercube, IEEE Trans. Parallel Distrib. Syst. 31 (2019), no. 3, 647–662.
[45] D.B. West, Introduction to Graph Theory, vol. 2, Prentice hall Upper Saddle  River, 2001.
[46] X. Yang, D.J. Evans, and G.M. Megson, The locally twisted cubes, Int. J. Comput. Math. 82 (2005), no. 4, 401–413.
https://doi.org/10.1080/0020716042000301752
[47] Y. Yang, M. Zhang, J. Meng, and R. Chen, The a-average degree edge-connectivity  of bijective connection networks, Comput. J. 66 (2022), no. 9, 2118–2122.  https://doi.org/10.1093/comjnl/bxac064
[48] J. Yuan, A. Liu, and X. Wang, The relationship between the g-extra connectivity  and the g-extra diagnosability of networks under the MM* model, Comput. J. 64  (2021), no. 6, 921–928.  https://doi.org/10.1093/comjnl/bxaa200
[49] F. Zane, P. Marchand, R. Paturi, and S. Esener, Scalable network architectures  using the optical transpose interconnection system (OTIS), J. Parallel Distrib.  Comput. 60 (2000), no. 5, 521–538.  https://doi.org/10.1006/jpdc.2000.1627
[50] M. Zhang, J. Meng, W. Yang, and Y. Tian, Reliability analysis of bijective connection networks in terms of the extra edge-connectivity, Inf. Sci. 279 (2014),  374–382.  https://doi.org/10.1016/j.ins.2014.03.125
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 12 May 2025

Files

Share

How to cite

Statistics