An optimized hybrid algorithm in term of energy and performance for mapping real time workloads on 2d based on-chip networks
An optimized hybrid algorithm in term of energy and performance for mapping real time workloads on 2d based on-chip networks
复制标题
DOI：
10.1007/s10489-018-1246-7
复制
发表时间：
2018-07
影响因子：
5.3
通讯作者：
Sarzamin Khan;Sheraz Anjum;Usman Ali Gulzari;Farruh Ishmanov;M. Palesi;M. Afzal
中科院分区：
文献类型：
--
作者：
Sarzamin Khan;Sheraz Anjum;Usman Ali Gulzari;Farruh Ishmanov;M. Palesi;M. Afzal
本文提出了一种优化的、基于搜索的近优映射启发式算法，称为ONMAP，用于映射基于2D片上互连网络平台的实时嵌入式应用负载。ONMAP使用了一种著名的快速最近邻启发式算法NMAP，并使用了模块化精确优化方法。该混合算法最小化了片上处理器间的通信能耗，优化了互连网络的性能参数。该算法继承了NMAP算法基于构造性搜索的启发式性质，以及用于将嵌入式应用映射到目标通信体系结构上的精确优化的性质。为了验证算法的效率和有效性，我们在相似的仿真环境和交通条件下，将该算法与NMAP算法和随机映射算法进行了比较。对VOPD、PIP、MPEG4、MWD、MMS和WiFi-80211arx等典型实际应用的映射结果表明，ONMAP算法在片上网络设计的大部分性能参数上都比竞争对手更高效。与NMAP算法和随机算法相比，该算法的能耗分别提高了20%和26%。同样，与NMAP和随机映射算法相比，成本分别优化了10%和60%。
In this paper, we propose an optimized, search based near-optimal mapping heuristic, named as ONMAP for mapping real time embedded application workloads on 2D based on-chip interconnection network platforms. ONMAP exploits NMAP, a well-known and fast nearest neighbor heuristic algorithm by using the modular exact optimization method. The proposed hybrid algorithm minimizes the on-chip inter-processor communication energy consumption and optimizes the interconnection network performance parameters. The algorithm inherits the constructive search based heuristic nature of the NMAP algorithm, as well as the property of exact optimization for mapping embedded applications on the target communication architecture. To verify the efficiency and effectiveness of the algorithm, we have compared the proposed algorithm with NMAP and random mapping algorithm under similar simulation environments and traffic conditions. The mapping results of the exemplary real world applications such as VOPD, PIP, MPEG4, MWD, MMS and WiFi-80211arx indicate that ONMAP algorithm is more efficient than its competitors for most of the performance parameters of the on-chip network designs. The algorithm successfully optimized the energy consumption, up to 20 % and 26% in comparison to NMAP and random algorithms, respectively. Similarly, the cost is optimized up to 10% and 60% as compared to NMAP and random mapping algorithms, respectively.