并行算法第一章并行计算性能测评课件

并行算法南京林业大学-信息学院并行算法南京林业大学-信息学院2任课教师：章春芳办公室：0250E-mail：cfzhang1982@2任课教师：章春芳3教材、参考书—教材并行计算-结构·算法·编程陈国良高等教育出版社并行算法实践陈国良高等教育出版社—参考书并行处理技术

张德富

南京大学出版社面向结构的并行算法设计与分析李晓梅

国防科技大学出版社3教材、参考书—教材主要内容

并行处理概论

1

并行计算性能测评

2

并行算法的一般设计方法

4

并行算法的基本设计技术5非数值并行算法

6图论

7矩阵运算

8

并行算法的设计基础

3并行程序设计基础

9主要内容并行处理概论1并行计算性5第一章并行计算机系统及结构模型1.1并行计算概论1.2并行计算机系统互连1.3并行计算机系统结构5第一章并行计算机系统及结构模型1.1并行计算概论1.21.1并行计算概论并行处理的定义并行性的含义并行处理的应用并行处理中的几个难题61.1并行计算概论并行处理的定义671.1.1并行处理的含义发展背景：仅提高电子部件的速度来改善计算机的性能以满足用户越来越高的要求是不可能的。计算科学：计算物理、计算化学、计算生物等。并行处理：一种有效的强调开发计算过程中并行事件的信息处理方式。并行计算：并行机上的计算，又称高性能计算（HPC)。并行计算机：为并行处理所设计的计算机系统。71.1.1并行处理的含义发展背景：仅提高电子部件的速度来改8并行性的含义同时性：两个或多个事件在同一时刻发生在多个资源中并发性：两个或多个事件在同一时间间隔内发生在多个资源中流水线：两个或多个事件发生在可能重叠的时间内模式：以数值计算为例计算并行性，有表达模式与递归模式8并行性的含义同时性：两个或多个事件在同一时刻发生在多个资源9并行性的含义例如：两个向量的内积：表达式形式：

9并行性的含义例如：两个向量的内积：10并行性的含义并行模式：x1Y1x2Y2…Xn-1Yn-1xnYn………R10并行性的含义并行模式：x1Y1x2Y2…Xn-1Yn-111并行性的含义递归模式：流水线模式：

*+11并行性的含义递归模式：*+121.1.2并行处理的应用高速并行计算主要有三种类型的应用需求：121.1.2并行处理的应用高速并行计算主要有三种类型的应13并行处理的应用主要应用领域：气象、海洋、天体物理遥测地球资源数据处理

石油开采及管理磁聚变及核反应堆生物及医学工程计算社会经济学及政府部门国防

…13并行处理的应用主要应用领域：14气象数值预报将地球由北至南分成2度一格，延赤道分成4度一格，将大气层分成20层，形成一个三维网格。设每个网格上计算量约为3000次，若时间步长为2分钟，则当给出一天的气象预报时，总计算量为3.5×1011次。在Gray1（Gray公司的向量流水机）上进行计算（每秒1亿次浮点运算，需计算1小时左右，若将网格边长减半，是原来计算量的8倍。14气象数值预报将地球由北至南分成2度一格，延赤道分成4度一15海洋学、天体物理以1。为间隔的类似网格，用Gyber-205（美国数据控制公司CDC，1982，52位4亿次每秒，400mflops的流水线机）对太平洋50年作一次完整模拟要1000小时。模拟地球等行星的形成过程，其动态范围从毫秒到几十亿，ILLIAC-V阵列处理机（美国Illiniosuinv,1973,64个PE主存13万字，1.5亿次每秒的阵列机）曾用于这一方面的研究。15海洋学、天体物理以1。为间隔的类似网格，用Gyber-216遥测地球资源数据处理大量卫星图像资料处理。陆地探测卫星的一张图像有3千万个字符，覆盖美国Alabama州需要13幅这样的图像，每15天产生一次新的图像，计算量很大。美国宇航局订购了并行处理机MPP（美国GoodyearAerospace，1979，128×128PES），最高速度每秒60亿次8位整数运算，能提供实时的情景分析。16遥测地球资源数据处理大量卫星图像资料处理。陆地探测卫星的17石油开采及管理地震探测

