二维torus网中的无死锁自适应路由方法

摘要

二维torus网络无死锁的自适应路由方法属于分布式高性能容错计算技术领域，其特征在于，把节点之间的每条物理通道被划分为两条虚拟通道，这两条通道均为两向通道，并分配到二维torus网络的四个虚拟子网中，利用虚拟通道分配策略避免了各子网内以及各子网间可能形成的死锁，同时达到更高的自适应性。本发明与传统的维序路由方法、西向优先和负向优先方法相比，当标准化输入负载和网络中故障节点数提高时，我们的方法明显可以提高网络实际流量，并降低传输延迟，从而提高整个网络的传输性能。

主权项

1、二维torus网中的无死锁自适应路由方法，其特征在于，所述方法是在每一维上有k个节点的二维torus网上依次按步骤实现的：步骤(1)：初始化对于二维torus网络，连接两个边界之间的物理通道称为边界通道；把每条物理通道被划分为两条虚拟通道：c1和c2，这两条通道均为两向通道，c1通道分为c1+和c1-两个方向的通道，c2通道分为c2+和c2-两个方向的通道，“+”和“-”表示消息传输的正负方向；将二维torus网划分为划分为如下四个虚拟子网：x-y-、x-y+、x+y-、x+y+，x+、x-即表示在x轴上的正、负方向的路由，对于y轴同理；步骤(2)：对于每个消息消息依次按以下步骤分配到所属虚拟子网：设当前节点为curr，目的节点为dest，当前节点和目的节点在两维上的偏移量为A＝xd-xc，B＝yd-yc，其中下标c、d分别代表当前节点和目的节点，dx表示所述维度上的虚拟子网分配，对于dy同理；当A≥0且B≥0时，如果A≥k/2，B≥k/2，dx＝-，dy＝-；如果A＜k/2，B≥k/2，dx＝+，dy＝-；如果A≥k/2，B＜k/2，dx＝-，dy＝+；如果A＜k/2，B＜k/2，dx＝+，dy＝+；当A≥0且B＜0时，如果A≥k/2，B≥-k/2，dx＝-，dy＝-；如果A＜k/2，B≥-k/2，dx＝+，dy＝-；如果A≥k/2，B＜-k/2，dx＝-，dy＝+；如果A＜k/2，B＜-k/2，dx＝+，dy＝+；当A＜0且B≥0时，如果A≤-k/2，B≥k/2，dx＝+，dy＝-；如果A≤-k/2，B＜k/2，dx＝+，dy＝+；如果A＞-k/2，B≥k/2，dx＝-，dy＝-；如果A＞-k/2，B＜k/2，dx＝-，dy＝+；当A＜0且B＜0时，如果A＜-k/2，B＜-k/2，dx＝+，dy＝+；如果A＜-k/2，B＞-k/2，dx＝+，dy＝-；如果A≥-k/2，B＜-k/2，dx＝-，dy＝+；如果A≥-k/2，B≥-k/2，dx＝-，dy＝-；步骤(3)：二维平面上的消息依次按以下步骤路由：步骤(3.1)：如果消息在x-y-虚拟子网中：如果A≥0，B≥0，则选择通道x(c1-)，y(c1-)；如果A＜0，B≥0，则选择通道x(c2-)，y(c1-)；如果A≥0，B＜0，则选择通道x(c1-)，y(c2-)；如果A＜0，B＜0，则选择通道x(c2-)，y(c2-)；步骤(3.2)：如果消息在x-y+虚拟子网中：如果A≥0，B≥0，则选择通道x(c1-)，y(c1+)；如果A＜0，B≥0，则选择通道x(c2-)，y(c1+)；如果A≥0，B＜0，则选择通道x(c1-)，y(c2+)；如果A＜0，B＜0，则选择通道x(c2-)，y(c2+)；步骤(3.3)：如果消息在x+y-虚拟子网中：如果A≥0，B≥0，则选择通道x(c1+)，y(c1-)；如果A＜0，B≥0，则选择通道x(c2+)，y(c1-)；如果A≥0，B＜0，则选择通道x(c1+)，y(c2-)；如果A＜0，B＜0，则选择通道x(c2+)，y(c2-)；步骤(3.4)：如果消息在x+y+虚拟子网中：如果A≥0，B≥0，则选择通道x(c1+)，y(c1+)；如果A＜0，B≥0，则选择通道x(c2+)，y(c1+)；如果A≥0，B＜0，则选择通道x(c1+)，y(c2+)；如果A＜0，B＜0，则选择通道x(c2+)，y(c2+)。