02第二章 并行法度模范设计基础(并行计算基础).ppt[精华]

《02第二章 并行法度模范设计基础(并行计算基础).ppt[精华]》由会员分享，可在线阅读，更多相关《02第二章 并行法度模范设计基础(并行计算基础).ppt[精华]（27页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,*,*,第二章 并行计算基础,组成并行计算机的各个部分：,节点（node）：每个节点由多个处理器构成，可以直接进行输入输出（I/O）操作；,互联网络（interconnect network）：所有节点通过互联网络相互连接通信；,内存（memory）：内存由多个存储模块组成,1、与节点对称的分布在互联网络的两侧；,2、位于各个节点的内部。,盒兵洛袍啮屿漆嘘霍冬舒准卑熊拥例蜜晋鲸礁柬遥李窥赋所呛裳匿蛹增图02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,第二章 并行计算

2、基础,内存模块与节点分离,内存模块位于节点内部,啮靳襟来砌叙欲哟像泪乃看钻凛伐狡持难檬橇衔酷玛芍厌莽盲桅默找陵毙02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,多级存储体系结构,解决内存墙（memory wall）性能瓶颈问题；,节点内部的cache称为二级cache（L2 cache）；,处理器内部更小的cache成为一级cache（L1 cache）；,L1 cache连接CPU寄存器和L2 cache，负责缓存L2 cache中的数据到寄存器中。,侨尉聊搪害预层未夫邢殴鹰纤茁莽浴卖搐崩此之惺靛组惧截钟挚你宁苛也02第二章 并行程序

3、设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,多级存储体系结构,并行计算机的多级存储结构主要包括两个问题：,Cache的映射策略，即cache如何从内存中取得数据进行存储；,节点内部或者节点之间内存的访问模式,。,cache,原理，,cache,以,cache,线为基本单位，每条,cache,包含,L,个字，每个字,8,个字节。例如，,L=4,，则表示,cache,线包含,4*8=32,个字节。内存空间分割成块（,block,），每个块大小与,cache,线长度一致，数据在内存和,cache,之间的移动以,cache,线为基本单位,。,For i=1 t

4、o M,Ai=Ai+2*Bi,如果操作数存在,cache,中，称该次访问是命中的，否则，该次操作是“扑空”的,。,饿潜蠕佛吐那撂鸳卤拌叹摈蚤目鞋槽慧坏淀篙畔奄罢应纤诺姜吗舆猴格避02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,多级存储体系结构,cache的映射策略（内存块和cache线之间如何建立相互映射关系）,：,直接映射策略（direct mapping strategy）：每个内存块只能被唯一的映射到一条cache线中,；,K路组关联映射策略（K-way set association mapping strategy）：Cach

5、e被分解为V个组，每个组由K条cache线组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一条cache线；,全关联映射策略（full association mapping strategy）:内存块可以被映射到cache中的任意一条cache线。,货淀枫攒置傅蒙悦犹琶起槐妒酵颇玲麓极困莹啮蝴臃臼昔真歼菜鳃叔舅沧02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,访存模型,UMA（Uniform Memory Access）模型：该模型内存模块与节点分离，分别位于互联网络的两侧,物理存储器被所有节点共享；,所有节

6、点访问任意存储单元的时间相同；,发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；,各节点的CPU可带有局部私有高速缓存；,外围I/O设备也可以共享，且每个节点有平等的访问权利。,找魏措疹翘堰强击初踢菱倦恶耐喇抬厌甭锚见斋恶哑壹舒释颓捣尔春煌郎02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,访存模型,NUMA（Non-Uniform Memory Access）模型：该模型内存模块分布在各个节点内部，所有局部内存模块均构成并行计算机的全局内存模块。内存模块在物理上是分布的，在逻辑上是全局共享的，这种模型也称之为“分布式共享访

7、存模型”,物理存储器被所有节点共享，任意节点可以直接访问任意内存模块；,节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的3倍以上；,发生访存竞争时，仲裁策略对节点可能是不等价的；,各节点的CPU可带有局部私有高速缓存（cache）；,外围I/O设备也可以共享，但对各节点是不等价的。,伍絮基笼晴炭叛骤壮朽梅缴旗费抓释隋肠泣般贿誉遂溯桌花涉昭僚轿西耙02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,访存模型,COMA（Cache-Only Memory Access）模型：全高速缓存存储访问模型,各处理器节点中没

8、有存储层次结构，全部高速缓存组成了全局地址空间；,利用分布的高速缓存目录进行远程高速缓存的访问；,COMA中的高速缓存容量一般都大于2级高速缓存容量；,使用COMA时，数据开始时可以任意分配，因为在运行时它最终会被迁移到要用到它的地方。,撤身丽发帆款搅午丛袍呜邀献杀纫峙拭允敷龚逗佑精珐少境磕蜗肋别弧苦02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,并行计算模型,SIMD同步并行计算模型,共享存储的SIMD模型（PRAM模型）；,分布存储的SIMD模型（SIMD互联网络模型）,MIMD异步并行计算模型,异步PRAM模型,BSP模型,Log

9、P模型,C3,模型,二洱辆贫际孪探青坑泞惰缀侨毙夷携业灸粘世碑愈院汐沉伶履钠最俊沪均02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,同步并行计算模型,SIMD共享存储模型假定存在着一个容量无限大的共享存储器，有有限或无限个功能相同的处理器，且均具有简单的算术运算和逻辑判断功能，在任何时刻各处理器均可通过共享存储单元相互交换数据。,SIMD共享存储模型（PRAM模型）,PRAM-EREW（Exclusive-Read and Exclusive-Write），不允许同时读和同时写；,PRAM-CREW（Concurrent-Read an

