Lower bounds on the switching activity in scheduled data flow graphs with resource constraints

This paper addresses the problem of estimating lower bounds on the switching activity in scheduled data flow graphs with a fixed number of allocated resources prior to binding. The estimated bound takes into account the effects of resource sharing. It is shown that by introducing Lagrangian multipliers and relaxinf the low power binding problem to the Assignment Problem, which can be solved in O(n^3), a tight and fast computable bound is achievable. Experimental results show the quality of the bound. In most cases, deviations smaller than 5% from the optimal binding were observed. The proposed technique can be applied in branch and bound high-level synthesis algorithms for efficiently pruning design space