Publicado

2017-04-01

Genetic algorithm for task mapping in embedded systems on a hierarchical architecture based on wireless network on chip WiNoC

Algoritmo genético para asignación de tareas en sistemas embebidos en una arquitectura jerárquica inalámbrica basada en redes de circuito integrado WiNoC

DOI:

https://doi.org/10.15446/dyna.v84n201.53886

Palabras clave:

WiNoC, NoC, Wireless, Hierarchical, Genetic, Mapping (en)
WiNoC, NoC, Inalámbricas, Jerárquicas, Genético, Mapeo (es)

Descargas

Autores/as

Network on Chip (NoC) systems were originally developed to provide high performance, using the availability of several processing units, connected to a wired network inside the integrated circuit. Wireless NoC (WiNoC or WNoC) are a natural evolution of NoC systems, which integrate a hierarchical communication inside the chip for the sake of improving scalability. Task mapping in WNoC systems represents a challenging process, which often involves several optimization objectives, such as power, performance, throughput, resources usage, and network metrics. This paper describes a genetic algorithm based approach for finding optimal tasks-mapping solutions in design time, for embedded systems working over a WiNoC. The optimization objectives were: Speedup, Energy Consumption, and Bandwidth. The target network used for simulation may be viewed as a two-level hierarchical WiNoC. The first level corresponds to a set of subnets which are linked by wires and mesh-type. The second level corresponds to a star-topology of wireless links, which connect the first level subnets. Proposed algorithm exhibits a good performance in relation to the optimization objectives, concerning the target heterogeneous WiNoC.
Los sistemas de red en chip (NoC) fueron desarrollados originalmente para proporcionar un alto rendimiento, mediante la disponibilidad de varias unidades de procesamiento, conectadas a través de una red cableada dentro del circuito integrado. Wireless NoC (WiNoC o WNoC) son una evolución natural de los sistemas NoC, que integran una comunicación jerárquica dentro del chip para mejorar la escalabilidad. El mapeo de tareas en los sistemas WNoC representa un proceso desafiante, que a menudo implica varios objetivos de optimización, como potencia, rendimiento, productividad, uso de recursos y métricas de red. Este artículo describe un algoritmo genético basado en un enfoque para encontrar soluciones óptimas de asignación de tareas en tiempo de diseño, para sistemas embebidos que trabajan sobre un WiNoC. Los objetivos de optimización fueron: Aceleración, Consumo de Energía y Ancho de Banda. La red de destino utilizada para la simulación puede ser vista como un WiNoC jerárquica de dos niveles. El primer nivel corresponde a un conjunto de subredes que están conectadas por cables y son de tipo malla. El segundo nivel corresponde a una topología en estrella de enlaces inalámbricos, que conectan las subredes de primer nivel. El algoritmo propuesto muestra un buen desempeño en relación con los objetivos de optimización y la WiNoC heterogéneo simulada.

Referencias

Asanovic, K., Bodik, R., Catanzaro, B.C., Gebis, J.J., Husbands, P., Keutzer, K., Patterson, D.A., Plishker, W.L., Shalf, J., Williams, S.W., and Yelick, K.A., The landscape of parallel computing research: A view from Berkeley, University of California, Berkeley, USA, Tech. Rep. UCB/EECS-2006-183, EECS Department, 2006, 54 P.

Sangiovanni-Vicentelli, A., Quo Vadis, SLD? Reasoning about the trends and challenges of system level design, Proceedings of the IEEE, 95(3), pp. 467-506, 2007. DOI: 10.1109/JPROC.2006.890107

Sarbazi-Azad, H., Bagherzadeh, N. and Jaberipour, G., Advances in multicore systems architectures, The Journal of Supercomputing, 71(8), pp. 2783-2786, 2015. DOI: 10.1007/s11227-015-1487-8

Thiele, L., Bacivarov, I., Haid, W. and Huang, K., Mapping applications to tiled multiprocessor embedded systems, in Seventh International Conference on Application of Concurrency to System Design, Bratislava, Slovakia, 2007, pp. 29-40. DOI: 10.1109/ACSD.2007.53

