并行计算Parallel Computing.ppt
并行计算ParallelComputing,主讲人徐云Spring,2019,国家高性能计算中心（合肥）,2,并行计算结构算法编程,第一篇并行计算的基础第一章并行计算与并行计算机结构模型第二章并行计算机系统互连第三章典型并行计算机系统介绍第四章并行计算性能评测,国家高性能计算中心（合肥）,3,第二章并行机系统互连与基本通信操作,2.1并行计算机互连网络2.1.1系统互连2.1.2静态互连网络2.1.3动态互连网络2.1.4标准互连网络,国家高性能计算中心（合肥）,4,系统互连,不同带宽与距离的互连技术:总线、SAN、LAN、MAN、WAN,国家高性能计算中心（合肥）,5,局部总线、I/O总线、SAN和LAN,国家高性能计算中心（合肥）,6,网络性能指标,节点度（NodeDegree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（NetworkDiameter）：网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度（BisectionWidth）：对分网络各半所必须移去的最少边数对剖带宽（BisectionBandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称网络为对称的（Symmetry）,国家高性能计算中心（合肥）,7,静态互连网络与动态互连网络,静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。,国家高性能计算中心（合肥）,8,静态互连网络（1）,一维线性阵列（1-DLinearArray）：并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为（双向环）或为N-1（单向环），对剖宽度为2,国家高性能计算中心（合肥）,9,静态互连网络（2）,二维网孔（2-DMesh）：每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为，对剖宽度为在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为，而对剖宽度为垂直和水平方向均带环绕，则变成了2-D环绕（2-DTorus），节点度恒为4，网络直径为，对剖宽度为,国家高性能计算中心（合肥）,10,静态互连网络（3）,二叉树：除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为如果尽量增大节点度数，则直径缩小为2，此时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。,国家高性能计算中心（合肥）,11,静态互连网络（4）,超立方：一个n-立方由个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。n-立方的节点度为n，网络直径也是n，而对剖宽度为。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。,国家高性能计算中心（合肥）,12,嵌入（1）,将网络中的各节点映射到另一个网络中去用膨胀（Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数如果该系数为1，则称为完美嵌入。环网可完美嵌入到2-D环绕网中超立方网可完美嵌入到2D环绕网中,国家高性能计算中心（合肥）,13,嵌入（2）,国家高性能计算中心（合肥）,14,静态互连网络特性比较,国家高性能计算中心（合肥）,15,动态互连网络(1),总线：PCI、VME、Multibus、Sbus、MicroChannel多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等,国家高性能计算中心（合肥）,16,动态互连网络（2）,交叉开关（Crossbar）：单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。,国家高性能计算中心（合肥）,17,动态互联网络（3）,单级交叉开关级联起来形成多级互连网络MIN（MultistageInterconnectionNetwork）,国家高性能计算中心（合肥）,18,动态互连网络（4）,交换开关模块：一个交换开关模块有n个输入和n个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突级间互连（InterstageConnection）：均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接n输入的网络需要级开关，在Illinois大学的Cedar2多处理机系统中采用了网络CrayY/MP多级网络，该网络用来支持8个向量处理器和256个存储器模块之间的数据传输。网络能够避免8个处理器同时进行存储器存取时的冲突。,国家高性能计算中心（合肥）,19,动态互连网络比较,n，节点规模w，数据宽度,国家高性能计算中心（合肥）,20,标准互连网络（1）,光纤通道FC（FiberChannel）:通道和网络标准的集成光纤通道既可以是共享介质，也可以是一种交换技术光纤通道操作速度范围可从100到133、200、400和800Mbps。FCSI厂商也正在推出未来具有更高速度（1、2或4Gbps）的光纤通道光纤通道的价值已被现在的某些千兆位局域网所证实，这些局域网就是基于光纤通道技术的连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、仲裁环及交换光纤连接FDDI:光纤分布式数据接口FDDI（FiberDistributedDataInterface）FDDI采用双向光纤令牌环可提供100-200Mbps数据传输速率FDDI具有互连大量设备的能力传统的FDDI仅以异步方式操作,国家高性能计算中心（合肥）,21,双向FDDI环作为主干网,国家高性能计算中心（合肥）,22,标准互连网络（2),快速以太网已经历了4代：第一代，1982年引入的10Mbps第二代，1994年宣布的100Mbps第三代，1997年IEEE802.3工作组宣布的1Gbps第四代，2002年IEEE802.3ae通过的10Gbps，并且2010年6月IEEE802.3ba公布了40-100Gbps,国家高性能计算中心（合肥）,23,标准互联网络（3）,Myrinet:Myrinet是由Myricom公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系统互连成为一种商业产品。Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及在南加州大学开发的ATOMIC/LAN技术。Myrinet能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。Myrinet在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上，Myrinet网使用全双工SAN链路，最长可达3米，峰值速率为（1.281.28）Gbps（目前有2.56+2.56)Myrinet交换开关:8,12,16端口Myrinet主机接口:32位的称作LANai芯片的用户定制的VLSI处理器，它带有Myrinet接口、包接口、DMA引擎和快速静态随机存取存储器SRAM。140oftheNovember2002TOP500useMyrinet,including15ofthetop100,国家高性能计算中心（合肥）,24,Myrinet连接的LAN/Cluster,国家高性能计算中心（合肥）,25,标准互联网络（4）,InfiniBandIntel及IBM、Compaq、HP等分别提出了“下一代I/O”和“未来I/O”技术，这就是放弃了总线结构的新I/O规范：InfiniBand。集合了整个业界的努力开发的，能够替代PCI总线的新标准。InfiniBand体系结构的第一个版本，于2000年10月发布是一种交换式通信结构，包括分层结构、基于信息包的通信机制、3种连接速度等技术。具体结构参见图2.16和图2.17.,国家高性能计算中心（合肥）,26,标准互连网络（5）,国家高性能计算中心（合肥）,27,Activity,问题1:画出8个节点的超立方一维组织方式。问题2:如何设计一个222个处理器的度数均衡互连网络(节点度数均衡是指度数至多差1)，用最少的连边数获得度数小于等于3的互连网络并使网络直径最小?,
