An analytically derived vectorized model for application graph mapping in interconnection networks

[Home ]		[ فارسی ]

Main Menu

Home

About

Research

People

Facilities

Sientific Nwes & Events

Contact Us

Useful links

Photo Album

Research Lab.

Search in website

IJEEE

An analytically derived vectorized model for application graph mapping in interconnection networks

| Post date: 2023/12/18 |

An analytically derived vectorized model for application graph mapping in interconnection networks

School of Electrical Engineering
Iran University of Science and Technology
Tehran, Iran

Hadi Shahriar Shahhoseini
School of Electrical Engineering
Iran University of Science and Technology
Tehran, Iran

PDF │ Abstract │ Keywords │ References │ Cite This

Abstract:
Application graph mapping is one of the hardest and time-consuming problems in interconnection networks. Although many approaches are targeting the quality of the solution, one fast and accurate algorithm for solving this kind of problem is needed strongly. In this paper, a vectorized model has been introduced to provide an accurate estimation of the mapping solution with a minimum time overhead. This model is based on a theoretical analysis of the distance matrix and average distance in interconnection networks. Simplifying the search space of possible solutions by a novel matrix-to-vector transformation technique made the proposed model more appropriate and applicable to large-scale applications. The final mapping configuration is computed by comparing vectors to obtain linear time-complexity and make a scalable approach for all sizes of input applications. Moreover, the output of the proposed model can be given to the evolutionary algorithms as the initial solution to save several optimization iterations. We performed extensive experiments to evaluate the execution time overhead and quality of solutions for solving mapping problem. Results show that the proposed vectorized model could save the searching time of evolutionary algorithms up to 70%.

Keywords: High-performance computing; Quadratic assignment; Graph mapping; Matrix analysis

