高级计算机体系结构 第六 互连与路由2

1、Parallel Computer Architecture并行计算机体系结构Lecture 6April 12, 2010 Wu junmin ()OverviewReview of Lec05MIN中的路由聚合通信支持栅栏同步硬件支持路由算法的分类确定性路由算法在任意节点对之间总是提供相同的路径不考虑网络的通信流量，当网络通信均匀的情况下性能一般较好，但不均匀时性能较差（尤其是一些非相邻节点之间频繁交换信息时）在虫孔交换网络中大量使用，便于硬件路由器实现通常为前进式和最短型的如维序路由:前进式路由算法每路由一步偏移量减1，当前维的偏移量为0后才计算下一维的偏移量XY路由/Internal是

2、连接本地节点的通道E-cube路由/firstone()返回第一个值为1的位死锁、活锁及饿死死锁避免定理路由算法使用路由函数和选择函数来描述，路由函数根据当前节点和目的节点提供一组输出通道；选择函数根据当前节点输出通道的状态，从路由函数提供的通道中选择一条空闲通道。路由函数决定路由算法是否是无死锁的，而选择函数只影响性能。通道相关：当一个报文占用一条通道，然后请求使用另一条通道时，这两条通道间就存在相关性。互连网络I的一个（确定性）路由函数R是无死锁的，当且仅当通道相关图D中没有环路。部分自适应路由算法在路由决策时要考虑网络的状态在源路由时通常意义不大，收集费时，信息可能过时分布式路由时通常只

3、考虑本地信息（从效率考虑）可分解为两个函数：路由和选择路由函数根据当前节点和目的节点提供一组输出通道选择函数根据当前节点输出通道的状态从路由函数提供的输出通道组中进行选择，进而选择一条空闲通道（如果有的话）提高了路由灵活性，但增加了硬件复杂度，更慢部分自适应算法只能使用路径集合中的一个子集灵活性与成本的折中通过增加适当的复杂度而获得全自适应路由的灵活性平面自适应路由针对n维网格和超立方体在同一时刻只在两维中提供自适应性，报文在一系列两维平面中进行自适应路由。因此，在报文向其目的地前进时，路由的维是不断变化的。转弯模型转弯模型中最基本的概念是禁止最小数量的转弯，防止环的出现，从而不会发生死锁。如

4、二维网格中西向优先算法最小西向优先算法Select()为选择函数，从通道集中选择一个空闲通道西向优先路由示例二维网格的转弯模型对于二维网孔，有8种可能的“转弯”，会形成两种简单的圈在二维网孔中，有16种方法可禁止两转弯（Two Turn），其中12种可以避免死锁，只有3种是独立的。 不能防止死锁的情况转弯模型P立方路由算法P立方路由算法：超立方体的部分自适应路由算法二元n立方体的源s=sn-1sn-2s0目的d=dn-1dn-2d0集合E由所有s和d有差别的维数组成，E分为两个不相交的子集E0和E1对于E中的所有i，如果si=0且di=1，则i E0，否则iE1P立方路由的基本概念就是将路由选

5、择分成两个阶段第一个阶段报文在E0中以任意维序路由第二个阶段在E1中以任意维序路由为什么无死锁可以派生出其它算法转弯模型=OverviewReview of Lec5MIN中的路由聚合通信支持栅栏同步硬件支持MIN中的阻塞N个处理器，每一级kxk开关之间恰好有N条链路，网络共有logkN级，其中每级具有N/k个开关。如果两对输入/输出路径经过同一中间链路或共享任意一个中间级的同一个输出，那么这两对输入输出路径就产生冲突。以Omega网络为例，假设网络是基于电路交换的Omega网络结构Omega中的地址映射考虑从Sn-1Sn-2S1S0 到dn-1dn-2d1d0建立一条电路经过第0级链路： S

6、n-1Sn-2S1S0-Sn-2Sn-3S1S0Sn-1作为第0级开关的输入地址，所以第0级开关必须将Sn-2Sn-3S1S0Sn-1 - Sn-2Sn-3S1S0Sn-1经过第1级链路： Sn-2Sn-3S1S0Sn-1-Sn-3Sn-4S0Sn-1Sn-2作为第1级开关的输入地址，所以第1级开关必须将Sn-3Sn-4S0S0-1Sn-2 - Sn-3Sn-4S0Sn-1Sn-2类似的有第i级开关的输出为Sn-i-2Sn-i-3S0Sn-1Sn-2Sn-i-1从而第n-1级开关的输出为Sn-1Sn-2S1S0最后一级连接为恒等排列，所以Sn-1Sn-2S1S0=dn-1dn-2d1d0从而有

