T-S-T三级交换网络路径搜索算法的研究

现在有了inport和outport，目标是通过这2个矩阵找到after_t1和after_s。从上面的设计要求和模型2个中间矩阵的特点可以看出，由inport到outport所经过的置换与由outport到inport所经过的置换是对称的，所以由outport到inpott置换所得的2个中间矩阵也是问题的解。而且inport相对于output较为确定，因此为了方便描述和算法实现，本文采用逆推法，由outport经过一系列的行内变换逆推出after_s，由after_s经过一系列的列内变换逆推出after_t1。很容易发现从after_s到after_t1只需要一个简单的排序就可以完成，因此算法的关键是由outport推导after_s。

这样本文研究的交换网络调度算法要解决的关键问题等效后分解为：将一个任意置换矩阵经过一系列的行内变换变成为同一列上不存在输入矩阵的同一行数据的置换矩阵(这是由AS的特点所决定的)。将解决这个关键问题的算法称为交换网络调度算法的核心算法。

5 关键矩阵算法的思想和步骤

5.1 高冲突值行优先排列算法

一些约定和定义：

规则：矩阵after_s同一列上不存在矩阵inport同一行上的数据。

那么对于任一给定输出矩阵outport(OP)，本算法的任务是；根据"规则"将outport的每一行元素放到after_s(AS)同行的适当位置上。例如假设现在开始第i行的排列，也就是说，第0行到第i～l行的数据已经初步放置完毕(考虑到回溯，所以说"初步")，则前i行的每一列元素的初始矩阵行可以组成1个一维矩阵，一共n个一维矩阵，定义为垂直行阵v[0]，v[1]。…，v[n一1]；而OP的第i行的所有元素的初始矩阵行又可以组成1个一维矩阵(元素的初始矩阵行等于该元素整除矩阵维数的商)，定义为水平行阵h，数据结构如图3所示：

定义：垂直冲突值：vRepeat[n]，其中vRepeat[i](i=0，1，2，…，n-1)等于u[i]中的元素在h中的重复次数的和。

水平冲突值：hRepeat[n]，其中hRepcat[i](i=0，1，…，n-1)等于k[i]在v中的重复次数的和。

生存数(lifenum)：假设vRepeat[j]等于k，也就是说，O[i]中有k个元素不能放在AS的第j列，能放在这一列的元素个数只有n-k个，定义为生存数(lifenum)，将这n-k个元素下标取出形成向量，定义为生存空间(lifespace)

5.2 高冲突值行优先排列算法的实现

算法安放数据元素时，首先从vRepeat最大的那一列开始安放hRepeat最大的符合"规则"的元素，再逐次安放vRepeat中较小的且符合"规则"的列。这样，大冲突值的元素得到优先安放，重排或回溯的可能性就大大减小。

5.2.1 主流程

(1)排列第1行数据，row=0；

(2)row=row+1，如果row≥n，则停止，否则转下一步；

(3)统计冲突值，调用判回溯算法判断是否回溯，如果回溯，调用回溯算法，否则转下一步；

(4)选择vRepeat冲突值最大的列，根据"规则"安放hRepeat中最大的元素；

(5)更新vRepeat和hRepeat；

(6)判断这一行的数据是否都安放完毕，如果是，转(2)，否则转(3)。

5.2.2 判断回溯算法

回溯条件：生存数为k，生存空间相同的列的个数和大于生存数k，则回溯，原因是某生存空间"不够分配"。例如，第i列和第j列(i不等于j)的生存数都为1和生存空间都为{2}，这样第2个元素只能放在一个位置上，也就是说，无论如何排列都无法满足"规则"，需要回溯。

定义节点数据结构如图4所示：

判回溯的算法流程：

(1)将生存数相同的所有节点串成链表，链表的序号等于生存数；

(2)从链表序号为0向链表序号为n顺序扫描链表，统计生存空间相同的节点个数，当出现节点个数大于生存数的情况，需要回溯，否则转下一步；

(3)将本链并入下一个链表；

(4)如果所有链表都不出现生存空间相同的节点个数和大于生存数的情况，则不需要回溯。

5.2.3 回溯算法

定义经历表：在回溯过程中，各元素所"呆过"的位置序列。

回溯算法流程：

(1)确定回溯元素(冲突值最大原则)；

(2)为回溯元素找一个"合法位置"；

合法条件：

规则：冲突值小于当前情况；位置不在经历表中。

(3)为其他元素找"合法位置"；

6 算法的正确性证明和复杂度分析

从前面的分析可以知道，要解决整个交换算法的关键是确定和寻找中间矩阵after_s，也就是说，在解决问题之前，必须确定问题有解。如何确定after_s一定存在，这里可以通过组合数学中的抽屉原理证明必然存在这样的矩阵，证明过程比较简单，本文在这里不做推导证明。

从前面的理论分析中知道，衡量交换算法有2个重要的指标：交换次数和比较次数。为了统计本文所研究的交换算法的性能，本文针对不同阶数矩阵的交换次数和比较次数做了系统的统计：

(1)对于每一行数据，由于统计冲突值、判回溯算法和元素的安放算法都是多项式复杂度，所以，在不存在回溯的条件下，本算法是多项式复杂度。

(2)在本算法中，"冲突"起着非常重要的作用，本身回避了许多回溯可能。即使回溯，本行可供回溯元素和非回溯元素"待"的位置个数非常有限，所以元素回溯的空间很小。

下面本文给出在不回溯的情况下，对高冲突行优先排列算法在阶数递增变化时，50次平均交换次数和比较次数统计结果如表1所示。

从前面对该算法的描述可知，该算法通过使每个元素"找到"尽可能适合自己的位置，从而回避了重新排列的许多可能，对于一行来说，完全避免了全排列，而且大大减小回溯概率。由于对大多数(约80％)矩阵来说，是不会出现回溯的，只有类似这样的矩阵才有可能出现回溯(也可能不回溯)，即，AS的某些行，可供选择的初始行太少。所以，该算法是一个近似多项式的算法，在不回溯的情况下，是多项式算法。该算法基本上能够完成交换网络的路径接续，他有一个很大的优势就是在交换过程中交换的次数达到最小，这样也就大大提高了寻找交换路径的效率。本算法具有良好的特性，而且通过芯片级联可实现。

作者：陈腊梅，周正道 (1.南京航空航天大学 金城学院 江 苏南 京211156；2.中兴通讯 南京研究所 江苏 南京 210000)