intel公司内部教材多核多线程技术.ppt

多核程序设计,参考资料：1.多核系列教材编写组.多核程序设计.清华大学出版社,2007.92.David B.Kirk,Wen-mei W.Hwu著.陈曙晖,熊淑华译.大规模并行处理器编程实践.清华大学出版社,2010.93.Maurice Herlihy,Nir Shavit著.金海,胡侃译.多处理器编程的艺术.机械工业出版社,2009.84.Richard Gerber,Aart,Kevin B.Smith等著,王涛,单久龙,孙广中译.软件优化技术IA-32平台的高性能手册(第2版).电子工业出版社,2007.4,多核程序设计,电子书及资料下载：,多核程序设计,第一章 多核技术导论,微处理器发展史,1945年，世界上第一台全自动电子数字计算机ENIAC计算机的发展按照硬件工艺可以分为第一代（19461958）：电子管数字计算机。第二代（19581964）：晶体管数字计算机。第三代（19641971）：集成电路数字计算机。第四代(1971年以后）：大规模集成电路数字计算机。微处理器第一代微处理器(4位)：英特尔4004,8008 第二代微处理器(8位)：采用NMOS工艺,采用汇编语言、BASIC、Fortran编程，使用单用户操作系统。如英特尔8080,8085。第三代微处理器(16位)：以1978年英特尔的8086出现为起点。第四代微处理器(32位)：运算模式包括实模式、保护模式和“虚拟86”。英特尔80386 DX,80486,Pentium 4,并行计算机,由一组处理单元组成，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。出现背景:60年代初期，晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。出现规模不大的共享存储多处理器系统，即大型主机（典型代表：IBM360）。60 年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了，在处理器内部的应用大大提高了并行计算机系统的性能。两个最主要的组成部分计算节点节点间的通信与协作机制,并行计算机的弗林分类,Flynn根据指令流和数据流的不同组织方式，把计算机系统的结构分为以下四类：单指令流单数据流（Single Instruction stream Single Data stream,SISD）单指令流多数据流（Single Instruction stream Multiple Data stream,SIMD）多指令流单数据流（Multiple Instruction stream Single Data stream,MISD）多指令流多数据流（Multiple Instruction stream Multiple Data stream,MISD）,并行计算机的弗林分类,并行计算机系统绝大部分为MIMD系统，包括：并行向量机（PVP，Parallel Vector Processor）；对称多处理机（SMP,Symmetric Multiprocessor）；大规模并行处理机（MPP，Massively Parallel Processor）；机群（Cluster）；分布式共享存储多处理机（DSM，Distributied Shared Memory）,并行计算机从系统结构角度分类,分布式存储器的SIMD处理机含有多个同样结构的处理单元（PE），通过寻径网络以一定方式互相连接。每个PE有各自的本地存储器（LM）。向量超级计算机（共享式存储器SIMD）集中设置存储器，共享的多个并行存储器通过对准网络与各处理单元PE相连。在处理单元数目不太大的情况下很理想。对称多处理器（SMP）一个计算机上汇集了一组处理器，各处理器之间共享内存子系统以及总线结构。并行向量处理机（PVP）使用定制的高带宽网络将向量处理器连向共享存储器模块使用大量的向量寄存器和指令缓冲器集群计算机由许多连在一起的独立计算机组成，像一个单独集成的计算机资源一样协同工作，用来解决大型计算问题。,并行计算机从系统结构角度分类,对称多处理共享存储并行机（SMP）内存模块和处理器对称地分布在互联网络的两侧，内存访问属典型的均匀访问模型。,并行计算机从系统结构角度分类,SMP主要特征对称共享存储 系统中任何处理器均可直接访问任何存储模块中的存储单元和I/O 模块，且访问的延迟、带宽和访问成功的概率是一致的。各个处理器之间的地位等价，操作系统可在任意处理器上运行。单一的操作系统映像 全系统只有一个操作系统驻留在共享存储器中，它根据各个处理器的负载情况，动态地分配各个进程到各个处理器，并保持各处理器间的负载平衡。局部高速缓存cache 及其数据一致性 每个处理器均配备局部cache，它们可以拥有独立的局部数据，但是这些数据必须与存储器中的数据保持一致。低通信延迟 各个进程通过读/写操作系统提供的共享数据缓存区来完成处理器间的通信，其延迟通常小于网络通信的延迟。共享总线带宽 所有处理器共享总线的带宽，完成对内存模块和I/O 模块的访问。支持消息传递、共享存储并行程序设计,并行计算机从系统结构角度分类,SMP典型代表SGI POWER Challenge XL 系列并行机（可扩展至36 个MIPS R10000 微处理器）。COMPAQ Alphaserver 84005/440（含12 个Alpha 21264微处理器）。HP9000/T600（含12 个HP PA9000 微处理器）。IBM RS6000/R40（含8 个RS6000 微处理器）。,并行计算机从系统结构角度分类,分布共享存储并行机（DSM）内存模块局部在各个结点内部，并被所有结点共享。这样，可以较好地改善对称多处理共享存储并行机的可扩展能力,并行计算机从系统结构角度分类,DSM主要特征 以结点为单位，每个结点包含一个或多个CPU，每个CPU 拥有自己的局部cache，并共享局部存储器和I/O设备，所有结点通过高性能互联网络相互连接；物理上分布存储：内存模块分布在各结点中，并通过高性能互联网络相互连接。单一的内存地址空间：所有这些内存模块都由硬件进行统一编址，并通过互联网络连接形成了并行机的共享存储器。非一致内存访问（NUMA）模式：由于远端访问必须通过高性能互联网络，而本地访问只需直接访问局部内存模块，因此，远端访问的延迟一般是本地访问延迟的3 倍以上。单一的操作系统映像：用户只看到一个操作系统，它可以根据各结点的负载情况，动态地分配进程。,并行计算机从系统结构角度分类,DSM主要特征 基于cache 的数据一致性：通常采用基于目录的cache 一致性协议来保证各结点的局部cache 数据与存储器中数据的一致性。低通信延迟与高通信带宽：专用的高性能互联网络使得结点间的延迟很小，通信带宽可以扩展。DSM 并行机可扩展到数百个结点，能提供每秒数千亿次的浮点运算性能。支持消息传递、共享存储并行程序设计。,并行计算机从系统结构角度分类,DSM典型代表 SGI Origin2000、SGI Origin 3800、SGI Altix,并行计算机从系统结构角度分类,大规模并行机系统（MPP）大规模并行机系统是典型的分布存储系统。,并行计算机从系统结构角度分类,MPP典型特征 由数百个乃至数千个计算结点和I/O 结点组成，每个结点相对独立，并拥有一个或多个微处理器。这些结点配备有局部cache，并通过局部总线或互联网络与局部内存模块和I/O 设备相连接。这些结点由局部高性能网卡(NIC)通过高性能互联网络相互连接。它一般采用由多种静态拓扑结构耦合而成的混合拓扑结构，其通信延迟和通信带宽均明显优于机群互联网络。MPP 的各个结点均拥有不同的操作系统映像。一般情况下，用户可以将作业提交给作业管理系统，由它负责调度当前最空闲、最有效的计算结点来执行该作业。各个结点间的内存模块相互独立，且不存在全局内存单元的统一硬件编址。仅支持消息传递或者高性能Fortran 并行程序设计，不支持全局共享的OpenMP 并行程序设计模式。,并行计算机从系统结构角度分类,机群（cluster）有三个明显的特征 系统由商用结点构成，每个结点包含2-4 个商用微处理器，结点内部共享存储。采用商用机群交换机连接结点，结点间分布存储。在各个结点上，采用机群Linux 操作系统、GNU 编译系统和作业管理系统。,片上多核处理器架构,片上多核处理器（Chip Multi-Processor，CMP）就是将多个计算内核集成在一个处理器芯片中，从而提高计算能力。按计算内核的对等与否，CMP可分为同构多核和异构多核CPU核心数据共享与同步的通信机制：总线共享Cache结构：每个CPU内核拥有共享的二级或三级Cache，用于保存比较常用的数据，并通过连接核心的总线进行通信。基于片上互连的结构：每个CPU核心具有独立的处理单元和Cache，各个CPU核心通过交叉开关或片上网络等方式连接在一起。给程序开发者带来的挑战,典型多核芯片架构,芯片组对多核的支持固件,固件是一种嵌入到硬件设备中的软件。它通常烧写在flash等介质中，可以被当作一个二进制映像文件由用户从硬件设备中调用。固件是在集成电路只读存储器中的计算机程序，是可擦写可编程芯片，其上的程序可以通过专门的外部硬件进行修改，但是不能被一般的应用程序改动。,芯片组对多核的支持固件(续),BIOS（Basic Input/Output System）作为系统硬件和操作系统之间的抽象层，主要用来初始化和配置系统的硬件，启动操作系统以及提供对系统设备底层的通讯。BIOS是连接CPU、芯片组和操作系统的固件，是IBM兼容计算机中启动时调用的固件代码。由两部分组成:上电自举即POST（Power On Self Test）和在线的中断服务（主要由legacy 操作系统使用）。计算机加电时BIOS从flash、PROM或是EPROM中启动并完成初始化，进行加电自检，对硬盘，内存，显卡，主板等硬件进行扫描检查，然后它将自己从BIOS内存空间中解压到系统的内存空间中，并开始从那里运行。正在被以EFI（Extensible Firmware Interface，可扩展固件接口）为代表的新一代技术所取代。,芯片组对多核的支持固件(续2),EFI（可扩展固件接口）在操作系统与平台固件之间的软件接口。EFI规范定义的接口包括包含平台信息的数据表和启动时及启动后的服务。EFI启动管理器被用来选择装载操作系统，不再需要专门的启动装载器机制辅助。Framework是一种固件的架构，它是EFI固件接口的一种实现，用来完全替代传统的BIOS。,EFI对多核支持,在Framework中定义了两类处理器BSP（boot strap processor），执行EFI的初始化代码，设置APIC环境，建立系统范围的数据结构，开始并初始化AP。AP（application processor），在系统上电或重启之后，AP会自己进行一个简单的设置，然后就等待BSP发出Startup信号。Framework在多核计算机中初始化过程如下：SEC：从实模式切换到保护模式，处理不同的重启事件、对每个处理器进行缓存设置。PEI：做尽量少的硬件初始化，而把更多的留给DXE。DXE：对所有可用的硬件设备进行初始化，为建立控制台和启动操作系统提供必要的服务。BDS：建立所需的控制台设备，在输出控制台上显示用户界面。当系统最后选择启动到操作系统时，EFI需要提交包括处理器在内的有关信息。,操作系统对多核处理器的支持方法,调度与中断对任务的分配进行优化。使同一应用程序的任务尽量在一个核上执行。对任务的共享数据优化。由于CMP体系结构共享二级缓存，可以考虑改变任务在内存中的数据分布，使任务在执行时尽量增加二级缓存的命中率。对任务的负载均衡优化。当任务在调度时，出现了负载不均衡，考虑将较忙处理器中与其他任务最不相关的任务迁移，以达到数据的冲突量小。输入输出系统多核体系处理器中，必须将中断处理分发给一组核处理。存储管理与文件系统库函数做成非阻塞调用方式（需要保证数据同步的机制）使用多线程内存分配,操作系统对多核处理器的支持方法,多核程序设计,第二章 并行计算基础,并行和并发,如果某个系统支持两个或多个动作（Action）同时存在，那么这个系统就是一个并发系统如果某个系统支持两个或多个动作同时执行，那么这个系统就是一个并行系统并发程序可同时拥有两个或多个线程。如果程序能够并行执行，则一定是运行在多核处理器上，每个线程都将分配到一个独立的处理器核上。“并行”概念是“并发”概念的一个子集,什么是并行计算,并行计算（parallel computing）是指，在并行机上将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加速求解速度，或者求解应用问题规模的目的。成功开展并行计算，必须具备三个基本条件：并行机 并行机至少包含两台或两台以上处理机，这些处理机通过互连网络相互连接，相互通信。应用问题必须具有并行度 也就是说，应用可以分解为多个子任务，这些子任务可以并行地执行。将一个应用分解为多个子任务的过程，称为并行算法的设计。并行编程 在并行机提供的并行编程环境上，具体实现并行算法，编制并行程序，并运行该程序，从而达到并行求解应用问题的目的。,并行计算的目的、目标,并行计算技术的主要目的：加速求解问题的速度 例如，给定某应用，在单处理器上，串行执行需要2 周，这个速度对一般的应用而言，是无法忍受的。于是，可以借助并行计算，使用100 台处理器，加速50 倍，将执行时间缩短为6.72 个小时。提高求解问题的规模 例如，在单处理器上，受内存资源2GB的限制，只能计算10 万个网格，但是，当前数值模拟要求计算千万个网格。于是，也可以借助并行计算，使用100 个处理器，将问题求解规模线性地扩大100 倍。并行计算的主要目标：在并行机上，解决具有重大挑战性计算任务的科学、工程及商业计算问题，满足不断增长的应用问题对速度和内存资源的需求。,并行计算的研究内容,并行计算的主要研究内容大致可分为四个方面：并行机的高性能特征抽取 充分理解和抽取当前并行机体系结构的高性能特征，提出实用的并行计算模型和并行性能评价方法，指导并行算法的设计和并行程序的实现。并行算法设计与分析 设计高效率的并行算法，将应用问题分解为可并行计算的多个子任务，并具体分析这些算法的可行性和效果。并行实现技术 主要包含并行程序设计和并行性能优化。并行应用 这是并行计算研究的最终目的。通过验证和确认并行程序的正确性和效率，进一步将程序发展为并行应用软件，应用于求解实际问题。同时，结合实际应用出现的各种问题，不断地改进并行算法和并行程序。,并行计算示例,N 个数被分布存储在P 台处理器，P 台处理器并行执行N 个数的累加和。首先，各个处理器累加它们各自拥有的局部数据，得到部分和；然后，P 台处理器执行全局通信操作，累加所有部分和，得到全局累加和。,并行计算机体系结构,组成并行计算机的各个部分：节点（node）构成并行机的基本单位互联网络（interconnect network）内存（memory）,内存模块与节点分离,内存模块位于节点内部,多级存储体系结构,为了解决内存墙（memory wall）性能瓶颈问题。在节点内部的cache称为二级cache（L2 cache）。在处理器内部更小的cache称为一级cache（L1 cache）。L1 cache连接CPU寄存器和L2 cache，负责缓存L2 cache中的数据到寄存器中。,多级存储体系结构,并行计算机的多级存储结构主要包括两个问题：Cache的映射策略，即cache如何从内存中取得数据进行存储；节点内部或者节点之间内存的访问模式。cache原理cache以cache线为基本单位，每条cache包含L个字，每个字8个字节。例如，L=4，则表示cache线包含4*8=32个字节。内存空间分割成块（block），每个块大小与cache线长度一致，数据在内存和cache之间的移动以cache线为基本单位。For i=1 to M Ai=Ai+2*Bi 如果操作数存在cache中，称该次访问是命中的，否则，该次操作是“扑空”的。,无Cache，访问内存2M次；有cache，访问内存2M/L次,多级存储体系结构,cache的映射策略指的是内存块和cache线之间如何建立相互映射关系。直接映射策略（direct mapping strategy）每个内存块只能被唯一的映射到一条cache线中K路组关联映射策略（K-way set association mapping strategy）Cache被分解为V个组，每个组由K条cache线组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一条cache线。全关联映射策略（full association mapping strategy）内存块可以被映射到cache中的任意一条cache线。,并行计算机访存模型,UMA（Uniform Memory Access）均匀存储访问模型物理存储器被所有节点共享；所有节点访问任意存储单元的时间相同；发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；各节点的CPU可带有局部私有高速缓存；外围I/O设备也可以共享，且每个节点有平等的访问权利。NUMA（Non-Uniform Memory Access）模型物理存储器被所有节点共享，任意节点可以直接访问任意内存模块；节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的3倍以上；发生访存竞争时，仲裁策略对节点可能是不等价的；各节点的CPU可带有局部私有高速缓存（cache）；外围I/O设备也可以共享，但对各节点是不等价的。,并行计算机访存模型,COMA（Cache-Only Memory Access）模型各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间利用分布的高速缓存目录D进行远程高速缓存的访问COMA中的高速缓存容量一般都大于2级高速缓存容量使用COMA时，数据开始时可以任意分配，因为在运行时它最终会被迁移到要用到它的地方NORMA（No-Remote Memory Access）模型所有存储器都是私有的；绝大多数NORMA都不支持远程存储器的访问；在DSM（分布式共享存储）中，NORMA就消失了。,并行计算机访存模型,并行计算机系统的不同访存模型分类,并行计算模型,计算模型是对计算机的抽象计算模型为设计、分析和评价算法提供基础冯偌依曼机就是一个理想的串行计算模型但现在还没有一个通用的并行计算模型,并行计算模型,SIMD同步并行计算模型共享存储的SIMD模型（PRAM模型）PRAM，Parallel Random Access Machine 并行随机存取模型分布存储的SIMD模型（SIMD互联网络模型）MIMD异步并行计算模型异步PRAM模型BSP模型LogP模型C3模型,SIMD同步并行计算模型,SIMD共享存储模型（PRAM模型）是一种抽象的并行计算模型，模型中：假定存在着一个容量无限大的共享存储器；有有限或无限各功能相同的处理器，且均具有简单的算术运算和逻辑判断功能；在任何时刻各处理器均可以通过共享存储单元交换数据。,SIMD同步并行计算模型,SIMD共享存储模型（PRAM模型）根据处理器对共享存储单元同时读写的限制，模型分为：PRAM-EREW（Exclusive-Read and Exclusive-Write），不允许同时读和同时写PRAM-CREW（Concurrent-Read and Exclusive-Write），允许同时读但不允许同时写PRAM-CRCW（Concurrent-Read and Concurrent-Write），允许同时读和同时写,SIMD同步并行计算模型,SIMD共享存储模型（PRAM模型）优点：适合于并行算法的表达、分析和比较；使用简单，很多诸如处理器间通信、存储管理和进程同步等并行计算机的低级细节均隐含于模型中；易于设计算法和稍加修改便可运行在不同的并行计算机上；有可能加入一些诸如同步和通信等需要考虑的方面。,SIMD同步并行计算模型,SIMD共享存储模型（PRAM模型）,SIMD-PRAM模型,MIMD同步并行计算模型,MIMD-PRAM模型,MIMD异步计算模型APRAM模型,APRAM模型特点:每个处理器都有其本地存储器、局部时钟和局部程序处理器间的通信经过共享全局存储器无全局时钟，各处理器异步地独立执行各自的指令处理器任何时间依赖关系需明确地在各处理器的程序中加入同步（路）障（Synchronization Barrier）一条指令可在非确定但有限的时间内完成。APRAM模型中有四类指令:全局读，将全局存储单元中的内容读入本地存储器单元中局部操作，对本地存储器中的数执行操作，其结果存入本地存储器中全局写，将本地存储器单元中的内容写入全本地存储器单元中同步，同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序,MIMD异步计算模型BSP模型,大同步并行BSP(Bulk Synchronous Parallel)模型作为计算机语言和体系结构之间的桥梁，由以下述三个参数描述分布存储的并行计算机模型：处理器/存储器模块（下文简称处理器）处理器模块之间点到点信息传递的路由器执行以时间间隔L为周期的路障同步器特点：将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅施行点到点的消息传递，不提供组合、复制或广播等功能，这样做既掩盖了具体的互联网络拓扑，又简化了通信协议采用路障方式的以硬件实现的全局同步是在可控的粗粒度级，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员并无过分的负担在分析BSP模型的性能时，假定局部操作可在一个时间步内完成，而在每一超级步中，一个处理器至多发送或接受h条消息（h-relation）,MIMD异步计算模型LogP模型,LogP模型是一种分布存储的、点到点通信的多处理机模型，其中通信网络由一组参数来描述，但它并不涉及到具体的网络结构，也不假定算法一定要用显式的消息传递操作进行描述。L（Latency）源处理机与目的处理机进行消息（一个或几个字）通信所需要的等待或延迟时间的上限。o（overhead）处理机准备发送或准备接受每个消息的时间开销（包括操作系统核心开销和网络软件开销），在这段时间里处理机不能执行其他操作。g（gap）一台处理机连续两次发送或连续两次接受消息时的最小时间间隔，其倒数即为处理机的通信带宽。P（Processor）处理机的个数。,MIMD异步计算模型LogP模型,揭示了分布存储并行计算机的性能瓶颈，用L、o、g三个参数刻画了通信网络的特性，但屏蔽了网络拓扑、选路算法和通信协议等具体细节参数g反映了通信带宽在任何时刻，最多只能有L/g条消息从一个处理器传到另一个处理器，这就是网络容限，当一台处理机发送的消息达到这个容限时，在发送的消息就会被阻塞；在网络容限范围内，点到点传送一条消息的时间为(2*o+L)。设想LogP模型中的L、o、g都为0，那么LogP模型就等同于PRAM模型,MIMD异步计算模型C3模型,C3（Computation,Communication,Congestion）模型是一个与体系结构无关的粗粒度的并行计算模型，旨在能反映计算复杂度，通信模式和通信期间潜在的拥挤等因素对粗粒度网络算法的影响。C3模型强调用共用的通信操作来开发粗粒度的并行算法BSP、LogP模型采用点到点的消息传递来进行通信，复杂的通信操作由编程实现,各种计算模型比较,并行编程方法,编写正确的串行程序分析：找出并发性找出包含独立计算的热点（Hotspot）位置。热点是指一段包含了大量操作的代码设计与实现：采用线程来实现算法并行算法是适合在并行机上实现的算法测试正确性：检测并修复在线程化时引入的错误性能调优：消除性能瓶颈,并行算法分类,并行算法根据运算基本对象的不同可分为：数值并行算法 主要为数值计算方法而设计的并行算法；非数值并行算法 主要为符号运算而设计的并行算法，如图论算法、遗传算法等。,并行算法分类,根据并行进程间相互执行顺序关系的不同可分为：同步并行算法 进程间由于运算执行顺序而必须相互等待的并行算法，如通常的向量算法、SIMD 算法、MIMD 并行机上进程间需要相互等待通信结果的算法等；异步并行算法 进程间执行相对独立，不需要相互等待的一种算法，通常针对消息传递MIMD 并行机设计，其主要特征是在计算的整个过程中均不需要等待，而是根据最新消息决定进程的继续或终止；独立并行算法 进程间执行是完全独立的，计算的整个过程不需要任何通信。,并行算法分类,根据各进程承担的计算任务粒度的不同，可分为：细粒度并行算法通常指基于向量和循环级并行的算法；中粒度并行算法通常指基于较大的循环级并行；大粒度并行算法通常指基于子任务级并行的算法，例如通常的基于区域分解的并行算法，它们是当前并行算法设计的主流。,并行编程环境,比较流行的并行编程环境主要有3类：消息传递、共享存储和数据并行：共享存储并行编程基于线程级细粒度并行，可移植性不如消息传递并行编程，但是，由于他们支持数据的共享存储，所以并行编程的难度较小，但一般情况下，当处理机个数较多时，其并行性能明显不如消息传递编程；消息传递并行编程基于大粒度的进程级并行，具有最好的可扩展性，几乎被所有当前流行的各类并行计算机所支持，其具有较好的可扩展性。消息传递并行编程只能支持进程间的分布式存储模式，即各个进程只能支持访问其局部内存空间，而对其他进程的局部内存空间的访问只能通过消息传递来实现，因此，学习和使用消息传递并行编程的难度均大于共享存储和数据并行这两种编程模式。,并行编程环境,比较流行的并行编程环境主要有3类：消息传递、共享存储和数据并行,编程语言与编译器,在科学计算领域对并行编程支持已经取得相当成功的三项技术：自动并行化数据并行语言HPF共享存储并行编程接口OpenMP,编程语言与编译器,自动并行始于20世纪70年代的自动向量化。20世纪80年代中期，基于依赖分析的向量化工具成熟，成为向量机的标准。自动化并行本身不足以解决并行程序设计问题。此领域的研究重点逐步转向基于语言的策略研究，即从用户那里获得更多的信息，同时利用自动并行化技术来减轻程序设计的负担。依赖分析：搜索确定对同一数据结构的哪些引用是访问同一存储单元的,编程语言与编译器,数据并行编程：HPF高性能Fortran(HPF)的思想是使数据管理的多数细节自动并行化HPF提供了一个指令集，通过注释形式的指令来扩展变量类型的说明，能够对数组的数据布局进行相当详细的控制。对显式并行机制的说明相当有限，通过系统而非程序员把任务分配给处理机。,编程语言与编译器,共享存储并行编程：OpenMP1997年由Silicon Graphics领导的工业协会推出了OpenMP是一个与Fortran77和C语言绑定的并行编程接口OpenMP指令在单机编译器上被当作注释而忽略通过parallel section 指令获得任务并行#pragma omp parallel for 提供了锁变量用于线程间细粒度同步是适合于具有一致性访存的共享存储计算机的编程接口,并行计算性能评测,并行程序执行时间 从并行程序开始执行到所有进程执行完毕，墙上时钟走过的时间，也称为墙上时间（wall clock time）。,并行计算性能评测,并行程序执行时间 对各个进程，墙上时间可进一步分解为计算CPU时间、通信CPU时间、同步开销时间、同步导致的进程空闲时间计算CPU时间：进程指令执行所花费的CPU时间，包括程序本身的指令执行占用的时间（用户时间）和系统指令花费的时间；通信CPU时间：进程通信花费的CPU时间；同步开销时间：进程同步花费的时间；进程空闲时间：进程空闲时间是指并行程序执行过程中，进程所有空闲时间总和（如进程阻塞式等待其他进程的消息时。此时CPU通常是空闲的，或者处于等待状态）,并行计算性能评测,并行程序性能评价方法浮点峰值性能与实际浮点性能峰值性能等于CPU内部浮点乘加指令流水线条数、每条流水线每个时钟周期完成的浮点运算次数、处理器主频三者的乘积实际浮点性能等于并行程序的总的浮点运算次数和并行程序执行时间的比值数值效率和并行效率,并行计算性能评测,并行加速比与效率在处理器资源独享的前提下，假设某个串行应用程序在某台并行机单处理器上的执行时间为TS，而该程序并行化后，P 个进程在P 个处理器并行执行所需要的时间为TP，则该并行程序在该并行机上的加速比SP 可定义为：效率定义为：,并行计算性能评测,加速比性能定律Amdahl定律能够计算并行程序相对于最优串行算法在性能提升上的理论最大值他将程序划分为可加速与不可加速两大部分，程序总的加速比是一个关于程序中这两部分所占比例以及可加速部分性能加速程度的函数 Amdahl定律:f 表示执行程序中串行部分的比例，p表示处理器核的数量。假设最优串行算法的执行时间为一个单位时间（也就是分子为1）。处理器核在数量上能够无限制的增加，但是无限的处理器核却并不能带来性能上的无限增长，无论如何，程序性能上的总是有个上限，这个要受限于串行部分所占的比例。,并行计算性能评测,Amdahl定律告诉我们：可并行计算量占主要比重通过并行化，增加的额外计算量所占比重有限：这些计算量由各个处理器/执行内核分摊要有足够的并行度(并行子任务数量)，实现负载均衡：问题规模越大，并行度也越大数据并行大规模数据处理数据规模与处理器/执行内核的规模比率要适当只有上述三个特征都满足了，采用并行处理技术才有意义,程序性能优化,串行程序性能优化 是并行程序性能优化的基础，一个好的并行程序首先应该拥有良好的单机性能，影响程序单机性能的主要因素是程序的计算流程和处理器的体系结构。,程序性能优化,串行程序性能优化调用高性能库 许多著名的高性能数学程序库如优化的BLAS、FFTW 等，由于经过厂商或第三方针对特定处理机进行的专门优化，其性能一般大大优于用户自行编写的同样功能的程序段或子程序。,程序性能优化,串行程序性能优化调用高性能库 BLAS(Basic Linear Algebra Subroutines)是一组高质量的基本向量、矩阵运算子程序。最早的BLAS 是一组Fortran 函数和子程序，后来又发展了其他语言接口，包括C、Java 等。BLAS 的官方网址在 国内镜像为 http:/。BLAS 的主要贡献是将高性能代数计算程序的开发同针对特定机器的性能优化独立开来：代数算法程序的开发者只需要运用适当的分块技术将计算过程变成矩阵、向量的基本运算并调用相应的BLAS 子程序而不必考虑与计算机体系结构相关的性能优化问题。线性代数软件包如LAPACK、ScaLAPACK 等都是基于这一思想设计的。,程序性能优化,串行程序性能优化调用高性能库 FFTW(The Fastest Fourier Transform in the West)是一个免费的快速富氏变换(FFT)软件包，开发者是麻省理工学院的Matteo Frigo 和Steven G.Johnson，下载网址：http 该软件包用C 语言开发，其核心技术(编码生成器)采用面向对象语言Caml 编写。FFTW 能自动适应系统硬件，可移植性很强。它能计算一维和多维离散傅立叶变换，其数据类型可以是实型、复型或半复型。该软件通过方案(plan)和执行器(executor)与用户进行接口，内部结构及其复杂性对用户透明，速度快。内部编译器、代码生成器利用AST（Abstract Syntax Tree）在运行时生成适合所运行的机器的代码并自我优化。,程序性能优化,串行程序性能优化选择适当的编译器优化选项 现代编译器在编译时能够对程序进行优化从而提高所生成的目标代码的性能。这些优化功能通常通过一组编译选项来控制。比较通用的优化选项有“-O”、“-O0”、“-O2”、“-O3”等，“-O0”表示不做优化，“-O1”、“-O2”、“-O3”等表示不同级别的优化，优化级别越高，生成的代码的性能可能会越好，但采用过高级别的优化会大大降低编译速度，并且可能导致错误的运行结果。通常，“-O2”的优化被认为安全的。,程序性能优化,串行程序性能优化合理定义数组维数 在进行连续数据访问时应该使得地址的增量与内存体数的最大公约数尽量小，特别要避免地址增量正好是体数的倍数。注意嵌套循环的顺序，尽量改善数据访问的局部性 通用的原则就是尽量使最内层循环的数据访问连续进行,程序性能优化,串行程序性能优化数据分块 当处理大数组时，对数组、循环进行适当分块有助于同时改善访存的时间和空间局部性。DO I=1,N DO J=1,N A(I)=A(I)+B(J)ENDDOENDDO对数组B 进行分块，S 为分块大小，改写上述程序：DO J=1,N,S DO I=1,N DO JJ=J,MIN(J+S-1,N)A(I)=A(I)+B(JJ)ENDDO ENDDOENDDO当S N 时，相当于原始循环；当S=1 时相当于交换I 和J 的循环顺序。根据cache 大小选择适当的S 值，使得B(J:J+S-1)能够被容纳在cache 中，可以改善对数组B 的访问的时间局部性。,程序性能优化,串行程序性能优化循环展开 是另一个非常有效的程序优化技术。它除了能够改善数据访问的时间和空间局部性外，还由于增加了每步循环中的指令与运算的数目，亦有助于CPU 多个运算部件的充分利用。DO I=1,N D=D+A(I)ENDDO将它进行4 步循环展开的代码如下：DO I=1,MOD(N,4)D=D+A(I)ENDDODO I=MOD(N,4)+1,N,4 D=D+A(I)+A(I+1)+A(I+2)+A(I+3)ENDDO上面的代码中第一个循环用于处理N 除以4 的余数，第二个循环是展开后的循环。,程序性能优化,串行程序：求小于N的全部素数 void main()int number;/小于N的素数个数；int primesn;/从primes0 primesnumber-1 中存放生成的素数；int i,j,k;primes0=2;for(i=3,j=1;ii)/如果 i 不能被前面的素数整除/则将它作为新素数存入数组 primes j=i;j+;,程序性能优化,并行程序性能优化 最主要的是选择好的并行算法和通信模式减少通信量、提高通信粒度 提高通信粒度的有效方法就是减少通信次数，尽可能将可以一次传递的数据合并起来一起传递全局通信尽量利用高效集合通信算法 对于标准的集合通信，如广播、规约、数据散发与收集等，尽量调用MPI标准库函数挖掘算法的并行度，减少CPU空闲等待 具有数据相关性的计算过程会导致并行运行的部分进程空闲等待.在这种情况下，可以考虑改变算法来消除数据相关性,程序性能优化,并行程序性能优化负载平衡 必要时使用动态负载平衡技术，即根据各进程计算完成的情况动态地分配或调整各进程的计算任务。动态调整负载时要考虑负载调整的开销及由于负载不平衡而引起的空闲等待对性能的影响，寻找最优负载调整方案。通信、计算的重叠 让通信和计算重叠进行，利用计算时间来屏蔽通信时间。实现方法一般基于非阻塞通信，先发出非阻塞的消息接受或发送命令，然后处理与收发数据无关的计算任务，完成计算后再等待消息收发的完成。通过引入重复计算来减少通信，即以计算换通信 由于当前大部分并行计算机的计算速度远远大于通信速度，并且在一些情况下，当一个进程计算时，别的进程往往处于空闲等待状态，因而适当引入重复计算可以提高程序的总体性能。,程序性能优化,并行程序：求小于N的全部素数pThread_prime,并行编译器,并行编译器大致由三部分组成：流分析 确定源代码中数据和控制的相关性程序优化 将代码变换成与之等效的的更好形式，以挖掘硬件潜力代码生成 将代码从一种描述转换成另一种中间形式的描述,并行编译器,并行编译过程,并行编译器,流分析 要使程序并行地执行，首先要进行相关性分析（Depend