基于lut结构fpga工艺映射算法研究论文

《基于lut结构fpga工艺映射算法研究论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要随着我国的信息产业的发展，设计开发具有自主知识产权的集成电路成为一项基础性的工作。FPGA在电子设计领域占有越来越重要的作用，但我国目前采用的FPGA芯片大多从国外进口。设计开发具有自主知识产权的FPGA芯片具有及其重要的意义。基于LUT结构的FPGA的工艺映射算法在EDA开发环境的设计中占有很重要的位置。本论文正是针对上述的问题，以基于LUT结构的FPGA的工艺映射算法为研究对象，全面介绍了逻辑分解、深度优化算法、面积优化算法等，对诸多方面作了创新性和探索性研究。主要内容为：1．详细介绍了工艺映射算法及其技术。详细介绍了布尔函数的逻辑分解的一般分解原理，详细介绍了面积优化、深度优

2、化、面积和深度同时优化以及功率优化的基本模型和技术。2．给出了面积优化算法的NP完全性更为简洁的证明。原有的证明是利用3-SAT问题规约到面积优化问题，但是要分别对K≥5、K=4和K=3的情况分别讨论，证明过程比较复杂。本论文利用最小顶点覆盖问题规约到面积优化问题，只需讨论K≥3一种情况，证明过程很简略。3．将现代组合优化算法模拟退火算法应用于面积优化算法中，取得了较好的效果。本论文利用点可见方法对映射方案进行编码，利用局部的点反转技术进行降温过程中的平衡处理，获得时间复杂度较小的情况下比较好的映射效果。4．自主实现了FlowMap算法，利用布尔网络的特点，采用新的标号法求得网络的最大

3、流。本论文利用标号法寻求起始点到终点的通路的方法，来求得布尔网络的最大流，使得图的变换减少，时间复杂度也随之减少。5．将遗传算法应用于深度和面积同时优化的算法中，取得了较好的效果。在本论文中，深度和面积优化的平衡，在计算适应度时用加权因子予以反映。利用遗传算法，深度和面积优化可以在一个阶段中同时考虑，实验结果表明效果较好。6．研究了深度优化算法的并行性，提出了深度优化的并行算法。节点标号的计算是具有局部性的，因此如果节点没有前驱后继关系，标号计算是相互不影响的。所以，可以利用这一特性进行节点标号的并行计算。映射阶段也具有类似的特性，也可用并行的算法进行计算。电子科技大学硕士学位论文关键

4、词：FPGA，LuT，工艺映射，优化IIABSTRACTAsdeveloppingofimformationindustryofourcountry，designofintegratecirciut，whichhasourOWnknowledgepropertyfight，isbecomeagroundworktask．FPGAisbecomingmoreandmoreimportantroleinthefieldofelectronicdesign．ButmostoftheFPGAchipswhichweneededwereimportedfromothercountries．Iti

5、simportanttodesignFPGAchipswhichhave0111"ownpropertyright．AndalgorithmsofLUT—basedFPGAtechnologymappingareplayingimportrolesindesigningofEDAdevelopmentenvironment．Inthisthesis，thealgorithnsofLUT-basedFPGAtechnologymappinghavebeenintrocucted．Thennovelmaterialsandprocessareexploredandinvestigatedf

6、ornon-redueibledielectrics．Themainresultsareasfollows：1．AlgorithmsinLUT-basedFPGAtechnologymappingareintroductedindetail．PrinciplesoflogicdecompositionofBooleanFunctionarein,educedindetail．Basicmodelsandtechnologies，ofareaminimization，depthandareaminimizationandpowermimmization,areintroducedinde

7、tail．2．AmorebriefproofabouttheNP—eompetenessofthesealgorithmisprovided．Apolynomialfunctionof3一SATtoareaminimizationWasgiveninapubilshedthesis，thiscouldprovetheareaminimizationisaNP-completeproblem．Buttllismustbediscussedinth