网络拓扑和通道标签对基于标签路由算法性能的影响

# 网络拓扑和通道标签对基于标签路由算法性能的影响 ## 1 引言 近年来，基于集群的不规则网络（INs），如工作站网络（NOWs，也称为不规则片上网络），已成为传统规则并行计算机的经济有效替代方案之一。在这类系统中，通常需要一个不规则的高速网络，以提供网络所需的布线灵活性，并设计具有增量扩展能力的可扩展系统。 如果不对 INs 的路由方案进行精心设计，这些网络可能会出现死锁。由于 INs 的拓扑结构不是预先定义的，因此设计和应用无死锁路由算法通常不依赖于对网络拓扑的任何预先假设。所以，这些网络的主要问题是设计通用无死锁路由算法的复杂性。 本文的主要目的是朝着这个目标迈出一步，首先在不规则拓扑的新路由算法家族（基于标签的路由算法）中开发一些无死锁路由方案。此外，在现实条件下评估基于标签的路由在不规则网络中的性能也是另一个主要关注点。为此，进行了广泛的模拟实验。 ## 2 基于标签的路由算法 为了使路由算法无死锁，消息与其分配的物理通道之间不能出现循环缓冲区依赖。当使用标签方法生成无死锁路由算法时，首先需要为给定的拓扑结构做好实现基于标签的路由算法的准备。下面简要描述拓扑结构的标签方式以及相关路由方案的生成方法。 基于标签的路由算法的主要思想是通过分配预定义的标签对网络通道进行分类，然后将标记的通道分组，使得每个组之间没有循环依赖。这些组在相关文献中被称为区域。之后，将生成的区域按顺序排列，当消息通过区域中所需的通道（按照区域的顺序）时，该顺序保证消息能够到达其目的地。 ### 2.1 图标签、无死锁区域和路由算法的基本概念 生成基于标签的路由算法的第一步是图标签。为了比较先前报道的路由算法和本文新提出的算法，本文使用了相关文献中报道的图标签方法。作为起点，在给定的不规则网络上基于广度优先搜索（BFS）图遍历形成一个生成树，作为标签过程的基础。节点和通道的标签分为两个阶段： - **第一阶段**：节点按照生成树的形成顺序，根据它们与生成树根节点的距离升序标记。朝向较低节点标签的通道标记为 '1'，背离较低节点标签的通道标记为 '0'。 - **第二阶段**：随后，对图应用第二阶段的标签，即按照前序树遍历的顺序为每个节点分配递增的编号。通道使用第一阶段的策略进行标记。 因此，每个通道被分配两个不同的标签，可以将通道标签视为包含两个不同标签的复合标签。对于给定的不规则拓扑，最多可能有四种通道标签：(00)、(01)、(10)、(11)。 当消息从节点 A 到节点 B 有单个 '0' 转换（通道）时，意味着节点 A 的相应标签低于 B；单个 '1' 转换表示节点 A 的相应标签高于 B。当同时考虑两个标签作为复合标签时，有以下结果： - (11)：表示节点 A 的两个标签都低于节点 B。 - (10)：表示节点 A 的第一个标签低于 B，第二个标签高于 B。 - (01)：表示节点 A 的第一个标签高于 B，第二个标签低于 B。 - (00)：表示节点 A 的两个标签都高于节点 B。 生成基于标签的路由算法的第二步是对通道进行分组，使得同一组内的通道之间没有循环依赖。由于有多种分组通道的方法，因此可以生成各种无死锁组（区域），进而生成不同的无死锁路由算法。 在基于标签的路由中，通道组之间有预定义的遍历顺序，消息不能使用属于先前遍历组的通道标签，但可以自适应地使用同一组的通道标签。因此，不同组的通道之间没有循环依赖。只需将无循环依赖的通道标签分组即可。 例如，消息 1 持有标记为 (10) 的通道 (A, B)，并请求使用标记为 (11) 的通道 (C, D)；消息 2 持有 (C, D) 并请求使用 (A, B)。假设这两个通道标签 {(10), (11)} 在同一组。对于消息 1，根据标签规则有相应的节点标签关系。如果消息 2 想在持有 (C, D) 的情况下请求 (A, B)，它需要跨越其他通道，如 (00)、(01)，这与组的遍历顺序矛盾。因此，可以将 (10)、(11) 放在一组。 以下推论定义了创建无循环依赖的无死锁区域或通道组的一般规则： 推论：通道 X 和 Y 之间没有循环依赖，当且仅当它们满足条件 (x₀ : y₀) ⊕ (x₁ : y₁) = 1，其中 : 是按位异或非运算符，⊕ 表示按位或运算符。需要注意的是，(x₀ x₁) 和 (y₀ y₁) 是通道标签，而不是节点标签。可能的无死锁区域有 (10, 11)、(01, 11)、(00, 10) 和 (00, 01)。 生成基于标签的路由算法的第三步是将无死锁区域按顺序排列，以