·266· 智能系统学报 第3卷 匹配问题(bipartite graph matching). 输入端口可能收到多个响应信号，随机地从中选择 G 一个输出端口并向其发送接受信号.每个信元时隙 输入输出都重新开始并预设为未匹配，在某次迭代 ●2 中完成的连接在后面的迭代中继续保持（卿使存在 更多的匹配数).一次迭代的PM算法吞吐率只能 达到63%，多次迭代可达到100% PM在硬件实现上复杂度比较高，对于一个 16Ⅺ的交换结构，要实现PM算法，就需要将近 图1二部图G及其匹配图M 64000个复杂的门器件」 Fig 1 B ipartite graph G and its'matching graphM 过P每次迭代也是请求、响应、接受3个步骤， 不同的是，在第2步的响应中，输出端口收到请求 如图1所示，G=Y,E,为顶点集，包括2个 后，从它的固定循环列表里选择当前Gant指针指 子集：左侧输入端口集和右侧输出端口集，分别代表 向的输入端口，输出端口通知所有输入端口说明其 输入和输出端口：E为边集，表示从输入端口到输出 请求是否被响应，当且仅当该响应在第3步里得到 端口可能的连接边，其权重记为W,例如：在PM和 确认接受后，Grant指针才增加1（模N)指向下一输 设P中W,=0或1，表示队列Q是否有信元传输； 入端口；在第3步接受中，输入端口按照固定循环列 在LQF和OCF中，W表示Q的长度或信元等待时 表选择响应信号，当某个输出端口被接受时，Accept 间.二部图G的匹配图M定义为边集E的子集，且 指针模N加1指向下一输出端口.这种指针更新方 M中没有2条边有公共定点.这就说明一个匹配图 法克服了PM的不公平性，不仅可以预防端口出现 满足交换结构的传输限制条件，即在同一时隙内，输饥饿现象，还使响应仲裁器趋向于非同步工作，可快 入端口传送的信元和输出端口接收的信元个数最多速实现端口间的最大匹配， 为一个 实现汉P算法的硬件需要包含2W个仲裁器： 实现二部图匹配的算法有最大数量匹配算法 N个用于输出端的响应仲裁器，N个用于输入端的 (maxium size matching,.MSM)6),最大权重匹配 接受仲裁器，每个仲裁器有N个可编程的输入优先 算法(maxmum weight matching,.MWM)-y,稳定结 级解码器.实现过P算法需要的门器件数量比PM 合算法)，神经网络算法等.设计调度算法的基本 少了一半 要求包括：公平性稳定性时延小、易于实现等 12最大权重匹配算法 11最大数量匹配算法 最大权重匹配算法的目标是使匹配边的总权重 最大数量匹配算法的目标是使匹配的边的数量 达到最大，除考虑输入队列是否为空外，还要考虑队 达到最大.M9M采用1位的请求信号长度作为边的 列长度或排队时间等权重因素，因此请求信号长度 权重，当某虚拟队列中有信元时，相应的边的权重为 由1位变为多位.在容许的信元流量下，不论是否均 1,否则为0仿真实验表明，在独立均匀和容许的 匀，最大权重匹配算法都可以达到100%的吞吐量. 信元流量时可以获得100%的吞吐量，对于非均匀 常用的迭代近似MWM算法有：最长队列优先算法 流量可能出现饿死现象，存在不稳定性和不公平性. (iterative lng queue first,LQF)、等待最久信元优先 由于实现的复杂性，常用多次迭代的方法近似MM 算法(iterative old cell first,CF)),最久端口优 算法，其实现的迭代算法有PM(parallel iterative 先算法(iterative ng port first,LPF)a&o等 matching)(iterative round obin matching LQF是LQF的迭代算法，也包括请求、响应、接 wi油LP)6等. 受3个迭代步骤，权重W,()等于输入队列长度 PM是一种并行迭代匹配时序算法，在一个时 Ly(.其输入端发送的请求信号为该队列的长度 隙内多次迭代产生不会冲突的匹配.每次迭代包括 信息，该请求信号字宽2b,其中b由输入队列的最 3个步骤：1)请求(Request):每个未匹配的输入端 大长度Lma决定，即2b≤Lma,LQF算法有可能出现 口向有输出要求的未匹配的输出端口发送请求信 饿死现象.DCF是OCF的迭代算法，算法权重 号；2)响应(Gran):一个未匹配的输出端口可能收 Wg(n等于输入队列队首信元的等待时间T,(. 到多个请求信号，随机地从中选择一个输入端口并 DCF算法不会出现饿死现象，因为如果有队首信元 向其发送响应信号；3)接受(Accep):一个未匹配的 得不到服务的话，那么它的权重T,(n)会一直增加 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net匹配问题 ( bipartite graph matching). 图 1 二部图 G及其匹配图 M Fig. 1 Bipartite graph G and its’matching graphM 如图 1所示 , G = [V, E ], V为顶点集 ,包括 2个 子集 :左侧输入端口集和右侧输出端口集 ,分别代表 输入和输出端口; E为边集 ,表示从输入端口到输出 端口可能的连接边 ,其权重记为 W ij . 例如 :在 PIM和 iSL IP中 W ij = 0或 1,表示队列 Qij是否有信元传输; 在 iLQF和 iOCF中 , W ij表示 Qij的长度或信元等待时 间. 二部图 G的匹配图 M 定义为边集 E的子集 ,且 M 中没有 2条边有公共定点. 这就说明一个匹配图 满足交换结构的传输限制条件 ,即在同一时隙内 ,输 入端口传送的信元和输出端口接收的信元个数最多 为一个. 实现二部图匹配的算法有最大数量匹配算法 (maximum size matching, MSM ) [ 627 ] , 最大权重匹配 算法 (maximum weight matching,MWM ) [ 8211 ] ,稳定结 合算法 [ 12 ] ,神经网络算法等. 设计调度算法的基本 要求包括 :公平性、稳定性、时延小、易于实现等 [ 10 ] . 1. 1 最大数量匹配算法 最大数量匹配算法的目标是使匹配的边的数量 达到最大. MSM采用 1位的请求信号长度作为边的 权重 ,当某虚拟队列中有信元时 ,相应的边的权重为 1,否则为 0. 仿真实验 [ 9 ]表明 ,在独立均匀和容许的 信元流量时可以获得 100%的吞吐量 ,对于非均匀 流量可能出现饿死现象 ,存在不稳定性和不公平性. 由于实现的复杂性 ,常用多次迭代的方法近似 MSM 算法 ,其实现的迭代算法有 PIM ( parallel iterative matching) [ 2, 6 ] , iSL IP ( iterative round robin matching with SL IP) [ 627 ]等. PIM是一种并行迭代匹配时序算法 ,在一个时 隙内多次迭代产生不会冲突的匹配. 每次迭代包括 3个步骤 : 1)请求 (Request) :每个未匹配的输入端 口向有输出要求的未匹配的输出端口发送请求信 号 ; 2)响应 ( Grant) :一个未匹配的输出端口可能收 到多个请求信号 ,随机地从中选择一个输入端口并 向其发送响应信号 ; 3)接受 (Accep t) :一个未匹配的 输入端口可能收到多个响应信号 ,随机地从中选择 一个输出端口并向其发送接受信号. 每个信元时隙 输入输出都重新开始并预设为未匹配 ,在某次迭代 中完成的连接在后面的迭代中继续保持 (即使存在 更多的匹配数 ). 一次迭代的 PIM 算法吞吐率只能 达到 63% ,多次迭代可达到 100%. PIM在硬件实现上复杂度比较高 ,对于一个 16 ×16的交换结构 ,要实现 PIM 算法 ,就需要将近 64 000个复杂的门器件. iSL IP每次迭代也是请求、响应、接受 3个步骤. 不同的是 ,在第 2步的响应中 ,输出端口收到请求 后 ,从它的固定循环列表里选择当前 Grant指针指 向的输入端口 ,输出端口通知所有输入端口说明其 请求是否被响应 ,当且仅当该响应在第 3步里得到 确认接受后 , Grant指针才增加 1 (模 N )指向下一输 入端口 ;在第 3步接受中 ,输入端口按照固定循环列 表选择响应信号 ,当某个输出端口被接受时 , Accep t 指针模 N 加 1指向下一输出端口. 这种指针更新方 法克服了 PIM的不公平性 ,不仅可以预防端口出现 饥饿现象 ,还使响应仲裁器趋向于非同步工作 ,可快 速实现端口间的最大匹配. 实现 iSL IP算法的硬件需要包含 2N 个仲裁器 : N 个用于输出端的响应仲裁器 , N 个用于输入端的 接受仲裁器 ,每个仲裁器有 N 个可编程的输入优先 级解码器. 实现 iSL IP算法需要的门器件数量比 PIM 少了一半. 1. 2 最大权重匹配算法 最大权重匹配算法的目标是使匹配边的总权重 达到最大 ,除考虑输入队列是否为空外 ,还要考虑队 列长度或排队时间等权重因素 ,因此请求信号长度 由 1位变为多位. 在容许的信元流量下 ,不论是否均 匀 ,最大权重匹配算法都可以达到 100%的吞吐量. 常用的迭代近似 MWM 算法有 :最长队列优先算法 ( iterative long queue first, iLQF)、等待最久信元优先 算法 ( iterative old cell first, iOCF) [ 9211 ]、最久端口优 先算法 ( iterative long port first, iLPF) [ 3, 6, 10211 ]等. iLQF是 LQF的迭代算法 ,也包括请求、响应、接 受 3个迭代步骤 , 权重 W ij ( n )等于输入队列长度 Lij ( n). 其输入端发送的请求信号为该队列的长度 信息 ,该请求信号字宽 2b,其中 b由输入队列的最 大长度 Lmax决定 ,即 2b≤Lmax . iLQF算法有可能出现 饿死现象. iOCF 是 OCF 的迭代算法 , 算法权重 W ij ( n)等于输入队列队首信元的等待时间 Tij ( n). iOCF算法不会出现饿死现象 ,因为如果有队首信元 得不到服务的话 ,那么它的权重 Tij ( n)会一直增加 ·266· 智 能 系 统 学 报 第 3卷