3_多线程

1多核程序设计吉林大学计算机科学与技术学院计算机协同工作教研室包铁邮箱：[e-mail]22第二章并行计算基础—复习32.0并行计算并行计算就是将一个大规模的计算问题分解成若干小的任务，通过运行在多个运算部件上的这些小任务的合作来求解一个规模很大的计算问题的一种方法。并行计算既能降低单个问题求解的时间，还能增加问题求解规模，从而提高问题求解精度和系统的吞吐率。42.0并行计算并行计算的分类强并行计算：如果一个计算由若干子计算构成，若各子计算之间不存在依赖关系，可以并行计算，那么这种计算可以称为强并行计算。(循环)弱并行计算：如果一个计算由若干子计算构成，若各子计算之间存在依赖关系，不能并行计算，但是单个的子计算内又可以分解为若干更小粒度的子计算，且这些更小粒度的子计算是可以并行执行的，这种并行计算可以称为弱并行计算。52.0并行计算层次和代码粒度funcnc1(){...}funcnc2(){...}funcnc3(){...}a[0]=...b[0]=...a[2]=...b[2]=...a[1]=...b[1]=...+/任务i-1×任务i-1任务i-1消息消息并行级别任务级控制级数据级指令级代码粒度粗粒度中粒度细粒度甚细粒度62.0并行计算并行程序设计模式►►►►►数据分解模式：将数据分解成若干独立的子数据块，每个线程处理其中的一个或多个子数据块；√√√数据集合√？？？？？？？？72.0并行计算并行程序设计模式►►►►►分治模式：将一个原问题的求解分解为多个子问题的求解，然后再将多个子问题的解通过一定的计算方法合并为原问题的解；问题集合82.0并行计算并行程序设计模式►►►►►流水线模式：将一个计算过程分解成流水线式的多个步骤序列，对于每个步骤的处理使用一个或多个线程来实现；获取网页文件数据处理网页文件数据显示网页文件数据网页文件浏览过程92.0并行计算任务并行模式：将一个大的静态计算任务分解成若干独立的小计算任务，让这些小计算任务并行执行（循环，任务量的平均划分）；任务图调度模式：将一个大的静态任务分解成若干小的计算任务时，由于很多时候各个小任务在执行时许多非独立的小任务之间存在依赖关系，将这种依赖关系通过一个无环有向图来描述，这个图就是任务图，对它的并行化方法是任务调度问题，这就是任务图调度模式;102.0并行计算动态任务调度模式:任务图调度模式调度的是静态的任务，但是在很多情况下任务不是静态的而是在运行过程中动态产生的。运用共享资源分布式计算的知识实现的关于动态任务调度的并行模式就是动态任务调度模式，它的突出特点就是可以实现并行计算。112.1多级存储体系结构Cache的主要功能解决内存墙性能瓶颈问题主要实现方法提高cache命中率，即减少访问内存的次数cache命中率：程序执行过程中cache命中的总次数和内存访问总次数的比值方法依据程序的数据访问具有局部性时间局部性空间局部性122.1多级存储体系结构在下面的多级存储模型中，从下往上，每个字节的成本越来越高，但访存延迟越来越小，带宽越来越高。主要包括两个问题：cache映射策略；内存访问模式。132.1多级存储体系结构Cache的原理cache以cache线为基本组成单位，每条cache线包含L个字，每个字为8个字节。内存空间分割成块，每块大小与cache线长度一致。数据在内存和cache之间的移动以cache线为基本单位。cache的映射策略指的是内存块和cache线之间如何建立相互映射关系,即cache如何在内存中取数并存储。142.1多级存储体系结构152.1多级存储体系结构Cache的映射策略►►►►►直接映射策略（directmappingstrategy）每个内存块只能唯一的映射到一条cache线中K－路组关联映射策略Cache被分解为若干个组，每个组由K个Block组成，内存块按Cache组数进行分块组直接映射，组内映射到任意Block全关联映射策略内存块可以被映射到Cache中的任意Cache线16Cache的映射策略►►►►►L0L1L2L3L4L5L6L7B0B1B2B3B4B5B6B7B8B9B10B11B12B13B14B17………A12345…B12345…数组：A(N),B(N),C(N),D(N)DoI=1,NA(I)=A(I)+B(I)+C(I)+D(I)17并行体系结构下的Cache一致性在含有多个Cache的系统中，数据的多个副本造成的不一致200200182.2并行计算模型SIMD同步并行计算模型共享存储的SIMD模型（PRAM模型）分布存储的SIMD模型（SIMD互联网络模型）MIMD异步并行计算模型异步PRAM模型BSP模型LogP模型C3模型19进程两个特征：资源特征（反映进程是资源拥有的最小单位），包括程序执行所必需的计算资源，例如程序代码、内存地址空间、文件系统、I/O设备、程序计数器、寄存器、栈空间等执行特征（反映进程是系统调度的基本单元），包括在进程执行过程中动态改变的特征，例如指令路径（即进程执行的指令序列）、进程的控制与执行状态等。2.3进程--Process202.4线程进程不适合细粒度的共享存储并行程序设计。线程（threads）又被称作轻量级进程。单个线程进程，即通常所说的串行执行多个线程进程来并行执行.多个线程将共享该进程的所有资源特征，可以使用不同的CPU，对不同的数据进行处理，从而达到提高进程执行速度的目的。212.5并行编程环境比较流行的并行编程环境主要有3类：消息传递、共享存储和数据并行特征消息传递共享存储数据并行典型代表MPI,PVMOpenMPHPF可移植性所有主流并行计算机SMP,DSMSMP,DSM,MPP并行粒度进程级大粒度线程级细粒度进程级细粒度并行操作方式异步异步松散同步数据存储模式分布式存储共享存储共享存储数据分配方式显式隐式半隐式学习入门难度较难容易偏易可扩展性好较差一般222.6编程语言与编译器对并行编程已经取得成功的三项技术：自动并行起源于自动向量化，依赖分析（访问同一单元）MIMD体系结构上更复杂（分布数据和优化通信）HPF：数据并行编程（数据管理自动并行化）HPF提供了注释形式的指令来扩展变量类型的说明，能够对数组的数据布局进行相当详细的控制。（如：cyclic(k)，independent）OpenMP：共享存储并行编程（paralleldo）232.7并行计算性能评测2.7.1并行程序执行时间响应时间从并行程序开始执行到所有进程执行完毕，称为响应时间（也称为墙上时间，wallclocktime）。各个进程的响应时间可进一步分解为：计算CPU时间：执行时间、系统时间通信CPU时间同步开销时间同步导致的进程空闲时间。242.7.2加速比性能定律加速比性能定律：加速比是指一个给定应用，并行算法的执行速度相对于串行算法的执行速度加快了多少倍。Amdahl（阿姆德尔）定律:任务一定Gustafson（古斯塔夫森）定律：时间一定Sun-Ni定律：存储一定25Amdahl定律（固定计算负载）定义参数：p：处理器数；W：问题规模（给定问题的总计算量即计算负载）；Ws：应用程序中的串行分量，f是串行分量比例；WP：应用程序中可并行化部分，1-f为并行分量比例；Ws+Wp=W；Ts：串行执行时间，Tp：并行执行时间；S：加速比，E：效率；26Amdahl定律基本出发点：许多科学计算，实时性要求很高，但计算负载固定不变；固定的计算负载可以分布在多个处理器上；利用增加处理器数量来提高固定负载的计算速度，从而达到实时性要求；27Amdahl定律：加速比固定负载的加速公式：Ws+Wp可相应地表示为(f+(1-f))W，则加速比p→∞时，上式极限为：S=1/f含义：随着处理器数目的无线增大，并行系统所能达到的加速比上限为1/f即并行加速受程序的串行分量影响pWWsWpWsSP/)1(11)1(pfppffffS28Amdahl定律：加速比处理器关系程序中顺序部分的百分比f(c)0%1%2%3%4%100%加速比SS1024=1024/(1+1023f)1024x91x48x31x24x1xWpWpWpWpWpWpW1W1W1W1W1W1工作负载W处理器数P(a)123456T1T1TpTpTpTpTpTpT1T1T1执行时间T处理器数P(b)T112345629Amdahl定律：结论和说明应用程序的执行速度随核数量增大而变快，但不是线性关系。因为任何应用程序都有串行部分。串行分量越大，可能获得的加速比越小，因此，要充分挖掘程序可能的并行部分。并行时的额外开销越大，可能获得的加速比越小，因此，要尽量减小额外开销，如通信开销。这是一个悲观的结论。3030Amdahl定律：举例工人人数时间加速比(speedup)130+300+30=3601.0230+150+30=2101.71030+30+30=904.010030+3+30=635.7无限多30+0+30=606.0工人给篱笆刷油漆，一共300个篱笆：准备30分钟－－串行。1分钟刷一个篱笆－－可以并行。刷完了，整理工具。30分钟。－－串行。31Gustafson定律：时间一定出发点：对于很多大型计算，精度要求很高，在此类应用中精度是关键因素为了提高精度，必须加大计算量在计算时间是固定不变的条件下完成大的计算量则必须增多处理器数；除非学术研究，在实际应用中没有必要固定工作负载而使计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。Gustafson给出了放大问题规模的加速比公式32Gustafson定律：时间一定加速比并行开销Wo：PSSSSWWpWpWpWppWpWpWS/')p-f(p--p)f(p-f)p(fS'111WWfpf33Gustafson定律：加速比处理器的关系程序中顺序部分的百分比f(c)S'1024=1024-1023f0%1%2%3%4%1024x1014x1004x993x983x加速比S'处理器数P工作负载W(a)W1W1W1W1W1W1WpWpWpWpWpWp123456TpT1T1T1T1T1T1执行时间T处理器数P(b)123456TpTpTpTpTp34Gustafson定律结论：当p→∞时，S’与p几乎成线性关系，其斜率为1-f;意味着随着处理器数目的增加，加速比几乎与处理器的速度成比例地线性增加，串行比例f不再是程序并行执行性能的瓶颈。这是一个乐观的结论。当考虑程序并行运行的额外开销时，由于Wo是p的函数，将会随p增大、减小或不变，若要达到线性加速比则必须使Wo随p减小，这很困难。35Sun-Ni定律：存储一定基本思想：只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之，此时工作负载W=fW+（1-f）W。在p个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到pM。令因子G（p）反应存储容量增加到p倍时并行工作负载的增加量，所以扩大后的工作负载W=fW+（1-f）G（p）W。存储受限的加速公式：ppGffpGff/11pWpGffWWpGffWS/11''36Sun-Ni定律：加速比与存储容量关系G(p)=1时就是Amdahl加速定律；G(p)=p变为f+p（1-f），就是Gustafson加速定律G(p)p时，表示计算机负载比存储要求增加得快，此时Sun-Ni加速均比Amdahl加速和Gustafson加速要高。T1Tp执行时间T处理器数P(b)T