多核程序设计课件2-并行计算基础

多核程序设计

第二章并行计算基础2008年8月18日§并行处理技术2.0.1 并行性概念一、并行技术定义开发计算过程中并行事件的处理方法事件的并行性结构的并行性二、并行性含义同时性：两个或两个以上事件在同一时刻发生并发性：两个或两个以上事件在同一时间间隔发生流水线：两个或两个以上事件在可能重叠的时间段内2.0并行处理技术概述§并行处理技术2.0.2并行性的层次一、程序执行的并行性指令内部并行：微操作并行指令间并行：多条指令并行任务或进程间并行：任务作并行性分解作业或程序间并行：资源的并行性分配算法二、数据处理的并行性位串字串：一次只对一个字的一位进行处理——无并行位并字串：一次对多个字的一位进行处理——1，B＞1位串字并：一次对一个字的多位进行处理——W＞1，1位并字并：一次对许多字的多位进行处理——W＞1，B＞1三、操作并行性的层次存储器操作并行：在一个存贮周期内访问多个存贮单元处理器操作步骤并行：指令执行子操作重叠处理器操作并行：多处理单元(多核)，在同一控制器控制下按同一条指令对多个数据组同时操作（多核）并行度增加通信与调度开销增加硬件实现的比例增加§并行处理技术2.0.3并行性措施及困难一、并行性措施时间重叠：时间上错开，轮流重叠使用硬件：如流水线资源重复：空间重叠，以量取胜资源共享：多用户按时间顺序轮流使用同一套资源：如分时系统二、并行性困难任务分配非常困难可并行性：任务的并行性划分和分发算法对并行性的限制算法不仅与问题有关，还与硬件有关处理机之间的通信开销限制当通信开销大时并行处理技术得不偿失并行处理环境可编程性并行开发环境需要并行编译和并行操作系统支持并行规模的确定可扩展性2.0.5多处理器互联方式通信网络是多处理机性能发挥的瓶颈主要方式：总线、交叉开关、多端口存贮器、开关枢纽网络参数节点度（）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（）：网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度（）：对分网络各半所必须移去的最少边数对剖带宽（）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称为对称的（）静态互连网络与动态互连网络静态互连网络处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。静态互连网络一维线性阵列1并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，N个节点用1条边串接之，内节点度为2，直径为1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为（双向环）或为1（单向环），对剖宽度为2静态互连网络二维网孔N×N二维网孔（2）每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为21，对剖宽度为N在垂直方向上带环绕，水平方向呈蛇状，就变成网孔了，节点度恒为4，网络直径为1，而对剖宽度为2N垂直和水平方向均带环绕，则变成了2环绕（2），节点度恒为4，网络直径为2[2]，对剖宽度为2N静态互连网络二叉树二叉树除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。静态互连网络超立方超立方一个立方由2n个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。立方的节点度为n，网络直径也是n，而对剖宽度为2。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。动态互连网络总线、、、、多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等动态互连网络交叉开关（）单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于服务器或向量超级计算机中处理器和存储器之间的存取。单级交叉开关级联构成多级互连网络（）2.1并行计算机体系结构并行计算机组成的各个部分：节点（）互联网络（）内存（）内存模块与节点分离内存模块位于节点内部2.1.0并行处理机的结构四种体系结构()()???;a():2：65535个1;：64个64;:;(~)():5000,T3D,:;;,:<=128并行处理机的结构多个处理节点通过互连网络联接互连网络节点1节点2节点3节点4…………节点n节点i结构

.

Q1:?():,’t():,a

Q2:?():,():,

.:(),()典型集中共享存储多处理机系统

总线结构典型分布存储多处理机系统

互连网络典型片上多处理器系统®®12

()L2:

微架构

架构核心的3.2『』处理器，包括8个协同处理器()，除1个保留用做其它用途，其余7个均以3.2频率运做，内建512二级缓存，浮点性能最高可达218二种常见的分布存储多处理机系统（)统一的逻辑地址空间，但物理空间是分布的每个处理器可以通过逻辑,.

