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