01-第01章-并行计算机系统及其结构模型-并行计算的基础-并行计算(共15章)

并行计算————结构结构••算法算法••编程编程国家高性能计算中心（合肥）22013/7/24Wednesday并行计算——结构•算法•编程第一篇第一篇并行计算的基础并行计算的基础第一章第一章并行计算机系统及其结构模型并行计算机系统及其结构模型第二章第二章当代并行机系统：当代并行机系统：SMPSMP、、MPPMPP和和ClusterCluster第三章第三章并行计算性能评测并行计算性能评测第二篇第二篇并行算法的设计并行算法的设计第四章第四章并行算法的设计基础并行算法的设计基础第五章第五章并行算法的一般设计方法并行算法的一般设计方法第六章第六章并行算法的基本设计技术并行算法的基本设计技术第七章第七章并行算法的一般设计过程并行算法的一般设计过程国家高性能计算中心（合肥）32013/7/24Wednesday并行计算——结构•算法•编程第三篇第三篇并行数值算法并行数值算法第八章第八章基本通信操作基本通信操作第九章第九章稠密矩阵运算稠密矩阵运算第十章第十章线性方程组的求解线性方程组的求解第十一章第十一章快速傅里叶变换快速傅里叶变换第四篇第四篇并行程序设计并行程序设计第十二章第十二章并行程序设计基础并行程序设计基础第十三章第十三章并行程序设计模型和共享存储系统编程并行程序设计模型和共享存储系统编程第十四章第十四章分布存储系统并行编程分布存储系统并行编程第十五章第十五章并行程序设计环境与工具并行程序设计环境与工具国家高性能计算中心（合肥）42013/7/24Wednesday第一章并行计算机系统及结构模型1.11.1并行计算并行计算1.1.11.1.1并行计算与计算科学并行计算与计算科学1.1.21.1.2当代科学与工程问题的计算需求当代科学与工程问题的计算需求1.21.2并行计算机系统互连并行计算机系统互连1.2.11.2.1系统互连系统互连1.2.21.2.2静态互联网络静态互联网络1.2.31.2.3动态互连网络动态互连网络1.2.41.2.4标准互联网络标准互联网络1.31.3并行计算机系统结构并行计算机系统结构1.3.11.3.1并行计算机结构模型并行计算机结构模型1.3.21.3.2并行计算机访存模型并行计算机访存模型国家高性能计算中心（合肥）52013/7/24Wednesday并行计算并行计算：并行机上所作的计算，又称高性能并行计算：并行机上所作的计算，又称高性能计算或超级计算。计算或超级计算。计算科学：计算物理、计算化学、计算生物等计算科学：计算物理、计算化学、计算生物等科学与工程问题的需求：气象预报、油藏模拟、科学与工程问题的需求：气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。核武器数值模拟、航天器设计、基因测序等。需求类型：计算密集、数据密集、网络密集。需求类型：计算密集、数据密集、网络密集。美国美国HPCCHPCC计划：重大挑战性课题，计划：重大挑战性课题，33TT性能性能美国美国PetaflopsPetaflops研究项目：研究项目：Pflop/sPflop/s。。美国美国ASCIASCI计划：核武器数值模拟。计划：核武器数值模拟。国家高性能计算中心（合肥）62013/7/24Wednesday高性能计算机IntelIntel（（OptionRed)OptionRed)：：1Tflops,1997,PentiumPro1Tflops,1997,PentiumProSGI(OptionBlueMountain):SGI(OptionBlueMountain):3Tflops,1998,MIPS100003Tflops,1998,MIPS10000IBM(OptionWhite):IBM(OptionWhite):7Tflops,Top4,2001,Power37Tflops,Top4,2001,Power3日本日本EarthSimulator:EarthSimulator:35Tflops,Top1,2002,VP35Tflops,Top1,2002,VPHewlettHewlett--PackardASCIQPackardASCIQ：：7Tflops,Top2,3,2002,AlphaServer7Tflops,Top2,3,2002,AlphaServer中国联想：中国联想：11Tflops,Top43,2002Tflops,Top43,2002国家高性能计算中心（合肥）72013/7/24Wednesday系统互连不同带宽与距离的互连技术不同带宽与距离的互连技术::总线、总线、SANSAN、、LANLAN、、MANMAN、、WANWAN局部总线I/O总线SCIHiPPIMyrinet千兆位以太网光纤通道快速以太网以太网10BaseTFDDIATM总线或开关SANLANMANWAN100Gb/s10Gb/s1Gb/s100Mb/s10Mb/sIsoEnet网络带宽交叉开关MIN或100BaseT国家高性能计算中心（合肥）82013/7/24Wednesday局部总线、I/O总线、SAN和LANPMI/O桥磁盘SAN(e.g.Myrinet)LAN(e.g.以太网,FDDI)系统III/O总线,接口系统I处理器总线局部总线,存储器总线SCSI节点2节点N系统总线节点1国家高性能计算中心（合肥）92013/7/24Wednesday网络性能指标节点度（节点度（NodeDegreeNodeDegree）：）：射入或射出一个节点的边射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。数。在单向网络中，入射和出射边之和称为节点度。网络直径（网络直径（NetworkDiameterNetworkDiameter）：）：网络中任何两个网络中任何两个节点之间的最长距离，即最大路径数。节点之间的最长距离，即最大路径数。对剖宽度（对剖宽度（BisectionWidthBisectionWidth））：：对分网络各半所必须对分网络各半所必须移去的最少边数移去的最少边数对剖带宽（对剖带宽（BisectionBandwidthBisectionBandwidth））::每秒钟内，在最小的对每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称网络为对称的如果从任一节点观看网络都一样，则称网络为对称的（（SymmetrySymmetry））国家高性能计算中心（合肥）102013/7/24Wednesday静态互连网络与动态互连网络静态互连网络：处理单元间有着固定连接的一类网络，静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。关和多级互连网络等。国家高性能计算中心（合肥）112013/7/24Wednesday静态互连网络（1）一维线性阵列（一维线性阵列（11--DLinearArrayDLinearArray）：）：并行机中最简单、最基本的互连方式，并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，每个节点只与其左、右近邻相连，也叫二近邻连接，NN个节点用个节点用NN--11条边串接之，内节点度为条边串接之，内节点度为22，直径为，直径为NN--11，，对剖对剖宽度为宽度为11当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为环，环可以是单向的或双向的，其节点度恒为22，直径或为，直径或为（双向环）或为（双向环）或为NN--11（（单向环），对剖宽度为单向环），对剖宽度为222/N国家高性能计算中心（合肥）122013/7/24Wednesday静态互连网络（2）二维网孔（二维网孔（22--DMeshDMesh）：）：每个节点只与其上、下、左、右的近邻相连（边界节点除每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为外），节点度为44，网络直径为，网络直径为，对剖宽度为，对剖宽度为在垂直方向上带环绕，水平方向呈蛇状，就变成在垂直方向上带环绕，水平方向呈蛇状，就变成IlliacIlliac网孔网孔了，节点度恒为了，节点度恒为44，网络直径为，网络直径为，而对剖宽度为，而对剖宽度为垂直和水平方向均带环绕，则变成了垂直和水平方向均带环绕，则变成了22--DD环绕（环绕（22--DDTorusTorus），），节点度恒为节点度恒为44，网络直径为，网络直径为，对剖宽度为，对剖宽度为)1(2NN1NN22/2NN2NN(a)2-D网孔(b)Illiac网孔(c)2-D环绕国家高性能计算中心（合肥）132013/7/24Wednesday静态互连网络（3）二叉树：二叉树：除了根、叶节点，每个内节点只与其父节点和两个子节点相连。除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为节点度为33，对剖宽度为，对剖宽度为11，而树的直径为，而树的直径为如果尽量增大节点度为，则直径缩小为如果尽量增大节点度为，则直径缩小为22，此时就变成了星形，此时就变成了星形网络，其对剖宽度为网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。路自叶向根逐渐变宽。1log2N2/N(a)二叉树(b)星形连接(c)二叉胖树国家高性能计算中心（合肥）142013/7/24Wednesday静态互连网络（4）超立方超立方：：一个一个nn--立方由立方由个顶点组成，个顶点组成，33--立方如图立方如图((a)a)所示；所示；44--立立方如图方如图((b)b)所示，由两个所示，由两个33--立方的对应顶点连接而成。立方的对应顶点连接而成。nn--立方的节点度为立方的节点度为nn，，网络直径也是网络直径也是nn，，而对剖宽度为而对剖宽度为。。如果将如果将33--立方的每个顶点代之以一个环就构成了如图立方的每个顶点代之以一个环就构成了如图((d)d)所示所示的的33--立方环，此时每个顶点的度为立方环，此时每个顶点的度为33，而不像超立方那样节点，而不像超立方那样节点度为度为nn。。nN22/N(b)4-立方(a)3-立方(c)顶点代之以环(d)3-立方环国家高性能计算中心（合肥）152013/7/24Wednesday嵌入将网络中的各节点映射到另一个网络中去将网络中的各节点映射到另一个网络中去用用膨胀膨胀（（DilationDilation）系数来描述嵌入的质量，它是指被）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数最大链路数如果该系数为如果该系数为11，则称为完美嵌入。，则称为完美嵌入。环网可完美嵌入到环网可完美嵌入到22--DD环绕网中环绕网中超立方网可完美嵌入到超立方网可完美嵌入到22－－DD环绕网中环绕网中国家高性能计算中心（合肥）162013/7/24Wednesday嵌入1000100110111010110011011