。逻辑上不连续，远程处理器无法访问。每一结点（）模块是一单独的计算机，故称为多计算机结构。计划，每一结点实质上是一工作站或，由连接而成。.:p0m03’t

:p0m0m13

(!)=>

2.1.1多级存储体系结构为了解决处理器与内存之间的性能/成本瓶颈问题。理论依据：局部性原理目前有多级在节点内部的称为二级（L2）。在处理器内部更小的成为一级（L1）。多级存储体系结构2的映射策略指的是内存块和线之间如何建立相互映射关系。直接映射策略（）每个内存块只能被唯一的映射到一条线中K－路组关联映射策略（）被分解为若干个组，每个组由K个组成，组直接映射，组内映射到任意全关联映射策略（）内存块可以被映射到中的任意一个多级存储体系结构3时的写策略写命中时同时修改主存（外层存储器）始终保证数据一致：存贮器或其它处理器始终有最新数据控制位：影响性能：可以用提高性能

写命中时不修改主存（外层存储器），数据块退出时一次修改数据存在不一致性：存贮器或其它处理器始终有最新数据控制位：、存储器带宽要求较低多级存储体系结构4时的写策略

数据块调入，再写大时影响性能，但可提高命中率与结合()数据块直接写入主存大时写性能较好下次访问还是与结合程序结构与效率循环交换每次访问间隔100个元素(k=0;k<100;k=1) (j=0;j<100;j=1) (i=0;i<5000;i=1) x[i][j]=2*x[i][j];连续访问100个元素(k=0;k<100;k=1) (i=0;i<5000;i=1) (j=0;j<100;j=1) x[i][j]=2*x[i][j];

改善空间局部性提高命中率ji程序结构与效率循环融合访问a、c时2次(i=0;i<N;i=1) (j=0;j<N;j=1) a[i][j]=1[i][j]*c[i][j];(i=0;i<N;i=1) (j=0;j<N;j=1) d[i][j]=a[i][j]+c[i][j];访问a、c时1次(i=0;i<N;i=1) (j=0;j<N;j=1) { a[i][j]=1[i][j]*c[i][j]; d[i][j]=a[i][j]+c[i][j];}

改善空间局部性提高命中率程序结构与效率数组融合多个一维数组[];[];一个结构数组{ ; ;};[];

改善空间局部性提高命中率程序结构与效率矩阵分割矩阵乘法(i=0;i<N;i=1) (j=0;j<N;j=1) {r=0; (k=0;k<N;k=1) r=r+y[i][k]*z[k][j]; x[i][j]=r; };:N1X[]N1Y[]Z[]aN&:2N3+N2=>(;…):y[1][k]z[k][j]x[1][j](())2N3+N2N3程序结构与效率矩阵分割2分块修改后(=0;<N;=)(=0;<N;=)(i=0;i<N;i=1) (j=;j<(1);j=1) {r=0; (k=;k<(1);k=1) r=r+y[i][k]*z[k][j]; x[i][j]=x[i][j]+r; };

Y改善空间局部性Z改善时间局部性减小容量2N3+N2→N32N2BNB×BBN()2)×()2=2N3+N2N3并行体系结构下的一致性写操作引起不一致写操作引起不一致

一致性解决思想

,()

硬件一致性协议():

a,()()()1()=>

()

硬件监听方案基本监听协议:,::::()::,,::!

写无效协议大多数系统常用的

,写更新协议(广播)两种协议性能的定性对比对同一字的多次写操作，多次写广播；（写更新）只要一次无效化操作；（写无效）(思考:为什么不是多次无效化操作?)数据块由多字组成的话，对块中每一字进行写操作每次都要写广播；（写更新）()只在第一次写块中任一字时，需要产生一无效信号；（写无效）从一个处理器写数到另一处理器读出写入的数的延时：写广播完成后，读命中；写无效化，读失配，直到得到返回值。

