PBFAA算法是一个基于平面的完全自适应最短虫孔路由算法(Planar一BasedFullyAdaptiveAlgorithm,PBFAA)。
人们对直接网络中采用虫孔路由切换技术的自适应路由算法已进行了大量研究,提出了很多算法,但它们或存在自适应性受限,或存在代价较大,或存在灵活性不够等缺点.在已有算法的基础上,以低通信延迟、高网络吞吐率和易VLSI实现为设计目标,提出了一个可扩展性好、自适应性强的基于平面的完全自适应路由算法PBFAA。
算法中将网络分成两个虚拟网VIN0和VI1I,VlN0中的虚通道按平面自适应路由策略路由消息,VIN1中的虚通道可完全自适应路由消息,由VIN0保证算法的无死锁性.由于两个网络均具有自适应性,故与已有一些较好的算法如(channel)相比,该算法自适应性更强,更能充分有效地利用网络资源,提高网络吞吐率,且容错能力更强一下面用n维mesh网络介绍PBFAA算法:
1)算法为每条物理通道设置4条虚通道,用VCdimension,label,direction来表示,其中dimension表示该虚通道沿哪一维传递消息;label表示虚通道的序号,取值0,1,2或3;direction可以为 (表示消息将沿正向传递)或-(表示消息将沿着逆向传递)。例如VC¨,一表示结点的第一维上的序号为1的负向虚通道。
2)将网络划分成两个虚拟网:VIN0和VIN1。在VIN0中使用序号从0至2的虚通道;在VIN1中使用序号为3的虚通道。
3)在VIN0中,按平面自适应路由策略选择趋于目的结点的虚通道路由消息;在VIN1中,按完全自适应最短路径路由策略选择趋于目的结点的虚通道路由消息。在两虚拟网中按相应路由策略可被选择的虚通道均称为所需虚通道,空闲的所需虚通道称为可用虚通道。
4)当一条消息的头微片到达某一结点时,如该结点是目的结点则消息被接收,否则:
a)若有可用虚通道,则对可用虚通道按最大间距输出虚通道选择策略,对相应维虚通道提出申请Req;若没有可用虚通道,则暂停提出申请,等待直至有所需虚通道变为可用再同上提出申请;
b)若申请被响应,则沿相应虚通道将消息传向邻近结点;若申请未被响应,则在下一拍重新执行同上述a)的操作,直至有申请被响应后将消息传向邻近结点。在每一中间结点上都重复执行上述操作,直至将消息传至目的结点。所谓最大间距输出虚通道选择策略是指在允许访问的通道中,对所在维的维间距(中间结点到目的结点)绝对值最大的虚通道首先提出申请,以缩小寻径区域。
VIN0中采用的平面自适应路由策略为:在n维mesh网络中,对每条物理通道的虚通道进行排序,用Ci,j表示第i维上的所有序号为j的虚通道构成的集合,它可分为正向的虚通道集合Ci,j 和逆向的虚通道集合Ci,j-平面自适应
路由算法定义n一1个自适应平面A0至An-1,每个平面由相邻二维上的虚通道构成:Ai=Ci,0 Ci 1,1 Ci 1,2,0≤i≤n-2。算法可分为两级(高层和低层):
高层算法:(在自适应平面之间)1) For i=0,i<(m-1),i do在A平面中自适应地路由消息趋近目的结点(见低层算法)end。2)在上述过程结束后,若消息还未到达目的结点,则通过An-2=Cn-1,0中的虚通道路由消息至目的结点。
低层算法(在自适平面内):
自适应平面A包含虚通道集合Ci,0,Ci 1,1和Ci 1,2在A内消息在第i维和第i 1维上趋近目的结点,自适应地路由。为避免死锁,将消息分为两类,一类是在路由过程中需增加第i维地址的称为增向消息,另一类需减小第i维地址的称为减向消息。同时,将A中的虚通道分成两个单独的虚拟子网:增向子网(包括虚通道集合Ci,0 和Ci 1,1)和减向子网(包括虚通道集合Ci,0-和Ci 1,2)。这样,增向消息在增向子网上路由,减向消息在减向子网上路由,每一消息都能在相应子网中自适应地趋近于目的结点。当消息到达的中间结点的第i维地址与目的结点的第i维地址相等时,在A内的路由过程结束,转向下一个高层步骤。