英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
基于二维最优循环拓扑的片上网络路由算法开发
Aleksandr Yu. Romanov *, Evgeny V. Lezhnev, Aleksandr Yu. Glukhikh, Aleksandr A. Amerikanov
摘要
本文致力于研究新拓扑在片上网络（NoC）设计中的应用。它是提出了使用二维最优循环拓扑进行NoC设计，并开发了一个优化的减少内存使用的路由算法。将提出的路由算法与以前针对环形循环拓扑开发的表路由、顺时针路由和自适应路由算法，以及对乘法循环开发的专用路由算法进行了比较。路由器的综合结果给出了路由算法的实现方法。估计在具有循环拓扑的NoC中实现通信子系统的ALM和注册资源的成本。
关键词：电气工程；计算机体系结构；计算机模拟；高性能计算网络（计算机科学）；算法；片上网络；循环拓扑；二维最优循环拓扑；规则拓扑；路由算法；乘法循环；环循环
- 介绍
多处理器片上系统（MPSOC）[1]目前是计算机领域发展最快的领域。大幅度增加芯片和每单位面积的晶体管数量允许开发即使现在也有几十个或几百个处理器核的芯片。同时，通信子系统的有效组织问题，以确保此类NoC的节点之间的快速数据交换变得越来越紧急了[2]。
因为沟通是在一个通信网络工作中存在的芯片、定律和原理。因此，开发新的解决方案和需要在这种网络中组织数据传输的方法。在尤其是拓扑结构对NoC性能有着重要的影响。最常见的是经典的正则拓扑，如网格[3]和环面[4]，并不总是满足现代要求对于NoC，尤其是随着节点数量的增加[5]。不同的研究者提出了其他的拓扑选择能分辨超立方体[6，7，8]，弦环[9，10]，蜘蛛形[11]，L网络[12]。它们的特点是可以简化为表示一般以环形图的形式称为循环拓扑形式。与网格和环形拓扑相比，最优循环有几个显著的优点--更好的结构生存性、可靠性和连通性[13，14]。此外，理论的数学方面对循环图的研究很好；如递归循环[15]，乘法循环[16]，环循环[14] 有相当有趣的性质是众所周知的。从理论上讲，所提到的拓扑（超立方体、弦环等）也是接近循环拓扑，通常是循环拓扑的特例亚家族，但是由于发展NoC的拓扑还没有完全考虑到循环网络以前做的。必须考虑实现这种NoC所需的芯片资源，研究其中的循环拓扑及其路由算法。
- 背景
2.1二维循环
顶点集为V的无向图={1，...， N - 1}和一组边缘E={（i,j）:|I-j|☰sm mod N,m=1,,k}被称为循环图表[13]（S=s1，s2，...，sk –生成器，N–图顶点数）（图1）。标志C（N；s1，s2，...，sk）是圆环状正则结构的一种表示，其中每个顶点通过弦s1，hellip;，sk具有连续顶点和上一顶点。
最常见的是C（N；s1，s2）的二维循环与网格拓扑和圆环拓扑具有相同程度的顶点。这允许使用具有4个先前开发的输入/输出的路由器通过其他研究（例如Netmaker库[17]）。
任何图的主要特征是它的直径：d(C)=，其中len（i，j）–从图i顶点到图C顶点的最短路径的长度最小直径最优图的合成是图论的一个基本问题。例如，对于某些类型的循环（C（N；D，D 1），已知计算最优循环的公式[18，19]；对于其他类型的循环，则开发了找到它们的软件[20]。一些循环图的子类，如环循环s C（N；1，s2）[14]，其中第一个生成器等于1，乘法循环MC（s，k）=C（sk；1，s，s2，...，sk-1）[16，21]并不总是非常最优的，但是它们有许多有用的性质，可以将它们用作NoC的拓扑。
工作[14]表明，与环面和网格相比，圆（以连接资源的同等代价）具有更小的直径和平均距离。对于任意数量的顶点，存在最优循环图，但其有效性没有降低。因此，循环图是改进NoC特性（与网格拓扑和圆环拓扑相比）的有希望的NoC发展的拓扑基础，它同时保持了网络的规则性和路由器的尺寸。
- 研究区域
3.1二维循环中的路由
由于循环拓扑具有规则结构，其中的路由不像不规则网络中的路由那样困难[22]。尽管如此，优化算法的开发将使包交付到目标节点是必需的。对于NoC，节点之间的通信可以是广播、闲聊和点对点。
3.1.1二维循环中的广播和闲聊
前两种类型主要与齐次并行有关计算系统[23]，其中从一个控制节点向所有节点广播，其他节点（广播）或从所有节点到所有节点（八卦）是常见的；例如，配置网络并定义其可能动态变化的结构。这种变化的特点是广播包只是沿着从一个节点链接到所有相邻节点，依此类推，直到它们到达网络的所有节点。这足以确保一个包，一次在同一个节点上多次，并不是每一次都被视为一个新节点时间，以及网络中数据包的生存期，因此不是无限传播的。这种分组交换过程主要是使用通信模型进行描述，并对循环进行了深入研究网络。例如，在[19]中提出了一个叫喊模型，根据每个顶点只与其相邻顶点交换一次。为了消除每个传输顶点的数据包重复，在以该顶点为中心的最短路径生成树的基。因此，包裹的递送时间等于图表的直径。
对于NoC，最短路径树在每个路由器中都是相当冗余的，因此人们可以使用代数方法来节省资源[24]；在工作中[25]结果表明，对于简化的单端口模型（耳语模型），当一次一个节点只能与一个相邻节点交换时，广播时间不超过直径值 2。
说长道短的任务比较复杂，但总的来说也是可以解决的，通过向所有网络节点分发广播方法。为了在二维循环称为高斯网的特殊情况下，工作[24]提出了 一种全对全广播的快速算法，它被应用于在路由器中使用附加缓冲区的NoC[26]和在[27]中得到了改进。
对于二维循环的另一个特殊情况[28]，则在[29]中，通过构造跨关系交换的最优树来解决问题；在[30]中，通过构造跨关系交换图的i端口模型（ile;4）来解决问题提出了C（N；D，D 1）型。
3.1.2二维循环中的点对点通信
任何网络最重要的通信问题是顶点间点对点通信的组织。寻找两个顶点之间最短路径的最普遍和最著名的算法是Dijkstra算法[31]。它具有复杂性O（n2），对于循环图是多余的。因此，对于二维循环的各种子类，路由算法有许多发展。因此，在[32]中，提出了一种复杂度O（D）（其中D-直径）的环循环算法。乘法循环中的佩雷克斯变化问题在[9，16]中有讨论。对于C（N:D D 1）型和C（N:1，2D 1）型最优图，文[33]提出了一种生成树的方法。
文献[24]中给出了一个通用的算法，用于任何二维循环，具有（D）复杂度并确保包以=O（D）步到达目标节点。另一项工作[34]提出了求任意加权无向有向二维循环图顶点间最短路径的算法。它需要（log N）算法步骤，其总比特复杂度为O（log 3N）。但是这项工作[19]，其中给出了在复杂度为O（并保证找到最优路径）的图（N；D，D 1）中查找路径的算法的描述。
3.1.3基于循环拓扑的片上网络路由问题
尽管已有许多不同的循环网络路由算法，但它们应用于NoC的局限性还是很大的。NoC的问题在于其通信子系统往往占据芯片面积的百分之十[35]，功耗可能达到百分之36[36]。
使用间隔（在上面的上下文中）可能很有意义文献[37，38]中描述的循环网络中的路由方法。这种方法允许在（N；1，s2）和C（N；1，2D 1）型图的每个顶点上以紧凑形式（O（）每位）存储路由表，而且，与任何算法一样，基于路由表，路由算法的复杂度相当于O（1）。不过，这种方法仍然不能解决这个问题，因为有必要在NoC路由器中开发作为RTL状态机实现的路由算法。兰布罗克。应尽量减少DSP块和ALMS的使用。在这种情况下，不 需要计算包的整个路径，但是计算数据包应发送到的端口号，以便可以到达目标节点。这使得简化了NoC路由器的结构。
- 设计
4.1 C（N；D，D 1）循环的路由算法描述
它首先在[39]被证明，然后在[18]再次被证实参数描述为C（N；D，D 1）的循环在直径和平均距离；根据公式计算参数D：
C（N；D，D 1），D=-1, Ngt;2 （1）
与循环C（N；1，）不同，在循环C（N；D，D 1）中，为了传递到相邻的节点，需要进行两次跳跃（首先发电机s2，然后沿s1返回）。我们称之为“单跳”（图1）。
“单跳”的跳数如下：沿s2，有必要向顶部；沿着s1- 到对面。如果仅跳到相邻节点整个循环都是以类似的方式完成的需要2次跳跃，这就是为什么有必要考虑情况这样就可以避免。
在最终节点和初始节点之间距离的任何计算，此类循环可简化为以下公式：
跳数 = |x| |y|，长度 = xbull;s1 ybull;s2 （2）
其中x，y属于 Z，hops- 从初始值开始需要通过的跳数沿发电机s1和s2到最终节点的节点；
长度 - 节间距离。
为了便于对算法的描述，我们引入了顺时针运动的概念。算法的第一步是计算包需要发送的方向以及如何发送需要很多跳。为此，从初始节点的索引。如果距离值是负数必须选择逆时针运动并取绝对值产生的距离。如果这个数字大于网络的一半然后，根据算法，有必要将相反的方向，计算这个方向进入的距离帐户。
在计算长度和方向后，有必要确定哪个发电机需要跳跃。琐碎的选择在当距离被一个没有残留物（3）。因此，有必要选择下一个顶点，基于当前节点和所选生成器的值。例外的情况是长度超过两个生成器值的乘积。在这种情况 下，可以认为路径在距离上是最优的：
跳数 = 长度/s1或跳数 = 长度/s2 （3）
如果当前距离不满足上述条件，则有必要考虑尽可能接近的情况通过为一个或另一个生成器选择跳数来结束节点。这个策略比使用“单跳”能产生更好的效果。下一个假设覆盖距离nbull;s2所需的跳数nbull;s2将等于n，因为没有什么可以阻止选择一个或另一个顶点。假设n是距离除以s1的整数；在这种情况下，如果距离不是超过nbull;s2的值。
nbull;s1le;长度le;nbull;s2 （4）
式中，n=长度/s1- 整数。
如果距离不合适，这个条件非常适合寻找路径超过s1bull;s2；所需跳数可以覆盖距离。它应该考虑到之前引入的限制距离不应超过节点数的一半。
考虑一下这样一种说法，即有可能越过这段距离在n 1跳中（其中1不是“单个”跳，而是一个附加的跳生成器s1；n是距离除以s2的整数）。然而必须遵守以下条件：
长度/s2 长度%s2ge;s1 （5）
在这种情况下，必须选择s1直到长度%s2 gt; 0。之后，算法将沿着s2移动。要实现该算法，必须从这两个选项中选择一个以上条件。
考虑一个不符合上述所有条件的情况。结果是如果我们沿着一个或另一个发电机走，剩下的距离这种情况下，长度lt;s1）必须通过“单”跳来达到。在某些情况下，最佳策略是采取额外的跳跃，以避免不必要的“单一”跳跃。以s1发生器为基础，计算公式为了发现需要进行额外的跳跃，将如下所示：
长度lt; |长度 - s1| （6）
如果条件为真，则将沿着生成器s1执行额外的跃点。
我们引入另一个条件，距离不大于s2；它需要检查以避免额外的“单”跳，因为可能是计算出的距离在特定范围。例如，在这种情况下：
nbull;s2 lt; X lt; s1/2 lt; Y （n
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[254233]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