,:()()

():::,,::

一致性机制的请求和操作监听无效协议请求状态机InvalidShared(read/only)Exclusive(read/write)CPUReadCPUWriteCPUReadhitPlacereadmissonbusPlaceWrite

MissonbusCPUreadmissWritebackblock,PlacereadmissonbusCPUWritePlaceWriteMissonBusCPUReadmissPlacereadmissonbusCPUWriteMissWritebackcacheblockPlacewritemissonbusCPUreadhitCPUwritehitCacheBlockState

监听无效协议总线请求状态机InvalidShared(read/only)Exclusive(read/write)WriteBackBlock;(abortmemoryaccess)Writemiss

forthisblockReadmiss

forthisblockWritemiss

forthisblockWriteBackBlock;(abortmemoryaccess)

监听无效协议状态机—合并PlacereadmissonbusInvalidShared(read/only)Exclusive(read/write)CPUReadCPUWriteCPUReadhitPlaceWrite

MissonbusCPUreadmissWritebackblock,PlacereadmissonbusCPUWritePlaceWriteMissonBusCPUReadmissPlacereadmissonbusCPUWriteMissWritebackcacheblockPlacewritemissonbusCPUreadhitCPUwritehitWritemiss

forthisblockWriteBackBlock;(abortmemoryaccess)Writemiss

forthisblockReadmiss

forthisblockWriteBackBlock;(abortmemoryaccess)’s

1L2::BRBWBWInvalidShared(clean)ModifiedPR,HIT&HITmPWPWCPUreadhitCPUwritehitExclusive(clean)BRPR,BRBR写无效化目录协议::≥1,(;):1();

,(,1)(r):

=>

无效化目录协议2没有总线，采用消息机制

3种节点a

aa

,关系与消息：读数据的流向为例本地节点→家节点→远程节点→家节点→本地节点→→

P,APA;

Pa P,APA;

P AaA. AA AA;

a() A,aA()消息类型与节点关系52目录无效协议请求状态机

()()

:

.

::

:

:53目录无效协议目录状态机

:={}()()():={P}

:

;={P};

:={P};

:{P};;

():{P};

:={P};;

542.1.2并行计算机访存模型（）模型物理存储器被所有节点共享；所有节点访问任意存储单元的时间相同；发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；各节点的可带有局部私有高速缓存；外围设备也可以共享，且每个节点有平等的访问权利。并行计算机访存模型（）模型物理存储器被所有节点共享，任意节点可以直接访问任意内存模块；节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其它节点内存模块的3倍以上；发生访存竞争时，仲裁策略对节点可能是不等价的；各节点的可带有局部私

有高速缓存（）；外围设备也可以共享，

