Don't-Care-Based Node Minimization for Threshold Logic Networks

Threshold logic re-attracts researchers' attention recently due to the advancement of hardware realization techniques and its applications to deep learning. In the past decade, several design automation techniques for threshold logic have been proposed, such as logic synthesis and logic optimization. Although they are effective, threshold logic network (TLN) optimization based on don't cares has not been well studied. In this paper, we propose a don't-care-based node minimization scheme for TLNs. We first present a sufficient condition for don't cares to exist and a logic-implication-based method to identify the don't cares of a threshold logic gate (TLG). Then, we transform the problem of TLG minimization with don't cares to an integer linear programming problem, and present a method to compute the necessary constraints for the ILP formulation. We apply the proposed optimization scheme to two set of TLNs generated by the state-of-the-art synthesis technique. The experimental results show that, for the two sets, it achieves an average of 11% and 19% of area reduction in terms of the sum of the weights and threshold values without overhead on the TLG count and logic depth. Additionally, it completes the optimization of most TLNs within one minute.