Extending Kernighan–Lin partitioning heuristic for application mapping onto Network-on-Chip

This paper extends the basic Kernighan–Lin graph bi-partitioning algorithm for partitioning core graphs of applications to be designed using Network-on-Chip (NoC) concept. Mapping techniques have been developed for three different types of NoC topologies – Mesh, Mesh-of-Tree (MoT), and Butterfly-Fat-Tree (BFT). Suitable post-processing schemes have been developed to improve upon the basic solution produced by the partitioning algorithm. Significant improvement in both static and dynamic performances could be observed, compared to many existing approaches reported in the literature.