经过改进的EDM模型，用于更精确地预测FPGA布线拥塞情况

《Pattern Recognition》：Patched-EDM for accurate FPGA routing congestion prediction

　　丁远 Nie | 刘鹏飞 | 王振浩
青岛理工大学，青岛，266520，中国

**摘要**
在FPGA（现场可编程门阵列）开发中，准确地进行早期路由拥塞预测对于加速设计流程至关重要。本文提出了一种名为Patched-EDM（阐明扩散模型的设计空间）的新方法，该方法将拥塞预测问题转化为图像生成任务。在阐明扩散模型（EDM）框架的基础上，该方法引入了一种连续补丁变换机制，显著降低了高分辨率布局图像的计算复杂性，同时增强了特征保留和训练稳定性。实验表明，Patched-EDM在多个图像相似性指标上均优于现有最先进的方法：其平均结构相似性（SSIM）、峰值信噪比（PSNR）、归一化均方根误差（NRMS）和像素精度（PIX）分别达到了89.25%、24.66%、8.90%和35.46%，相比最近的条件生成对抗网络（CGAN）模型分别提高了3.82%、7.25%、18.94%和20.65%。与原始EDM和补丁扩散模型（PDM）相比，Patched-EDM还展示了更高的预测效率。所提出的模型为早期识别拥塞热点提供了有效工具，并为将生成模型集成到电子设计自动化（EDA）工作流程中提供了实用框架。