但对各节点是不等价的。LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSM…………PCINCSMPPCSMCSM群1……PCINCSM群NPPCSMCSM……并行计算机访存模型（）模型各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间利用分布的高速缓存目录D进行远程高速缓存的访问中的高速缓存容量一般都大于2级高速缓存容量使用时，数据开始时可以任意分配，因为在运行时它最终会被迁移到要用到它的地方并行计算机访存模型（）模型所有存储器都是私有的；绝大多数都不支持远程存储器的访问；在中，就消失了。并行计算机访存模型（）模型是高速缓存一致性非均匀存储访问模型的简称大多数使用基于目录的高速缓存一致性协议；保留结构易于编程的优点，也改善常规的可扩放性；实际上是一个分布共享存储的多处理机系统；它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。并行计算机系统的不同访存模型分类2.2并行计算模型同步并行计算模型共享存储的模型（模型）分布存储的模型（互联网络模型）异步并行计算模型异步模型模型模型C3模型2.2.1同步并行计算模型模型基本概念由和1978年提出，又称模型。有一个集中的共享存储器和一个指令控制器，通过的交换数据，隐式同步计算。ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory共享存储模型模型（），不允许同时读和同时写（），允许同时读但不允许同时写（），允许同时读和同时写()：仅允许写入相同数据()：仅允许优先级最高的处理器写入()：允许任意处理器自由写入特点优点：适合于并行算法的表达、分析和比较；使用简单，很多诸如处理器间通信、存储管理和进程同步等并行计算机的低级细节均隐含于模型中；易于设计算法和稍加修改便可运行在不同的并行计算机上；缺点不适合并行机，忽略了的竞争、通讯延迟等因素计算能力比较是最强的计算模型，可倍模拟和分布存储模型采用一维线性连接的模型，简记为采用网孔连接的模型，简记为采用树形连接的模型，简记为采用树网连接的模型，简记为采用立方连接的模型，简记为采用立方环连接的模型，简记为采用洗牌交换连接的模型，简记为采用蝶形连接的模型，简介为采用多级互联网络连接的模型，简记为2.2.2异步计算模型特点:每个处理器都有其本地存储器、局部时钟和局部程序无全局时钟各处理器异步地独立执行各自的指令处理器间的通信经过共享全局存储器（）同步栅栏（）需在并行程序中显式地加入同步路栅栏同步各进程一条指令可在非确定但有限的时间内完成。模型中有四类指令:全局读：将全局存储单元中的内容读入本地存储器单元中局部操作：对本地存储器中的数执行操作，其结果存入本地存储器中全局写：将本地存储器单元中的内容写入全本地存储器单元中同步：在程序的某一个逻辑点进程同步，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序的计算过程的性能计算时间设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而增加；同步路障时间为(p) 满足关系；或设为全局各处理器执行时间最长者，则上的计算时间为优缺点易编程和分析算法的复杂度，但与现实相差较远其上并行算法非常有限，也不适合模型。模型（）基本概念由(1990)提出的，“块”同步模型，是一种异步模型，支持消息传递系统，块内异步并行，块间显式同步。模型参数p：处理器数(带有存储器)l：同步障时间()g：带宽因子()=1模型计算过程计算过程由若干超级步组成，每个超级步计算模式为左图优缺点强调了计算和通讯的分离，提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多h条消息的传递等。3模型模型(，1993)是一种分布存储的、点到点通信的多处理机模型，其中通信网络由一组参数来描述，但它并不涉及到具体的网络结构，也不假定算法一定要用显式的消息传递操作进行描述。L：o:g:C3（,,）模型是一个与体系结构无关的粗粒度的并行计算模型，旨在能反映计算复杂度，通信模式和通信期间潜在的拥挤等因素对粗粒度网络算法的影响。2.3进程2.3.1进程概念进程四元组（P,C,D,S）P是程序代码C是进程的控制状态D是进程的数据S是进程的执行状态两个特征：资源特征，包括程序执行所必需的计算资源，例如程序代码、内存地址空间、文件系统、设备、程序计数器、寄存器、栈空间等执行特征，包括在进程执行过程中动态改变的特征，例如指令路径（即进程执行的指令序列）、进程的控制与执行状态等。进程状态非存在状态：进程依赖的程序还没有投入运行；就绪状态：进程由其父进程（例如，操作系统的内核进程或进程，或其它应用程序进程）调入并准备运行；运行状态：进程占有和其它必须的计算资源，并执行指令；挂起状态：由于或其它必须的计算资源被其它进程占有，或必须等待某类事件的发生，进程转入挂起状态，以后一旦条件满足，由操作系统唤醒并转入就绪状态；退出状态：进程正常结束或因异常退出而被废弃2.3.2进程间通信现代操作系统提供基本的系统调用函数，允许位于同一台处理机或不同处理机的多个进程之间相互交流信息三种表现形式：通信：进程间的数据传递称为进程间通信。同步：同步是使位于相同或不同处理机中的多个进程之间相互等待的操作，它要求进程的所有操作均必须等待到达某个控制状态之后才进行。聚集（或规约）：聚集将位于相同或不同处理机中的多个进程的局部结果综合起来，通过某种操作，产生一个新的结果，存储在某个指定的或者所有的进程的变量中。具体实现：在共享存储环境中，通过读/写操作系统通过的共享数据缓存区来实现在分布式存储网络环境中，通过网络通信来实现同步同步概念运行在不同处理器上的进程之间需要通信以协调地完成一个任务。进程间的通信可以通过使用共享变量来实现信息交换。但对共享变量的访问要保证互斥访问。即：保证每次只有一个进程访问共享变量。同步机制的实现硬件提供同步原语；用户层软件实现。在小规模或竞争较少的情况下硬件的关键功能：提供不可中断的指令；或实现原子地读和更新一个值的指令。软件机制在硬件基础上建立：如自旋锁。在规模较大或竞争较多的情况下同步成为性能瓶颈。（延时增加）需研究更好的硬件机制来支持同步。基本硬件同步原语硬件原语的功能支持原子地读和修改存储单元；以某种方式告知是否进行了原子读或写操作(执行反馈)。是构造同步操作和同步库的基本构造模块。几种典型的硬件原语原子交换（)测试和设置（）取值和增值（）指令对：链接指令/条件指令（/）锁同步原子交换自旋锁：R20，#1: R2,0(R1)R2,无一致性时，锁变量存放在内存中。有一致性时，锁变量可存放在本地中。获得锁的自旋过程在本地中进行，不必作全局访问。因访问局部性，锁值常驻,减少了获得锁的时间。缺点每次交换都尝试作一次写操作，此时，若多个处理器都试图获得锁，则每个处理器都会产生一个写失配。:R2,0(R1); R2,;R2,R0，#1; R2，0（R1）;R2,;锁同步链接条件: R2,0(R1) R2,R20，#1 R2,0(R1) R2,第一条转移指令是自旋循环，（读锁值，等待可用。）第二条转移指令：是当两个处理器同时看到可用锁后竞争获得锁，失败者重新进入自旋等待。自旋锁的扩展性不好由于由目录或总线来完成处理器同步操作的串行化，当处理器数目增大时，处理器间同步会使锁的竞争迅速加剧并带来大量的总线数据传输。造成同步性能下降。自旋锁的同步性能分析设：共享总线的10个同时企图对一共享变量上锁（竞争锁）。设每次总线事务（一次或）需要花100个时钟周期。忽略在中读写锁的时间。设开始的时候所有锁均释放，所有处理器都在自旋读锁值。假设总线是完全对称的，要等在新请求前的所有请求服务完以后才会响应新到来的请求，并且所有处理器一样快。问：10个处理器都得到一次锁，共需完成多少个总线事务？完成10个处理器的上锁任务，需要多长时间。锁释放后的锁值竞争过程

