4.5虚信道和虚网络 双环路由 。上述每一个单向信道增加一个虚信道的方法叫 双环路由 ·形式化地描述双环路由： 。假定 使用n个进程：Pn1,Pn-2.P1,Po: 信道是Ch或C: 17/83
17/83 4.5虚信道和虚网络 双环路由 ⚫ 上述每一个单向信道增加一个虚信道的方法叫 双环路由 ⚫ 形式化地描述双环路由： ⚫ 假定 使用n个进程：Pn-1 ,Pn-2 ,…P1 , P0， 信道是Ch或Cl：
4.5虚信道和虚网络 双环路由算法 P(-1)= *initiate a routing [ send (m,des)to Ca(n-1) 任选高信道或低信道 口send(,des）toCi(n-l) receive(m,des)from Cho→只可能从高信道接收消息 Pn-1=des-send (m)to local processor oPt-:≠des→send(m,des)toCn-) 在非目标节点的情况下，一定切换到低信道 P(i:0.n-2)= *initiate&routing→ true-send (m,des)to Chi 总是可以走高信道 ▣i>des→send(m,des)to Cu 仅当源大于目标时，才可走低信道 Oreceive(m,des)from Ch(i+)(orC(i+l)）→ Pi des send (m)to local processor OP≠des→send(m,des)to Ch:(orCi) 在非目标节点的情况下，高→高，低→低 18/83
18/83 4.5虚信道和虚网络 双环路由算法 总是可以走高信道 仅当源大于目标时，才可走低信道 任选高信道或低信道 在非目标节点的情况下，一定切换到低信道 只可能从高信道接收消息 在非目标节点的情况下，高→高，低→低
4.6完全自适应和无死锁路由算法 适应性和无死锁是两个互相矛盾的要求。 像2维网格的XY路由和n维立方的e-立方等决定性的 无死锁路由虽然简单，但都不是适应性的。 ·一个决定性路由在存在错误组件（如链接或节点)的 系统中有可能失效 。例如，一个XY路由完成了X方向的路由，但在Y方向 上由于错误被阻塞，这个信息就不能被继续转发 但没有限制的适应性路由可能引发死锁。 。因此，必须在不引发死锁的前提下增加适应性 19/83
19/83 4.6 完全自适应和无死锁路由算法 ⚫ 适应性和无死锁是两个互相矛盾的要求。 ⚫ 像2维网格的XY路由和n维立方的e-立方等决定性的 无死锁路由虽然简单，但都不是适应性的。 ⚫ 一个决定性路由在存在错误组件（如链接或节点）的 系统中有可能失效 ⚫ 例如，一个XY路由完成了X方向的路由，但在Y方向 上由于错误被阻塞，这个信息就不能被继续转发 ⚫ 但没有限制的适应性路由可能引发死锁。 ⚫ 因此，必须在不引发死锁的前提下增加适应性
4.6完全自适应和无死锁路由算法 。几乎所有的完全适应性路由都可以通过增加 定数量的虚信道（或虚网络） 来避免死锁。 例如，一个最小化的适应性的n维立方路由可以 通过加入个虚信道来避免死锁 。每一步都使用比前一个具有更高标记的信道。 因为最多需要n步，所以n个虚信道足以避免虚信道之 间的循环等待 然而使用虚信道会引入附加的缓冲区等开销。 所以，要尽量限制虚信道的数目。 20/83
20/83 4.6 完全自适应和无死锁路由算法 ⚫ 几乎所有的完全适应性路由都可以通过增加一 定数量的虚信道（或虚网络）来避免死锁。 ⚫ 例如，一个最小化的适应性的n维立方路由可以 通过加入n个虚信道来避免死锁。 ⚫ 每一步都使用比前一个具有更高标记的信道。 ⚫ 因为最多需要n步，所以n个虚信道足以避免虚信道之 间的循环等待。 ⚫ 然而使用虚信道会引入附加的缓冲区等开销。 所以，要尽量限制虚信道的数目
4.6.1虚信道类 如前所述，通过引入足够多的虚信道，任何路 由都可以保证避免死锁。 当路由开始时，使用虚信道1，VC1。 。在第ⅰ步使用虚信道i,VC及相应的链接。 如果一个给定网络的最长路径（也叫直径)是Dmax, 那么就要用Dmax个虚信道； 21/83
21/83 4.6.1 虚信道类 ⚫ 如前所述，通过引入足够多的虚信道，任何路 由都可以保证避免死锁。 ⚫ 当路由开始时，使用虚信道1，vc1。 ⚫ 在第i 步使用虚信道i，vci及相应的链接。 ⚫ 如果一个给定网络的最长路径（也叫直径）是Dmax， 那么就要用Dmax个虚信道；