多核程序设计

《多核程序设计》由会员分享，可在线阅读，更多相关《多核程序设计（127页珍藏版）》请在金锄头文库上搜索。

1、多核程序设计 第一章 多核技术导论,2007年6月12日,微处理器发展史,1945年，世界上第一台全自动电子数字计算机ENIAC 计算机的发展按照硬件工艺可以分为 第一代（19461958）：电子管数字计算机。 第二代（19581964）：晶体管数字计算机。 第三代（19641971）：集成电路数字计算机。 第四代(1971年以后）：大规模集成电路数字计算机。 微处理器 第一代微处理器(4位)：英特尔4004,8008 第二代微处理器(8位)：采用NMOS工艺,采用汇编语言、BASIC、Fortran编程，使用单用户操作系统。如英特尔8080,8085。 第三代微处理器(16位)：以1978年

2、英特尔的8086出现为起点。 第四代微处理器(32位)：运算模式包括实模式、保护模式和“虚拟86”。英特尔80386 DX, 80486, Pentium 4,并行计算机,由一组处理单元组成，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。 出现背景: 60年代初期，晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。出现规模不大的共享存储多处理器系统，即大型主机（Mainframe）。 60 年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了，在处理器内部的应用大大提高了并行计算机系统的性能。 两个最主要的组成部分

3、计算节点 节点间的通信与协作机制,并行计算机的弗林分类,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

4、Data stream, MISD）,并行计算机系统结构分类,分布式存储器的SIMD处理机 含有多个同样结构的处理单元（PE），通过寻径网络以一定方式互相连接。每个PE有各自的本地存储器（LM）。 向量超级计算机（共享式存储器SIMD） 集中设置存储器，共享的多个并行存储器通过对准网络与各处理单元PE相连。在处理单元数目不太大的情况下很理想。 对称多处理器（SMP） 一个计算机上汇集了一组处理器，各处理器之间共享内存子系统以及总线结构。 并行向量处理机（PVP） 集群计算机,片上多核处理器架构,片上多核处理器（Chip Multi-Processor，CMP）就是将多个计算内核集成在一个处理器

5、芯片中，从而提高计算能力。 按计算内核的对等与否，CMP可分为同构多核和异构多核 CPU核心数据共享与同步 总线共享Cache结构：每个CPU内核拥有共享的二级或三级Cache，用于保存比较常用的数据，并通过连接核心的总线进行通信。 基于片上互连的结构：每个CPU核心具有独立的处理单元和Cache，各个CPU核心通过交叉开关或片上网络等方式连接在一起。 给程序开发者带来的挑战,芯片组对多核的支持固件,固件是一种嵌入到硬件设备中的软件。它通常烧写在flash等介质中，可以被当作一个二进制映像文件由用户从硬件设备中调用。 固件是在集成电路只读存储器中的计算机程序，是可擦写可编程芯片，其上的程序可以

6、通过专门的外部硬件进行修改，但是不能被一般的应用程序改动。,芯片组对多核的支持固件(续),BIOS（Basic Input/Output System） 作为系统硬件和操作系统之间的抽象层，主要用来初始化和配置系统的硬件，启动操作系统以及提供对系统设备底层的通讯。 BIOS是连接CPU、芯片组和操作系统的固件，是IBM兼容计算机中启动时调用的固件代码。 由两部分组成:上电自举即POST（Power On Self Test）和在线的中断服务（主要由legacy 操作系统使用）。 计算机加电时BIOS从flash、PROM或是EPROM中启动并完成初始化，进行加电自检，对硬盘，内存，显卡，主板等

7、硬件进行扫描检查，然后它将自己从BIOS内存空间中解压到系统的内存空间中，并开始从那里运行。 正在被以EFI（Extensible Firmware Interface，可扩展固件接口）为代表的新一代技术所取代。,芯片组对多核的支持固件(续2),EFI（可扩展固件接口） 在操作系统与平台固件之间的软件接口。 EFI规范定义的接口包括包含平台 信息的数据表和启动时及启动后的 服务。 EFI启动管理器被用来选择装载操 作系统，不再需要专门的启动装载 器机制辅助。 Framework是一种固件的架构， 它是EFI固件接口的一种实现，用 来完全替代传统的BIOS。,EFI对多核支持,在Framewor

8、k中定义了两类处理器 BSP（boot strap processor），执行EFI的初始化代码，设置APIC环境，建立系统范围的数据结构，开始并初始化AP。 AP （application processor），在系统上电或重启之后，AP会自己进行一个简单的设置，然后就等待BSP发出Startup信号。 Framework在多核计算机中初始化过程如下： SEC：从实模式切换到保护模式，处理不同的重启事件、对每个处理器进行缓存设置。 PEI：做尽量少的硬件初始化，而把更多的留给DXE。 DXE：对所有可用的硬件设备进行初始化，为建立控制台和启动操作系统提供必要的服务。 BDS：建立所需的控制台

9、设备，在输出控制台上显示用户界面。 当系统最后选择启动到操作系统时，EFI需要提交包括处理器在内的有关信息。,操作系统对多核处理器的支持方法,调度与中断 对任务的分配进行优化。使同一应用程序的任务尽量在一个核上执行。 对任务的共享数据优化。由于CMP体系结构共享二级缓存，可以考虑改变任务在内存中的数据分布，使任务在执行时尽量增加二级缓存的命中率。 对任务的负载均衡优化。当任务在调度时，出现了负载不均衡，考虑将较忙处理器中与其他任务最不相关的任务迁移，以达到数据的冲突量小。 输入输出系统 存储管理与文件系统 虚拟化技术 平台虚拟化 资源虚拟化,多核程序设计 第二章 并行计算基础,2007年6月1

10、2日,并行计算机体系结构,组成并行计算机的各个部分： 节点（node） 互联网络（interconnect network） 内存 （memory）,内存模块与节点分离,内存模块位于节点内部,多级存储体系结构,为了解决内存墙（memory wall）性能瓶颈问题。 在节点内部的cache称为二级cache（L2 cache）。 在处理器内部更小的cache成为一级cache（L1 cache）。 L1 cache连接CPU寄存器和L2 cache，负责缓存L2 cache中的数据到寄存器中。,多级存储体系结构(续),cache的映射策略指的是内存块和cache线之间如何建立相互映射关系。 直接

11、映射策略（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）模型 物理存储器被所有节点共享

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

13、,COMA（Cache-Only Memory Access）模型 各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间 利用分布的高速缓存目录D进行远程高速缓存的访问 COMA中的高速缓存容量一般都大于2级高速缓存容量 使用COMA时，数据开始时可以任意分配，因为在运行时它最终会被迁移到要用到它的地方 NORMA（No-Remote Memory Access）模型 所有存储器都是私有的； 绝大多数NORMA都不支持远程存储器的访问； 在DSM中，NORMA就消失了。,并行计算机访存模型(续2),并行计算机系统的不同访存模型分类,并行计算模型,SIMD同步并行计算模型 共享存储的S

14、IMD模型（PRAM模型） 分布存储的SIMD模型（SIMD互联网络模型） MIMD异步并行计算模型 异步PRAM模型 BSP模型 LogP模型 C3模型,SIMD同步并行计算模型,SIMD共享存储模型（PRAM模型） PRAM-EREW （Exclusive-Read and Exclusive-Write），不允许同时读和同时写 PRAM-CREW （Concurrent-Read and Exclusive-Write） ，允许同时读但不允许同时写 PRAM-CRCW （Concurrent-Read and Concurrent-Write） ，允许同时读和同时写 优点： 适合于并行算

15、法的表达、分析和比较； 使用简单，很多诸如处理器间通信、存储管理和进程同步等并行计算机的低级细节均隐含于模型中； 易于设计算法和稍加修改便可运行在不同的并行计算机上； 且有可能加入一些诸如同步和通信等需要考虑的方面。,SIMD分布存储模型,采用一维线性连接的SIMD模型，简记为SIMD-LC 采用网孔连接的SIMD模型，简记为SIMD-MC 采用树形连接的SIMD模型，简记为SIMD-TC 采用树网连接的SIMD模型，简记为SIMD-MT 采用立方连接的SIMD模型，简记为SIMD-CC 采用立方环连接的SIMD模型，简记为SIMD-CCC 采用洗牌交换连接的SIMD模型，简记为SIMD-SE

16、 采用蝶形连接的SIMD模型，简介为SIMD-BF 采用多级互联网络连接的SIMD模型，简记为SIMD-MIN,MIMD异步计算模型PRAM模型,APRAM特点: 每个处理器都有其本地存储器、局部时钟和局部程序 处理器间的通信经过共享全局存储器 无全局时钟，各处理器异步地独立执行各自的指令 处理器任何时间依赖关系需明确地在各处理器的程序中加入同步（路）障（Synchronization Barrier） 一条指令可在非确定但有限的时间内完成。 APRAM模型中有四类指令: 全局读，将全局存储单元中的内容读入本地存储器单元中 局部操作，对本地存储器中的数执行操作，其结果存入本地存储器中 全局写，

17、将本地存储器单元中的内容写入全本地存储器单元中 同步，同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序,MIMD异步计算模型BSP模型,作为计算机语言和体系结构之间的桥梁，由以下述三个参数描述分布存储的并行计算机模型： 处理器/存储器模块（下文简称处理器） 处理器模块之间点到点信息传递的路由器 执行以时间间隔L为周期的路障同步器 特点： 将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅施行点到点的消息传递，不提供组合、复制或广播等功能，这样做既掩盖了具体的互联网络拓扑，又简化了通信协议 采用路障方式的以硬件实现的全局同步是在可控的粗粒度级，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员并无过分的负担 在分析BSP模型的性能时，假定局部操作可在一个时间步内完成，而在每一超级步中，一个处理器至多发送或接受h条消息（h-relation）,