1985年，我国南海西部石油公司向美国订购PE3230MPS并行处理计算机。地震数据处理费用占地震探测总费用的10%，地震数据相当多，仅1979年就有1015位地震数据处理。美国休斯顿一家地球物理公司存储的地球地震数据有200万个磁带卷。17石油开采及管理地震探测18石油开采及管理储油层模型的建立

SOHO公司用Cyber-203（CDC）建立波罗的海湾油田数值模拟器，包括1000个油井，一个需一年模拟实验的工作量，在Cyber-203仅用33分钟即可完成。18石油开采及管理储油层模型的建立19工程计算水坝、桥梁、船只、超音速飞机、高层建筑、太空飞行器设计需解大型偏微分方程组和代数方程组，可以用并行处理机提高设计效率。在空气动力学计算中美国航天局Ames研究中心用超级计算机作风洞实验三级模拟。由Burroughs公司及CDC公司推出“数值航空动力学模拟设备“（NAFS）的两台10亿次超级计算机可以模拟完整的飞机设计。19工程计算水坝、桥梁、船只、超音速飞机、高层建筑、太空飞行20社会经济学及政府部门计量经济学、社会工程、政府人口普查、犯罪控制2000年世界经济模型构造等计算的计算量大，需并行计算。诺贝尔奖学金获得者W.W.Leontief1980年提出一个世界经济输入/输出模型，在CDC科学计算机上运算，认为一个以部分裁军为特征的国际性经济关系系统，可以缩小贫富国家的差距，该项目受到联合国支持。美国使用大型计算机控制犯罪、收税与审计，进行人口普查及民意测验。过去美国制造的大型计算机57%由政府使用。20社会经济学及政府部门计量经济学、社会工程、政府人口普查、21国防、人工智能、基础研究国防军事部门使用现存的大部分超级计算机，如Cray-1多用于弹头核武器设计。在关联处理机上为反弹道导弹程序处理雷达信号，用S-1多处理机做反潜艇海洋监视。21国防、人工智能、基础研究国防22国防、人工智能、基础研究人工智能图像处理模式识别计算机视觉自然语言理解机器推理智能机器人专家系统知识工程基础研究计算化学计算物理计算几何VLSI辅助设计22国防、人工智能、基础研究人工智能23当代科学与工程问题的计算需求评测计算机性能的指标70年代Mflops106

百万现在Pflops1015

千万亿次90年代Tflops1012

万亿80年代Gflops109

十亿世界上第一台峰值速度超过1Tflops的高性能计算机是由Intel公司于1996年12月研制成功的。23当代科学与工程问题的计算需求评测计算机性能的指标70年代24当代科学与工程问题的计算需求美国HPCC计划（HighPerformanceComputing&Communication）为了保持美国的世界领先地位，1993年，美国科学、工程、技术联邦协调理事会的国会提出了题为“重大挑战项目：高性能计算与通信”的报告，简称HPCC计划3T性能目标

Tflops计算能力、1TB主存容量、1TB/s的I/O带宽24当代科学与工程问题的计算需求美国HPCC计划（High25HPCC应用领域高速民航用计算流体动力学来研制超音速喷气发动机新药设计研制癌症和艾滋病的药物催化作用仿生催化剂计算机建模，分析合成过程中酶的作用燃料燃烧通过化学动力学，揭示流体力学的作用，设计新型发动机海洋建模对海洋活动与大气流的热交换进行整体海洋模拟大气污染对大气质量模型进行模拟研究，揭示其物理和化学机理蛋白质结构设计使用计算机模拟，对蛋白质组成的三维结构进行研究图像理解实时绘制图像或动画密码破译破译由长位数组成的密码，求找该数的两个乘积因子1994年4月26日，美国宣布破译了世界上最长的RSA129密码，在因特网上使用1600台计算机，600多人工作8个月，破译了129位数字组成的密码25HPCC应用领域高速民航用计算流体动力学来研制超音速喷气26科学计算的需要26科学计算的需要27当代科学与工程问题的计算需求美国ASCI计划（AcceleratedStrategicComputingInitiative）全面禁止核实验条约签订后，1996年6月能源部联合美国三大武器实验室共同提出了“加速战略计划创新”，简称为ASCI计划27当代科学与工程问题的计算需求美国ASCI计划（Accel28美国ASCI计划目的通过数值模拟，评估核武器的性能、安全性、可靠性等，达到高分辨率、高逼真度、三维、全物理、全系统的规模和能力，该计划被认为是与当年曼哈顿计划等同的一个巨大的挑战。平台三大核武器实验室向三大公司（Intel，IBM和SGI/Cray）预订了峰值超过1Tflops的并行计算机，预计2003年使用运算100Tflops，50TB存储容量，I/O传输速率为5000GB/s的并行机28美国ASCI计划29并行处理中的几个难题任务分配非常困难考虑时空复杂度，还需考虑模块之间的通信量很难摆脱串行处理方式的约束软件和算法大都是按照串行结构设计的现有的算法语言对并行性限制很大现有语言以VonNeumann方式为基础，对并行性限

