改进的FPGA延迟优化算法：LUT驱动的FlowMap标记策略

本文主要探讨了一种基于查找表（Look-up Table, LUT）的FPGA面向延迟优化的工艺映射算法，即FlowMap算法。该算法由徐国培、段振华和范全润在西安电子科技大学计算技术与理论研究所提出，旨在解决FPGA设计中的延迟最优化问题。FPGA因其灵活性和设计效率而在电路设计中备受欢迎，而工艺映射作为FPGA设计的关键步骤，其性能直接影响到设计的结果。 FlowMap算法的核心在于对网络中的节点进行标记，它将节点标记问题转化为最小高度K可行割集问题，进一步转化为带权重的网络最大流问题。通过网络最大流最小割算法，可以在多项式时间内找到最优解。然而，原算法在标记节点时仅考虑局部最优，忽略了网络中可能存在的非唯一最小高度K可行割集，这可能导致工艺映射过程中其他环节，如覆盖问题，受到影响，从而影响整体优化效果。 针对这个问题，本文作者深入研究了原算法的节点标记过程，并提出了一个改进的标记方法。这个改进的方法旨在通过更全面的考量，找到更为合适的选择，从而提高工艺映射的整体性能。作者以MCNC的标准测试电路为例，实验证明了新方法相较于原算法在延迟优化上具有更好的效果。 FPGA的工艺映射问题涉及三个关键部分：可配置逻辑块（CLB）、内部连线网（IN）和输入输出模块（IO）。在实际应用中，工艺映射不仅要考虑到设计的逻辑功能实现，还要关注硬件资源的分配和信号传输的延迟，以达到设计性能的最佳平衡。本文的研究成果对于提升FPGA设计工具的效率和精度具有重要意义，对于FPGA领域的工程师和研究人员来说，理解和掌握这种面向延迟优化的工艺映射算法，对于提高设计质量和缩短设计周期具有实际价值。