整数规划驱动的层次FPGA布线优化算法

本文主要探讨了一种基于整数规划的层次式FPGA布线算法，针对FPGA设计中常见的布线线序处理不当导致的布通问题，提出了一种全局优化的解决方案。该算法的关键在于建立FPGA布线问题与整数规划的数学模型关联，利用层次式FPGA的结构特性，将原本复杂的布线问题转化为一个二进制整数规划问题。 在算法设计上，作者首先深入分析了层次式FPGA的内在结构，这是一种特殊的硬件架构，通过分层次的方式组织逻辑功能单元，使得逻辑资源的布局和连接更为有序。层次结构的优势在于能够降低复杂度，提高布线效率。接着，他们将FPGA布线问题转化为整数规划问题，整数规划是一种数学优化方法，特别适用于解决含有离散变量的问题，如布线中的路径选择和资源分配等。 算法的具体实施步骤包括问题建模、变量定义、目标函数设定和约束条件确定。通过将FPGA的布线网络表示为整数决策变量，以及定义合适的成本函数来衡量布线的质量（如长度、延迟等），算法能够寻找最优的布线方案。在求解过程中，层次结构的运用有助于减小搜索空间，提高求解效率。 与传统的可满足性布线算法相比，本文提出的算法展现出明显的优点。它在求解速度上更快，能处理更大的布线规模，并且在保持布线质量和效率的同时，能更好地适应层次式FPGA的特点。这不仅提高了设计效率，也降低了设计者的负担，对于大规模和高密度的FPGA设计具有重要的实际应用价值。 该研究工作由四位来自清华大学的学者共同完成，他们分别是朱利民博士研究生，边计年教授和博士生导师（研究领域包括数字系统设计自动化、系统级综合与验证），周强副教授和CCF高级会员（专注于VLSI高层次综合、布图规划和FPGA物理设计），以及蔡懿慈教授和博士生导师（半导体集成电路和ICCAD领域的专家）。他们的合作表明了跨学科研究在解决复杂FPGA布线问题上的力量。 本文的主要贡献是提供了一种有效的整数规划方法，用于提升层次式FPGA的布线性能，这对现代电子设计自动化有着重要意义。