论文部分内容阅读
聚类与划分算法分别采用自底向上和自顶向下的方法对电路进行层次化操作和分割操作，有效提高了EDA工具处理大规模电路的效率。本文着重研究了可进行特殊结构识别与处理的层次化聚类算法、时序驱动的多级划分算法、早期性能评估中所需的线长预测算法及其在性能驱动FPGA聚类算法中的应用。
在层次化聚类算法方面，本文提出一种基于超图模型的高通用性层次化聚类算法。首先对网表中最基本的迭代、总线、扇入和串联结构进行自动识别，然后再按不同的组合方式进行多级聚类，最终建立起了网表的层次化结构。实验结果表明，该算法既可以得到较准确的层次信息又能保证较高的运算速度。
本文在时序驱动的多级划分算法方面，分别提出了基于通路和基于线网的两种算法。对于基于通路的算法，首先通过聚类保护降低关键通路被分割的几率，减小后续操作对最小割目标的影响。然后使用划分保护控制通路被分割的次数，将关键通路时延限定在指定时钟周期之内。与现有算法相比，该算法不仅可以完全控制关键通路时延，而且只需对最底层网表进行一次时序分析。在基于线网的多级划分算法中，本文通过提出线网通路群的概念，使用全局性较强且计算代价较小的线网通路群关键度表示线网的时延权重，并以此指导划分操作。实验表明，在对线长目标影响较小的情况下，该方法不仅可以有效提高电路的时序性能，而且能够有效减小时序振荡现象。
在性能驱动的聚类、划分算法中，需要使用预测线长值估算目标函数中的性能相关量，为此本文提出一种基于拓扑结构的线长预测模型。在拓扑级和物理级的定义下，首先依据布局区域假设，使用虚拟的物理级作为中间变量表示线长的预估值；然后根据拓扑级中结点的布放格式假设，使用已知的拓扑级代替物理级作为线长预估值的表示量。实验表明，该方法在预测精度和运算时间上全面优于MC和重回聚方法。另外，本文将线长预测方法应用到了性能驱动的FPGA聚类算法中。在聚类阶段，分别将关键通路上的线网和功耗值较大的线网用局部布线资源实现，以便提高时序性能和减小动态功耗。