7、Si=di所以第i级开关的输出为Sn-i-2Sn-i-3S0dn-1dn-2dn-i-1阻塞条件对于任意两个输入/输出对（S,D)和（R,T)，可以建立无冲突的两条路径的充要条件是：对于任意的i都有sn-i-2sn-i-3s0dn-1dn-2dn-i-1不等于rn-i-2rn-i-3r0tn-1tn-2tn-i-1将两个输入/输出对的地址级联在一起，将一个大小为n的窗口在两个输入/输出对上滑动，并对两个窗口中的内容进行比较。如果它们在任意点相等，那么两条路径在网络的某一级存在冲突。如（0110，1100） （1010，1111）有冲突 （0110，1100） （1110，1011）有冲突 （0

8、110，1100） （1010，1011）无冲突MIN的自路由算法Delta网络的自路由特性：允许根据目的地址做出路由决策，不必考虑源地址。自路由使用路由标志T=tn-1.t1t0执行，ti控制Gi级开关每一级路由标志都考虑哪一位是最低有效位，其最终映射到的目标地址的相应位为哪一位，从而ti等于目标地址中该位的值。在OMEGA网络中，在第i级开关最低有效位为第n-i-1位，并且最终映射到的目标地址中的对应位为第n-i-1位，所以ti=dn-i-1 0=i=n-1在蝶形MIN中，ti=di+1(0=i=n-2),tn-1=d0在立方体MIN中ti=?蝶式MIN中基于标志的路由OverviewRe

9、view of Lec5MIN中的路由聚合通信支持栅栏同步硬件支持聚合通信服务涉及全局数据迁移和全局控制的操作称为聚合通信，执行这些操作时会聚合地涉及到许多处理器。很多并行编程支持聚合通信，如HPF，MPI等很多科学应用需要，能简化并行编程聚合通信包括一组进程，通常称为一个进程组假设一个进程组G有n个进程P1,P2,Pn，所有进程都涉及到聚合通信多个点到点通信每个进程至多可以发送一个消息并至多接收一个消息如果每个进程都恰好发送一个消息并恰好接收一个消息，则总共有n!种排列或通信模式。一对全通信一个进程作为发送者，组中所有的进程都是接收者，包括两种不同的服务：广播：同一个消息从发送者发送到所有的

10、接收者散播：发送者向不同的接收者发送不同的消息，也称为私人化广播。多对一通信进程组中所有进程都是发送者，而只有一个进程被确定为唯一的接收者。包括：归约：来自不同发送者的不同消息结合在一起形成一条消息送往发送者。结合操作码通常是可交换或可结合的聚集: 来自不同发送者的不同消息级联在一起形成一条消息送往接收者。级联的顺序取决于发送者的ID多对多通信进程组中所有的进程执行各自的一对多通信，每个进程接收来自进程组内n个不同发送者的n个消息。包括：全广播：所有的进程都执行各自的广播，所有的进程都拥有同一组接收消息全散播：所有的进程执行各自的散播多播通信的评价标准通信量：消息从源发送到所有目的节点所使用的

11、通道数，包括某些重复使用的通道。时间：源发送第一个消息副本到最后一个目的节点接收完消息副本之间的时间。多播的硬件实现多地址编码多目的消息的消息头包含多个目的地址，好的多地址编码策略应能最小化消息头长度，减少消息头的处理时间全目的编码：所有的目的地址都包含在消息头中。单播的路由硬件可以用于多播消息消息头可以在地址微片一到达就马上处理只适合于地址数目较少的情形位串编码：每一位代表一个目的节点平均地址数目很大时有优势路由器通常需要缓冲整个位串以做出路由决策和产生输出位串地址解码不能使用和单播消息相同的硬件执行位串的长度通常取决于网络大小，限制了扩展性多地址编码方案多播的硬件实现基于树的多播路由尽可能

