An optimized hybrid algorithm in term of energy and performance for mapping real time workloads on 2d based on-chip networks

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.