Research On Optimizations Of FPGA Techonology Mapping Algorithms

Technology mapping, as a front-end step of FPGA CAD flow, is important to the followed packing, placing and routing procedures. It requires optimizing logic network firstly, then structural LUT-based mapping and finally post-optimization flows such as area resynthesis to transfer a technology independent logic network to a network consists of PLBs. This thesis focuses on the following two aspects during technology mapping and proposes novel improvements.Optimizing technology independent logic network results in obvious improvements on LUT mapping. The proposed newest method in this thesis helps reduce the LUT network delay by 45% and 37% respectively for 4-LUT and 6-LUT mapping. The core sub-problem in optimizing AIG delay is to find a better AIG structure to substitute the original AIG structure. The LMS leanrns from other algorithms by collecting AIG structures generated from them. However, the filter strategy in LMS is not good enough to build larger input library due to it occupies too much memory. Besides, memory bottleneck limits the LMS to collect more structures from other algorithms. This thesis proposes a new filter strategy to optimize library size, which achieves 2000x times library size reduction and additional 5% delay optimization.Boolean matching is one of the fundamental and time-consuming procedures in FPGA mapping. 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 with 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 paper proposes a novel Boolean matcher with much less memory requirement. Compared with F-BM, the Boolean matcher proposed in this paper has achieved an average of 5% better result with 2000x smaller storage and only 1.6x more runtime when applying to same application. The significant reduction of storage requirements makes the proposed new Boolean matcher able to handle more complicated PLB structures with larger input sizes.