P0

P1

P2

Coherencestateoflock

Bus/directory

activity

1

Has

lock

Spins,testiflock==0

Spins,testiflock==0

Shared

None

2

Setlock

to0

(Invalidate

received)

(Invalidate

received)

Exclusive

(P0)

Writeinvalidateoflock

VariablefromP0

3

Cachemiss

Cachemiss

Shared

Bus/directoryservicesP2cachemiss;writebackfromP0

4

(Waitswhilebus/directorybusy)

Lock=0

Shared

CachemissforP2Satisfied

5

Lock=0

Executesswap,getscachemiss

Shared

CachemissforP1satisfied

6

Executesswap,getscachemiss

Completess

0

andsetLock=1

Exclusive

(P2)

Bus/directoryservicesP2cachemiss;generatesinvalidate

7

Swapcompletesandreturns1,and

setLock=1

Entercritical

section

Exclusive

(P1)

Bus/directoryservicesP1

cachemiss;generateswriteback

8

Spins,testif

Lock==0

None

自旋锁的同步性能分析2i个处理器从上一次释放锁到下次释放锁的过程i次读锁值访问总线；i次锁锁值访问总线1次释放锁，锁的所有者写写失配10个处理器作无效化操作。共有2i+1个总线事务；对于n个处理器，共有总线事务是Σ（2i+1）(1)2+2n10个处理器有120个总线事务，共12000个时钟，平均1个锁120时钟改进后的栅栏同步=!;();=+1;(){ =0; =;}();(==);栅栏同步实现：两个自旋锁一个用于锁住共享变量：已到达进程计数器；一个迫使到达的进程自旋等待最后一个进程；();(0)=0;>=+1;();(){=0;=1;}{(1);}栅栏同步的性能分析设：共享总线的10个同时企图执行同步操作。每次总线事务需要花100个时钟周期。忽略在中读写锁的时间以及操作中其它非同步操作的时间。设开始的时候所有10个处理器都在自旋等待对计数器上锁。假设总线是完全对称的，请求按顺序响应,并且所有处理器一样快。问：10个处理器到达，然后释放离开，共需完成多少个总线事务？整个过程需要多长时间。栅栏同步的锁竞争过程栅栏同步的性能分析-2第i个处理器共有34个总线事务最后一个处理器到达栅栏需要少1个总线事务10个处理器总共有204个总线事务: Σ（3i+4）－1=当多处理器数量较多时处理器间对共享变量的访问竞争严重同步性能会成为整个系统性能的瓶颈。3n2+11n2-12.4线程进程不适合细粒度的共享存储并行程序设计。线程（）又被称作轻量级进程。单个线程进程，即通常所说的串行执行多个线程进程来并行执行.多个线程将共享该进程的所有资源特征，并可以使用不同的，对不同的数据进行处理，从而达到提高进程执行速度的目的。2.5并行编程环境比较流行的并行编程环境主要有3类：消息传递、共享存储和数据并行特征消息传递共享存储数据并行典型代表,可移植性所有主流并行计算机,,,并行粒度进程级大粒度线程级细粒度进程级细粒度并行操作方式异步异步松散同步数据存储模式分布式存储共享存储共享存储数据分配方式显式隐式半隐式学习入门难度较难容易偏易可扩展性好较差一般2.6编程语言与编译器自动并行起源于自动向量化结构远远复杂：数据并行编程提供了注释形式的指令来扩展变量类型的说明，能够对数组的数据布局进行相当详细的控制。：共享存储并行编程2.7并行计算性能评测2.7.1并行程序执行时间响应时间从并行程序开始执行到所有进程执行完毕，称为响应时间（也称为墙上时间，）。各个进程的响应时间可进一步分解为：计算时间通信时间同步开销时间同步导致的进程空闲时间。2.7.2加速比性能定律加速比性能定律定律:任务一定定律：时间一定定律：存储一定定律:任务一定定义：P：处理器数；W：问题规模（计算负载、工作负载，给定问题的总计算量）；：应用程序中的串行分量，f是串行分量比例（f=，1）；：应用程序中可并行化部分，1为并行分量比例；p；1：串行执行时间，Tp：并行执行时间；S：加速比，E：效率；出发点：固定不变的计算负载；固定的计算负载分布在多个处理器上的，增加处理器加快执行速度，从而达到了加速的目的。定律：加速比固定负载的加速公式：

