| Since the first commercially viable Field Programmable Gate Array (FPGA) chip appearing in 1980s, due to the short development cycle and low non-recurring engineer-ing cost, FPGAs have been holding a tight market share in applications such as design prototyping and circuit system implementation with low or middle production scale. Entering the 21st century, the semiconductor industry has encountered new problems. Firstly as the manufacturing cost keeps increasing as technology scales down, the devel-opment cost for application specific integrated circuit keeps going higher. Secondly, to keep power consumption under acceptable ranges, integrated circuits have turned into multi-core architecture. Among various solutions, FPGAs have the natural benefits of low development cost and highly parallel processing architecture. Therefore, FPGAs have drawn more and more attention from the market, and have entered new application domains such as communication, network processing and high performance computing.Boolean matching is one of the key sub problems in FPGA design automation flow. It solves the problem of whether a specific Programmable Logic Block (PLB) structure is capable of implementing the given Boolean function, and has been widely used in ap-plications such as technology mapping, logic re-synthesis and architecture evaluation. To flexibly implement more logic functions with minimal area cost, PLBs have evolved from simple and homogeneous architectures to complex and heterogeneous architec-tures. Realistically, a good Boolean matcher targeting complex PLB structures should have a balance among flexibility, scalability, speed and space overhead. However, ex-isting Boolean matching methods do not satisfy these requirements. Among different approaches, the Boolean satisfiability (SAT) based matching method offers best flexibil-ity, but its high computational complexity limits its application to large PLB structures. In this thesis, standing on the SAT-based Boolean matching method, we propose two fast and still flexible Boolean matching methods.Based on the observation of huge difference in runtime for implementable and non-implementable Boolean functions in SAT-based Boolean matching process, we pro- pose a fast way to prune the majority of non-implementable functions with table lookup where pre-calculated matching results are kept. Our main contributions are:(1) Taking advantage of the similarities existing in different circuits, we propose a training method to extract datas more efficiently. (2) To make the matching lookup table fitting into main memory of nowadays desktop computers, we propose to use Bloom Filter as the building data structure. (3) We further propose two pruning strategies, and leave users with the flexibility to make matching speed and quality tradeoff. According to experi-ment results, the proposed method is 80 times faster along with only 0.5% area overhead than the SAT-based method, when incorporated into a logic re-synthesis application.Software as a Service (SaaS) is a unique model for software development in the up-coming cloud computing era, which has tremendous impacts on the information technol-ogy industry. In the second part of this thesis, we take Boolean matching as a concrete example to analyze the new opportunities and challenges that SaaS brings to electronic design automation field. More specifically, the major contributions are:(1) We propose an SaaS-based solution and architecture for the Boolean matching problem, and perform detail evaluations on issues such as security, cost and performance. (2) Based on the new requirements for cloud storage, we propose to use key/value database instead the popular relational database to build matching library, which is used to completely avoid SAT solving. (3) We explore the optimizations on network transportation, server and client side configuration. Compared to the SAT-based matching method, the proposed method achieves a 863 times speedup when applied to a logic re-synthesis application. |
PDF Full Text Request