论文部分内容阅读
近年来,非曼哈顿互连结构由于具有减小线长、增加芯片吞吐量、改善芯片性能等优点而受到学术界和工业界的极大关注。但是,目前对于非曼哈顿互连结构下的布图规划算法的研究仍然很欠缺,这将使得非曼哈顿互连结构很难完全发挥出它的优势。针对这些问题,本文主要进行了三个方面的研究工作。第一,我们提出了一种新的适用于六边形/三角形布局(HTP)问题的布图表示——扩展序列对。基于扩展序列对表示,我们提出了一种新型的、高效的HTP布局算法。实验结果显示,我们的算法在较短的时间内获得了目前最好的布局结果。此外,我们还第一次提出了一套适合在Y互连结构下使用的坐标系。第二,我们提出了一种精确的、高效的、适用于Y互连结构的线长估计模型APWL-Y。APWL-Y具有线性时间复杂度。对157万个来自工业界实际电路的线网,APWL-Y的平均误差是4.41%。APWL-Y因其高效和较好的精度而尤其适合用作HTP布图规划器/布局器中的线长估计工具。而且,我们还开发了用APWL-Y作为线长估计器的具有线长优化功能的HTP布局器。与仅仅优化面积的HTP布局器相比,我们的布局器可以在仅仅增加芯片面积9.07%的前提下,减小芯片总线长达54.3%。另外,我们研究了Y互连结构下的半周长模型,给出了高效计算半周长线长的公式。据我们所知,本文是国际上第一次提出包含线长优化的HTP布图规划/布局算法的论文。第三,我们分析了X互连结构下采用液态布线技术时的拥挤度估计问题。然后基于对走线需求的概率分析,我们第一次提出了X互连结构下考虑液态布线技术的拥挤度估计模型。为了更精确预测拥挤度,我们的模型采用了动态布线资源分配方法。实验证明,我们的拥挤度模型与X互连结构下采用液态布线技术的布线器的结果具有很好的相关性。模型的精确性和高效性使得它成为适合嵌入X互连结构下的布图规划器和布局器中的理想的拥挤度估计工具。