Load balanced sub-tree decomposition algorithm for solving Mixed Integer Linear Programming models in behavioral synthesis

Mixed Integer Linear Programming (MILP) is utilized in behavioral synthesis as a mathematical model to design efficient hardware. However, solving large MILP models poses significant computational challenges due to their NP-hard nature. Paralleling can tackle this challenge by amortizing the execution time, yet unbalanced loads can hinder its effectiveness. In this paper, we address the load balance issue of parallel Branch and Bound (B&B) algorithms, particularly sub-tree parallelism, which exhibit efficiency in solving MILP models derived from behavioral synthesis. The proposed algorithm strategically partitions the original problem into sub-problems by selecting decision variables that appear in a higher number of constraints to prioritize load balance and enhance solver performance. We evaluate the effectiveness of our method using MILP models derived from Mediabench data flow graphs of various sizes. The experimental results indicate that the proposed algorithm achieves speedups ranging from approximately 1 to 13 times, highlighting its efficacy in improving the scalability and efficiency of MILP solving for behavioral synthesis.