制严重：语句执行结果、执行顺序与前面结果和状态相关大量赋值语句使得处理器与存储器频繁交换信息，

降低系统效率29并行处理中的几个难题任务分配非常困难30并行处理中的几个难题VonNeumann模式一直伴随着并行机未摆脱以指令流为主导的VonNeumann模式，由于指令相关及地址空间相关，使并行受到制约处理机间的通讯开销使并行处理技术可能得不偿失

并行处理技术的主要难点在于软件串行机中软件好坏对于工作性能影响2-3倍，并行计算机中却是50-100倍，而且最困难的在于并行编译程序30并行处理中的几个难题VonNeumann模式一直伴随着传统VonNeumann结构及其存在问题存储程序控制方式31存储器指令寄存器、计数器存储器指令数据指令流驱动传统VonNeumann结构及其存在问题存储程序控制方式332研究并行处理应考虑的几个问题算法、体系结构、高级语言三者之间的关系应考虑：对于一些特定的计算机如何设计软件对于一个给定的程序如何使之结构化以便在给定的计算机上处理对于一个给定的计算机和一组应用软件怎样设计语言及编译系统对于给定的计算机、语言及编译系统如何设计算法与程序32研究并行处理应考虑的几个问题算法、体系结构、高级语言三者33并行处理机系统的优点具有很高的性能价格比由于系统的模块性，使之便于维护具有较高的可靠性具有较高的处理速度结构的灵活性便于VLSI实现33并行处理机系统的优点具有很高的性能价格比341.1.3并行处理机的分类1342341.1.3并行处理机的分类134235Flynn分类法单指令流单数据流SISD单指令流多数据流SIMD多指令流单数据流MISD（实际不存在）多指令流多数据流MIMD35Flynn分类法单指令流单数据流SISD36SISDCUPUMMISDSISCU：控制单元PU：处理单元MM：存储器IS：指令流DS：数据流36SISDCUPUMMISDSISCU：控制单元PU37SIMDCUPU1ISPU2PUn…MM1MM2MMn…DS1DS2DSnIS37SIMDCUPU1ISPU2PUn…MM1MM2MMn…38MIMDPU1PU2PUn…MM1MM2MMn…DS1DS2DSnIS1IS2ISnCU1CU2CUn…IS1IS2ISn38MIMDPU1PU2PUn…MM1MM2MMn…DS1D39Handler分类法1977年，Handler根据计算机系统中流水线和并行度出现的级别，将一台计算机表示为三对整数：

CPU数目能执行流水线的CPU数目CPU所控制的ALU数目