Guerre, A., Ventroux, N., David, R. and Merigot, A., Hierarchical network-on-chip for embedded many-core architectures, in Fourth International Symposium on Networks-on-Chip (NOCS), (Grenoble, France), ACM/IEEE, 2010, pp. 189-196. DOI: 10.1109/NOCS.2010.28

Chen, S-J., Lan, Y-Ch., Tsai, W-Ch. and Hu, Y-H., Reconfigurable networks-on-chip. New York, USA: Springer, 2012, pp. 3-31. DOI: 10.1007/978-1-4419-9341-0

Hennessy, J.L. and Patterson, D.A., Computer organization and design: The Hardware, Software. 5nd ed. Waltham, MA, USA: Morgan Kaufmann/Elsevier, 2014, pp. 1-39.

Gustafson, J.L., Reevaluating Amdahl’s Law. Communications of the ACM, 31(5), pp. 532-533, 1988. DOI: 10.1145/42411.42415

Deb, S. and Mondal, H., Wireless network-on-chip: A new era in multi-core chip design, in 25th International Symposium on Rapid System Prototyping (RSP), New Delhi, India, IEEE, 2014, pp. 59-64. DOI: 10.1109/RSP.2014.6966893

Li, X., Survey of wireless network-on-chip systems, MSc. Thesis, University Auburn, Alabama, USA 2012, 60 P.

Dai, P., Chen, J., Zhao, Y. and Lai, Y-H., A study of a wire-wireless hybrid NoC architecture with an energy-proportional multicast scheme for energy efficiency, [Online], June of 2015, [date of reference August 25th of 2015]. Available at: http://www.researchgate.net/publication/278742599_A_study_of_a_wirewireless_hybrid_NoC_architecture_with_an_energy-proportional_multicast_scheme_for_energy_efficiency.

Neishaburi, M. and Zilic, Z., NISHA: A fault-tolerant NoC router enabling deadlock-free interconnection of subnets in hierarchical architectures, Journal of Systems Architecture, 59(7), pp.551-569, 2013. DOI: doi:10.1016/j.sysarc.2012.12.002

Das, R., Eachempati, S., Mishra, A.K., Narayanan, V. and Das, C.R., Design and evaluation of a hierarchical on-chip interconnect for next-generation CMPs, in 15th International Symposium on High Performance Computer Architecture (HPCA), Raleigh, NC, USA, IEEE, 2009, pp. 175-186. DOI: 10.1109/HPCA.2009.4798252

Manevich, R., Cidon, I. and Kolodny, A., Dynamic traffic distribution among hierarchy levels in hierarchical networks-on-chip (NoCs), in Seventh International Symposium on Networks on Chip (NoCS), Tempe, AZ, USA, IEEE/ACM, 2013, pp. 1-8. DOI: 10.1109/NoCS.2013.6558412

Carrillo, S., Harkin, J., McDaid, L.J., Pande, S., Cawley, S., McGinley, B. and Morgan, F., Hierarchical network-on-chip and traffic compression for spiking neural network implementations, in Sixth International Symposium on Networks on Chip (NoCS), Copenhagen, Denmark, IEEE/ACM, 2012, pp. 83-90. DOI: 10.1109/NOCS.2012.17

Hu, W.H., Wang, C. and Bagherzadeh, N., Design and analysis of a mesh-based wireless network-on-chip, in Proceedings of the 20th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP, Garching, Germany, 2012, pp. 483-490. DOI: 10.1109/PDP.2012.19

Rahmani, A.M., Vaddina, K., Latif, K., Liljeberg, P., Plosila, J. and Tenhunen, H., High-performance and fault-tolerant 3D NoC-Bus hybrid architecture using ARB-NET based adaptive monitoring platform, IEEE Transactions on Computers, 63(3), pp. 734-747, 2014. DOI: 10.1109/TC.2012.278

Agyeman, M.O. and Ahmadinia A., A systematic generation of optimized heterogeneous 3D Networks-on-Chip architecture, in NASA/ESA Conference on Adaptive Hardware and Systems (AHS), (Torino, Italy), IEEE, 2013, pp. 79-83.