12、远地沿一条共用的路径传送消息，然后复制消息，再把副本传到结合一个特定目的节点集的不同通道上每个副本传送的路径可以按这种方式进一步分支，直到消息传到每个目的节点。目的节点可以是树的叶节点，也可以是树的中间节点网络中的每个节点都应该能够复制消息，把副本传送到不同的输出通道上超立方体中的广播树考虑一个n立方拓扑结构，该算法形成一棵生成二项式树，系统中的每个节点都在不超过n步的时间内恰好接收一次广播消息，令s为源节点的地址，v为接收广播消息的节点地址，FirstOne(d)表示一个n位二进制数d中最低有效位为1的位置(0到n-1）；若d=0，令Firstone(d)=n。4立方中的广播树XY多播路由模

13、式基于树的多播虫孔交换中的死锁由于路由器中没有消息缓冲，如果树的一个分支被阻塞，则所有的分支会被阻塞，进而可能导致死锁双通道XY多播虫孔路由该算法基于网络分割概念，一个多播操作由几个子多播操作实现，每个子多播以一个目的节点子集为目的，在不同的子网上路由。因为子网是不相交和无环的，不存在任何资源的环相关，该算法是无死锁的二维网格中的每条通道都加倍，网络被分成四个子网：N+x,+yN+x,-yN-x,+yN-x,-y,其中N+x,+y包含(i,j),(i,j+1)和(i,j),(i+1,j)的单向通道，以此类推。网络分割示意子网上的子多播对一个给定的多播，根据源节点u0与目的节点的相对位置，将目的

14、节点集D至多分成4个子集：D+x,+y、D+x,-y、D-x,+y、D-x,-y。集合D+x,+y包括u0右上方的目的节点，依次类推。这样多播最多被分成从u0到D+x,+y、D+x,-y、D-x,+y、D-x,-y的四个子多播， u0到D+x,+y的子多播在子网N+x,+y上使用XY路由实现，依次类推。多级网络中基于树的多播多播在某些交叉开关同时向几个输出端口发送微片，一次性通过网络在开关中复制消息可以是同步或异步同步复制时多目的消息的分支只有在所有请求的输出通道都有效时才能够前进，在某一个给定时刻，消息头都处于网络同一级的不同开关中。需要复杂的硬件信号传输机制，使微片传送变慢异步复制中每个分

15、支可以独立的传输，不用与其它分支保持一致死锁通过剪枝从死锁中恢复MIN中多目的消息的死锁MIN中利用剪枝恢复死锁基于路径的多播通信基于树的多播通信中任何一个分支被阻塞，整个树都会被阻塞。解决方法：阻止在中间节点的分支，形成多播路径模式为了减少多播路径的长度，目的节点集可以分成几个不相交的子集，源消息的副本可以在不相交的几条多播路径上传送，每条路径对应一个目的节点子集。这种多目的路由策略称为基于路径的路由。每个副本的消息头包含多个目的节点，源节点根据目的节点传输的顺序给目的地址安排一个次序表，只要消息注入网络，它就按照对应于第一个目的节点的地址路由，一旦消息头到达第一个目的节点路由器，路由器将包

16、含该地址的微片清除，然后消息按下一个头微片中的地址路由，该地址对应于次序表中的第二个目的节点。当消息到达最后一个目的节点时，将不再继续路由而被该节点完全吸收。基于哈密尔顿路径的路由函数一条哈密尔顿路径恰好能够访问图中每个节点一次。网络中的每个节点u根据在哈密尔顿路径上的位置都被指定一个标记l(u)，第一个节点标记为0，最后一个节点标记为N-1。高通道子网包括所有从低标记节点指向高标记节点的通道，低通道子网包括所有从高标记节点指向低标记节点的通道。在二维网格中，单播消息采用一条基于标记的路径来代替XY路由，如果目的节点的标记大于源节点的标记，则路由总在高通道子网上进行，否则将在低通道子网上进行。

17、二维网格节点标记法l(x,y)=yn+x y为偶数 =yn+n-x-1 y为奇数路由函数：假设当前节点为u，目的节点为v,定义R(u,v)=w，使w为u的邻居节点,并且l(w)=maxl(z):l(z)=l(v)，z为u的相邻节点,若l(u)=l(v)，z为u的相邻节点,若l(u)l(v)节点标记示意双路径多播路由把目的节点集分割成两个子集：DH和DL ,其中DH中每个节点的标记都比源节点的标记高， DL中每个节点的标记都比源节点低。从源节点发出的多播消息使用高通道网络向DH中的目的节点发送消息，使用低通道网络向DL中的目的节点发送消息。双路径多播路由的消息准备路径路由算法双路径多播路由示意多

18、路径多播路由多路径算法中将DH和DL进一步分割DH集被分成两个集合，分割节点的规则取决于源节点在网络中的位置和所用的标记方法，如(源节点为8时）：一个包含X坐标大于或等于源的节点，另一个包含DH中其它节点，DL类似分割。这样可以利用更多的路径来发送消息多路径多播路由的消息准备且l(v1)l(v2)多路径多播路由示意OverviewReview of Lec5MIN中的路由聚合通信支持栅栏同步硬件支持线性阵列的栅栏同步第一阶段用聚集消息实现报告，第二阶段使用广播消息实现唤醒结构支持路由器接口提供一组缓冲，可支持实现多个栅栏缓冲器包括：id位、加入位、到达位、聚集消息缓冲聚集广播消息中目的地址编码为位串通信序列执行栅栏x前，每个中间处理器要加入栅栏就会获得其路由器接口的x缓冲，并将相应的加入标志位置1、到达标志位清0。最右边的加入处理器发出一个同步id=x的聚集消息，该消息通过中间路由器接口时检查相应缓冲器x的加入标志和到达标志。如果处理器没有加入，则消息继续前进如果处理器已经加入并且已经到达同步点，则消息继续前进如果处理器已经加入但没有到达同步点，则消息阻塞在相应的路由器接口上。此时消息保存在缓冲器x的“消息”域中，直到到达标志被处理器置为1。然后聚集消息再次发往网络最后这个聚集消息被最左边的加入处理器吸收聚集阶段结束后，最左边的处理器发出一个广播消息，该消息通过中