并行程序设计ChapterH.ppt

第一章第一章 概概 述述11.1 并行化的现状与未来并行化的现状与未来21.1 并行化的现状与未来并行化的现状与未来一、并行的威力和潜力一、并行的威力和潜力•并行的目的并行的目的–加快计算速度加快计算速度•传统程序中的并行性传统程序中的并行性–大多数编程语言的语义体现为顺序执行大多数编程语言的语义体现为顺序执行 程序都假设指令是按顺序执行的程序都假设指令是按顺序执行的–提升串行程序性能的方法：提升串行程序性能的方法：隐式并行隐式并行(hidden parallelism)•为加快程序执行速度，在程序执行过程中部分操作被并行执行，并对为加快程序执行速度，在程序执行过程中部分操作被并行执行，并对程序程序透明透明•指令级并行指令级并行(ILP—Instruction Level Parallelism) 举例：计算举例：计算(a + b) * (c + d)时，时，(a+b)和和(c+d)可以分别并行计算可以分别并行计算•隐式并行由编译和系统结构支持隐式并行由编译和系统结构支持–多级流水、多发射、乱序执行、多级流水、多发射、乱序执行、…–问题：隐式并行的发掘问题：隐式并行的发掘有极限有极限，支持隐式并行的处理器硬件，支持隐式并行的处理器硬件也存在极限也存在极限3二、多核处理器带来的问题二、多核处理器带来的问题•摩尔定律摩尔定律(Moore’s Law)–Intel公司创始人公司创始人Gordon Moore首先提出首先提出–主要内容：主要内容：集成电路上可容纳的晶体管数目大约每集成电路上可容纳的晶体管数目大约每18个月增加一倍个月增加一倍–通常认为，其集成电路性能每通常认为，其集成电路性能每18个月也增加一倍个月也增加一倍–摩尔定律从摩尔定律从1960年代延续至今年代延续至今–摩尔定律并不是科学定律，而是技术摩尔定律并不是科学定律，而是技术-经济定律经济定律–摩尔定律在很大程度上推动了包括计摩尔定律在很大程度上推动了包括计算机技术在内的信息技术的发展算机技术在内的信息技术的发展–摩尔定律还能走多远？摩尔定律还能走多远？–在可预见的在可预见的10～～15年仍将延续年仍将延续–新材料、新工艺、新材料、新工艺、…1.1 并行化的现状与未来并行化的现状与未来4在单核处理器时代，提升处理器性能的主要方法：在单核处理器时代，提升处理器性能的主要方法：•提升主频提升主频–1978：：8086 5MHz–2005：：P4 >3.2GHz•多种指令级并行技术多种指令级并行技术(ILP—Instruction level Parallelism)–多级流水、多发射和乱序多级流水、多发射和乱序执行执行(out-of-order execution)等等–占用了大量硅片面积占用了大量硅片面积•增加增加cache容量容量1.1 并行化的现状与未来并行化的现状与未来5•挑战一：处理器功耗随主频提升而持续增长挑战一：处理器功耗随主频提升而持续增长–栅极漏电越来越大栅极漏电越来越大–散热越来越困难散热越来越困难•挑战二：指令级并行技术已近极限挑战二：指令级并行技术已近极限–主要原因：程序中的指令级并行性是有限的主要原因：程序中的指令级并行性是有限的•在摩尔定律延续的情况下，多核处理在摩尔定律延续的情况下，多核处理器应运而生器应运而生•从单纯追求性能从单纯追求性能  追求追求Performance/Watt•多核处理器在一定程度上是多核处理器在一定程度上是“无奈无奈”的选择的选择•目前多核处理器已成为主流，且有向目前多核处理器已成为主流，且有向众核众核(many-core)发展的趋势发展的趋势1.1 并行化的现状与未来并行化的现状与未来61.1 并行化的现状与未来并行化的现状与未来•多核处理器带来的问题多核处理器带来的问题–过去：并行程序设计只涉及少数专业领域过去：并行程序设计只涉及少数专业领域•高性能计算、服务器应用开发、高性能计算、服务器应用开发、…–现在和将来：桌面应用也涉及到并行程序设计现在和将来：桌面应用也涉及到并行程序设计•必须通过并行程序设计使多核资源得到充分利用必须通过并行程序设计使多核资源得到充分利用高性能计算高性能计算 vs. 服务器计算服务器计算 vs. 客户端并行计算客户端并行计算71.1 并行化的现状与未来并行化的现状与未来二、顺序程序与并行程序二、顺序程序与并行程序•并行编译：通过编译将顺序程序并行化并行编译：通过编译将顺序程序并行化–相关研究已经进行了相关研究已经进行了30多年多年–编译可进行局部的并行化，但无法改变算法的基本特征编译可进行局部的并行化，但无法改变算法的基本特征•要更好地进行并行化计算，需要从算法设计到编程都考虑并行化要更好地进行并行化计算，需要从算法设计到编程都考虑并行化•一个简单的例子：求和一个简单的例子：求和–对对n个数的序列求和个数的序列求和 x0, x1, x2, …, xn-1–迭代求和迭代求和sum = 0;for ( i = 0; i < n; i++ ){sum += x[i];}顺序求和，难以并行顺序求和，难以并行后续迭代需要使用前后续迭代需要使用前次迭代的计算结果，次迭代的计算结果，存在数据相关存在数据相关(依赖依赖)81.1 并行化的现状与未来并行化的现状与未来二、顺序程序与并行程序二、顺序程序与并行程序–顺序求和顺序求和  成对求和成对求和t[0] = x[0] + x[1];t[1] = x[2] + x[3];t[2] = x[4] + x[5];t[3] = x[6] + x[7];t[4] = t[0] + t[1];t[5] = t[2] + t[3];sum = t[4] + t[5];可以并行计算可以并行计算•并行计算常用操作：并行前缀求和并行计算常用操作：并行前缀求和(parallel prefix sum)–也称为也称为扫描扫描(scan)对对n个数的序列个数的序列x0, x1, x2, …, xn-1计算如下序列计算如下序列y0, y1, y2, …, yn-1其中每个其中每个yi是前是前i个元素的和：个元素的和：yi = Σj≤iXj一个好的并行程序需一个好的并行程序需要从算法设计到编程要从算法设计到编程都考虑并行化都考虑并行化91.2 并行计算机与并行计算模型并行计算机与并行计算模型101.2 并行计算机与并行计算模型并行计算机与并行计算模型一、并行计算机分类一、并行计算机分类 •弗林弗林(Flynn)分类法分类法–单指令流单数据流单指令流单数据流(SISD—Single Instruction stream Single Datastream)•典型实例：传统顺序计算机典型实例：传统顺序计算机–单指令流多数据流单指令流多数据流(SIMD—Single Instruction stream Multiple Datastream)•典型实例：向量计算机典型实例：向量计算机–多指令流单数据流多指令流单数据流(MISD—Multiple Instruction stream Single Datastream)•典型实例：无典型实例：无–多指令流多数据流多指令流多数据流(MIMD—Multiple Instruction stream Multiple Datastream)•典型实例：多处理机系统典型实例：多处理机系统√√11CU--Control Unit; PU—Processing Uning ; MM—Main MemoryIS—Instruction Stream; DS– Data Stream121.2 并行计算机与并行计算模型并行计算机与并行计算模型•多级存储体系结构多级存储体系结构–现代计算机普遍采用冯现代计算机普遍采用冯.诺依曼结构诺依曼结构–存储墙存储墙(memory-wall)问题是冯问题是冯.诺依曼结构的固有问题诺依曼结构的固有问题•处理器与存储器之间的性能差距导致的系统性能瓶颈处理器与存储器之间的性能差距导致的系统性能瓶颈–尚未出现能够从根本上突破存储墙的技术尚未出现能够从根本上突破存储墙的技术•改善方法：多级存储体系、预取等改善方法：多级存储体系、预取等25%52%20%9%60%9%131.2 并行计算机与并行计算模型并行计算机与并行计算模型•另一种并行体系结构分类另一种并行体系结构分类①①共享存储共享存储(shared-memory)系统系统–节点间通过节点间通过共享内存共享内存实现隐式通信，开销小、实现隐式通信，开销小、耦合紧密耦合紧密–可支持多进程可支持多进程和和多线程，进程多线程，进程/线程间可共享线程间可共享变量变量–易于编程易于编程(可编程性好可编程性好)，但系统可扩展性差，但系统可扩展性差②②消息消息传递传递(message-passing)系统系统–又称为分布式内存又称为分布式内存(distributed memory)系统系统–处理器处理器/节点节点间间不不共享内存共享内存，通过显式地发送，通过显式地发送/接收消息进行通信接收消息进行通信–一般只支持多进程，仅节点内多线程一般只支持多进程，仅节点内多线程–编程较困难编程较困难(可编程性差可编程性差)，但系统可扩展性，但系统可扩展性好好•随着随着技术发展，很多系统为技术发展，很多系统为混合混合结构结构–例如：采用多核处理器的机群系统例如：采用多核处理器的机群系统141.2 并行计算机与并行计算模型并行计算机与并行计算模型二、几种典型的并行计算机二、几种典型的并行计算机 ①①片上多处理器片上多处理器(CMP—Chip Multiprocessor)②②对称多处理对称多处理(SMP—Symmetrical Multi-processing)或或NUMA(Non-Uniform Memory Access)③③异构处理器异构处理器(Heterogeneous processor)④④机群机群(Cluster)⑤⑤超级计算机超级计算机(Supercomputer)这些系统分属共享存储、消息传递型、或是混合型系统这些系统分属共享存储、消息传递型、或是混合型系统151.2 并行计算机与并行计算模型并行计算机与并行计算模型①①片上多处理器片上多处理器(CMP--Chip Multiprocessor)–又称为多核又称为多核(multi-core)处理器处理器–同一微处理器芯片内集成多个处理器核同一微处理器芯片内集成多个处理器核–是摩尔定律是摩尔定律(Moore’s Law)发展与性能发展与性能/功耗折衷的产物功耗折衷的产物–例例1：：Intel Core i7四核处理器四核处理器•L2 cache: 4x256KB•L3 cache: 8MB16•多核处理器正在朝众核多核处理器正在朝众核(many-core)方向发展方向发展Intel Xeon Phi•60核，支持核，支持240个并行线程个并行线程•共享内存，核间共享内存，核间cache一致性一致性•单处理器性能达单处理器性能达1TeraFlops双精度浮点双精度浮点•核的特性核的特性–基于基于Pentium架构，做了改进架构，做了改进(64位，位，SIMD支持支持)–32KB L1 cache, 512KB L2 cache(核内核内)–支持支持512bit向量，传统的向量，传统的SSE 128bit，，AVX 256bit–支持支持4个超线程，普通个超线程，普通Xeon处理器是处理器是2个超线程个超线程–主频主频1.053GHzTilera•TILE64–64个同构处理器核，每个核有独立个同构处理器核，每个核有独立L1和和L2 cache–核间互连：片上核间互连：片上mesh结构结构–片上集成片上集成4个内存控制器和多个个内存控制器和多个I/O部件部件–每个核可独立运行每个核可独立运行OS，也可几个核组合以，也可几个核组合以SMP形形式运行式运行OS，，Linux–面向计算密集型嵌入式应用，如网络数据包处理、面向计算密集型嵌入式应用，如网络数据包处理、音视频高速处理音视频高速处理171.2 并行计算机与并行计算模型并行计算机与并行计算模型②②异构处理器异构处理器(Heterogeneous processor)–结构：通用核结构：通用核 + 专用部件专用部件(核核)–由通用处理器核完成通用计算部分，由专用部件完成密集计由通用处理器核完成通用计算部分，由专用部件完成密集计算部分算部分–典型实例典型实例•GPU(Graphic Processing Unit)•现场可编程门阵列现场可编程门阵列(FPGA)•CellAMD Fusion体系结构Intel Larrabee体系结构Nvidia GT200系列GPU18•GPU举例：举例：Nvidia Tesla K20X–2688个流处理核个流处理核–处理器频率：处理器频率：732MHz–单精度浮点性能：单精度浮点性能：3.95TFlops–双精度浮点性能：双精度浮点性能：1.31TFlops–专用显存数量：专用显存数量：6GB–最大功耗：最大功耗：235Watt–接口：接口：PCI Express x16–编程环境：编程环境：CUDA•Linux/Windows系统，系统，C语言语言19③③对称多处理对称多处理(SMP—Symmetric Multiprocessor Architecture)–所有处理器访问单一逻辑存储器所有处理器访问单一逻辑存储器–cache一致性机制是影响系统设计的关键因素一致性机制是影响系统设计的关键因素•基于总线监听基于总线监听(snoopy-based)•基于目录基于目录(directory-based)–随着处理器技术发展，随着处理器技术发展，SMP向向NUMA结构发展结构发展•内存分布在多个处理器或节点上内存分布在多个处理器或节点上•硬件实现共享内存硬件实现共享内存Cache一致性示意图一致性示意图典型典型SMP结构结构20•系统举例：双路刀片服务器系统举例：双路刀片服务器–2个个Intel Xeon处理器处理器–由于处理器内置由于处理器内置memory controller，内存分别连接到两，内存分别连接到两个处理器个处理器•访问另一个处理器的访问另一个处理器的RAM的时延的时延比访问本地比访问本地RAM长长•结构类似于结构类似于NUMA(Non-uniform Memory Access)211.2 并行计算机与并行计算模型并行计算机与并行计算模型④④机群机群(Cluster)–将产品化的计算机通过互连网络连接而形成的并行计算机将产品化的计算机通过互连网络连接而形成的并行计算机–主要特征主要特征•各节点只有局部存储器，节点间没有共享存储，节点间通信需通过消各节点只有局部存储器，节点间没有共享存储，节点间通信需通过消息传递机制进行息传递机制进行–互连网络常用技术互连网络常用技术•千兆以太网千兆以太网•Myrinet•Infiniband•…–便于构建，性价比较高，在便于构建，性价比较高，在TOP500中占有相当比例中占有相当比例刀片机箱刀片机箱221.2 并行计算机与并行计算模型并行计算机与并行计算模型⑤⑤超级计算机超级计算机(Supercomputer)–泛指计算性能很高的计算机，通常造价高昂，专门用于各种高性能计算应泛指计算性能很高的计算机，通常造价高昂，专门用于各种高性能计算应用用–相当比例的超级计算机采用机群系统结构相当比例的超级计算机采用机群系统结构–Top500超级计算机排行榜：超级计算机排行榜：•按基准测试程序按基准测试程序Linpack所测得的性能进行排名所测得的性能进行排名2015年年11月月Top500排名前排名前10的超级计算机的超级计算机排名地点系统/制造商处理器核数Rmax(TFlops)Rpeak(TFlops)Power(KW)1中国Tianhe-2 / NUDTIntel Xeon + Phi3386354902178082美国Titan / Cray Inc.AMD Opteron + K20560640175902711282093美国Sequoia / IBM BlueGeneIBM Power171732013278904日本K / FujitsuSparc7050241051011280126595美国Mira / IBM BlueGeneIBM Power78643285861006639456美国Trinity / Cray Inc.Intel Xeon3010568101110787瑞士Piz Daint / Cray Inc.Intel Xeon + K201159846271778823258德国Hazel Hen / Cray Inc.Intel Xeon185088564074039沙特Shaheen II / Cray Inc.Intel Xeon19660855377235283410美国Stampede / PowerEdgeIntel Xeon + Phi46246251688520451023•Supercomputer举例：联想深腾举例：联想深腾7000–1288个刀片节点，其中计算刀片个刀片节点，其中计算刀片1140个，个，I/O节点节点120个，网络启动服务个，网络启动服务器器12个，管理及登录节点个，管理及登录节点16个个–节点配置节点配置•2个个Intel Xeon四核处理器，四核处理器，32GB RAM•Infiniband 4xDDR互连网络接口互连网络接口–1410TB磁盘存储磁盘存储–Linux操作系统，操作系统，LSF作业管理作业管理联想深腾联想深腾70007000天河一号天河一号曙光星云曙光星云24高性能计算的一些典型应用高性能计算的一些典型应用气象数值预报气象数值预报( (沙尘暴沙尘暴) )飞机设计中的飞机设计中的CFDCFD网格网格( (静气动弹性耦合计算静气动弹性耦合计算) )天体物理仿真天体物理仿真( (太阳风太阳风) )汽车碰撞及安全性分析汽车碰撞及安全性分析251.2 并行计算机与并行计算模型并行计算机与并行计算模型三、并行计算机模型三、并行计算机模型 •冯冯.诺依曼模型诺依曼模型(RAM模型模型)–顺序计算机被抽象成由指令执行部件和无限容量顺序计算机被抽象成由指令执行部件和无限容量存储器组成的装置存储器组成的装置–存储器存储程序指令和数据，且任何存储单元能存储器存储程序指令和数据，且任何存储单元能在在“单位单位”时间内读时间内读/写写–指令执行部件按顺序每个周期取出并执行一条指指令执行部件按顺序每个周期取出并执行一条指令令•PRAM模型模型–RAM模型的并行扩展模型的并行扩展–多个指令执行部件多个指令执行部件 + 无限容量存储器无限容量存储器–所有执行部件访问全局存储器，即单一存储器映所有执行部件访问全局存储器，即单一存储器映像像–问题问题•单位时间内实现单一存储器映像实际上不可能单位时间内实现单一存储器映像实际上不可能261.2 并行计算机与并行计算模型并行计算机与并行计算模型•CTA模型模型–Candidate Type Architecture–由由m个标准的顺序计算机个标准的顺序计算机(处处理器或处理单元理器或处理单元)构成，处理构成，处理器通过一个互连网络相连器通过一个互连网络相连–处理器可以访问自己的本地处理器可以访问自己的本地存储器，也可以访问其他处存储器，也可以访问其他处理器的存储器理器的存储器–非本地存储器访问时间非本地存储器访问时间λ>>1–一个全局的控制器帮助完成一个全局的控制器帮助完成初始化、同步等基本操作初始化、同步等基本操作27典典型型互互连连网网络络281.2 并行计算机与并行计算模型并行计算机与并行计算模型•CTA模型模型(续续)–访问非本地存储器的三种技术访问非本地存储器的三种技术•共享存储器共享存储器–需硬件支持需硬件支持–需要有同步机制保证存储一致性需要有同步机制保证存储一致性(memory consistency)•单边通信单边通信(one-sided communication)–支持单一地址共享空间支持单一地址共享空间–不保证存储一致性，由软件保证不保证存储一致性，由软件保证•用专门的用专门的get和和put操作访问非本地地址空间操作访问非本地地址空间•消息传递消息传递(message passing)–处理器只能访问本地存储器处理器只能访问本地存储器–通过消息传递通过消息传递(send()和和recv())访问其他处理器的存储器访问其他处理器的存储器–对硬件要求最少对硬件要求最少291.3 并行性与程序性能并行性与程序性能301.3 并行性与程序性能并行性与程序性能一、并行程序应具备的特征一、并行程序应具备的特征 •正确性正确性–最基本的要求最基本的要求–保证并行程序的正确性比串行程序困难保证并行程序的正确性比串行程序困难•原因：编程复杂；调试困难原因：编程复杂；调试困难•好的性能好的性能–如何评价？如何评价？•可扩展性可扩展性(scalability)–能够运行在不同规模的并行平台上，且性能随之增长能够运行在不同规模的并行平台上，且性能随之增长•性能可移植性性能可移植性(performance portability)–不但要使程序能运行在不同的并行平台上，还要能很好地运不但要使程序能运行在不同的并行平台上，还要能很好地运行在这些平台上行在这些平台上(在各种平台上都有好的性能在各种平台上都有好的性能)–难度较大：并行平台有多个种类，体系结构差异较大难度较大：并行平台有多个种类，体系结构差异较大•共享存储、共享地址空间、分离地址存储器共享存储、共享地址空间、分离地址存储器31二、性能度量二、性能度量(1/2)① ① 执行时间执行时间(execution time)–完成一个并行计算所花费的时间完成一个并行计算所花费的时间–另一个常用指标另一个常用指标•FLOPS(floating-point operations per second)：浮点运算次数：浮点运算次数/秒秒–1GFlops = 109次浮点运算次浮点运算/秒，秒，10亿次亿次–1TFlops = 1000GFlops，万亿次，万亿次–1PFlops = 1000TFlops，千万亿次，千万亿次–1EFlops = 1000PFlops，百亿亿次，百亿亿次•常用做衡量处理器和并行计算机计算性能的指标常用做衡量处理器和并行计算机计算性能的指标•峰值性能峰值性能(peak performance)：理想状态可达到的最高性能：理想状态可达到的最高性能•应用性能：应用程序实际运行获得每秒浮点运算次数应用性能：应用程序实际运行获得每秒浮点运算次数–常用有代表性的基准测试程序，如常用有代表性的基准测试程序，如Linpack、、Lapack、、NPB等等–不同处理器指令系统有差异性，不同处理器指令系统有差异性， MIPS(million instructions per second)指标难以客观地反映处理器计算性能指标难以客观地反映处理器计算性能1.3 并行性与程序性能并行性与程序性能32二、性能度量二、性能度量(2/2)② ② 加速比加速比(speedup)–常用来衡量并行加速的效果，以及常用来衡量并行加速的效果，以及随处理器随处理器/任务数增长的变化情况任务数增长的变化情况–超线性加速比超线性加速比(superlinar speedup)•某些情形下，计算能获得超过线性某些情形下，计算能获得超过线性的加速比的加速比•大多是由于并行后每节点访问的数大多是由于并行后每节点访问的数据集变小，据集变小，cache命中率提高命中率提高加速比加速比(speedup)是度量一个并行是度量一个并行程序性能和可扩展性的常用指标程序性能和可扩展性的常用指标1.3 并行性与程序性能并行性与程序性能331.3 并行性与程序性能并行性与程序性能三、性能损失的原因三、性能损失的原因 •通常情况下，使用通常情况下，使用P个处理器并不能使计算加速个处理器并不能使计算加速P倍倍–也就是说，通常很难获得线性加速比也就是说，通常很难获得线性加速比•原因之一：并行开销原因之一：并行开销(出现在并行求解而不会出现在串出现在并行求解而不会出现在串行求解中的代价行求解中的代价)–通信通信(communication)•线程间和进程间通信，主要开销线程间和进程间通信，主要开销–同步同步(synchronization)•一个线程一个线程/进程必须等待另一个线程进程必须等待另一个线程/进程中出现的事件进程中出现的事件–计算计算•串行求解时不存在的额外计算，如计算各线程的计算任务，这部分开销较小串行求解时不存在的额外计算，如计算各线程的计算任务，这部分开销较小–存储器存储器•计算规模受制于存储器容量计算规模受制于存储器容量341.3 并行性与程序性能并行性与程序性能三、性能损失的原因三、性能损失的原因 •原因之二：无法并行的计算部分原因之二：无法并行的计算部分–如果一个计算在本质上是串行的，则使用多个处理器并不能如果一个计算在本质上是串行的，则使用多个处理器并不能提高其性能提高其性能Amdahl’s Law•基本思想：系统中某一部件由于采用更快的执行方式后，整个系统性基本思想：系统中某一部件由于采用更快的执行方式后，整个系统性能的提升与这种执行方式的使用频率或占总执行时间的比例有关能的提升与这种执行方式的使用频率或占总执行时间的比例有关–对并行计算，假设程序的对并行计算，假设程序的1/S是串行的是串行的(不可并行不可并行)，程序串行，程序串行执行时间是执行时间是Ts，则并行执行时间，则并行执行时间Tp计算如下：计算如下：–性能改善与性能改善与S密切相关，密切相关，S越大，说明可并行计算的部分越多越大，说明可并行计算的部分越多程序中被频繁执行的程序中被频繁执行的部分部分(密集计算部分密集计算部分)应首先被并行化应首先被并行化351.3 并行性与程序性能并行性与程序性能三、性能损失的原因三、性能损失的原因 •原因之三：闲置的处理器原因之三：闲置的处理器–计算过程中，可能有部分处理器在某些时间处于空闲状态计算过程中，可能有部分处理器在某些时间处于空闲状态–原因：原因：•负载不平衡负载不平衡•存储器受限计算存储器受限计算•同步与通信同步与通信•…•原因之四：对资源的竞争原因之四：对资源的竞争–多个线程多个线程/进程竞争共享资源导致性能下降进程竞争共享资源导致性能下降361.3 并行性与程序性能并行性与程序性能四、并行结构四、并行结构•相关性相关性(dependence)，又称为依赖关系，又称为依赖关系–相关性是指两个计算之间的顺序关系相关性是指两个计算之间的顺序关系–相关性使我们可以区分哪些操作必须顺序进行以保证正确性，相关性使我们可以区分哪些操作必须顺序进行以保证正确性，哪些操作不必顺序进行哪些操作不必顺序进行–一种典型的相关性：数据相关性一种典型的相关性：数据相关性(data dependence)•流相关流相关(flow dependence)：写后读：写后读 •反相关反相关(anti dependence)：读后写：读后写•输出相关输出相关(output dependence)：写后写：写后写1sum = a + 1;2first_term = sum * scale13sum = b + 1;4second_term = sum * scale2伪相关伪相关真相关真相关1first_sum = a + 1;2first_term = first_sum * scale13second_sum = b + 1;4second_term = second_sum * scale2消除反相关消除反相关流相关流相关流相关流相关反相关反相关371.3 并行性与程序性能并行性与程序性能四、并行结构四、并行结构•相关性限制并行性相关性限制并行性–相关性在很大程度上会限制并行性相关性在很大程度上会限制并行性–在编写并行程序时，要尽量避免引入相在编写并行程序时，要尽量避免引入相关性关性–易并行计算易并行计算(embarrassingly parallel computtations)•某些计算很容易并行化，它们由大量某些计算很容易并行化，它们由大量没有相关性的线程组成，这类计算称没有相关性的线程组成，这类计算称为易并行计算为易并行计算381.3 并行性与程序性能并行性与程序性能四、并行结构四、并行结构•粒度粒度(Granularity)–并行的粒度并行的粒度•并行粒度由进程并行粒度由进程/线程间的交互频率所决定，即跨越进程线程间的交互频率所决定，即跨越进程/线程边界的线程边界的相关性的频率。

