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

Mina Mirhoseini, Mahmood Fazlali, Mohammad K Fallah, Jeong‑A Lee

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)12042-12073
Number of pages32
JournalJournal of Supercomputing
Early online date6 Mar 2023
Publication statusPublished - 30 Jul 2023


  • High-level synthesis
  • Hybrid branch and bound
  • Mixed integer linear programming


Dive into the research topics of 'A fast MILP solver for high‑level synthesis based on heuristic model reduction and enhanced branch and bound algorithm'. Together they form a unique fingerprint.

Cite this