Optimization methodology for application mapping in wireless network-on-chip

Network-on-Chip is a novel communication technology that has replaced the traditional bus-based or point-to-point communication methods between the electronic components to allow for faster and more energy-efficient communication in a system. Nevertheless, in NoC, some communicating components may be too far from each other, making the multi-hop communication between such cores inefficient in terms of high latency and energy consumption. As a solution to shorten the hop count between such components, wireless connections between tiles were introduced, leading to Wireless Network-on-Chip architectures that enable higher scalability and bandwidth along with lower communication latency and energy consumption than traditional NoC by reducing communication distance between faraway points to a single-hop wireless interconnect. However, there are still some important challenges for WiNoC design related to the application mapping, routing, and integration of wireless routers, such as the complexity of hardware or power overhead. The application mapping to multiple cores is an NP-hard problem. Although there are several successful mapping algorithms for NoCs, the literature lacks the optimal mapping techniques for hybrid WiNoCs. In this study, we present quadratic programming-based and simulated annealing-based application mapping methods for hybrid WiNoC mesh topologies. The QP-based model gives us optimal solutions with high computational complexity for smaller problem sizes, while our metaheuristic SA-based method provides optimal or near-optimal results in realistic runtimes for bigger problem sizes. Our methods take the application graph and the hybrid 2D WiNoC mesh topology, where some routers communicate through wireless links as inputs and generate the optimal application mapping with the objective to minimize the communication energy consumption of the application. Our proposed QP-based model generates the optimal solutions in faster execution times, while the proposed metaheuristic SA-based application mapping method is able to generate optimal or near-optimal solutions for most of the test cases for relatively smaller benchmark sizes with slower performance than the QP-based method. For bigger problem sizes, the QP-based method cannot finish execution in acceptable running times. We also investigated the effects of different wired-to-wireless communication cost ratios on the overall communication cost in hybrid WiNoCs.