10、d Exclusive-Write），允许同时读但不允许同时写；,PRAM-CRCW（Concurrent-Read and Concurrent-Write），允许同时读和同时写。,优点：,适合于并行算法的表达、分析和比较；,使用简单，很多诸如处理器间通信、存储管理和进程同步等并行计算机的低级细节均隐含于模型中；,易于设计算法和稍加修改便可运行在不同的并行计算机上；,且有可能加入一些诸如同步和通信等需要考虑的方面。,山任盏痛哟住鹰靠慎列咋讼厅卡休秉矽稼山否确液啃批忙棵沈白拳销演扛02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,同步并行

11、计算模型,SIMD分布存储模型,采用一维线性连接的SIMD模型，简记为SIMD-LC,采用网孔连接的SIMD模型，简记为SIMD-MC,采用树形连接的SIMD模型，简记为SIMD-TC,采用树网连接的SIMD模型，简记为SIMD-MT,采用立方连接的SIMD模型，简记为SIMD-CC,采用立方环连接的SIMD模型，简记为SIMD-CCC,采用洗牌交换连接的SIMD模型，简记为SIMD-SE,采用蝶形连接的SIMD模型，简介为SIMD-BF,采用多级互联网络连接的SIMD模型，简记为SIMD-MIN,盯郭丸死妥逾盖吵寥晴亨仅斟紫姆包掩磁贺稿骏搔准敬必娜草姿世啊委邢02第二章 并行程序设计基础(并

12、行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,MIMD异步计算模型APRAM模型,APRAM特点:,每个处理器都有其本地存储器、局部时钟和局部程序,处理器间的通信经过共享全局存储器,无全局时钟，各处理器异步地独立执行各自的指令,处理器任何时间依赖关系需明确地在各处理器的程序中加入同步障（Synchronization Barrier）,一条指令可在非确定但有限的时间内完成。,器屹笺振格径被咱倦螟拓猿绍贴谴侄巩莽麻岳瘦赋荤僚滥牲唆吸稗诌座弧02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,MIMD异步计算模型PR

13、AM模型,APRAM模型中有四类指令:,全局读，将全局存储单元中的内容读入本地存储器单元中,局部操作，对本地存储器中的数执行操作，其结果存入本地存储器中,全局写，将本地存储器单元中的内容写入全本地存储器单元中,同步，同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序,赢遵像顿盈憨裤泽缚糯讫屏垦察戏竭敬籍斡仍弗骋揉羌桐锣搂瘤寝暮厦休02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,MIMD异步计算模型BSP模型,大同步并行,BSP,（,Bulk Synchronous Parallel,）模型,作为计算机

14、语言和体系结构之间的桥梁，由下述三个参数描述分布存储的并行计算机模型：,处理器/存储器模块（下文简称处理器）；,处理器模块之间点到点信息传递的路由器；,执行以时间间隔L为周期的路障同步器。,匈滩篱脆听紫樱豌砧测限讣闻偏袄宛故挞智狱诅滞橱罢皂饯吉爷可愧浮逝02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,MIMD异步计算模型BSP模型,特点：,将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅施行点到点的消息传递，不提供组合、复制或广播等功能，这样做既掩盖了具体的互联网络拓扑，又简化了通信协议；,采用路障方式的以硬件实现的全局

15、同步是在可控的粗粒度级，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员并无过分的负担；,在分析BSP模型的性能时，假定局部操作可在一个时间步内完成，而在每一超级步中，一个处理器至多发送或接受h条消息（h-relation）,巩核笺我舀听随葛峻烦奏女窃梢罪吸抵锅手沟差抖矿罗缸啥刑姥拳诣扯琵02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,MIMD异步计算模型LogP,C3模型,LogP模型,一种分布存储的、点到点通信的多处理机模型，其中通信网络由一组参数来描述，但它并不涉及到具体的网络结构，也不假定算法一定要用显式的消息传递操作进行

16、描述。,C3,（Computation,Communication,Congestion）,是一个与体系结构无关的粗粒度的并行计算模型，旨在能反映计算复杂度，通信模式和通信期间潜在的拥挤等因素对粗粒度网络算法的影响。,界椰没缝忘蛋沤吴滁记褂颠朵家宋殿槐攒袄而筐民蕉挚颈湿袁碗浅珠诌垂02第二章 并行程序设计基础(并行计算基础).ppt02第二章 并行程序设计基础(并行计算基础).ppt,并行编程环境,比较流行的并行编程环境主要有3类：消息传递、共享存储和数据并行，,共享存储并行编程基于线程级细粒度并行，可移植性不如消息传递并行编程，但是，由于他们支持数据的共享存储，所以并行编程的难度较小，但一般情况下，当处理机个数较多时，其并行性能明显不如消息传递编程,；,消息传递并行编程基于大粒度的进程级并行，具有最好的可扩展性，几乎被所有当前流行的各类并行计算机所支持，其具有较好的可扩展性，但是，消息传递并行编程只能支持进程间的分布式存储模式，即各个进程只能支持访问其局部内存空间，而对其他进程的局部内存空间的访问只能通过消息传递来实现，因此，学习和使用消息传递并行编程的难度均大于共享存储和数据并行这