Energy-efficient contention-aware application mapping and scheduling on NoC-based MPSoCs

We consider the problem of energy-efficient contention-aware application mapping and scheduling on Network-on-Chip (NoC) based multiprocessors. For an application represented by a directed acyclic graph, we present a model where voltage scaling techniques for processors can be combined with frequency tuning techniques for NoC links to save overall system energy consumption. We employ a two-step approach to solve the overall mapping and scheduling problem. First, the application mapping problem is formulated as a quadratic binary programming problem, which aims to minimize the communication energy; we apply a relaxation-based iterative rounding algorithm to solve it. With the mapping achieved, we further consider the application scheduling problem, which aims to find the optimal voltage level for each task of the application and optimal frequency level for each communication of the application to minimize the overall system energy consumption, given the application deadline. To attack the second problem, we first design an algorithm based on the earliest time first scheduling to determine the application's finish time if a voltage and frequency assignment is given; then, we develop a genetic algorithm to search the solution space for the voltage and frequency assignment that minimizes the overall system energy consumption and meets the application's deadline. Through these two steps, we produce a mapping and scheduling that meets the application's deadline, and significantly reduces the overall system energy consumption. Experiments are conducted for a number of randomly generated application graphs, as well as several real application graphs to verify the energy reduction and applicability of the proposed model and algorithms.