References:
[1] M. Abdel-Basset, G. Manogaran, H. Rashad, and A.N. Zaied, "A comprehensive review of quadratic assignment problem: variants, hybrids and applications," Journal of Ambient Intell Humaniz Comput, vol. 20, pp. 1–24, 2018.
[2] K. Bhavani and S. Jena, "Exchanged folded crossed cube: a new interconnection network for parallel computation," Inf Process Lett, vol. 137, pp. 40–46, 2018.
[3] P.N. Bibilo, "The use of models of incompletely specified Boolean functions in logical circuit synthesis based on VHDL descriptions," Autom Control Comput Sci, vol. 47, no. 3, pp. 122–131, 2013.
[4] E. Cela, "The quadratic assignment problem: theory and algorithms," Springer Science & Business Media, Boston, 2013.
[5] S. Cheng, W. Zhong, K.E. Isaacs, and K. Mueller K, "Visualizing the topology and data traffic of multi-dimensional torus interconnect networks," IEEE Access 6:57191–57204
[6] G. Chmaj and H. Selvaraj, "Interconnection Networks Efficiency in System-on-Chip Distributed Computing System: Concentrated Mesh and Fat Tree," In: 2017 International Conference on Systems Engineering (ICSEng), pp. 277–286, 2017.
[7] R. Collier, C. Fobel, L. Richards, and G. Grewal, "A formal and empirical analysis of recombination for genetic algorithm-based approaches to the FPGA placement problem," In: 2012 Canadian Conference on Electrical and Computer Engineering (CCECE), pp. 1–6, 2012.
[8] H. Daryanavard, M. Eshghi, and A. Jahanian, "A fast placement algorithm for embedded just-in-time reconfigurable extensible processing platform," Journal of Supercomput, vol. 71, no. 1, pp. 121–143, 2015.
[9] C.S. Edwards, "A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem," Combinatorial Optimization II 1980, pp. 35–52, 1980.
[10] J. Fang, T. Yu, and Z. Wei, "Improved ant colony algorithm based on task scale in network on chip (NoC) mapping," Electronics, vol. 9, no. 1, p. 6, 2020.
[11] K. Gaffour, M.K. Benhaoua, S. Dey, and A.K. Singh, "Dynamic clustering approach for run-time applications mapping on NoC-based multi/many-core systems," In: 2020 International Conference on Embedded & Distributed Systems (EDiS), pp. 15–20, 2020.
[12] F. Galea, S. Carpov, and L. Zaourar, "Multi-start simulated annealing for partially-reconfigurable FPGA floorplanning," In: 2018 International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 1335–1338, 2018.
[13] A. Jain, R. Dwivedi, A. Kumar, and S. Sharma, "Scalable design and synthesis of 3D mesh network on chip," In: Proceeding of International Conference on Intelligent Communication, Control and Devices, pp. 661–666, 2017.
[14] G.N. Khan and M.O. Haran, "Application Specific Reconfigurable SoC Interconnection Network Architecture," In: International Conference on Architecture of Computing Systems, pp. 322–333, 2019.
[15] S. Khan, S. Anjum, U.A. Gulzari, M.K. Afzal, T. Umer, and F. Ishmanov, "An efficient algorithm for mapping real time embedded applications on NoC architecture," IEEE Access 6, pp. 16324–16335, 2018.
[16] S. Khan S, S. Anjum, U.A. Gulzari, T. Umer, and B.S. Kim, "Bandwidth-constrained multi-objective segmented brute-force algorithm for efficient mapping of embedded applications on NoC architecture," IEEE Access 6, pp. 11242–11254, 2017.
[17] T.C. Koopmans and M. Beckmann, "Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society 1, pp. 53–76, 1957.
[18] Y. Li, Y. Yan, W. Li, and M. Liu, "The research of interconnection network on coarse-grained reconfigurable Cipher Logic Array," In: 2017 Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), pp. 1046–1051, 2017.
[19] J. Liu, X. Huang, D. Jiang, and Y. Luo, "An Energy-aware Spiking Neural Network Hardware Mapping based on Particle Swarm Optimization and Genetic Algorithm," In: 2020 International Conference on Hardware/Software Codesign and System Synthesis (CODES+ ISSS), pp. 11–13, 2020.
[20] E.M. Loiola, N.M. de Abreu, P.O. Boaventura-Netto, P. Hahn, and T. Querido, "A survey for the quadratic assignment problem," Eur J Oper Res 176(2):657–690, 2007.
[21] T. Maqsood, S. Ali, S.U. Malik, and S.A. Madani, "Dynamic task mapping for network-on-chip based systems," Journal of System Architecture, vol. 61, no. 7, pp. 293–306, 2015.
[22] A. McKendall and C. Li, "A tabu search heuristic for a generalized quadratic assignment problem," Journal of Ind Prod Eng., vol. 34, no. 3, pp. 221–231, 2017.
[23] S.M. Mohtavipour and H.S. Shahhoseini, "A large-scale application mapping in reconfigurable hardware using deep graph convolutional network," In: 2020 International Conference on Computer and Knowledge Engineering (ICCKE), pp. 382–387, 2020.
[24] S.M. Mohtavipour and H.S. Shahhoseini, "A link-elimination partitioning approach for application graph mapping in reconfigurable computing systems," Journal of Supercomput., vol. 76, no. 1, pp. 726–754, 2020b.
[25] S.M. Mohtavipour and H.S. Shahhoseini, "A low-cost distributed mapping for large-scale applications of reconfigurable computing systems," In: 2020 International Computer Conference, Computer Society of Iran (CSICC), pp. 1–6, 2020.
[26] Y. Nalci, P. Kullu, S. Tosun, and O. Ozturk, "ILP formulation and heuristic method for energy-aware application mapping on 3D-NoCs," Journal of Supercomput., vol. 77, no. 3, pp. 2667–2680, 2021.
[27] A. Punhani, P. Kumar, and N. Nitin, "Three-dimensional topology based on modified diagonal mesh interconnection network," Journal of Telecommun Electron Comput Eng 9(3–6), pp. 1–6, 2017.
[28] S. Sahni S and T. Gonzalez, "P-complete approximation problems," Journal of ACM, vol. 23, no. 3, pp. 555–565, 1976.
[29] P.K. Sahu, K. Manna, N. Shah, and S. Chattopadhyay, "Extending Kernighan-Lin partitioning heuristic for application mapping onto Network-on-Chip," Journal of Syst. Architect., vol. 60, no. 7, pp. 562–578, 2014.
[30] C. Steiger, H. Walder, and M. Platzner, "Operating systems for reconfigurable embedded platforms: Online scheduling of real-time tasks," IEEE Trans Comput., vol. 53, no. 11, pp. 1393–1407, 2004.
[31] M. Tozaki and Y. Li, "Topological properties and routing algorithm for the static k-ary n-tree interconnection network," In: 2017 International Symposium on Computing and Networking (CANDAR), pp. 318–322, 2017.
[32] R. Trobec, R. Vasiljević, M. Tomašević, V. Milutinović, R. Beivide, and M. Valero, "Interconnection networks in petascale computer systems: a survey," ACM Comput. Surv., vol. 49, no. 3, pp. 1–24, 2016.
[33] Y. Xia, "Gilmore-Lawler bound of quadratic assignment problem," Front Math China, vol. 3, no. 1, pp. 109–118, 2008.
[34] P. Zhang, Y. Gao, J. Fierson, and Y. Deng, "Eigenanalysis-based task mapping on parallel computers with cellular networks," Math Comput., vo. 1, pp. 1727–1756, 2014.

Cite this paper as:
S.M. Mohtavipour and H.S. Shahhoseini, 2023. An analytically derived vectorized model for application graph mapping in interconnection networks. Journal of Ambient Intelligence and Humanized Computing, 14(7), pp.8899-8911.

View: 101 Time(s) | Print: 24 Time(s) | Email: 0 Time(s) | 0 Comment(s)

کلیه حقوق مادی و معنوی این سایت متعلق به پژوهشکده الکترونیک می باشد . نقل هرگونه مطلب با ذکر منبع بلامانع می باشد .