能执行流水线的ALU数目ALU或PE中的位数ALU或PE中流水线的位数39Handler分类法1977年，Handler根据计算机40按体系结构分类同步系统向量流水机阵列处理机：（含心动阵列）SIMD关联处理机：具有联想存储、按内容存取、逻辑操作等多处理机系统MIMD:由独立执行指令的处理器构成分布存储系统：每个结点有独立的存储单元共享存储系统MIMD变体（MIMD/SIMD混合型）40按体系结构分类同步系统41现代并行机结构分类SIMDPVP并行向量处理机SMP对称多处理机MPP大规模并行处理机DSM分布式共享存储多处理机COW工作站机群GrayC-90GrayT-90银河1号41现代并行机结构分类SIMDGrayC-9042对称多处理机SMPIBMR50、SGIPowerChakenge、曙光1号使用商用微处理的芯片，由高速总线连向共享存储器，对称性共享存储，PE个数不能太多。系统是对称的，每个处理器可等同的访问共享存储，I/O设备。42对称多处理机SMPIBMR50、SGIPower43大规模并行处理机MPP经典机型：IBMSP2、IntelParagon、IntelTFLOPS、曙光1000等。特性：节点为微处理器物理上的分布存储高带宽、低延迟的网络成百上千个PE异步MIMD，程序由多个进程组成，每个进程有私有空间，进程间采用消息传递的方式43大规模并行处理机MPP经典机型：IBMSP2、Inte44分布式共享存储多处理机DSM经典机型：CrayT3D、SGI/GrayOrigin2000特点：分布在各个节点上的局存形成了一个共享的存储器与SIMD相同，在物理上有分布在各点的共享主存，但采用单一地址空间，与MPP相比，易于编程44分布式共享存储多处理机DSM经典机型：CrayT3D、45工作站机群COW经典机型：BerkeleyNow、Digital、Toucluster等特点：每个节点都是一个工作站、PC机或SMP各节点由低成本网络相连（商品网络、以太网、FDDI等）各节点有本地磁盘各节点有一完整的OS（MPP中只有一个微核），整个系统是工作站Unix45工作站机群COW经典机型：BerkeleyNow、Di461.2并行计算机系统互连静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的连接保持不变动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组成461.2并行计算机系统互连静态互连网络：47静态互连网络一维线性阵列二维网孔树形连接超立方网络立方环洗牌交换网蝶形网络…47静态互连网络一维线性阵列48动态连接总线交叉开关多级互连网络…48动态连接总线49网络性能指标网络直径对剖宽度49网络性能指标网络直径对剖宽度50网络性能指标节点：用图表示网络，则处理机或存储器为节点，连接为边节点度（NodeDegree）：射入或射出一个节点的边数。在单向网络中，射入和射出边之和称为节点度网络直径（NetworkDiameter）：

网络中任何两个节点之间的最长距离，即最大路径数对剖宽度（BisectionWidth）：将网络分成两部分必须移去的最少边数如果从任一节点观看网络都一样，则称网络为对称的（Symmetry）50网络性能指标节点：用图表示网络，则处理机或存储器为节点，51静态互连网络（1）一维线性阵列（1-DLinearArray）：并行机中最简单、最基本的互连方式每个节点只与其左、右近邻相连，也叫二近邻连接节点度为直径为对剖宽度为21N-151静态互连网络（1）一维线性阵列（1-DLinearA52一维线性阵列线性连接函数：52一维线性阵列线性连接函数：53一维线性阵列当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是双向的或单向的互连网络节点度直径对剖宽度单向环双向环222N-12双向环单向环53一维线性阵列当首、尾节点相连时可构成循环移位器，在拓扑结54二维网孔四近邻连接：每个节点只与其上、下、左、右的近邻相连54二维网孔四近邻连接：每个节点只与其上、下、左、右的近邻相55二维网孔Illiac网孔：简记为MC2，在垂直方向上带环绕，水平方向呈蛇状55二维网孔Illiac网孔：简记为MC2，在垂直方向上带环56二维网孔2-D环绕：垂直和水平方向均带环绕56二维网孔2-D环绕：垂直和水平方向均带环绕57二维网孔4互连网络节点度直径对剖宽度四近邻连接Illiac网孔2-D环绕4457二维网孔4互连网络节点度直径对剖宽度四近邻连接Illia58网孔连接网孔中的PE节点编号是按行为主顺序，编号为0～N-1连接函数：012345678910111213141558网孔连接网孔中的PE节点编号是按行为主顺序，编号为0～N59网孔连接例：n=16时的网孔012345678910111213141559网孔连接例：n=16时的网孔012345678910119-1-57-56-48-47-46-45网孔连接在MC2上已经有许多有效的并行算法，但MC2通信功能较差，在最坏情况下，任意两个PE间信息交换至少要步。如N=64时P63-P10：P9-P45：63-7-8-9-109-1-57-56-48-47-46-45网孔连接在MC2上61树形连接二叉树连接（简记为TC）：P1P8P2P3P4P5P6P7P9P10P11P12P13P14P1561树形连接二叉树连接（简记为TC）：P1P8P2P3P4P62树形连接除了根、叶节点，每个内节点只与其父节点和两个子节点相连设二叉树有d层，层号由根至叶子为1~d，则共有个节点节点度为：对剖宽度为：直径为：2d-13162树形连接除了根、叶节点，每个内节点只与其父节点和两个子节树形连接的典型用法P1P8P2P3P4P5P6P7P9P10P11P12P13P14P15根及叶子节点具有I/O功能，且叶子节点执行并行计算，内节点负责节点间的通信树型连接的最长通信路径与树高相关，显然根为通信瓶颈，因此使用X-树，形成树网连接，可使同级兄弟之间彼此相连树形连接的典型用法P1P8P2P3P4P5P6P7P9P1064超立方体连接一个n-立方由个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。n-立方的节点度为，网络直径也是