Hammami, O., M'zah, A., Jabbar, M.H. and Houzet, D., 3D IC Implementation for MPSOC architectures: Mesh and butterfly based NoC, in 4th Asia Symposium on Quality Electronic Design (ASQED), Penang, Malaysia, IEEE, 2012, pp. 155-159.

Petracca, M., Lee, B.G., Bergman, K. and Carloni, L.P., Design exploration of optical interconnection networks for chip multiprocessors, in Symposium on High-Performance Interconnects, Stanford University, CA, USA, IEEE, 2008, pp. 31-40.

Shacham, A., Bergman, K. and Carloni, L.P., Photonic networks-on-chip for future generations of chip multiprocessors, IEEE Transactions on Computers, 57(9), 1246-1260, 2008. DOI: 10.1109/TC.2008.78

Kurian, G., Miller, J.E., Psota, J., Eastep, J., Liu, J., Michel, J., Kimerling, L.C. and Agarwal, A., Atac: A 1000-core cache-coherent processor with on-chip optical network, in Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques (PACT’10), New York, NY, USA, ACM, 2010, pp.477-488.

Wettin, P., Vidapalapat, A., Ganguly, A. and Pande, P.P., Complex network-enabled robust wireless network-on-chip architectures, ACM Journal on Emerging Technologies in Computing Systems, 9(3), pp. 1-19, 2013. DOI: 10.1145/2491676

Carloni, L.P., Pande, P. and Xie, Y., Networks-on-chip in emerging interconnect paradigms: Advantages and challenges, in Proceedings 3rd International Symposium on Networks-on-Chip, NoCS 2009, San Diego, CA, USA, ACM/IEEE, 2009, pp. 93-102.

Kumar, A. and Kapoor, H.K., Modelling and analysis of wireless communication over networks-on-chip, in 18th International Symposium on VLSI Design and Test, Coimbatore, India, IEEE, 2014, pp.1-6.

Chang, M.F., Cong, J., Kaplan, A., Naik, M., Reinman, G., Socher, E. and Tam, S.W., CMP network-on-chip overlaid with multi-band RF-interconnect, in Proceeding of the 14th International Symposium on High-Performance Computer Architecture (HPCA’08), Salt Lake City, UT, USA, IEEE, 2008, pp.191-202.

DiTomaso, D., Laha, S., Kaya, S., Matolak, D. and Kodi, A., Energy efficient modulation for a wireless network-on-chip architecture, in 10th International New Circuits and Systems Conference, NEWCAS, Montreal, Canada, IEEE, 2012, pp. 489-492.

Wang, S. and Jin, T., Wireless network-on-chip: A survey. The Journal of Engineering, [Online], 2014, [date of reference August 27th 2015]. Available at: http://digital-library.theiet.org/content/journals/10.1049/joe.2013.0209.

Rezaei, A., Safaei, F., Daneshtalab, M. and Tenhunen, H., HiWA: A hierarchical wireless network-on-chip architecture, in International Conference on High Performance Computing & Simulation (HPCS), Bologna, Italy, IEEE, 2014, pp.499-505.

Deb, S., Ganguly, A., Chang, K., Pande, P., Belzer, B. and Heo, D., Enhancing performance of network-on-chip architectures with millimeter-wave wireless interconnects, in Proceedings of the 21st International Conference on Application-specific Systems Architectures and Processors (ASAP’10), Rennes, France, IEEE, 2010, pp.73-80.

Lee, S-B., Tam, S-W., Pefkianakis, I., Lu, S., Chang, M.F., Guo, C., Reinman, G., Peng, C., Naik, M., Zhang, L. and Cong, J., A scalable micro wireless interconnect structure for cmps. In Proceedings of the 15th Annual International Conference on Mobile Computing and Networking (MobiCom’09), Beijing, China, ACM, 2009, pp. 20-25.

