Algorithmic aspects for power-efficient hardware/software partitioning

Power efficiency is one of the major considerations in the current hardware/software co-designs. This paper models hardware/software partitioning as an optimization problem with objective of minimizing power consumption under the constraints: hardware area A and execution time E. An efficient heuristic algorithm with running time O(nlog⁡n)O(nlog⁡n) is proposed for the quality approximate solutions of the problems with n   code fragments. Also, an exact algorithm based on dynamic programming is presented to produce the optimal solution in O(n⋅A⋅E). The optimal solution for small-sized problems is used to evaluate the performance of the approximate solution. The approximate solutions are compared experimentally with the optimal solutions in our empirical study. The average errors of the approximate solutions is less than 0.9%0.9% for the cases simulated in this paper.