Accelerating Boolean Matching Using Bloom Filter

Chun ZHANG  Yu HU  Lingli WANG  Lei HE  Jiarong TONG  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.10   pp.1775-1781
Publication Date: 2010/10/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.1775
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
Keyword: 
FPGA,  Boolean matching,  Bloom filter,  SAT,  re-synthesis,  

Full Text: PDF>>
Buy this Article




Summary: 
Boolean matching is a fundamental problem in FPGA synthesis, but existing Boolean matchers are not scalable to complex PLBs (programmable logic blocks) and large circuits. This paper proposes a filter-based Boolean matching method, F-BM, which accelerates Boolean matching using lookup tables implemented by Bloom filters storing pre-calculated matching results. To show the effectiveness of the proposed F-BM, a post-mapping re-synthesis minimizing area which employs Boolean matching as the kernel has been implemented. Tested on a broad selection of benchmarks, the re-synthesizer using F-BM is 80X faster with 0.5% more area, compared with the one using a SAT-based Boolean matcher.