**引言**
随着FPGA设计技术和流程的不断进步，路由拥塞已成为设计过程中的一个重要问题[1]。由于设计复杂性和电路资源有限，它可能影响性能、功耗和延迟等关键性能指标。因此，FPGA设计中的路由拥塞预测受到了更多关注。通过开发准确的预测模型，可以在早期设计阶段识别并解决潜在的路由拥塞问题，从而促进设计流程的完成并降低开发成本[2]。
近年来，机器学习在优化相关领域的成功应用使其成为新的研究热点[3]。这些方法在电子设计自动化（EDA）的分类、检测和设计空间探索方面也取得了显著成果[4]。许多基于机器学习的预测方法被引入来解决难以处理的路由拥塞问题。
Goswami等人提出了一种基于回归的机器学习模型，用于预测FPGA中的拥塞情况，旨在缓解布局和路由阶段的拥塞问题。作者提取了关键的设计特征，如逻辑密度和路由需求，并评估了包括线性回归和支持向量回归在内的各种回归算法的预测性能。实验结果表明，该模型能够有效识别FPGA设计中的拥塞热点[5]。
Al-Hyari等人开发了一种两阶段的机器学习模型用于FPGA设计优化。在第一阶段，该模型专注于FPGA布局过程中的高精度拥塞预测；在第二阶段，利用拥塞预测结果来评估可路由性。这种方法能够早期识别潜在的路由挑战，从而实现更高效的设计迭代。与传统方法相比，所提出的框架在预测性能上有所提升，为FPGA物理设计优化提供了宝贵的见解[6]。
2022年，Chen等人提出了一种名为PROS的插件工具，用于路由长度估计和可路由性优化，可以应用于商业或学术EDA工具，且运行开销可忽略不计[7]。Al-Hyari等人提出了一种基于卷积神经网络的深度学习框架，用于预测FPGA电路布局的可路由性。该模型通过分析布局生成的拥塞热图，快速准确地预测电路可路由性，预测准确率达到了97%，运行时间仅几毫秒[8]。
Wang等人开发了一种名为LHNN（格子超图神经网络）的异构图神经网络架构，用于电路设计中的拥塞预测。LHNN结合了格子图和超图的优势，以几何和拓扑方式传播拥塞信息。结果表明，它在预测准确性方面显著优于传统方法，尤其是在F1分数上[9]。
Yang等人提出了一种图神经网络，该网络整合了电路布局的拓扑和几何特征来预测路由密度和拥塞情况。通过在不同层次上分层学习电路表示，有效捕捉了全局和局部路由特征之间的复杂关系，显著提高了预测准确性[10]。Karimullah等人提出了一种水平和垂直方向的路由拥塞估计方法，并采用了以网络为中心的移动策略来解决局部拥塞问题，同时在总路由长度上仅带来了轻微的成本增加[11]。
Bai等人提出了一种高效且高性能的全局路由算法，重点关注物理设计中的拥塞控制和运行时间优化。该工作引入了一种基于R树的兼容路由区域划分算法和基于“桶效应”的3D模式路由方案，以更准确地评估拥塞情况。此外，作者还开发了一种动态规划优化的路径搜索方法来提高路由质量和性能[12]。
Li等人提出了一种基于密度模型的路由拥塞估计方法，用于指导FPGA的可路由性驱动的打包算法。该方法将FPGA划分为路由单元，并通过计算每个单元内网状物边界框的加权重叠区域来估计拥塞水平，其中权重根据网状物中的引脚数量动态调整[13]。Zheng等人提出了一种名为Lay-Net的多模态拥塞预测模型，通过结合布局和网表信息，利用多尺度特征提取和异构图神经网络的消息传递机制，有效提高了拥塞预测的准确性和性能[14]。
由于这些技术成功保持了设计的空间属性，FPGA路由拥塞预测在许多研究中被转化为图像处理任务，以提高预测准确性和可解释性。Szentimrey等人提出了一种卷积编码器和解码器，用于生成显示拥塞热点的拥塞图，从而通过卷积神经网络预测布局的可路由性[15]。
条件生成对抗网络（CGAN）是一种改进的生成对抗网络，通过引入条件约束来指导生成过程，广泛应用于图像生成任务[16]。Mirza等人将条件变量引入传统的生成对抗网络（GAN），以提高生成过程的可控性。通过联合训练生成器和判别器，CGAN可以根据输入条件生成特定的目标数据，为后续任务（如图像合成和风格转换）奠定了基础[17]。
Ruffino等人提出了一种像素级别的CGAN，用于高精度图像合成和完成。与标准CGAN不同，该方法在像素级别引入条件约束，以生成更符合局部结构细节的图像[18]。Liu等人提出了一种结合激光视觉和CGAN的焊缝跟踪系统，用于多层和多遍焊接[19]。Yang等人提出了一种改进的CGAN方法，用于SAR到光学图像的转换，使用并行特征融合生成器。实验结果表明，生成的图像在视觉效果上更优，并实现了出色的分类准确性[20]。
在文献中，CGAN作为图像生成模型在预测路由拥塞方面表现出优异的效率。Yu等人利用CGAN通过将布局后的地图与连接图堆叠成图像来准确预测路由拥塞[21]。Alawieh等人从大规模FPGA设计中提取了引脚密度、水平路由需求和垂直路由需求等特征，并将它们映射成高分辨率图像，作为CGAN的输入来预测路由拥塞[22]。
尽管CGAN在预测拥塞方面显示出潜力，但仍存在影响预测准确性的缺点。首先，CGAN的训练相对不稳定，容易发生模式崩溃，即生成器提供的样本分布有限，导致无法覆盖实际数据的多样性。模式崩溃使得CGAN无法准确捕捉与路由拥塞相关的信息，从而影响预测的全面性和准确性。其次，CGAN生成的样本仍包含随机噪声，可能会降低预测性能。
基于概率的生成去噪扩散模型相比CGAN模型表现出更好的稳定性、可控性和图像生成质量，为图像处理任务提供了一种新的方法。Ho等人于2019年提出了DDPM（去噪扩散概率模型），该模型源自非平衡热力学[23]。通过在扩散模型中引入时间步长和噪声预测，该模型在图像生成方面取得了显著成功[23]。Song等人提出了一种无限生成噪声的方法[24]，使用SDE（随机微分方程）描述整个扩散模型过程，以提高生成样本的质量。Luhman等人提出了PDM（补丁扩散模型），通过引入补丁变换显著降低了生成高分辨率图像的计算需求[25]。Ling等人提出了一种基于条件扩散模型的方法，用于短期降水预测，通过结合条件编码器和去噪网络实现端到端降水预测，在降水预测的准确性、稳定性和效率方面优于传统生成模型（如GAN）[26]。
Chen等人提出了一种基于扩散模型的多相干半监督医学图像分割方法，旨在解决医学图像分割中标签数据稀缺的问题。该文章提出了一种扩散特征自举模块，通过从预训练的扩散模型中提取多尺度特征并将这些特征自举到多相干分割网络中，优化了分割结果[27]。Lu等人通过结合扩散模型和视觉风格线索，提高了模糊或低质量人脸的恢复效果。该方法利用提示学习机制使模型能够适应性地捕捉不同人脸的视觉风格特征，从而获得更自然、质量更高的恢复结果[28]。2022年，Karras等人提出了EDM（阐明扩散模型的设计空间），以改进采样、训练和预处理，简化了当前去噪扩散模型的理论和实践[29]。
尽管CGAN在基于图像的路由拥塞预测方面取得了进展，但其内在局限性阻碍了预测准确性和可靠性的进一步提高。基于CGAN的方法虽然有效，但存在两个根本性缺点：（1）训练不稳定和模式崩溃，即生成器无法捕捉到真实拥塞模式的全部多样性；（2）对随机噪声敏感，这通常会降低生成拥塞图的像素级精度和结构保真度。
相比之下，扩散模型提供了一种更稳定和可控的生成范式。通过将生成过程视为渐进式去噪任务，它们可以避免GAN的对抗动态，从而实现更平滑的收敛和更广泛的数据覆盖。具体来说，扩散模型在保持细粒度空间细节和上下文依赖性方面表现出色——这对于准确建模复杂的路由结构（如导线交叉和引脚密集区域）至关重要。然而，直接将标准扩散模型（如EDM）应用于高分辨率布局图像可能会导致高昂的计算成本。为了解决这个问题，我们引入了连续补丁变换，将图像像素从空间维度重新组织为通道维度，显著减少了内存和计算开销，同时保持了结构连续性。这种适应使扩散过程能够专注于局部模式，而不会失去全局一致性，从而提高了效率和预测性能。
所提出的Patched-EDM结合了基于扩散的生成能力和针对FPGA拥塞预测的定制架构。它通过使用连续补丁划分而不是离散补丁划分，超越了之前的补丁扩散模型，最小化了边界伪影并更好地保持了拓扑关系。此外，我们的模型接受包含布局拥塞、网表连接性和引脚利用率的多通道输入图像，从而在逆向去噪过程中提供了更丰富的指导。
主要贡献如下：
（1）首次提出了一种扩散模型Patched EDM，将连续补丁变换引入EDM以预测FPGA设计的路由拥塞。
（2）该工作通过三个与FPGA路由拥塞密切相关的特征图合成学习图像，并将路由拥塞预测视为图像处理任务。
（3）Patched EDM模型由于特征保持和学习稳定性而表现出高预测效率，其性能优于最先进的模型CGAN以及类似的扩散模型EDM和PDM。

**本文的组织结构如下：**
第2节介绍了去噪扩散模型、图像条件扩散模型和补丁变换。第3节概述了提出的方法。第4节分析和解释了实验结果。最后，第5节提供了本文的工作总结。