WWp可相应地表示为((1))W，则

p→∞时，上式极限为：1/f设，并行开销的额外开销为Wo 加速比定律：加速比处理器关系定律：时间一定出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，必须增多处理器数才能维持时间不变；并行开销Wo：加速比定律：加速比处理器的关系定律：存储一定基本思想：只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之，此时工作负载+（1）W。在p个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到。令因子G（p）反应存储容量增加到p倍时并行工作负载的增加量，所以扩大后的工作负载W=+（1）G（p）W。存储受限的加速公式：并行开销Wo:定律：加速比与存储容量关系G(p)=1时就是加速定律；G(p)变为f+p（1），就是加速定律G(p)>p时，相应于计算机负载比存储要求增加得快，此时Ni加速均比加速和加速高。加速比讨论参考的加速经验公式：p≤S≤P线性加速比：很少通信开销的矩阵相加、内积运算等p的加速比：分治类的应用问题通信密集类的应用问题：S=1/C(p)超线性加速绝对加速：最佳并行算法与串行算法相对加速：同一算法在单机和并行机的运行时间2.7.3并行程序性能评价方法浮点峰值性能与实际浮点性能数值效率和并行效率2.7.4程序性能优化串行程序性能优化调用高性能库，比如优化的，等选择适当的编译器优化选项合理定义数组维数注意嵌套循环的顺序，尽量改善数据访问的局部性循环展开并行程序性能优化减少通信量、提高通信粒度全局通信尽量利用高效集合通信算法挖掘算法的并行度，减少空闲等待负载平衡通信、计算的重叠通过引入重复计算来减少通信，即以计算换通信2.8常用并行数值算法假设算法针对的是一台有p个处理机的并行系统，每个处理机上运行一个进程，表示第j个处理机或进程，表示当前的处理机或进程，()和()分别表示在中把x传送到和从中接收x，此外，用ip表示i对i取模运算。通常采用的是矩阵在处理机阵列按卷帘方式存放。设分块矩阵是8×8，处理机阵列是3×2，则矩阵的存放方式如下：2.8.1常用并行数值算法——并行矩阵乘法jiABC2.8.1常用并行数值算法——并行矩阵乘法串行矩阵乘法 串行矩阵乘积子程序（形式） I=1,M J=1,L K=1,N C（）=C（）+A（）*B（）

