TY - JOUR
T1 - A fast MILP solver for high‑level synthesis based on heuristic model reduction and enhanced branch and bound algorithm
AU - Mirhoseini, Mina
AU - Fazlali, Mahmood
AU - Fallah, Mohammad K
AU - Lee, Jeong‑A
N1 - © 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023/3/6
Y1 - 2023/3/6
N2 - Modeling high-level synthesis (HLS) as mixed integer linear programming (MILP) affords 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 MILP models and customize them for application in domain-specific 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 first 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 by considering the properties of the original HLS problem. In this regard, we propose two heuristic techniques that enable the B&B algorithm to prove that some branches are not promising and should be pruned. Moreover, we have developed a best-first strategy by suggesting a new priority key calculation scheme to improve tree traversal in the B&B algorithm. Besides, the sifting method has been employed as the LP relaxation method to achieve fast processing of large models. Our proposed approach was evaluated using a set of MILP models derived from the synthesis of Mediabench data flow graphs. The experimental results indicate that our approach outperforms modern MILP solvers in terms of speed and the scale of the MILP models which can solve. According to the test results on the large MILP models, we solved models with 7254 integer and binary variables in less than 13 minutes.
AB - Modeling high-level synthesis (HLS) as mixed integer linear programming (MILP) affords 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 MILP models and customize them for application in domain-specific 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 first 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 by considering the properties of the original HLS problem. In this regard, we propose two heuristic techniques that enable the B&B algorithm to prove that some branches are not promising and should be pruned. Moreover, we have developed a best-first strategy by suggesting a new priority key calculation scheme to improve tree traversal in the B&B algorithm. Besides, the sifting method has been employed as the LP relaxation method to achieve fast processing of large models. Our proposed approach was evaluated using a set of MILP models derived from the synthesis of Mediabench data flow graphs. The experimental results indicate that our approach outperforms modern MILP solvers in terms of speed and the scale of the MILP models which can solve. According to the test results on the large MILP models, we solved models with 7254 integer and binary variables in less than 13 minutes.
KW - High-level synthesis
KW - Hybrid branch and bound
KW - Mixed integer linear programming
UR - http://www.scopus.com/inward/record.url?scp=85149405094&partnerID=8YFLogxK
U2 - 10.1007/s11227-023-05109-2
DO - 10.1007/s11227-023-05109-2
M3 - Article
AN - SCOPUS:85149405094
SP - 1
EP - 32
JO - Journal of Supercomputing
JF - Journal of Supercomputing
SN - 0920-8542
ER -