Lower-Bound Estimation for Multi-Bitwidth Scheduling

Abstract--In high-level synthesis, accurate lower-bound estimation is helpful to explore the search space efficiently and to evaluate the quality of heuristic algorithms. For the lower-bound estimation of the scheduling problems, previous works mainly focus on the number of resources with uniform bitwidth. In this paper, we study the problem of lower-bound estimation on bitwidth summation of functional units for multi-bitwidth scheduling, where data-paths are composed of operations with various bitwidth. An integer linear programming (ILP) formulation and a polynomial time algorithm are presented. Experimental results indicate that the proposed algorithm produces good estimation, only 2% lower than the optimal results, which are obtained from ILP. I