串行矩阵乘积子程序（形式） J=1,L K=1,N I=1,M C（）=C（）+A（）*B（）

常用并行划分列块带状划分行循环带状划分常用并行划分2块棋盘划分循环棋盘划分常用并行数值算法——行列划分算法数据结构：和存放在中(0,1,2,…1) 的计算时按对角线位置进行(乘加) p个处理机，一维结构,每次每个处理机计算出一个 计算C需要p次来完成。TT行列划分算法分析

A0A1A2….….1B0B1B2….….1P0P1P2…..1=子阵对应元素相乘的计算是按对角线进行的×行列划分算法程序(1)p;(1)p;01 ()p

(1){()()}{}设：l为列下标=P0a00a01a02a03b00b10b20b30P1a10a11a12a13b01b11b21b31P2a20a21a22a23b02b12b22b32P3a30a31a32a33b03b13b23b33行列划分算法4×4实例—0P0a00a01a02a03b00b10b20b30P1a10a11a12a13b01b11b21b31P2a20a21a22a23b02b12b22b32P3a30a31a32a33b03b13b23b33对应行列子块元素相乘求和呈对角线位置子矩阵B垂直循环传送给相邻P,垂直滚动发送地址：1p接收地址：1p颜色的位置行列划分算法4×4实例—1P0a00a01a02a03b01b11b21b31P1a10a11a12a13b02b12b22b32P2a20a21a22a23b03b13b23b33P3a30a31a32a33b00b10b20b30对应行列子块元素相乘求和呈对角线位置子矩阵B垂直循环传送给相邻P,垂直滚动发送地址：1p接收地址：1p行列划分算法4×4实例—2P0a00a01a02a03b02b12b22b32P1a10a11a12a13b03b13b23b33P2a20a21a22a23b00b10b20b30P3a30a31a32a33b01b11b21b31对应行列子块元素相乘求和呈对角线位置子矩阵B垂直循环传送给相邻P,垂直滚动发送地址：1p接收地址：1p行列划分算法4×4实例—3P0a00a01a02a03b03b13b23b33P1a10a11a12a13b00b10b20b30P2a20a21a22a23b01b11b21b31P3a30a31a32a33b02b12b22b32对应行列子块元素相乘求和呈对角线位置子矩阵B垂直循环传送给相邻P,垂直滚动发送地址：1p接收地址：1p常用并行数值算法——行行划分算法TTTT数据结构：和存放在中(0,1,2,…1) 计算时按对角线位置进行的部分积 p个处理机，一维结构 每次每个处理机计算出的部分积,采用乘累加 计算C需要p次来完成。行行划分算法分析

