论文部分内容阅读
为了满足多核及众核处理器对高并发、低延迟、高可靠片上通信的需求，片上网络逐渐取代总线成为芯片内部的主流互连方案。但是由于芯片内部资源的限制、芯片特征尺寸的不断缩小、以及金属互连线工艺的限制等等，片上网络系统面临着网络性能以及可靠性等一系列问题。本文从路由算法的角度出发针对三种可能引起片上网络系统重构的问题展开研究。首先针对片上网络内突发流量造成的拥塞问题，研究流量感知的无死锁路由的动态生成和动态重构策略；其次针对路由器和通道故障造成的通信失效问题，研究离线和在线的容错路由算法；最后针对片上光网络光路重构问题，研究光控制信号的广播路由算法。本文的创新贡献主要在以下几个方面：
1．提出算盘转向模型及相应的可重构路由算法。通过分析大规模并行程序的流量特性，论证了在片上网络系统中进行路由动态重构的必要性及可能性，并提出算盘转向模型。该模型可用于解决无死锁路由的动态生成和动态重构两个技术难题。基于算盘转向模型的可重构路由算法可根据在线收集的网络流量信息实现路由自适应度的按需分配，从而为热点区域的数据包提供更多的路径分集用于缓解网络拥塞。针对可综合流量模型、splash-2、以及PARSEC基准测试集程序的仿真实验表明，相对目前不依赖虚通道的路由算法本文算法可获得最大19％的网络性能提升。
2．提出使用转向合法中间节点的多遍维序路由算法。转向合法中间节点打破了路由阶段与虚通道之间的一对一关系，可用于解决当前多阶段路由算法无法在无虚通网络内实现的关键问题。本文算法可以在不增加虚通道的前提下通过增加路由阶段的方式大幅提升路由算法的容错能力。实验结果表明，相对于当前的多阶段容错路由算法，本文算法最大可减少90%以上的不可达节点对。另外转向合法中间节点打破了虚通道之间的优先级关系，有利于虚通道之间的流量平衡。针对uniform等可综合流量模型的仿真实验表明，本文算法在不增加路由器面积和时序开销的基础上，相对已有多阶段容错路由算法可获得20%～30%的网络性能提升。
3．提出防守区模型及相应的区域防守路由算法。防守区使得数据包可以提早获知故障的位置从而及时采取措施绕过故障区域，其可用于解决当前针对无虚通道片上网络的容错路由算法中非故障节点损失过多的问题。实验结果表明，相对当前算法本文算法可容忍的故障分布最大增加15%以上，非故障节点损失最大降低80%以上。另外防守区的构造只需要局部信息因此具有良好的可扩展性。实验结果表明使用本文算法的网络收敛时间最大减少30%以上。
4．提出二叉树波导及相应的光控制信号广播路由算法。通过使用非对称Y分支波导构建均匀的二叉树波导，任意两点间的光路建立只需对光控制信号进行一次额外的光电及电光转换。该技术可用于解决当前片上光网络中光路建立时间长的问题。实验结果表明，使用本文提出的光控制信号二叉树广播路由机制，数据包平均延迟仅为现有方法的1/10。