We propose an efficient binding algorithm for power optimization in behavioral synthesis. In prior work, it has been shown that several binding problems for low-power can be formulated as multi-commodity flow problems (due to an iterative execution of data flow graph) and be solved optimally. However, since the multi-commodity flow problem is NP-hard, the application is limited to a class of small sized problems. To overcome the limitation, we address the problem of how we can effectively make use of the property of efficient flow computations in a network so that it is extensively applicable to practical designs while producing close-to-optimal results. To this end, we propose an efficient two-step algorithm, which (1) it determines a feasible binding solution by partially utilizing the computation steps for finding a maximum flow of minimum cost in a network and then (2) refines it iteratively. Experiments with a set of benchmark examples show that the proposed algorithm saves the run time significantly while maintaining close-to-optimal bindings in most practical designs.
본 논문은 회로의 전력 소모를 최소화 하기 위한 behavioral synthesis level 에서의 binding 알고리즘을 다룬다.
저전력 소모를 위한 binding 알고리즘들은 multi-commodity flow 문제로 공식화될 수 있으며, 이를 풀면 optimal solution을 구할 수 있음이 알려져 있다. 그러나 multi-commodity flow 문제가 NP-hard이기 때문에, 이 방법은 작은 크기의 문제에만 적용될 수 있다는 단점이 있다.
이러한 단점을 극복하기 위해서, 본 논문에서는 실제적인 크기의 문제에도 이용할 수 있도록, flow structure를 효과적으로 이용하는 방법을 다룬다. 이를 위해 효과적인 2단계 알고리즘을 제안한다. 첫번째 단계에서는 network상에서 minimum cost의 maximum flow를 구하는 방법을 부분적으로 이용하여 feasible solution을 구한다. 두번째 단계에서는 network상에서 첫번째 단계에서 구해진 initial solution를 iterative하게 개선시킨다.
behavioral synthesis용 benchmark 프로그램을 이용한 실험결과는 제안된 알고리즘이 짧은 시간안에 optimal에 가까운 결과를 내는 것을 보여준다.