Ganguly, A., Chang, K., Deb, S., Pande, P.P., Belzer, B. and Teusher, C., Scalable hybrid wireless network-on-chip architectures for multicore systems, IEEE Transactions on Computers, 60(10), pp. 1485-1502, 2011. DOI: 10.1109/TC.2010.176

DiTomaso, D., Kodi, A., Matolak, D., Kaya, S., Laha, S. and Rayess, W., A-WiNoC: Adaptive wireless network-on-chip architecture for chip multiprocessors, IEEE Transactions on Parallel and Distributed Systems, PP(99), pp.1-13, 2014. DOI: 10.1109/TPDS.2014.2383384

Garey, M.R. and Johnson, D.S., Computers and intractability; A guide to the theory of NP-Completeness. New York, NY, USA: W. H. Free- man & Co, 1990, 338 P.

Sacanamboy, M., Bolaños, F. and Nieto, R., A primer for mapping techniques on NoC systems, in Proceedings of the 2014 International Conference on Embedded Systems and Applications, ESA 2014, Las Vegas, USA, 2014, pp. 70-75.

Tosun, S., Cluster-based application mapping method for Network-on-Chip, Advances in Engineering Software, 42(10), pp. 868-874, 2011. DOI: 10.1016/j.advengsoft.2011.06.005

Hamedani, P.K., Hessabi, S., Sarbazi-Azad, H. and Jerger, N.E., Exploration of temperature constraints for thermal aware mapping of 3D networks on chip, in Proceedings of the 20th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP, Garching, Germany, IEEE, 2012, pp.499-506.

Zhong, L., Sheng, J., Jing, M., Yu, Z., Zeng, X. and Zhou, D., An optimized mapping algorithm based on simulated annealing for regular NoC architecture, in 9th International Conference on ASIC (ASICON), Xiamen, China, IEEE, 2011, pp. 389-392.

Singh, A.K., Kumar, A. and Srikanthan, T., A hybrid strategy for mapping multiple throughput-constrained applications on MPSoCs, in Proceedings of the 14th International Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES), Taipei, China, IEEE, 2011, pp.175-184.

Mandelli, M., Amory, A., Ost, L. and Moraes, F.G., Multi-task dynamic mapping onto NoC-based MPSoCs, in Proceedings of the 24th Symposium on Integrated Circuits and Systems Design - SBCCI’11, New York, NY, USA, ACM, 2011, pp.191-196.

Sepúlveda, J., Strum, M., Chau, W.J. and Gogniat, G., A multi-objective approach for multi-application NoC mapping, in 2nd Latin American Symposium on Circuits and Systems, (LASCAS), Bogotá, Colombia, IEEE, 2011, pp.9-12.

Sheng, J., Zhong, L., Jing, M., Yu, Z. and Zeng, X., A method of quadratic programming for mapping on NoC architecture, in Proceedings of International 9th Conference on ASIC (ASICON), Xiamen, China, 2011, pp.200-203.

Antunes, E., Soares, M., Aguiar, A., Filho, S.J., Sartori, M., Hessel, F. and Marcon, C.A.M., Partitioning and dynamic mapping evaluation for energy consumption minimization on NoC-based MPSoC, in Proceedings 13th International Symposium on Quality Electronic Design, ISQED, Santa Clara, CA, USA, IEEE, 2012, pp.451-457.

Rezaei, A., Daneshtalab, M., Zhao, D., Safaei, F., Xiaohang, W. and Ebrahimi, M., Dynamic application mapping algorithm for wireless network-on-chip, in 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Turku, Finland, IEEE, 2015, pp.421-424.

Kaida, J., Taniguchi, I., Hieda, T. and Tomiyama, H., A static task mapping algorithm with dynamic task switching for embedded many-core SoCs, in 13th International Symposium on Communications and Information Technologies: Communication and Information Technology for New Life Style Beyond the Cloud, ISCIT, Surat Thani, Thailand, IEEE, 2013, pp.293-297.

Carle, T., Djemal, M., Potop-Butucaru, D., De Simone, R. and Zhen, Z., Static mapping of real-time applications onto massively parallel processor arrays, in 14th International Conference on Application of Concurrency to System Design (ASCD), La Marsa, Tunisia, IEEE, 2014, pp.112-121.

