Scheduling with Integer Time Budgeting for Low-Power Optimization
Wei Jiang, Zhiru Zhang, Miodrag Potkonjak, Jason Cong · 2008
In this paper we present a mathematical programming formu-lation of the integer time budgeting problem for directed acyclic graphs. In particular, we formally prove that our constraint ma-trix has a special property that enables a polynomial-time algo-rithm to solve the problem optimally with a guaranteed integral solution. Our theory can be directly applied to solving a scheduling prob-lem in behavioral synthesis with the objective of minimizing the system power consumption. Given a set of scheduling constraints and a collection of convex power-delay tradeoff curves for each type of operation, our scheduler can intelligently schedule the op-erations to appropriate clock cycles and simultaneously select the module implementations that lead to low-power solutions. Ex-periments demonstrate that our proposed technique can produce near-optimal results (within 6 % of the optimum by the ILP for-mulation), with 40x+ speedup. I.