2.5虚信道和虚网络 双环路由 ·上述每一个单向信道增加一个虚信道的方法叫 双环路由 ·形式化地描述双环路由： ·假定 使用n个进程：Pn-1,Pn-2,.P1,Po, 信道是Ch或C:
2.5虚信道和虚网络 双环路由 ⚫ 上述每一个单向信道增加一个虚信道的方法叫 双环路由 ⚫ 形式化地描述双环路由： ⚫ 假定 使用n个进程：Pn-1 ,Pn-2 ,…P1 , P0， 信道是Ch或Cl：
2.5虚信道和虚网络 双环路由算法 P(-1)= *[initiate a routing→ I send (m,des)to Ca(n-1) 口send(t,des）toC(n-l) receive(m,des）from Cho-→ 【Pa-1=des-→send(m)to local processor oP-1≠cdes→send(mn,des)toCr(n-l) 1 P(i:0.n-2）= *initiate a routing true-send (m,des)to Chi ▣i>des→send(m,de.s)toCi receive(m,des)from Ch(i+l)(orC(i+y）→ Pi=des send (m)to local processor □P≠des→send(m,des)to Cha(orCi) 1
2.5虚信道和虚网络 双环路由算法
2.5虚信道和虚网络 双环路由 ●在上述算法中，当进程发起路由时， 。如果i>des,可以使用高信道或者低信道。 如果i<des,则侧只能使用高信道
2.5虚信道和虚网络 双环路由 ⚫ 在上述算法中，当进程发起路由时， ⚫ 如果i > des ，可以使用高信道或者低信道。 ⚫ 如果i < des ，则只能使用高信道
2.6完全自适应和无死锁路由算法 适应性和无死锁是两个互相矛盾的要求。 像2维网格的XY路由和n维立方的e-立方等决定性的 无死锁路由虽然简单，但都不是适应性的。 ·一个决定性路由在存在错误组件（如链接或节点）的 系统中有可能失效 。例如，一个XY路由完成了X方向的路由，但在Y方向 上由于错误被阻塞，这个信息就不能被继续转发 但没有限制的适应性路由可能引发死锁。 。因此，必须在不发死锁的前提下增加适应性
2.6 完全自适应和无死锁路由算法 ⚫ 适应性和无死锁是两个互相矛盾的要求。 ⚫ 像2 维网格的XY路由和n维立方的e-立方等决定性的 无死锁路由虽然简单，但都不是适应性的。 ⚫ 一个决定性路由在存在错误组件（如链接或节点）的 系统中有可能失效 ⚫ 例如，一个XY路由完成了X方向的路由，但在Y方向 上由于错误被阻塞，这个信息就不能被继续转发 ⚫ 但没有限制的适应性路由可能引发死锁。 ⚫ 因此，必须在不引发死锁的前提下增加适应性
2.6完全自适应和无死锁路由算法 几乎所有的完全适应性路由都可以通过增加 定数量的虚信道（或虚网络）来避免死锁。 例如， 一个最小化的适应性的n维立方路由可以通过加入n 个虚信道来避免死锁。 每一步都使用比前一个具有更高标记的信道 因为需要n步，所以n个虚信道足以避免虚信道之间的 循环等待。 然而使用虚信道会引入附加的缓冲区等开销。 所以，要尽量限制虚信道的数目
2.6 完全自适应和无死锁路由算法 ⚫ 几乎所有的完全适应性路由都可以通过增加一 定数量的虚信道（或虚网络）来避免死锁。 ⚫ 例如， ⚫ 一个最小化的适应性的n 维立方路由可以通过加入n 个虚信道来避免死锁。 ⚫ 每一步都使用比前一个具有更高标记的信道。 ⚫ 因为需要n步，所以n个虚信道足以避免虚信道之间的 循环等待。 ⚫ 然而使用虚信道会引入附加的缓冲区等开销。 所以，要尽量限制虚信道的数目