TIPO: A heuristic algorithm for delay constrained power optimization

In this paper, we present TIPO, a heuristic algorithm for timing constrained power optimization. The algorithm utilizes Dynamic Programming-like (DP_like) search method with consistency iteration and a fast gradient-based multiplier selection method that provides an effective set of Lagrange multipliers. Compared to the previous subgradient method provided by DP_like approach, TIPO is considerably faster and does not have the inefficiencies due to difficulties to determine initial vector of multipliers and the step size for updating multipliers. We compared the two algorithms on ISCAS85 benchmarks. On average TIPO is 54 times faster than the previously published algorithm and can reach tight delay constraint which cannot be reached by DP_like approach.