并行计算(中科大讲义)

并行计算——结构•算法•编程国家高性能计算中心（合肥）22020/1/31并行计算——结构•算法•编程第一篇并行计算的基础第一章并行计算机系统及其结构模型第二章当代并行机系统：SMP、MPP和Cluster第三章并行计算性能评测第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程国家高性能计算中心（合肥）32020/1/31并行计算——结构•算法•编程第三篇并行数值算法第八章基本通信操作第九章稠密矩阵运算第十章线性方程组的求解第十一章快速傅里叶变换第四篇并行程序设计第十二章并行程序设计基础第十三章并行程序设计模型和共享存储系统编程第十四章分布存储系统并行编程第十五章并行程序设计环境与工具国家高性能计算中心（合肥）42020/1/31第一章并行计算机系统及结构模型1.1并行计算1.1.1并行计算与计算科学1.1.2当代科学与工程问题的计算需求1.2并行计算机系统互连1.2.1系统互连1.2.2静态互联网络1.2.3动态互连网络1.2.4标准互联网络1.3并行计算机系统结构1.3.1并行计算机结构模型1.3.2并行计算机访存模型国家高性能计算中心（合肥）52020/1/31并行计算并行计算：并行机上所作的计算，又称高性能计算或超级计算。计算科学：计算物理、计算化学、计算生物等科学与工程问题的需求：气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。需求类型：计算密集、数据密集、网络密集。美国HPCC计划：重大挑战性课题，3T性能美国Petaflops研究项目：Pflop/s。美国ASCI计划：核武器数值模拟。国家高性能计算中心（合肥）62020/1/31高性能计算机Intel（OptionRed)：1Tflops,1997,PentiumProSGI(OptionBlueMountain):3Tflops,1998,MIPS10000IBM(OptionWhite):7Tflops,Top4,2001,Power3日本EarthSimulator:35Tflops,Top1,2002,VPHewlett-PackardASCIQ：7Tflops,Top2,3,2002,AlphaServer中国联想：1Tflops,Top43,2002国家高性能计算中心（合肥）72020/1/31系统互连不同带宽与距离的互连技术:总线、SAN、LAN、MAN、WAN局部总线I/O总线SCIHiPPIMyrinet千兆位以太网光纤通道快速以太网以太网10BaseTFDDIATM总线或开关SANLANMANWAN100Gb/s10Gb/s1Gb/s100Mb/s10Mb/sIsoEnet网络带宽交叉开关MIN或100BaseT国家高性能计算中心（合肥）82020/1/31局部总线、I/O总线、SAN和LANPMI/O桥磁盘SAN(e.g.Myrinet)LAN(e.g.以太网,FDDI)系统III/O总线,接口系统I处理器总线局部总线,存储器总线SCSI节点2节点N系统总线节点1国家高性能计算中心（合肥）92020/1/31网络性能指标节点度（NodeDegree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（NetworkDiameter）：网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度（BisectionWidth）：对分网络各半所必须移去的最少边数对剖带宽（BisectionBandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称网络为对称的（Symmetry）国家高性能计算中心（合肥）102020/1/31静态互连网络与动态互连网络静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。国家高性能计算中心（合肥）112020/1/31静态互连网络（1）一维线性阵列（1-DLinearArray）：并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为（双向环）或为N-1（单向环），对剖宽度为22/N国家高性能计算中心（合肥）122020/1/31静态互连网络（2）二维网孔（2-DMesh）：每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为，对剖宽度为在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为，而对剖宽度为垂直和水平方向均带环绕，则变成了2-D环绕（2-DTorus），节点度恒为4，网络直径为，对剖宽度为)1(2NN1NN22/2NN2NN(a)2-D网孔(b)Illiac网孔(c)2-D环绕国家高性能计算中心（合肥）132020/1/31静态互连网络（3）二叉树：除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。1log2N2/N(a)二叉树(b)星形连接(c)二叉胖树国家高性能计算中心（合肥）142020/1/31静态互连网络（4）超立方：一个n-立方由个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。n-立方的节点度为n，网络直径也是n，而对剖宽度为。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。nN22/N(b)4-立方(a)3-立方(c)顶点代之以环(d)3-立方环国家高性能计算中心（合肥）152020/1/31嵌入将网络中的各节点映射到另一个网络中去用膨胀（Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数如果该系数为1，则称为完美嵌入。环网可完美嵌入到2-D环绕网中超立方网可完美嵌入到2－D环绕网中国家高性能计算中心（合肥）162020/1/31嵌入10001001101110101100110111111110010001010111011000000001001100100101010000000001011101100010001111011100100010011111111010101011国家高性能计算中心（合肥）172020/1/31网络名称网络规模节点度网络直径对剖宽度对称链路数线性阵列21非环形2（双向）2是2-D网孔4非Illiac网孔4非2-D环绕4是二叉树31非星形2非超立方nn是立方环3是NNNNNNNNNNnN2kkN21N1N2/N)1(2N1N2/2N1log2N2/12kkNN2N22/N2/N)2/(kN1NN)(2NNN2N21N1N2/nN2/3N静态互连网络特性比较国家高性能计算中心（合肥）182020/1/31动态互连网络(1)总线：PCI、VME、Multics、Sbus、MicroChannel多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等LMIOC本地总线高速缓存CPUIFIFIF存储器总线存储器单元IFIFCPU板存储器板I/O板通信板系统总线(底板上)数据总线缓冲CCIOP数据总线网络(以太网等)磁盘和磁带部件打印机或绘图仪本地外围设备(SCSI总线)MCIF缓冲国家高性能计算中心（合肥）192020/1/31动态互连网络（2）交叉开关（Crossbar）：单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。国家高性能计算中心（合肥）202020/1/31动态互联网络（3）单级交叉开关级联起来形成多级互连网络MIN（MultistageInterconnectionNetwork）0101010101010101(a)4种可能的开关连接000001010011100101110111输入000001010011100101110111输出第0级第1级第2级(b)一种8输入的Omega网络国家高性能计算中心（合肥）212020/1/31动态互连网络（4）交换开关模块：一个交换开关模块有n个输入和n个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突级间互连（InterstageConnection）：均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接n输入的Ω网络需要级开关，在Ilinois大学的Cedar[2]多处理机系统中采用了Ω网络CrayY/MP多级网络，该网络用来支持8个向量处理器和256个存储器模块之间的数据传输。网络能够避免8个处理器同时进行存储器存取时的冲突。n2log22国家高性能计算中心（合肥）222020/1/31动态互连网络比较n,节点规模w，数据宽度动态互连网络的复杂度和带宽性能一览表网络特性总线系统多级互连网络交叉开关硬件复杂度每个处理器带宽～报道的聚集带宽SunFire服务器中的Gigaplane总线：2.67GB/sIBMSP2中的512节点的HPS：10.24GB/sDigital的千兆开关：3.4GB/s)(wnO))log((wnnOk)(2wnO)/(nwfO)(wfO)(wfO)(wfO国家高性能计算中心（合肥）232020/1/31标准互联网络（1）Myrinet:Myrinet是由Myricom公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系统互连成为一种商业产品。Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及在南加州大学开发的ATOMIC/LAN技术。Myrinet能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。Myrinet在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上，Myrinet网使用全双工SAN链路，最长可达3米，峰值速率为（1.28＋1.28）Gbps（目前有2.56+2.56)Myrinet交换开关:8,12,16端口Myrinet主机接口:32位的称作LANai芯片的用户定制的VLSI处理器，它带有Myrinet接口、包接口、DMA引擎和快速静态随机存取存储器SRAM。140oftheNovember2002TOP500useMyrinet,including15ofthetop100国家高性能计算中心（合肥）242020/1/31Myrinet连接的LAN/Cluster交换开关交换开关交换开关交换开关桌面主机机箱内多计算机机群多处理机机群网络RAM和VME单板磁盘国家高性能计算中心（合肥）252020/1/31标准互连网络（2)高性能并行接口（HiPPI）LosAl