GOMIL: Global Optimization of Multiplier by Integer Linear Programming
Weihua Xiao1,a, Weikang Qian1,2,3,b and Weiqiang Liu4
1University of Michigan-Shanghai Jiao Tong University Joint Institute, Shanghai Jiao Tong University, Shanghai, China
a019370910014@sjtu.edu.cn
2MoE Key Laboratory of Artificial Intelligence, Shanghai Jiao Tong University, Shanghai, China
3State Key Laboratory of ASIC & System, Fudan University, Shanghai, China
bqianwk@sjtu.edu.cn
4College of Electronic and Information Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing, China
liuweiqiang@nuaa.edu.cn
ABSTRACT
Multiplier is an important arithmetic circuit. Stateof- the-art designs consist of a partial product generator (PPG), a compressor tree (CT), and a carry propagation adder (CPA), with the last two components dominating the area and delay. Existing representative works optimize the CT and the CPA separately, adding a rigid boundary between these two components. In this paper, we break the boundary by proposing GOMIL, a global optimization for multiplier by integer linear programming. Two ILP sub-problems are first formulated to optimize the CT and the prefix structure in the CPA, respectively. Then, they are unified to provide a global optimization to the multiplier. The proposed method is applicable to not only multipliers with the AND gatebased PPG, but also those with Booth encoding-based PPG. The experimental results showed that the multipliers optimized by GOMIL can reduce the power-delay product by up to 71%, compared to the state-of-the-art multipliers developed in industry. The code of GOMIL is made open-source.
Keywords: Multiplier, Compressor Tree, Prefix Tree, Integer Linear Programming, Optimization.
