Energy minimization using a greedy randomized heuristic for the voltage assignment problem in NoC

Scaling down the voltage levels of the processing elements (PEs) in a Network-on-Chip (NoC) can significantly reduce the computation energy consumption with an overhead of the level shifters between two adjacent PEs operating at two different voltage levels. The objective of the voltage assignment problem in the NoC domain is to assign a voltage level to each PE within its allowable voltage range such that the overall energy consumption, due to the processing of the PEs and the level shifters, is minimized subject to the task deadline constraints. In this paper, we formulate the voltage assignment problem as a Quadratic Programming (QP) and reduce it to an Integer Linear Program (ILP). A greedy randomized heuristic is then proposed for solving the voltage assignment problem. Experimental results based on the E3S benchmark suite show the quality of our proposed heuristic as for all the benchmark applications it finds solutions close to the optimal ones in negligible amount of time. The effectiveness of the approach of using multiple voltage levels for the PEs in energy minimization is also reflected from the experimental results.