为了从inport矩阵变换到outport矩阵，必须找到两个中间矩阵after_t1和after_s，从而完成交换路径的接续。因此本文的目标是研究一种算法，根据输入矩阵和输出矩阵产生这两个中间矩阵，从而使处理机可以根据4个矩阵往寄存器阵列中填值，这样就可以实现T-S-T网络交换。为了以后叙述方便，3个寄存器阵列定义为：Tregister1(时分)、Sregister(空分)、Tregister2(时分)。

由于在实际的T-S-T交换中，CPU根据各个控制寄存器中的值来完成交换。由交换的特点可知，每个控制寄存器的值是由输入序列和输出序列决定的。其中Tregisterl的值可以由inport和after_t1决定，同理，Sregister的值由after_t1和after_s决定，Tregister2的值由after_s和outport决定。

4.2 算法思想的设计

算法设计要求：

(1)对于任意给定的输入矩阵和输出矩阵，都能够得到2个中间矩阵；

(2)由输入矩阵到第一个中间矩阵只能经过一系列行内置换；

(3)由第一个中间矩阵到第二个中间矩阵只能经过一系列列内置换；

(4)由第二个中间矩阵到输出矩阵只能经过一系列行内置换。

由行内变换和列内变换的性质可以推断出after_t1(AT)和after_s(AS)矩阵的特点如下：

AT的特点：ATij=INij'(只能在同一行上进行置换)；AS的特点：AS是inport的一个置换矩阵；AS的同一列上不可能出现inport同一行上的元素。

这是由于AT同一列上不可能出现inport同一行上的元素，而AT到AS经过的是列内变换。

现在有了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)。