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

1、2 任课教师：章春芳任课教师：章春芳 办公室：办公室：0250 E-mail：3教材、参考书主要内容5第一章并行计算机系统及结构模型1.1 并行计算概论并行计算概论1.2 并行计算机系统互连并行计算机系统互连1.3 并行计算机系统结构并行计算机系统结构1.1 并行计算概论671.1.1并行处理的含义8并行性的含义9并行性的含义),.,(211nxxxv ),.,(212nyyyv nnyxyxyxvvR.22112110并行性的含义11并行性的含义niyxzzizRiiii, 2 , 10010121,.,xxxxnn121,.,yyyynn121.1.2 并行处理的应用计算密集计算密集数据密

2、集数据密集网络密集网络密集13并行处理的应用14气象数值预报15海洋学、天体物理16遥测地球资源数据处理17石油开采及管理18石油开采及管理19工程计算20社会经济学及政府部门21国防、人工智能、基础研究22国防、人工智能、基础研究23当代科学与工程问题的计算需求24当代科学与工程问题的计算需求25HPCC应用领域26科学计算的需要27当代科学与工程问题的计算需求28美国美国ASCI计划计划29并行处理中的几个难题30并行处理中的几个难题传统传统Von Neumann结构及其存在问题结构及其存在问题31存储器指令寄存器、计数器存储器指令数据指令流驱动32研究并行处理应考虑的几个问题33并行处理

3、机系统的优点341.1.3 并行处理机的分类35Flynn分类法36SISD37SIMD38MIMD39Handler分类法,)(WWDDKKcT40按体系结构分类41现代并行机结构分类42对称多处理机SMP43大规模并行处理机MPP44分布式共享存储多处理机DSM45工作站机群COW461.2 并行计算机系统互连47静态互连网络48动态连接49网络性能指标50网络性能指标51静态互连网络（1）52一维线性阵列一维线性阵列201)(111)(11nPPPLCnPPPLC右连接：左连接：53一维线性阵列2/N54二维网孔二维网孔55二维网孔二维网孔56二维网孔二维网孔57二维网孔二维网孔) 1(

4、2NN1NN22/2NN2(a)2-D网孔(b)Illiac网孔(c)2-D环绕58网孔连接)()()()(222121PMCPMCPMCPMCNNNNPmod)1(NNNPmod)(NNPmod)1(NNNPmod)(59网孔连接)15,11, 7 , 3)(14,10, 6 , 2)(13, 9 , 5 , 1)(12, 8 , 4 , 0()()0 , 4 , 8 ,12)(1 , 5 , 9 ,13)(2 , 6 ,10,14)(3 , 7 ,11,15()()15,14,.,1 , 0()()0 , 1,.,14,15()(2162162121PMCPMCPMCPMC网孔连接1N61

5、树形连接62树形连接311log22N树形连接的典型用法64超立方体连接nN22/N65超立方体连接66立方环连接（环型嵌入超立方体）67立方环连接68二进制码与格雷码1 , 2,.11mibbgbgiiimm1 , 2,.11migbbgbiiimm69二进制编码与格雷编码70立方环连接71立方环连接72立方环连接73NNNNNN NN NN nN2kkN21N1N2/N) 1(2N1N2/2N1log2N2/12kkNN2N22/N2/N)2/( kN1NN)(2NN N2N21N1N2/nN2/3N静态互连网络特性比较74洗牌交换网络75交换网络洗牌交换网络77逆洗牌交换网络78逆洗牌交

6、换网络动态互连网络7980公共总线81交叉开关（Croosbar）82交叉开关（Croosbar）83多级互连网络84多级互连网络85多级互连网络86多级互连网络-交换开关87多级互连网络-拓扑结构88多级互连网络-控制方式89多级互连网络90多级互连网络91多级互连网络思考题931.3 并行处理机的系统结构941.3.1并行向量处理机PVP95对称多处理机SMP96大规模并行处理机MPP97分布共享存储多处理机DSM工作站机群COW99公用结构100shell结构101公用结构 102公用结构 103小结 1041.3.2 并行计算机访存模型105均匀存储访问模型UMA106非均匀存储访问模

7、型NUMA107全高速缓存存储访问模型COMA108全高速缓存存储访问模型COMA高速缓存一致性非均匀存储访问模型110高速缓存一致性非均匀存储访问模型111高速缓存一致性非均匀存储访问模型112非远程存储访问模型NORMA非远程存储访问模型NORMA小结114115小结属性属性PVPSMPMPPDSMCOW结构类型结构类型处理器类型处理器类型互连网络互连网络通信机制通信机制地址空间地址空间系统存储器系统存储器访存模型访存模型MIMDMIMDMIMDMIMDMIMD专用定制专用定制商用商用商用商用商用商用商用商用定制交叉定制交叉 开关开关总线交总线交叉开关叉开关定制网络定制网络定制网络定制网络

8、商用网络商用网络共享变量共享变量共享变量共享变量共享变量共享变量消息传递消息传递消息传递消息传递单地址单地址单地址单地址单地址单地址多地址多地址多地址多地址集中共享集中共享集中共享集中共享分布不共享分布不共享分布不共享分布不共享分布共享分布共享UMAUMANORMANUMANORMA练习 测评并行计算机运行速度的性能指标是每秒钟执行的测评并行计算机运行速度的性能指标是每秒钟执行的指令条数，若单位是指令条数，若单位是pflops时表示的数量级是时表示的数量级是10的的_次方。次方。 DSM结构的并行机的访存模型是结构的并行机的访存模型是_，SMP结结构的并行机的访存模型是构的并行机的访存模型是_

9、。 在含有在含有N个节点的个节点的2-D环绕互连结构中，节点的度为环绕互连结构中，节点的度为_，网络直径为，网络直径为_，对剖宽度为，对剖宽度为_。11615NUMAUMA42/2NN2练习117 请在表格的单元格中填入相应的编码请在表格的单元格中填入相应的编码二进制编码格雷码1111110001100010110110000110011111001001练习 美国的美国的HPCC计划是在全面禁止核试验条约签订后提计划是在全面禁止核试验条约签订后提出的，该计划的目的是利用并行机在实验室进行核武出的，该计划的目的是利用并行机在实验室进行核武器的数值模拟。器的数值模拟。 （ ） 我国的并行机银河我国的并行机银河1号属于号属于SMP结构。结构。 （ ） 采用全高速缓存存储访问模型采用全高速缓存存储访问模型COMA的处理器没有存的处理器没有存储层次结构，全部高速缓存构成了全局地址空间。储层次结构，全部高速缓存构成了全局地址空间。 （ ） MPP结构的并行机采用的是消息传递机制，而结构的并行机采用的是消息传递机制，而SMP结结构的并行机采用的是共享变量通信机制。构的并行机采用的是共享变量通信机制。 （ ）118