Advanced Techniques for NP3-Boolean Matching: Leveraging Multi-bit Ports and Reverse Engineering to Minimize Search Space

Kai-Po Hsu1, Yi-Ting Li1, Fu-Cheng Cai2, Chia-Feng Chien1, Wuqian Tang2, Ting-Yu Ku1, Yu-Chen Cheng1, Tsung-Han Lai1, Cheng-Lung Wang1, Yi-Ting Shen1, Kuan-Ling Chou1, Zi-Wei Huang1, Tao-Chun Huang1, Tzu-Li Hsu1, Yung-Chih Chen3, Shih-Chieh Chang1, Ting-Chi Wang1, TingTing Hwang1, Chun-Yao Wang1
1National Tsing Hua University, 2National Tsing Hua Univer, 3National Taiwan University of Science and Technology


Abstract

NP3 (Non-exact Projective NPNP)-Boolean matching problem has various applications, e.g., library binding, engineering change order (ECO), and hardware Trojan detection. However, existing NP3-Boolean matching algorithms have not considered multi-bit input and output ports, which are prevalent in modern IC designs. These multi-bit ports can provide additional information for the NP3-Boolean matching process. In this paper, we propose an approach to NP3-Boolean matching problem, which leverages the information of multi-bit input and output ports for accelerating the matching process. We also participated in the Problem A of the 2023 CAD Contest@ICCAD with this approach. The revised version of our program achieved higher scores than the first place team of the Contest.