，而对剖宽度为nn64超立方体连接一个n-立方由个顶点组成，365超立方体连接如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。65超立方体连接如果将3-立方的每个顶点代之以一个环就构成了66立方环连接（环型嵌入超立方体）BRGC编码（二进制反射格雷码）在2n个数中，相邻两数只有一位二进制代码不同n=1:01n=2:00011110即0132n=3:000001011010110111101100i01234567G(i)01326754环上号为i的处理机对应立方环上号为G(i)的处理机66立方环连接（环型嵌入超立方体）BRGC编码（二进制反射格67立方环连接12345670i01234567G(i)0132675467立方环连接12345670i01234567G(i)0168二进制码与格雷码二进制编码B=bmbm-1…b2b1格雷码G=gmgm-1…g2g1二进制码转换成格雷码：

格雷码转换成二进制码：68二进制码与格雷码二进制编码B=bmbm-1…b2b169二进制编码与格雷编码十进制数二进制格雷码00000000010001000120010001130011001040100011050101011160110010170111010081000110091001110110101011111110111110121100101013110110111411101001151111100069二进制编码与格雷编码十进制数二进制格雷码0000000070立方环连接1981年由Preparato等人提出立方环连接，简记为CCC，将立方体的每一个顶点由一个环代之，使每个顶点的度不大于3。例如以四个结点组成的一个环，此时立方环中有32个结点，n=32,q=5,r=2。顶点号一般表示为(k,i)，其中k为三位二进制数，决定环号，i为两位二进制数，决定向外的连接。与顶点(k,i)相连的另一顶点为(k(i),i)。70立方环连接1981年由Preparato等人提出立方环连71立方环连接例1：编号为30的处理机

30=（11110）2

k=111i=10

k(i)=011

30是环号为7上的第2个顶点，连向第3个环的第2个顶点1471立方环连接例1：编号为30的处理机72立方环连接例2：编号为25的处理机

25=（11001）2

k=110i=01

k(i)=100

25是环号为6上的第1个顶点，连向第4个环的第1个顶

17例3：编号为27的处理机

27=（11011）2

k=110i=11

k(i)不存在

27是环号为6上的第3个顶点，无连接顶点72立方环连接例2：编号为25的处理机73网络名称网络规模节点度网络直径对剖宽度对称链路数线性阵列21非环形2（双向）2是2-D网孔

4非Illiac网孔

4非2-D环绕4是二叉树31非星形2非超立方

nn是立方环3是静态互连网络特性比较73网络名称网络规模节点度网络直径对剖宽度对称链路数线性阵列74洗牌交换网络洗牌网络：

SH(Pm-1Pm-2…P1P0)=Pm-2Pm-3…P0Pm-1例对8个对象的洗牌连接：

