Estimation of lower and upper bounds on the power consumption from scheduled data flow graphs

In this paper, we present an approach for the calculation of lower and uppe r bounds on the power consumption of data path resources like functional un its, registers, I/O ports, and busses from scheduled data flow graphs execu ting a specified input data stream. The low power allocation and binding pr oblem is formulated, First, it is shown that this problem without constrain ing the number of resources can be relaxed to the bipartite weighted matchi ng problem which is solvable in O(n)(3). n is the number of arithmetic oper ations, variables, I/O-access or bus-access operations which have to be bou nd to data path resources, In a second step we demonstrate that the relaxat ion can be efficiently extended by including Lagrange multipliers in the pr oblem formulation to handle a resource constraint, The estimated bounds tak e into account the effects of resource sharing. The technique can be used, for example, to prune the design space in high-level synthesis for low powe r before the allocation and binding of the resources. The application of th e technique on benchmarks with real application input data shows the tightn ess of the bounds.