2.6.2逃逸信道 混合路由(cont'd) ●混合路由算法： 1.开始时，使用完全适应路由，直到阻塞为止； 2.然后切换到限制性路由。 ·混合路由是无死锁的 。由于等待信道是在无死锁路由中定义的，并且 ●) 消息仅仅等待上述等待信道 ● 合理分配等待和非等待信道是关系到混合路由效率 的关键问题
2.6.2 逃逸信道 混合路由（cont'd） ⚫ 混合路由算法： 1. 开始时，使用完全适应路由，直到阻塞为止； 2. 然后切换到限制性路由。 ⚫ 混合路由是无死锁的 ⚫ 由于等待信道是在无死锁路由中定义的，并且 ⚫ 消息仅仅等待上述等待信道 ⚫ 合理分配等待和非等待信道是关系到混合路由效率 的关键问题
2.6.2逃逸信道 混合路由的扩展！ 。扩展引：当消息发现等待信道被占用时，可以使用非等 待信道 。扩展增加灵活性的同时也引入了选定的逃逸信道之间新的依 赖性。 通过使用一个或多个中间的一般信道，一个逃逸信道可能间 接地依赖于另一个逃逸信道。 ● 因此无回路条件必须包括逃逸信道之间的所有间接依赖。 ● 不幸的是，没有循环依赖只是不发生死锁的一个充分 条件；也即，对于一个特定的虫孔网络，若使用某 个路由算法，扩展太弱，不会得到任何结果。扩展信 道依赖图中的一个回路可能表示一个死锁状态，也可 能不是
2.6.2 逃逸信道 混合路由的扩展I ⚫ 扩展I：当消息发现等待信道被占用时，可以使用非等 待信道 ⚫ 扩展I增加灵活性的同时也引入了选定的逃逸信道之间新的依 赖性。 ⚫ 通过使用一个或多个中间的一般信道，一个逃逸信道可能间 接地依赖于另一个逃逸信道。 ⚫ 因此无回路条件必须包括逃逸信道之间的所有间接依赖。 ⚫ 不幸的是，没有循环依赖只是不发生死锁的一个充分 条件；也即，对于一个特定的虫孔网络，若使用某一 个路由算法，扩展I太弱，不会得到任何结果。扩展信 道依赖图中的一个回路可能表示一个死锁状态，也可 能不是
2.6.2逃逸信道 混合路由的扩展I川 ●Duato通过使用基于消息日标的逃逸路径进一 步扩展了上述思想 。对于不同的目标，使用不同的逃逸信道。 在同样的无回路条件下，可以得到一个无死锁 的充分必要条件 然而，在生成扩展信道依赖图的时候，直接依 赖、间接依赖、直接交叉依赖（在不同目标的 逃逸信道之间)和间接交叉依赖都要被考虑进 去
2.6.2 逃逸信道 混合路由的扩展I I ⚫ Duato通过使用基于消息目标的逃逸路径进一 步扩展了上述思想 ⚫ 对于不同的目标，使用不同的逃逸信道。 ⚫ 在同样的无回路条件下，可以得到一个无死锁 的充分必要条件。 ⚫ 然而，在生成扩展信道依赖图的时候，直接依 赖、间接依赖、直接交叉依赖（在不同目标的 逃逸信道之间）和间接交叉依赖都要被考虑进 去
2.6.2逃逸信道 ● 上述两个扩展都可用于避免死锁。 为了设计一个无死锁的路由函数，首先创建 一 个名为R1(仪，y)的路由子函数，它的功能是将当 前和目标节点映射到当前节点的输出信道的子 集。R(x,y)是连通的，无回路的。可以通过增 加信道或者将己有信道分割为虚信道将R1(仪，y) 扩展为R(仪，y),以便增加可选路径的数日，同 时又不会在R(xy)的扩展信道依赖图中增加回 路 。这一设计规程又被称为Duato协议
2.6.2 逃逸信道 ⚫ 上述两个扩展都可用于避免死锁。 ⚫ 为了设计一个无死锁的路由函数，首先创建一 个名为R1 (x,y)的路由子函数，它的功能是将当 前和目标节点映射到当前节点的输出信道的子 集。R1 (x,y)是连通的，无回路的。可以通过增 加信道或者将已有信道分割为虚信道将R1 (x,y) 扩展为R(x,y)，以便增加可选路径的数目，同 时又不会在R1 (x,y)的扩展信道依赖图中增加回 路。 ⚫ 这一设计规程又被称为Duato协议
2.6.2逃逸信道 维度逆转路由 如果不要求最小路由，那么虚信道的数量还可以 减少。 。对于一个k元维立方（没有环绕连接），有如下 的一般非最小无死锁路由： 。对每个物理信道，有k个虚信道与之对应 ·其中一个用于逃逸信道，以便进行无死锁的按维排序的路由 。消息可以按照任何方向路由，而不一定是最小路径。 ·每个消息都有一个维度逆转数DR相对应， ·DR:记录消息从高维度路由到低维度的次数
2.6.2 逃逸信道 维度逆转路由 ⚫ 如果不要求最小路由，那么虚信道的数量还可以 减少。 ⚫ 对于一个k元n维立方（没有环绕连接），有如下 的一般非最小无死锁路由： ⚫ 对每个物理信道，有k个虚信道与之对应 ⚫ 其中一个用于逃逸信道，以便进行无死锁的按维排序的路由 ⚫ 消息可以按照任何方向路由，而不一定是最小路径。 ⚫ 每个消息都有一个维度逆转数DR相对应， ⚫ DR：记录消息从高维度路由到低维度的次数