
تعداد نشریات | 5 |
تعداد شمارهها | 116 |
تعداد مقالات | 1,347 |
تعداد مشاهده مقاله | 1,352,373 |
تعداد دریافت فایل اصل مقاله | 1,293,418 |
Topological properties of OTIS bijective connection graphs | ||
Communications in Combinatorics and Optimization | ||
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 22 اردیبهشت 1404 اصل مقاله (577.99 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2025.29342.1950 | ||
نویسندگان | ||
Paul Immanuel؛ Berin Greeni* | ||
School of Advanced Sciences, Vellore Institute of Technology, Chennai, 600 127, India | ||
چکیده | ||
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. | ||
کلیدواژهها | ||
Optical transpose interconnection system؛ Bijective connection graph؛ Hamiltonicity؛ graph theoretical properties؛ edge isoperimetric problem | ||
مراجع | ||
[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 | ||
آمار تعداد مشاهده مقاله: 36 تعداد دریافت فایل اصل مقاله: 13 |