Heuristic algorithm for task mapping problem in a hierarchical wireless network-on-chip architecture

被引:4
|
作者
Sacanamboy, Maribell [1 ]
机构
[1] Pontificia Univ Javeriana Cali, Dept Elect & Ciencias Comp, St 118,118-250,Canas Gordas,123,Valle, Cali, Colombia
来源
CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS | 2024年 / 27卷 / 01期
关键词
Wireless network-on-chip; Task mapping; Heuristic optimization; Entropy;
D O I
10.1007/s10586-022-03919-2
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Given the complexity and wide range of applications being developed for the Internet of Things (IoT) requiring an efficient mapping of application tasks in hardware resources, especially embedded systems, it is necessary to address the problem of resource optimization, taking into account constraints for energy consumption, latency, and bandwidth, among others. This paper proposes a population based multi-objective heuristic algorithm to solve the task mapping for an application into a hierarchical hardware architecture known as Wireless Network on Chip using a mathematical modeling, as well as Artificial Intelligence algorithms, that combine the strategies of neural networks and genetic algorithms. A Population Based Incremental Learning (PBIL) algorithm is used in this research to solve the task mapping problem oriented to IoT applications, allowing heterogeneous systems to be involved with different bandwidths, latencies and technologies. The optimization goals addressed in this paper are bandwidth, speedup, power consumption and communication cost. The PBIL algorithm was tested on synthetic applications with heavy workload, where performance is measured taking into account the combination of low power consumption and maximum speedup and bandwidth. Other tests carried out with the PBIL algorithm were aimed to reduce the cost of communication in task mapping for real applications such as Multi-Window Display (MWD) and MPEG4 decoder. The results obtained in both synthetic and real applications showed an improvement when Escort entropy was used compared to Renyi and Shannon. In the case of real applications, when using a 2D Mesh topology, an improvement of 15.25% for MWD and 40.32% for MPEG-4 was observed when compared to the ISFL algorithm. Also, when the Mesh-Star topology was used, better results were obtained compared to ISFL (48.74% MWD and 62.06% MPEG-4).
引用
收藏
页码:159 / 175
页数:17
相关论文
共 50 条
  • [21] HDA: Hierarchical and dependency-aware task mapping for network-on-chip based embedded systems
    Huang, Chun-Hsian
    JOURNAL OF SYSTEMS ARCHITECTURE, 2020, 108
  • [22] A-WiNoC: Adaptive Wireless Network-on-Chip Architecture for Chip Multiprocessors
    DiTomaso, Dominic
    Kodi, Avinash
    Matolak, David
    Kaya, Savas
    Laha, Soumyasanta
    Rayess, William
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (12) : 3289 - 3302
  • [23] Spiral: A heuristic mapping algorithm for network on chip
    Mehran, Armin
    Saeidi, Samira
    Khademzadeh, Ahmad
    Afzali-Kusha, Ali
    IEICE ELECTRONICS EXPRESS, 2007, 4 (15): : 478 - 484
  • [24] Crinkle: A heuristic mapping algorithm for network on chip
    Saeidi, Samira
    Khademzadeh, Ahmad
    Vardi, Fatemeh
    IEICE ELECTRONICS EXPRESS, 2009, 6 (24): : 1737 - 1744
  • [25] CGMAP: a new approach to Network-on-Chip mapping problem
    Moein-darbari, Fahime
    Khademzade, Ahmad
    Gharooni-fard, Golnar
    IEICE ELECTRONICS EXPRESS, 2009, 6 (01): : 27 - 34
  • [26] Low-latency Mapping Algorithm for Network-on-Chip
    Cao, Qinping
    Qin, Huabiao
    Chen, Wu
    Yi, Sijun
    2017 INTERNATIONAL CONFERENCE ON COMPUTER SYSTEMS, ELECTRONICS AND CONTROL (ICCSEC), 2017, : 1203 - 1206
  • [27] An improved tabu search algorithm for network-on-chip mapping
    School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China
    不详
    不详
    Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao, 2008, 2 (155-160):
  • [28] A Constructive Heuristic for Application Mapping onto Mesh Based Network-on-Chip
    Sahu, Pradip Kumar
    Manna, Kanchan
    Shah, Tapan
    Chattopadhyay, Santanu
    JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, 2015, 24 (08)
  • [29] Dynamic Task Mapping with Congestion Speculation for Reconfigurable Network-on-Chip
    Chao, Hung-Lin
    Tung, Sheng-Ya
    Hsiung, Pao-Ann
    ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS, 2016, 10 (01)
  • [30] On an Overlaid Hybrid Wire/Wireless Interconnection Architecture for Network-on-Chip
    Wang, Ling
    Guo, Zhihai
    Lv, Peng
    Jiang, Yingtao
    INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS, 2014, 5 (04) : 168 - 174