0134526701345267循环左移1位74洗牌交换网络洗牌网络：0134526701345267循75交换网络洗牌网络往往不够充分，因此常与交换连接一起使用EX(Pm-1Pm-2…P1P0)=Pm-1Pm-2…P1P’0例对8个对象的交换连接：013452670134526775交换网络洗牌网络往往不够充分，因此常与交换连接一起使用0洗牌交换网络12345670当n=8时SH(p)=(0)(1,2,4)(3,6,5)(7)EX(p(=(0,1)(2,3)(4,5)(6,7)洗牌交换网络1234567077逆洗牌交换网络UNSH(Pm-1Pm-2…P1P0)=P0Pm-1…P2P1例对8个对象的逆洗牌连接：013452670134526777逆洗牌交换网络UNSH(Pm-1Pm-2…P1P0)=78逆洗牌交换网络12345670例对8个对象的逆洗牌交换连接：78逆洗牌交换网络12345670动态互连网络公共总线交叉开关多级互连网络79互连网络中最简单的一种连接动态互连网络公共总线79互连网络中最简单的一种连接80公共总线总线是连接处理器、存储模块和I/O设备的一组导线和插座，实现它们之间的数据传输公共总线：所有PE及存储模块排在同一总线上，彼此以均等竞争的方式使用总线，会出现冲突现象改进：多总线、多级总线、多维总线、分时总线等PcachePcachePcacheMMM80公共总线总线是连接处理器、存储模块和I/O设备的一组导线81交叉开关（Croosbar）一种高带宽网络，是互连结构中功能最强的连接方式单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。P0P1MMSSSS81交叉开关（Croosbar）一种高带宽网络，是互连结构中82交叉开关（Croosbar）交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取P0P1MMSSSS每一列只能接通一个交叉点开关82交叉开关（Croosbar）交叉开关一般有两种使用方式：83多级互连网络单级互连网络的局限性:只能实现有限几种连接，并不能实现任意处理机之间的连接。完全交叉开关网络虽然可以实现，但结构复杂，价格昂贵，适用于处理器数目不多的系统。解决办法:多级互连网络

83多级互连网络单级互连网络的局限性:84多级互连网络单级交叉开关级联起来形成多级互连网络MIN（MultistageInterconnectionNetwork）优点：速度快，灵活性好，传输率低于完全开关网络，适用于PE较多的情形84多级互连网络单级交叉开关级联起来形成多级互连网络MIN（85多级互连网络多级互连网络的性能反映在三个方面：交换开关拓扑结构控制方式85多级互连网络多级互连网络的性能反映在三个方面：86多级互连网络-交换开关交换开关：由2×2的交叉开关构成，具有两个输入和两个输出的交换单元四种关联状态：直连、交换、下播和上播

两功能单元:仅包含直连和交换功能四功能单元:包含全部四种功能86多级互连网络-交换开关交换开关：由2×2的交叉开关构成，87多级互连网络-拓扑结构若N为输入端数，则多级网络一般有log2N级，每一级使用N/2个开关单元。拓扑结构：网络中每级的输出与下一级的输入之间如何连接87多级互连网络-拓扑结构若N为输入端数，则多级网络一般有l88多级互连网络-控制方式几个互连函数：设C=(bn…,bk+1,bk,bk-1,…b2,b1)蝶形排列：(k)(C)=(bn…,bk+1,b1,bk-1,…b2,bk)混洗：(k)(C)=(bn…,bk+1,bk-1,…b2,b1,bk)交换：E(k)(C)=(bn…,bk+1,b’k,bk-1,…b2,b1)88多级互连网络-控制方式几个互连函数：89多级互连网络例对8个对象的多级互连—E(2)连接：013452670134526789多级互连网络例对8个对象的多级互连—E(2)连接：0190多级互连网络例对8个对象的多级互连—(2)连接：013452670134526790多级互连网络例对8个对象的多级互连—(2)连接：0191多级互连网络例对8个对象的多级互连—(3)连接：013452670134526791多级互连网络例对8个对象的多级互连—(3)连接：01思考题0134526701345267E(1)E(1)E(1)(2)(3)-101345267021345670213456707415026307415263思考题0134526701345267E(1)E(1)E(1931.3并行处理机的系统结构并行计算机结构SIMDPVPSMPMPPDSMCOW并行计算机访存模型UMANUMACOMACC-NUMANORMA931.3并行处理机的系统结构并行计算机结构SIMD并行计941.3.1并行向量处理机PVPParallelVectorProcessor，典型的并行向量处理机的结构如图：无cache，使用大量的向量寄存器及指令缓冲器系统中使用了高带宽的交叉开关网络，存储器可达每秒兆字节的速度VPVPVPSMSMSM交叉开关941.3.1并行向量处理机PVPParallelVect95对称多处理机SMPSymmetricMultiprocessor其结构如图：对称性：每个处理器可等同地访问SM、I/O等共享存储：系统中的PE一般少于64个，总线与交叉开关一旦作成，难以扩展P/CP/CP/CSMSMSM总线或交叉开关95对称多处理机SMPSymmetricMultiproc96大规模并行处理机MPPMassivelyParallelProcessor其结构如图：分布式：每个处理器都有局部存储空间是异步的MIMD机器，程序有多个进程构成，每个都有其私有空间，由进程传递消息NIC定制网络LMP/CMB…NICLMP/CMB96大规模并行处理机MPPMassivelyParalle97分布共享存储多处理机DSM高速缓存目录DIR用于支持分布高速缓存的一致性与SMP的主要差异：DSM在物理上有分布在各节点的LM从而形成一个共享的存储器，对用户而言，形成了一个单地址的编址空间NIC定制网络LMP/CMB…DIRNICLMP/CMBDIR97分布共享存储多处理机DSMNIC定制网络LMP/CMB…工作站机群COW每个节点可以是一台PC或SMP各节点通过低成本的商品网络互连NIC商品网络（以太网、ATM等）MP/CMB…BridgeIOBLDNICMP/CMBBridgeIOBLD工作站机群COW每个节点可以是一台PC或SMPNIC商品网络99公用结构SMP、MPP、DSM等并行机结构渐趋一致，DSM是SMP与MPP的自然结合，MPP与COW的界限逐渐不清，它们最终趋于一致，形成当代并行机的公用结构。其三种不同的结构如下图所示：节点NNIC互连网络…shellNICPCMD节点1（a）无共享结构99公用结构节点NNIC互连网络…shellNICPCMD节100shell结构系统中大量的节点通过高速网络连接，节点通常遵循shell结构（ShellArchitecture），是其中一个专门设计定制的电路。shell结构将商品微处理器及其余的节点，包括cache、局存、NIC及磁盘连接起来。一个节点内可有多个处理器。shell结构的优点：当处理器芯片更新换代时，只要改变shell结构。100shell结构系统中大量的节点通过高速网络连接，节点通101公用结构将无共享结构图(a)中节点内的磁盘D移出来构成共享磁盘的结构盘(b):NIC互连网络…shellNICPCM节点1节点N共享磁盘（b）共享磁盘101公用结构将无共享结构图(a)中节点内的磁盘D移出102公用结构把图(b)中主存(M)移出来就变成了共享存储结构图(c):互连网络shellPC共享存储器（c）共享存储结构shellPC共享磁盘102公用结构把图(b)中主存(M)移出来就变成了共享103小结结构类型：皆为MIMD处理器类型：PVP为专用定制，其余为商用互连网络：PVP：定制交叉开关SMP：总线交叉开关MPP：定制网络DSM：定制网络COW：商用网络（以太网或ATM）通信机制：PVP、SMP、DSM：共享变量MPP、COW：消息传递103小结结构类型：皆为MIMD1041.3.2并行计算机访存模型均匀存储访问模型UMA非均匀存储访问模型NUMA全高速缓存存储访问模型COMA高速缓存一致性非均匀存储访问模型CC-NUMA非远程存储访问模型NORMA1041.3.2并行计算机访存模型均匀存储访问模型UMA105均匀存储访问模型UMAUMA：UniformMemoryAccess特点：物理存储器被所有处理器均匀共享所有处理器访问存储器的时间相同每台处理器可带有高速缓存cache外设也可以一定形式共享P1P2PnI/OSM1SMn系统互连……105均匀存储访问模型UMAUMA：UniformMemo106非均匀存储访问模型NUMANUMA：NonuniformMemoryAccess特点：被共享的存储器在物理上是分布在所有的处理机中的,所有的本地存储器的集合就组成了全局地址空间处理器访问时间不一样每个处理器可以带cache，外设也可以某种形式共享P2互连网络…P1PnLM1LM2LMn…106非均匀存储访问模型NUMANUMA：Nonunifor107全高速缓存存储访问模型COMACOMA：Cache-onlyMemoryAccessNUMA的一种特例C互连网络DPCDPCDP…高速缓存目录107全高速缓存存储访问模型COMACOMA：Cache-o108全高速缓存存储访问模型COMA特点：各处理器中无存储层次结构，全部高速缓存构成了全局地址空间利用分布的高速缓存目录D进行远程高速缓存的访问COMA中的高速缓存容量一般都大于二级高速缓存的容量使用COMA时，数据开始时可任意分配，因为在运行时它最终被迁移到要用到它的地方108全高速缓存存储访问模型COMA特点：高速缓存一致性非均匀存储访问模型CC-NUMA：Coherent-CacheNonuniformMemoryA