Lut Structure-based Fpga Technology Mapping Algorithm

As developping of imformation industry of our country, design of integrate circiut, which has our own knowledge property right, is become a groundwork task. FPGA is becoming more and more important role in the field of electronic design. But most of the FPGA chips which we needed were imported from other countries. It is important to design FPGA chips which have our own property right. And algorithms of LUT-based FPGA technology mapping are playing import roles in designing of EDA development environment.In this thesis, the algorithns of LUT-based FPGA technology mapping have been introcucted. Then novel materials and process are explored and investigated for non-reducible dielectrics.The main results are as follows:1. Algorithms in LUT-based FPGA technology mapping are introducted in detail. Principles of logic decomposition of Boolean Function are introduced in detail. Basic models and technologies, of area minimization , depth minimization, depth and area minimization and power minimization, are introduced in detail.2. A more brief proof about the NP-competeness of these algorithm is provided. A polynomial function of 3-SAT to area minimization was given in a pubilshed thesis, this could prove the area minimization is a NP-complete problem. But this must be discussed in there cases: K≥5, K=4, and K=3. In this thesis, A polynomial function of EXACT COVER to area minimization was given, and one case, K≥3, is discussed.3. A modern combination algorithm SAA (Simulated Annealing Algorithm) is applied in area minimization algorithms. In this thesis, vertex visibility and local vertex reversion are applied and lower time complexity and good effect are obtained.4. A famous depth minimization algorithm FlowMap is described and implemented. A new technology are applied in computing maximal flow of a Boolean Network. Paths from start point to end point are founded, and the max-flow of Boolean Network is got by this way, which avoid conversion of graphics, and time complexity is lowered as well.