Performance Analysis of Quine-McCluskey Method on CPU

Abstract

The Quine-McCluskey method is a widely used procedure to minimize Boolean functions. Although the method can be programmed on computers, it takes a long time to return the set of essential prime implicants, thus slowing the analysis and design of digital logic circuits. In this paper, we first propose three ways of data representation for prime implicants in memory, followed by our performance analysis for each representation. We then propose a multithreading scheme to find all prime implicants of a Boolean function. The scheme aims to accelerate step 1 of the method on multicore platforms. After that, we propose an algorithm for step 2 of the Quine-McCluskey method to select the minimal number of essential prime implicants. The evaluation shows that the mask-based representation achieves the highest performance when the input number is small. When the input number is more than or equal to 20, the best data representation is bitarray-based. The bitarray-based representation achieves a 5x higher performance than the ASCII-based representation when the input number equals 24 and the fill factor equals 0.002. The number of essential prime implicants can be reduced up to 45% of the total prime implicants generated in step 1 of the method for a 16-input Boolean function at a fill factor of 0.05.