一种高效高质量的FPGA技术映射算法

发布时间：2018-06-28 23:32

本文选题：现场可编程门阵列 + 技术映射　；参考：《西安电子科技大学》2015年硕士论文

【摘要】：技术映射的任务是将一个电路的门级网表转换成采用FPGA芯片内部LUT实现的LUT网表,它是FPGA CAD流程中的重要一环,包含逻辑优化与结构优化两个部分。逻辑优化的主要目标是对电路进行分解,使得电路能够满足FPGA芯片内部LUT k-输入的要求;结构优化的主要目标是将电路转换为LUT网络。目前,现有的逻辑优化算法运行效率并不理想,而现有的结构优化算法在电路延时、面积以及算法运行效率方面仍有提高的空间。本文针对技术映射的两个部分,分别提出了相应的改进算法。逻辑优化部分,本文以ROBDD为基础,对规模不同的电路采用不同的ROBDD表示方法:对于大规模电路,为了减少内存的开销,保证算法正常执行,选择Local ROBDD对电路进行描述,对于小规模电路,选择Global ROBDD对电路进行描述,提高逻辑优化的效率。在电路表示完成后,利用ROBDD中的域节点以及域操作对电路进行分解,使得电路能够满足FPGA内部LUT k-输入的要求。结构优化部分,本文提出了一种以延时、面积和效率为优化目标的基于迭代的启发式结构优化算法,主要包含三部分:划分产生、划分选择和LUT覆盖。划分产生通过动态规划的思想,快速为电路中的每一个节点产生所有k-可行划分,划分的选择是一个迭代的过程,它包含向前遍历和向后遍历,向前遍历根据优化目标为每一个节点选择最优划分,而向后遍历则选择合适的节点作为LUT的根节点,通过多次向前遍历向与后遍历的迭代,最终选出最优的划分集。LUT覆盖则是采用划分选择的结果,利用FPGA芯片内部的LUT实现对电路的覆盖,最终形成LUT网络。实验结果表明,本文提出的技术映射算法在电路的延时面积以及算法运行效率上都取得明显提升。
[Abstract]:The task of technology mapping is to convert the gate network table of a circuit into a LUT network table implemented by the LUT inside the FPGA chip. It is an important link in the FPGA CAD process, which includes two parts: logic optimization and structure optimization. The main goal of logic optimization is to decompose the circuit to satisfy the requirement of LUT k- input in FPGA chip, and the main goal of structure optimization is to convert the circuit to LUT network. At present, the running efficiency of the existing logic optimization algorithms is not ideal, but the existing structural optimization algorithms still have room for improvement in circuit delay, area and efficiency. In this paper, the corresponding improved algorithms are proposed for the two parts of the technology mapping. In the part of logic optimization, based on ROBDD, different ROBDD representation methods are adopted for circuits with different scales. For large scale circuits, in order to reduce the memory cost and ensure the normal execution of the algorithm, Local ROBDD is selected to describe the circuit. For small scale circuits, Global ROBDD is chosen to describe the circuits to improve the efficiency of logic optimization. After the circuit representation is completed, the domain node and domain operation in ROBDD are used to decompose the circuit, so that the circuit can meet the requirements of LUT k- input in FPGA. In the structural optimization part, an iterative heuristic structure optimization algorithm based on delay, area and efficiency is proposed, which consists of three parts: partition generation, partition selection and LUT coverage. Partition is generated by the idea of dynamic programming, and all k- feasible partition is generated for each node in the circuit quickly. The selection of partition is an iterative process, which includes forward traversal and backward traversal. Forward traversal selects the optimal partition for each node according to the optimization goal, while backward traversal selects the appropriate node as the root node of LUT. Finally, the optimal partition set. LUT coverage is chosen as the result of partition selection. The LUT in FPGA chip is used to cover the circuit, and finally the LUT network is formed. The experimental results show that the proposed technique mapping algorithm has achieved a significant improvement in both the circuit delay area and the efficiency of the algorithm.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN791

【相似文献】