Khajekarimi, E. and Hashemi, M.R., Energy-aware ILP formulation for application mapping on NoC based MPSoCs, in 21st Iranian Conference on Electrical Engineering, ICEE, Mashhad, Iran, IEEE, 2013, pp.1-5.

He, O., Dong, S., Jang, W., Bian, J. and Pan, D.Z., UNISM: Unified scheduling and mapping for general networks on chip, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 20(8), pp.1496-1509, 2012. DOI: 10.1109/TVLSI.2011.2159280

Derin, O., Kabakci, D. and Fiorin, L., Online task remapping strategies for fault-tolerant Network-on-Chip multiprocessors, in Proceedings of the Fifth International Symposium, Pittsburgh, USA, ACM/IEEE, 2011, pp.129-136.

Tei, Y.Z., Marsono, M.N., Shaikh-Husin, N. and Hau, N.Y., Network partitioning and GA heuristic crossover for NoC application mapping, in Proceedings International Symposium on Circuits and Systems (ISCAS), Beijing, China, IEEE, 2013, pp.1228-1231.

Racu, A. and Indrusiak, L.S., Using genetic algorithms to map hard real-time on NoC-based systems, in Proceedings of the 7th International Workshop on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC), York, England, IEEE, 2012, pp.1-8.

Kang, S-H., Yang, H., Kim, S., Bacivarov, I., Ha, S. and Thiele, L., Static mapping of mixed-critical applications for fault-tolerant MPSoCs, in Proceedings of the 51st Annual Design Automation Conference DAC '14, New York, NY, USA, ACM/EDAC/IEEE, 2014, pp.1-6.

Bolaños, F., Mapping techniques for embedded systems design with reliability considerations, PhD. Dissertation, Universidad de Antioquia, Medellín, Colombia, 2012, 156 P.

Maqsood, T., Ali, S., Malik, S. and Madani, S.A., Dynamic task mapping for network-on-chip based systems, Journal of Systems Architecture: the EUROMICRO Journal, 61(7), pp. 293-306, 2015. DOI: 10.1016/j.sysarc.2015.06.001

Yi, J., Liu, W., Jiang, W., Qin, M., Yang, L., Liu, D., Xiao, C., Du, L. and Sha, E.H.-M., An improved thermal model for static optimization of application mapping and scheduling in multiprocessor system-on-chip, in Annual Symposium on VLSI (ISVLSI), Tampa, USA, IEEE Computer Society, 2014, pp. 547-552.

Blem, E., Menon, J. and Sankaralingam, K., Data to accompany a detailed analysis of contemporary arm and x86 architectures, [Online], 2013, [date of reference August 8th 2015]. Available at: http://www.cs.wisc.edu/vertical/isa-power-struggles.

Dimensions

PlumX

Visitas a la página del resumen del artículo

611

Descargas

Los datos de descarga aún no están disponibles.

Cómo citar

[1]
M. Sacanamboy Franco, F. Bolaños-Martinez, Álvaro Bernal-Noreña, y R. Nieto-Londoño, «Algoritmo genético para asignación de tareas en sistemas embebidos en una arquitectura jerárquica inalámbrica basada en redes de circuito integrado WiNoC», DYNA, vol. 84, n.º 201, pp. 202–209, abr. 2017, doi: 10.15446/dyna.v84n201.53886.

Licencia

Derechos de autor 2017 DYNA

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.

El autor o autores de un artículo aceptado para publicación en cualquiera de las revistas editadas por la facultad de Minas cederán la totalidad de los derechos patrimoniales a la Universidad Nacional de Colombia de manera gratuita, dentro de los cuáles se incluyen: el derecho a editar, publicar, reproducir y distribuir tanto en medios impresos como digitales, además de incluir en artículo en índices internacionales y/o bases de datos, de igual manera, se faculta a la editorial para utilizar las imágenes, tablas y/o cualquier material gráfico presentado en el artículo para el diseño de carátulas o posters de la misma revista.