A two-step genetic algorithm for mapping task graphs to a network on chip architecture

Network on Chip (NoC) is a new paradigm for designing core based System on Chip which supports high degree of reusability and is scalable. In this paper we describe an efficient two-step genetic algorithm that has been used to build a tool for mapping an application, described by a parameterized task graph, on to a NoC architecture with a two dimensional mesh of switches as a communication backbone. The computational resources in NoC consist of a set of heterogeneous IP cores. Our algorithm finds a mapping of the vertices of the task graph to available cores so that the overall execution time of the task graph is minimized. We have developed a NoC architecture specific communication delay model to estimate the execution time. Our algorithm is able to handle large task graphs and provide near optimal mapping in a few minutes on a PC platform. Our tool also provides facilities for specifying NoC architecture, generation and viewing synthetic task graphs and viewing the progress of the genetic algorithm as it converges to a solution.