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

1、23教材、参考书主要内容5第一章并行计算机系统及结构模型1.1 并行计算概论671.1.1并行处理的含义8并行性的含义9并行性的含义),.,(211nxxxv ),.,(212nyyyv nnyxyxyxvvR.22112110并行性的含义11并行性的含义niyxzzizRiiii, 2 , 10010121,.,xxxxnn121,.,yyyynn121.1.2 并行处理的应用13并行处理的应用14气象数值预报15海洋学、天体物理16遥测地球资源数据处理17石油开采及管理18石油开采及管理19工程计算20社会经济学及政府部门21国防、人工智能、基础研究22国防、人工智能、基础研究23当代科学

2、与工程问题的计算需求24当代科学与工程问题的计算需求25HPCC应用领域26科学计算的需要27当代科学与工程问题的计算需求28美国美国ASCI计划计划29并行处理中的几个难题30并行处理中的几个难题传统传统Von Neumann结构及其存在问题结构及其存在问题31存储器指令寄存器、计数器存储器指令数据指令流驱动32研究并行处理应考虑的几个问题33并行处理机系统的优点341.1.3 并行处理机的分类35Flynn分类法36SISD37SIMD38MIMD39Handler分类法,)(WWDDKKcT40按体系结构分类41现代并行机结构分类42对称多处理机SMP43大规模并行处理机MPP44分布式

3、共享存储多处理机DSM45工作站机群COW461.2 并行计算机系统互连47静态互连网络48动态连接49网络性能指标50网络性能指标51静态互连网络（1）52一维线性阵列一维线性阵列201)(111)(11nPPPLCnPPPLC右连接：左连接：53一维线性阵列2/N54二维网孔二维网孔55二维网孔二维网孔56二维网孔二维网孔57二维网孔二维网孔) 1(2NN1NN22/2NN2(a)2-D网孔(b)Illiac网孔(c)2-D环绕58网孔连接)()()()(222121PMCPMCPMCPMCNNNNPmod)1(NNNPmod)(NNPmod)1(NNNPmod)(59网孔连接)15,11

4、, 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树形连接62树形连接311log22N树形连接的典型用法64超立方体连接nN22/N65超立方体连接66立方环连接（环型嵌入超立方体）67立方环连接68二进制码与格雷码1 , 2,.11mibbgbgiiimm1 , 2,.11migbbgbi

5、iimm69二进制编码与格雷编码70立方环连接71立方环连接72立方环连接73NNNNNN NN NN nN2kkN21N1N2/N) 1(2N1N2/2N1log2N2/12kkNN2N22/N2/N)2/( kN1NN)(2NN N2N21N1N2/nN2/3N静态互连网络特性比较74洗牌交换网络75交换网络洗牌交换网络77逆洗牌交换网络78逆洗牌交换网络动态互连网络7980公共总线81交叉开关（Croosbar）82交叉开关（Croosbar）83多级互连网络84多级互连网络85多级互连网络86多级互连网络-交换开关87多级互连网络-拓扑结构88多级互连网络-控制方式89多级互连网络90

6、多级互连网络91多级互连网络思考题931.3 并行处理机的系统结构941.3.1并行向量处理机PVP95对称多处理机SMP96大规模并行处理机MPP97分布共享存储多处理机DSM工作站机群COW99公用结构100shell结构101公用结构 102公用结构 103小结 1041.3.2 并行计算机访存模型105均匀存储访问模型UMA106非均匀存储访问模型NUMA107全高速缓存存储访问模型COMA108全高速缓存存储访问模型COMA高速缓存一致性非均匀存储访问模型110高速缓存一致性非均匀存储访问模型111高速缓存一致性非均匀存储访问模型112非远程存储访问模型NORMA非远程存储访问模型NORMA小结114115小结属性属性PVPSMPMPPDSMCOW结构类型结构类型处理器类型处理器类型互连网络互连网络通信机制通信机制地址空间地址空间系统存储器系统存储器访存模型访存模型MIMDMIMDMIMDMIMDMIMD专用定制专用定制商用商用商用商用商用商用商用商用定制交叉定制交叉 开关开关总线交总线交叉开关叉开关定制网络定制网络定制网络定制网络商用网络商用网络共享变量共享变量共享变量共享变量共享变量共享变量消息传递消息传递消息传递消息传递单地址单地址单地址单地址单地址单地址多地址多地址多地址多地址集中共享集中共享集中共享集中共享分布不共享分布不共享分布不共享分布不