Abstract | ||
---|---|---|
Boolean matching is one of the most important fundamental algorithms in FPGA synthesis and architecture evaluations. However, existing Boolean matchers for FPGAs, even with numerous improvements, are still not scalable to complex PLBs and large circuits. This paper aims to improve the efficiency of Boolean matching using lookup tables implemented by Bloom filters, which can store terabyte-lookup tables with a desktop PC. The key improvement is to efficiently prune a large set of non-implementable functions use the Bloom filter. Using the area-oriented re-synthesis as an application, the experiments on a broad selection of benchmark sets show that the re-synthesis with our improved Boolean matcher is 18X faster than the one with an optimized SAT-based Boolean matcher, while preserving the quality of the re-synthesizer. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1145/1723112.1723145 | FPGA |
Keywords | Field | DocType |
area-oriented re-synthesis,bloom filter,optimized sat-based boolean matcher,large set,architecture evaluation,fpga synthesis,improved boolean matcher,boolean matching,boolean matcher,boolean matchers,large circuit,sat,fpga,lookup table | Lookup table,Bloom filter,Boolean circuit,Computer science,Parallel computing,Field-programmable gate array,Theoretical computer science,Standard Boolean model,Electronic circuit,Circuit minimization for Boolean functions,Scalability | Conference |
Citations | PageRank | References |
1 | 0.39 | 12 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chun Zhang | 1 | 1 | 0.39 |
Yu Hu | 2 | 75 | 9.62 |
Lingli Wang | 3 | 86 | 25.42 |
Lei He | 4 | 364 | 30.35 |
Jiarong Tong | 5 | 68 | 11.74 |