第3期 张重洋，等：基于输入排队的高速交换调度算法研究 ·267 到得到服务为止.DCF其余性质和LQF一样 先清单.信元的紧急值定义为在仿真的FOOQ队 LPF是LPF的迭代算法，其权值定义为 列中，排在该信元前面的信元的个数.输入端口根 R,(n)+C;(n),Li(n)>0. 据队首信元的紧急值为每个输出端口赋一个优先值 Wg(n) (0,J,(nl=0 并建立相应的优先清单 式中：Lg(n)是第n时隙队列Q,的长度.Rg(n)= 在JM(jined preferred matching)liJ和CCF (critical cell first)us1算法中，输入优先清单的信元 ,()为输入占有，表示输入端口在第n时隙 分别按等待时间和输出占有排列.与MUCFA算法 所有缓冲队列总和：C,(n= ∑Lg(n)为输出占 一样，JM和CCF算法的输出优先清单的信元按紧 急值排列」 有，表示所有要发送到输出端口的信元缓冲队列 LOOFA lowest output occupancy first algo- 长度总和，LP℉匹配总权重等于所有已匹配输入与 rim)161算法的输入优先清单与CCF算法相同，输 输出的总和.LP℉迭代有2个步骤：1算法按输入与 出优先清单按信元等待时间排列，LOOA可以在传 输出的占有率建立一个排序表：2从最大占有端口 输流级限制每个分组的传输延迟 开始至最小占有端口，通过循环迭代，找到最大容量 表2稳定结合类算法综合比较 匹配.由于在第一步中己已经将请求信号按权重排序， Ta ble2 The com prehensive com parison of GSAs 因此在第2步中无需对请求权重进行比较，使得算 算法输入优先清单输出优先清单加速比时间复杂度 法容易由硬件实现 表1M9M类与MWM类算法的综合比较 MUCEA 紧急值 紧急值 0w2) Tablel The com prehensive com parison of MSM and JMM 等待时间 紧急值 2 0w2) MWM algor ithms CCF 输出占有 紧急值 0N2) 最大吞 算法 权重 时间复杂度 稳定性公平性 LOOFA输出占有 等待时间 0N2) 吐率% MM 100 010w23) 表2列出了稳定结合类算法的一些特性比较 从表中可以看出，与最大匹配类算法相比，稳定结合 PM 100 0/1 O(N*bgN) 本 算法除需要加速比外，还有以下特点：)某些输入 iS P 100 0/1 O(i*N*logN) 是 输出端口的优先清单可能是不完全的，结果有可能 MWM 100 W尊 O(N3*bgN) 导致稳定结合数降低，算法性能下降；2)在算法中， LQF 100 O(i*b*bgN) + 否 一个已建立的连接在随后的迭代中可能被拒绝，这 OCF 100 Ty o(i*b*bgN) + 是 是与最大匹配算法的显著区别：3)目前没有证明稳 LPF 100 R:+C,0W2) 定结合算法带宽的利用效率及是否会导致饿死现 MWM算法需要2W个仲裁器和一个权重寄存 象，但算法会偏重于输入或输出的某一方：4)稳定 器，每个响应仲裁器需要2N个比较器，按信号权重 结合不一定有最大权重，而最大权重也不一定是稳 信息给予优先匹配.MWM算法的硬件复杂度要比 定结合1 改P高 14神经网络算法 13稳定结合匹配算法 人工神经网络具有高度的并行处理能力和快速 稳定结合问题2/(stable marriage matching)最 收敛的特性，特别是HNN(hopfield neural netork) 早由Gale和Shap ley提出，因此该算法称为GSA 擅长解决优化问题，因此可以用HNN实现信元调度 (Gale-Shap ley algorithm),GS4算法利用输入输出端 器功能18201 口定义的优先级清单寻找稳定的输入输出匹配.如 采用的HNN包含NW个神经元，分别对应于 果在没有完成匹配的输入输出端口集合中不能发现 VOQ输入端口NW个缓冲器队首信元的服务状 一个端口，其优先级比己匹配的端口高，那么就称己 态，整个网络的状态可用NW矩阵表示.NN经 完成匹配的输入输出端口是稳定的 过迭代收敛到稳定状态时，若矩阵元素(；为1，则 MUCFA(most urgent cell first algorithm)算法 表示对应的神经元处于激发状态，相应的队首信元 利用GS4和输入输出优先清单寻找稳定结合匹配. 被送入交换结构，为0则表示神经元处于抑制状态 输出端口根据队列Q,队首信元的紧急值(urgent 相应的队首信元不被送入交换结构， vaue)为输入端口i赋一个优先值并建立相应的优 神经元的输入输出关系为 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net到得到服务为止. iOCF其余性质和 iLQF一样. iLPF是 LPF的迭代算法 ,其权值定义为 W ij ( n) = Ri ( n) + Cj ( n) , Lij ( n) > 0, 0, Jij ( n) = 0 . 式中 : Lij ( n)是第 n时隙队列 Qij的长度. Rij ( n) = ∑ N j=1 Lij ( n) 为输入占有 ,表示输入端口 i在第 n时隙 所有缓冲队列总和; Cij ( n) = ∑ N i =1 Lij ( n) 为输出占 有 ,表示所有要发送到输出端口 j的信元缓冲队列 长度总和 , iLPF匹配总权重等于所有已匹配输入与 输出的总和. iLPF迭代有 2个步骤 : 1算法按输入与 输出的占有率建立一个排序表; 2从最大占有端口 开始至最小占有端口 ,通过循环迭代 ,找到最大容量 匹配. 由于在第一步中已经将请求信号按权重排序 , 因此在第 2步中无需对请求权重进行比较 ,使得算 法容易由硬件实现. 表 1 MSM类与 MWM类算法的综合比较 Table1 The com prehen sive com par ison of M SM and MWM a lgor ithm s 算法 最大吞 吐率 % 权重 时间复杂度 稳定性 公平性 MSM 100 0 /1 O (N 2. 5 ) - P IM 100 0 /1 O (N 3 logN ) - 否 iSL IP 100 0 /1 O ( i3 N 3 logN ) - 是 MWM 100 W ij O (N33 logN ) + iLQF 100 Lij O ( i3 b3 logN ) + 否 iOCF 100 Tij O ( i3 b3 logN ) + 是 iLPF 100 Ri + Cj O (N 2 ) + 是 MWM 算法需要 2N 个仲裁器和一个权重寄存 器 ,每个响应仲裁器需要 2N 个比较器 ,按信号权重 信息给予优先匹配. MWM 算法的硬件复杂度要比 iSL IP高. 1. 3 稳定结合匹配算法 稳定结合问题 [ 12 ] ( stable marriage matching)最 早由 Gale 和 Shap ley提出 ,因此该算法称为 GSA (Gale2Shap ley algorithm) , GSA算法利用输入输出端 口定义的优先级清单寻找稳定的输入输出匹配. 如 果在没有完成匹配的输入输出端口集合中不能发现 一个端口 ,其优先级比已匹配的端口高 ,那么就称已 完成匹配的输入输出端口是稳定的. MUCFA (most urgent cell first algorithm) [ 13 ]算法 利用 GSA和输入输出优先清单寻找稳定结合匹配. 输出端口 j根据队列 Qij队首信元的紧急值 ( urgent value)为输入端口 i赋一个优先值并建立相应的优 先清单. 信元的紧急值定义为在仿真的 FIFO2OQ队 列中 ,排在该信元前面的信元的个数. 输入端口 i根 据队首信元的紧急值为每个输出端口赋一个优先值 并建立相应的优先清单. 在 JPM ( joined p referred matching) [ 14 ] 和 CCF ( critical cell first) [ 15 ]算法中 ,输入优先清单的信元 分别按等待时间和输出占有排列. 与 MUCFA 算法 一样 , JPM和 CCF算法的输出优先清单的信元按紧 急值排列. LOOFA ( lowest output occupancy first algo2 rithm) [ 16 ]算法的输入优先清单与 CCF算法相同 ,输 出优先清单按信元等待时间排列 , LOOFA可以在传 输流级限制每个分组的传输延迟. 表 2 稳定结合类算法综合比较 Table2 The com prehen sive com par ison of GSA s 算法 输入优先清单输出优先清单 加速比 时间复杂度 MUCFA 紧急值 紧急值 4 O (N 2 ) JPM 等待时间 紧急值 2 O (N 2 ) CCF 输出占有 紧急值 2 O (N 2 ) LOOFA 输出占有 等待时间 2 O (N 2 ) 表 2列出了稳定结合类算法的一些特性比较. 从表中可以看出 ,与最大匹配类算法相比 ,稳定结合 算法除需要加速比外 ,还有以下特点 : 1)某些输入 输出端口的优先清单可能是不完全的 ,结果有可能 导致稳定结合数降低 ,算法性能下降; 2)在算法中 , 一个已建立的连接在随后的迭代中可能被拒绝 ,这 是与最大匹配算法的显著区别; 3)目前没有证明稳 定结合算法带宽的利用效率及是否会导致饿死现 象 ,但算法会偏重于输入或输出的某一方; 4)稳定 结合不一定有最大权重 ,而最大权重也不一定是稳 定结合 [ 17 ] . 1. 4 神经网络算法 人工神经网络具有高度的并行处理能力和快速 收敛的特性 ,特别是 HNN ( hopfield neural network) 擅长解决优化问题 ,因此可以用 HNN实现信元调度 器功能 [ 18220 ] . 采用的 HNN包含 N ×N 个神经元 ,分别对应于 VOQ输入端口 N ×N 个缓冲器队首信元的服务状 态 ,整个网络的状态可用 N ×N 矩阵表示. HNN 经 过迭代收敛到稳定状态时 ,若矩阵元素 ( i, j)为 1,则 表示对应的神经元处于激发状态 ,相应的队首信元 被送入交换结构 ,为 0则表示神经元处于抑制状态 , 相应的队首信元不被送入交换结构. 神经元的输入输出关系为 第 3期 张重洋 ,等 :基于输入排队的高速交换调度算法研究 ·267·