A子阵列块与B子阵对应元素相乘,构成,每次得出的部分积,要累加的计算是按行进行的×+行行划分算法分析-2

A0A1A2….….1B0B1B2….….1P0P1P2…..1×P0a00a01a02a03b00b01b01b03P1a10a11a12a13b10b11b12b13P2a20a21a22a23b20b21b22b23P3a30a31a32a33b30b31b32b33颜色部分值的位置行行划分算法程序1=(1)p;1=(–1)p;i=01 l=（i+）p

(i1){(1)(1)}{}设：l为行下标= 0,1,2…1P0a00a01a02a03b00b01b01b03P1a10a11a12a13b10b11b12b13P2a20a21a22a23b20b21b22b23P3a30a31a32a33b30b31b32b33行行划分算法4×4实例—0,0与各元素相乘,构成,乘累加子矩阵B垂直循环传送给相邻P发送地址：1p接收地址：1pP0a00a01a02a03b00b01b01b03P1a10a11a12a13b10b11b12b13P2a20a21a22a23b20b21b22b23P3a30a31a32a33b30b31b32b33行行划分算法4×4实例—1,1与各元素相乘,构成,乘累加子矩阵B垂直循环传送给相邻P发送地址：1p接收地址：1pP0a00a01a02a03b10b11b12b13P1a10a11a12a13b20b21b22b23P2a20a21a22a23b30b31b32b33P3a30a31a32a33b00b01b02b03行行划分算法4×4实例—2,2与各元素相乘,构成,乘累加子矩阵B垂直循环传送给相邻P发送地址：1p接收地址：1pP0a00a01a02a03b20b21b22b23P1a10a11a12a13b30b31b32b33P2a20a21a22a23b00b01b02b03P3a30a31a32a33b10b11b12b13行行划分算法4×4实例—3,3与各元素相乘,构成,乘累加子矩阵B垂直循环传送给相邻P发送地址：1p接收地址：1pP0a00a01a02a03b30b31b32b33P1a10a11a12a13b00b01b02b03P2a20a21a22a23b10b11b12b13P3a30a31a32a33b20b21b22b23常用并行数值算法算法(块划分)数据结构：A、B和C划分成m×m的方块阵、和, 其中、和均为n×n的方阵。 、和存放在 设处理器数m×m，二维结构 每次每个处理机计算出的部分积,采用乘累加 计算C需要p次来完成。广播滚动算法分析

×设：块置换矩阵()×算法分析-2

定义：对角块矩阵((l))(m)算法分析-3

算法分析4

算法分析5 传送，每个处理器做对应子块乘累加，一次完成的部分积。循环m次完成C的全部乘法算法：列向右在行内广播传送,行向上在列内滚动传送.P0,0P1,0P2,0Pm-1,0P0,1P1,1P2,1Pm-1,1P0,2P1,2P2,2Pm-1,2P0,m-1P1,m-1P2,m-1Pm-1,m-1A0,0B0,0A0,1B0,1A0,2B0,2A0,m-1B0,m-1A1,0B1,0A1,1B1,1A1,2B1,2A1,m-1B1，m-1A2,0B2,0A2,1B2,1A2,2B2,2A2,m-1B2,m-1Am-1,0Bm-1,0Am-1,1Bm-1,1Am-1,2Bm-1,2Am-1,m-1Bm-1,m-1处理器阵列：初始化数据结构……………………… … … …… … … …块划分并行算法程序在处理机节点上的算法： C=0 1=(1)m;1=(1)m; 1=(1)m;1=(1)m; i=01 k=（+i）m; r=（k–i）m （==k==r） (A,(,1));(); （==r） （,（,1））; (k1)(,(,1)); {} C=C+*B; （i1） （B,（1,））;（B,（1,））; {} {}A0,0B0,0A0,1B0,1A0,2B0,2A03B0,3A1,0B1,0A1,1B