论文部分内容阅读
随着电子设计进入超深亚微米(UDSM)时代，据国际半导体技术蓝图(ITRS)预测，在未来几年内单个片上晶体管数目将会增长到数十亿，工作频率可以提高到10GHz。集成度的增加使传统的芯片通信结构显现出很多不足，如信号传递的完整性差、连线延时长、串扰严重等。片上网络(Network on Chip，NoC)是一种采用包交换的通信方式的互连结构，有望取代传统的片上总线，成为新一代片上通信结构。
本文的主要任务是针对定制片上网络互连问题，构建直角最小Steiner树(RSMT, Rectilinear Steiner Minimal Tree)，以映射到NoC的互连来确保各IP之间的连接长度最小，进而使NoC的全局连线延时可能缩短。以互连拓扑结构分类，NoC可以分为规整的片上网络(regularNoC)和定制的片上网络(custom NoC)，其中定制的片上网络因具有更高的片上资源利用率而成为近期的研究热点。直角最小Steiner树是一个NP完全问题，它通过增加新节点使各待连节点的连通长度最短。因此，我们将定制的片上网络互连问题抽象为一个有障碍物的曼哈顿平面(Manhattan plane)上的Steiner树生成问题，以使片上连线长度最短并进一步优化网络性能。
本文的主要工作与成果包括：
(1)调研了NoC结构在学术界及业界的研究发展状况，归纳了NoC互连算法的抽象描述形式；深入分析了Steiner树问题和已有的图论及VLSI布局布线中的RSMT算法，包括迷宫算法、线搜索算法、蚁群优化算法、模拟退火算法和构造-修正算法等，并编程实现了这些算法，分析了它们的优点与不足。
(2)根据定制的片上网络互连问题的抽象模型，利用从最小生成树(MST)到RSMT的转换关系，提出了一种新的基于构造-修正的RSMT算法。该算法首次把Steiner树算法应用到定制片上网络的互连中，能够使得片上全局连线长度最小。由于是在一定的搜索空间即Escape图上调用Dijkstra算法以生成直角Steiner树，而非针对全体网格空间，所以算法执行时间较短，可以得到较低的时间复杂度，即O((n+2m)2)。在实现方面，采用C++语言编程实现了本文提出的算法及一些其他的RSMT算法，以便于完成实验结果的对比和测试。结果表明，与已有的RSMT算法相比，在不增加复杂度的前提下，本文提出的算法可以使NoC的全局连线长度缩短约4.1％。
(3)针对算法运行结果，提出了一种新的消除连线冗余的优化方法。该方法考虑到在算法执行步骤中会有U型连线冗余出现，通过“边生成边优化”的方法调整Steiner点的位置，以去除U型结构中重复的平行连线，进一步使连线长度减少约1.5％。