频率可用交互的指令数衡量相关性的频率频率可用交互的指令数衡量•粗粒度粗粒度(coarse grain)：进程：进程/线程依赖于其他进程线程依赖于其他进程/线程数据或事件的线程数据或事件的频率较低频率较低•细粒度细粒度(fine grain)：进程：进程/线程间交互频繁的计算线程间交互频繁的计算–粒度概念的应用粒度概念的应用•较细粒度的计算适合在通信时延较低的平台上运行，如多核处理器较细粒度的计算适合在通信时延较低的平台上运行，如多核处理器•较粗粒度的计算适合在通信时延较高的平台上运行，如机群较粗粒度的计算适合在通信时延较高的平台上运行，如机群–一种极端的例子：基于一种极端的例子：基于Internet的并行计算的并行计算•在并行程序中，最好不要固定粒度，而应该使粒度与硬件资源及问题在并行程序中，最好不要固定粒度，而应该使粒度与硬件资源及问题规模相匹配规模相匹配并行粒度是否并行粒度是否恰当恰当在很大程在很大程度上影响着并行程序的性能度上影响着并行程序的性能391.3 并行性与程序性能并行性与程序性能四、并行结构四、并行结构•局部性局部性(Locality)–程序执行过程中，程序执行过程中，Cache命中率对性能有较大影响命中率对性能有较大影响–在并行程序中应充分利用时间和空间局部性在并行程序中应充分利用时间和空间局部性访问模式访问模式L1D(clk)L2(clk)L3(clk)Memory(ns)顺序访问411146页内随机4111822完全随机4113865.8Intel i7-3960X(Sandy Bridge E)的访存测试数据的访存测试数据(3.3GHz/6C/L1 32KB每核每核/L2 256KB每核每核/L3 15MB共享共享/DDR3内存内存)40。