多核平台编程技术

2020/2/81第8讲多核平台编程技术2020/2/82目录8.1多核技术概论8.2为什么要学习多核程序设计8.3并行计算基础8.4Linux多线程编程8.5OpenMP多线程编程及性能优化2020/2/83微处理器发展史•1945年，世界上第一台全自动电子数字计算机ENIAC•计算机的发展按照硬件工艺可以分为–第一代（1946~1958）：电子管数字计算机。–第二代（1958~1964）：晶体管数字计算机。–第三代（1964~1971）：集成电路数字计算机。–第四代(1971年以后）：大规模集成电路数字计算机。•微处理器–第一代微处理器(4位)：英特尔4004,8008–第二代微处理器(8位)：采用NMOS工艺,采用汇编语言、BASIC、Fortran编程，使用单用户操作系统。如英特尔8080,8085。–第三代微处理器(16位)：以1978年英特尔的8086出现为起点。–第四代微处理器(32位)：运算模式包括实模式、保护模式和“虚拟86”。英特尔80386DX,80486,Pentium4…2020/2/84并行计算机•由一组处理单元组成，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。•出现背景:–60年代初期，晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。出现规模不大的共享存储多处理器系统，即大型主机（Mainframe）。–60年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了，在处理器内部的应用大大提高了并行计算机系统的性能。•两个最主要的组成部分–计算节点–节点间的通信与协作机制2020/2/85并行计算机的弗林分类•Flynn根据指令流和数据流的不同组织方式，把计算机系统的结构分为以下四类：–单指令流单数据流（SingleInstructionstreamSingleDatastream,SISD）–单指令流多数据流（SingleInstructionstreamMultipleDatastream,SIMD）–多指令流单数据流（MultipleInstructionstreamSingleDatastream,MISD）–多指令流多数据流（MultipleInstructionstreamMultipleDatastream,MISD）2020/2/86并行计算机系统结构分类•分布式存储器的SIMD处理机–含有多个同样结构的处理单元（PE），通过寻径网络以一定方式互相连接。每个PE有各自的本地存储器（LM）。•向量超级计算机（共享式存储器SIMD）–集中设置存储器，共享的多个并行存储器通过对准网络与各处理单元PE相连。在处理单元数目不太大的情况下很理想。•对称多处理器（SMP）–一个计算机上汇集了一组处理器，各处理器之间共享内存子系统以及总线结构。•并行向量处理机（PVP）•集群计算机2020/2/872005+Dual-andMulti-core2-waySMPsystem4Cores4Threads2001Hyper-Threading2-waySMPsystem2Cores4Threads1995Multi-processing2-waySMPsystem2Cores2Threads通过并行方式改进处理器的性能2020/2/88CacheExecutionStateStateBusCacheExecutionStateBusCacheExecutionStateBusCacheExecutionStateBusCacheExecutionStateBusPentium4withHTDualXeonProcessorsDualCore2Threads1Package2Threads2Packages2Threads1PackageTwoindependentexecutioncoresinthesameprocessor多核技术的发展2020/2/89片上多核处理器架构•片上多核处理器（ChipMulti-Processor，CMP）就是将多个计算内核集成在一个处理器芯片中，从而提高计算能力。•按计算内核的对等与否，CMP可分为同构多核和异构多核•CPU核心数据共享与同步–总线共享Cache结构：每个CPU内核拥有共享的二级或三级Cache，用于保存比较常用的数据，并通过连接核心的总线进行通信。–基于片上互连的结构：每个CPU核心具有独立的处理单元和Cache，各个CPU核心通过交叉开关或片上网络等方式连接在一起。•给程序开发者带来的挑战2020/2/810AMD与Intel双核架构的对比AMDOpteron双核架构示意图Intel奔腾至尊版双核架构示意图2020/2/811芯片组对多核的支持——固件•固件是一种嵌入到硬件设备中的软件。它通常烧写在flash等介质中，可以被当作一个二进制映像文件由用户从硬件设备中调用。•固件是在集成电路只读存储器中的计算机程序，是可擦写可编程芯片，其上的程序可以通过专门的外部硬件进行修改，但是不能被一般的应用程序改动。硬件固件操作系统和应用软件汇编器内核2020/2/812芯片组对多核的支持——固件(续)•BIOS（BasicInput/OutputSystem）–作为系统硬件和操作系统之间的抽象层，主要用来初始化和配置系统的硬件，启动操作系统以及提供对系统设备底层的通讯。–BIOS是连接CPU、芯片组和操作系统的固件，是IBM兼容计算机中启动时调用的固件代码。–由两部分组成:上电自举即POST（PowerOnSelfTest）和在线的中断服务（主要由legacy操作系统使用）。–计算机加电时BIOS从flash、PROM或是EPROM中启动并完成初始化，进行加电自检，对硬盘，内存，显卡，主板等硬件进行扫描检查，然后它将自己从BIOS内存空间中解压到系统的内存空间中，并开始从那里运行。–正在被以EFI（ExtensibleFirmwareInterface，可扩展固件接口）为代表的新一代技术所取代。2020/2/813芯片组对多核的支持——固件(续2)•EFI（可扩展固件接口）–在操作系统与平台固件之间的软件接口。–EFI规范定义的接口包括包含平台信息的数据表和启动时及启动后的服务。–EFI启动管理器被用来选择装载操作系统，不再需要专门的启动装载器机制辅助。–Framework是一种固件的架构，它是EFI固件接口的一种实现，用来完全替代传统的BIOS。2020/2/814EFI对多核支持•在Framework中定义了两类处理器–BSP（bootstrapprocessor），执行EFI的初始化代码，设置APIC环境，建立系统范围的数据结构，开始并初始化AP。–AP（applicationprocessor），在系统上电或重启之后，AP会自己进行一个简单的设置，然后就等待BSP发出Startup信号。•Framework在多核计算机中初始化过程如下：–SEC：从实模式切换到保护模式，处理不同的重启事件、对每个处理器进行缓存设置。–PEI：做尽量少的硬件初始化，而把更多的留给DXE。–DXE：对所有可用的硬件设备进行初始化，为建立控制台和启动操作系统提供必要的服务。–BDS：建立所需的控制台设备，在输出控制台上显示用户界面。•当系统最后选择启动到操作系统时，EFI需要提交包括处理器在内的有关信息。2020/2/815操作系统对多核处理器的支持方法•调度与中断–对任务的分配进行优化。使同一应用程序的任务尽量在一个核上执行。–对任务的共享数据优化。由于CMP体系结构共享二级缓存，可以考虑改变任务在内存中的数据分布，使任务在执行时尽量增加二级缓存的命中率。–对任务的负载均衡优化。当任务在调度时，出现了负载不均衡，考虑将较忙处理器中与其他任务最不相关的任务迁移，以达到数据的冲突量小。•输入输出系统•存储管理与文件系统•虚拟化技术–平台虚拟化–资源虚拟化2020/2/8168.2为什么要学习多核程序设计8.2.1背景：科学技术的发展呼唤巨大的、不断增长的计算能力•中长期天气预报。每增加一天，要求计算速度增加一个数量级。三天百万次/sec，四天千万次/sec，五天亿次/sec•信息战。关键是对信息的处理速度，如雷达信息的处理•地震预报预测•石油勘测•生物信息处理•……2020/2/8178.2.2提高计算能力的基本途径•器件：新工艺（超大规模集成电路）•新材料（生物计算机、光计算机）•系统结构的改进：主要是克服VonNeumann的瓶颈问题。•流水线计算机、向量计算机、多处理机、并行计算机、集群。8.2为什么要学习多核程序设计2020/2/8188.2.3现实状况•计算能力几乎提高了上万倍，但是，实际的并行计算能力提高只有几十倍。•原因：不能利用计算机的并行处理能力。也就是没有解决并行计算中的并行程序设计的问题。•其核心问题是并行算法Back8.2为什么要学习多核程序设计2020/2/8198.3并行计算基础•组成并行计算机的各个部分：–节点（node）–互联网络（interconnectnetwork）–内存（memory）内存模块与节点分离内存模块位于节点内部2020/2/820多级存储体系结构•为了解决内存墙（memorywall）性能瓶颈问题。•在节点内部的cache称为二级cache（L2cache）。•在处理器内部更小的cache成为一级cache（L1cache）。•L1cache连接CPU寄存器和L2cache，负责缓存L2cache中的数据到寄存器中。2020/2/821多级存储体系结构(续)•cache的映射策略指的是内存块和cache线之间如何建立相互映射关系。•直接映射策略（directmappingstrategy）–每个内存块只能被唯一的映射到一条cache线中•K－路组关联映射策略（K-waysetassociationmappingstrategy）–Cache被分解为V个组，每个组由K条cache线组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一条cache线。•全关联映射策略（fullassociationmappingstrategy）–内存块可以被映射到cache中的任意一条cache线。2020/2/822并行计算机访存模型•UMA（UniformMemoryAccess）模型–物理存储器被所有节点共享；–所有节点访问任意存储单元的时间相同；–发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；–各节点的CPU可带有局部私有高速缓存；–外围I/O设备也可以共享，且每个节点有平等的访问权利。•NUMA（Non-UniformMemoryAccess）模型–物理存储器被所有节点共享，任意节点可以直接访问任意内存模块；–节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的3倍以上；–发生访存竞争时，仲裁策略对节点可能是不等价的；–各节点的CPU可带有局部私有高速缓存（cache）；–外围I/O设备也可以共享，但对各节点是不等价的。2020/2/823并行计算机访存模型(续)•COMA（Cache-OnlyMemoryAccess）模型–各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间–利用分布的高速缓存目录D进行远程高速缓存的访问–COMA中的高速缓存容量一般都大于2级高速缓存容量–使用COMA时，数据开始时可以任意分配，因为在运行时它最终会被迁移到要用到它的地方•NORMA（No-RemoteMemoryAccess）模型–所有存储器都是私有的；–绝大多数NORMA都不支持远程存储器的访问；–在DSM中，NORMA就消失了。2020/2/824并行计算机访存模型(续2)•并行计算机系统的不同访存模型分类2020/2/825并行计算模型•SIMD同步并行计算模型–共享存储的SIMD模型（PRAM模型）–分布存储的SIMD模型（SIMD互联网络模型）•MIMD异步并行计算模型