Cluster-based application mapping method for Network-on-Chip

Network-on-Chip (NoC) is a newly introduced paradigm to overcome the communication problems of System-on-Chip architectures. Mapping applications onto mesh-based NoC architecture is an NP-hard problem and several heuristic methods have been presented to solve it so far. Scalability is the main problem of the heuristic methods and it is very difficult to conclude that one heuristic is better than the others. Integer Linear Programming (ILP) based methods determine the optimum mappings. However, they take very long execution times. In this paper, we propose a clustering based relaxation for ILP formulations. Our experiments conducted on several multimedia benchmarks and custom graphs show that the proposed method obtains optimal or close to optimal results within tolerable time limits.

► We present Integer Linear Programming (ILP) formulation for task mapping on NoCs. ► We observe that ILP based mapping takes very long CPU times. ► We introduce cluster based method that decomposes the application into clusters. ► The proposed method applies ILP for each cluster. ► Cluster based application mapping reduces the CPU time significantly.