随着我国的信息产业的发展,设计开发具有自主知识产权的集成电路成为一项基础性的工作。FPGA在电子设计领域占有越来越重要的作用,但我国目前采用的FPGA芯片大多从国外进口。设计开发具有自主知识产权的FPGA芯片具有及其重要的意义。基于LUT结构的FPGA的工艺映射算法在EDA开发环境的设计中占有很重要的位置。本论文正是针对上述的问题,以基于LUT结构的FPGA的工艺映射算法为研究对象,全面介绍了逻辑分解、深度优化算法、面积优化算法等,对诸多方面作了创新性和探索性研究。主要内容为:1.详细介绍了工艺映射算法及其技术。详细介绍了布尔函数的逻辑分解的一般分解原理,详细介绍了面积优化、深度优化、面积和深度同时优化以及功率优化的基本模型和技术。2.给出了面积优化算法的NP完全性更为简洁的证明。原有的证明是利用3-SAT问题规约到面积优化问题,但是要分别对K≥5、K=4和K=3的情况分别讨论,证明过程比较复杂。本论文利用最小顶点覆盖问题规约到面积优化问题,只需讨论K≥3一种情况,证明过程很简略。3.将现代组合优化算法模拟退火算法应用于面积优化算法中,取得了较好的效果。本论文利用点可见方法对映射方案进行编码,利用局部的点反转技术进行降温过程中的平衡处理,获得时间复杂度较小的情况下比较好的映射效果。4.自主实现了FlowMap算法,利用布尔网络的特点,采用新的标号法求得网络的最大流。本论文利用标号法寻求起始点到终点的通路的方法,来求得布尔网络的最大流,使得图的变换减少,时间复杂度也随之减少。5.将遗传算法应用于深度和面积同时优化的算法中,取得了较好的效果。在本论文中,深度和面积优化的平衡,在计算适应度时用加权因子予以反映。利用遗传算法,深度和面积优化可以在一个阶段中同时考虑,实验结果表明效果较好。6.研究了深度优化算法的并行性,提出了深度优化的并行算法。节点标号的计算是具有局部性的,因此如果节点没有前驱后继关系,标号计算是相互不影响的。所以,可以利用这一特性进行节点标号的并行计算。映射阶段也具有类似的特性,也可用并行的算法进行计算。