A fast MILP solver for high‑level synthesis based on heuristic model reduction and enhanced branch and bound algorithm

Modeling high-level synthesis (HLS) as mixed integer linear programming (MILP)afords the opportunity to integrate constraints and optimization objectives of hardware design in the form of a mathematical intermediate representation. Consequently, it is possible to improve previously developed methods to solve MILPmodels and customize them for application in domain-specifc functions. However,the problem remains NP-hard, and solving large models requires methods that investigate the state space intelligently. Despite the high potential of branch and bound (B&B) algorithms to solve MILP models quickly, computing the best answer is still an open challenge. In this paper, we frst develop three model improvement techniques that reduce the size of the search space for MILP models derived from HLS.Then, we present a new B&B algorithm to tackle the computational challenge byconsidering the properties of the original HLS problem. In this regard, we proposetwo heuristic techniques that enable the B&B algorithm to prove that some branchesare not promising and should be pruned. Moreover, we have developed a best-frststrategy by suggesting a new priority key calculation scheme to improve tree traversal in the B&B algorithm. Besides, the sifting method has been employed asthe LP relaxation method to achieve fast processing of large models. Our proposedapproach was evaluated using a set of MILP models derived from the synthesis ofMediabench data fow graphs. The experimental results indicate that our approach outperforms modern MILP solvers in terms of speed and the scale of the MILPmodels which can solve. According to the test results on the large MILP models, wesolved models with 7254 integer and binary variables in less than 13 minutes.