An Efficient LowPower Binding Algorithm in HighLevel Synthesis.pdfVIP

An Efficient Low-Power Binding Algorithm in High-Level Synthesis Yoonseo Choi and Taewhan Kim Department of Electrical Engineering Computer Science and Advanced Information Technology Research Center Korea Advanced Institute of Science and Technology, KOREA Abstract – We propose an efficient binding algorithm for power vided optimal solutions, the application is limited to a number of optimization in high-level synthesis. In prior work, it has been specific small sized low-power problems. This motivates us to shown that several binding problems for low-power can be for- develop a new technique which makes use of the property of ef- mulated as multi-commodity flow problems (due to an iterative ficient flow computations in a network so that it is extensively execution of data flow graph) and be solved optimally. How- applicable to practical designs while producing near-optimal re- ever, since the multi-commodity flow problem is NP-hard, the sults. application is limited to a class of small sized problems. To over- Specifically, we propose a heuristic algorithm, called BIND- come the limitation, we address the problem of how we can effec- lp, which finds a feasible binding by partially utilizing the flow tively make use of the property of efficient flow computations in computation steps and then refines it incrementally. In this pa- a network so that it is extensively applicable to practical designs per, we restrict our presentation to the problem of functional unit while producing close-to-optimal results. To this end, we propose binding for low power, and it should become evident that our al- an efficient two-step algorithm, which (1) determines a feasible gorithm