Fast Filter-Based Boolean Matchers

摘要

Boolean matching is one of the fundamental and time-consuming procedures in field-programmable gate array (FPGA) synthesis. The SAT-based Boolean matchers (BMs) are not scalable while other Boolean matchers based on complicated Boolean logic operation algorithms are not flexible for complex PLBs. Recently, a scalable Boolean matcher (F-BM) based on the Bloom filter has been proposed for both scalability and flexibility. However, it requires large amount of memory space which can be a bottleneck for traditional personal computers. To tackle that problem, this letter proposes a novel Boolean matcher with much less memory requirement. Compared with F-BM, the proposed Boolean matcher has achieved an average of 5% better result with 2000x smaller storage and only 1.6x more runtime when applying to the same application. The significant reduction of storage requirements makes the proposed Boolean matcher able to handle more complicated PLB structures with larger input sizes.