并行计算多媒体课件并行体系结构.ppt

《并行计算多媒体课件并行体系结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ParallelComputerArchitecture并行计算机体系结构Lecture7OverviewReviewofLec5选路与死锁流量控制交换开关的设计ReviewofLec6互连网络静态互连一维、二维Mesh、超立方、树动态互连总线、交叉开关、MIN机群互连技术Myrinet、HiPPI、FC、ATM、SCI、以太网OverviewReviewofLec5选路与死锁流量控制交换开关的设计存储转发选路存储转发SF(Store-and-Forward)网络：消息是基本的传输单位。在传输过程中，中间节点必须收齐消息且存储在缓冲区中后，它才可能传向下一节点。

2、ts是启动时间(包括打包、执行选路算法和建立通信界面的时间)，th是节点延迟时间（即消息穿越网络中两直接相连的处理器所需的时间）,与交换开关内选路时间直接相关tw是传输每个字的时间（它是带宽的倒数）。对于长度为m的消息，穿越l条链路，在存储转发的网络中总通信时间为：tcomm(SF)=ts+(mtw+th)lth远小于mtwtcomm(SF)=ts+mltw包路由（PackRouting)消息：节点间通信的逻辑单位，由一些定长的（信）包(也叫报文，Packet)组成信包：带有选路信息的基本通信单位。包路由（PackRouting)包路由非常适合动态、错误率较高的局域

3、网或广域网，因为不同的包可以选择不同的路由，重传代价也较小。包路由延迟启动时间ts假设路由表是静态的，所有的包经过同样的路径消息分成包，每个包包含数据、路由信息、校验码、序列号等，长度为（r+s)打包时间与消息长度成正比，令其为mtw1网络传输一个字的时间为tw2包经过每个中间交换开关的时间为th每个包共经过l个链路第一个包经过网络的时间为:thl+tw2(r+s)以后每经过tw2(r+s)时间就会通过一个包，故总时间为tcomm=ts+mtw1+thl+tw2(r+s)+(m/r-1)tw2(r+s)=ts+mtw1+thl+mtw2+s/rmtw2=ts+thl

4、+twm其中tw=tw1+tw2(1+s/r)切通CT(Cut-Through)网络在并行计算机，由于网络可靠性较高，可对包路由进一步限制，减少包交换的开销：所有的包经过同样的链路，消除每个包的路有信息开销强制按序发包，消除包序列号的开销校验信息加在消息级，消除包校验的开销这就是切通CT(Cut-Through)网络：将消息分成固定大小的更小的片(数据片和包头)进行传输，这些片的大小要远小于包，由于没有信包的开销。典型大小为4到32字节虫蚀(Wormhole)选路是切通选路的一种形式。在传输过程中，中间节点只备有很小的片缓冲区，一旦收到整个片就传至下一节点。同一消息

5、中的所有片一同以流水线方式穿越网络，整个消息犹如一列火车，由火车头（消息头）牵引着车厢（数据片）顺序前进。对于长度为m的消息，穿越l条链路，在切通网络中总通信时间为：tcomm(CT)=ts+mtw+lthSF和CT选路的时间比较简化的性能模型在并行机通信中，l通常较小，th或者小于ts(对于短消息），或者小于mtw(对于长消息），因此通常可简化tcomm=ts+twm有助于体系结构无关的算法设计对于性能预测，如果没有网络阻塞情况出现，通常是正确的。对于由网络阻塞的情况，可用有效带宽代替tw。如：Mesh中，仅相邻节点间通信，那么通信时间为ts+twm，符合我们的公

6、式如果节点间存在随机通信，经过一个对剖平面(p1/2条链路）最多可能有p/4个双向通信，那么每个链路上有p1/2/4个消息，时间为ts+twmp1/2/4。选路算法在并行机中决定消息从源节点发送到目的节点的路径输入源和目的节点输入网络的当前状态输出一条或多条路经最小选路（Minimal):总是选择源和目的间的一条最短路径。每一条链路都离目的更近了，但可能会导致拥挤非最小选路：可能会为了避免拥塞选择一条较远的路。选路算法（算术选路）维序选路：在二维网孔中选路时，首先沿X维方向确定路径，然后再沿Y维方向确定路径（X-Y选路）选路算法（算术选路）E-立方选路法(1)for

7、i=1tondo/*计算方向位*/ri=si-1⊕di-1/*⊕为异-或运算符*/endfor(2)i=1,V=S/*初始化*/(3)whilei≤ndo(3.1)ifri=1then从当前节点V选路到节点V⊕2i-1(3.2)i=i+1endwhile选路算法源选路算法：源节点为消息建立一个头部，其中包含选路路径上经过的所有交换开关的输出端口。消息路径的各个交换开关简单地从消息头中取出端口号并将消息传递到相应的通道。相对简单的开关设计缺点是可能使得消息头过大，而且长度不固定。用于MITParc和Arctic路由器，MeikoCS-2以及Myrinet上查表选路