多核多线程技术

多核程序设计参考资料：1.多核系列教材编写组.多核程序设计.清华大学出版社(第7版),2007.92.DavidB.Kirk,Wen-meiW.Hwu著.陈曙晖,熊淑华译.大规模并行处理器编程实践.清华大学出版社,2010.93.MauriceHerlihy,NirShavit著.金海,胡侃译.多处理器编程的艺术.机械工业出版社,2009.84.RichardGerber,AartJ.C.Bik,KevinB.Smith等著,王涛,单久龙,孙广中译.软件优化技术——IA-32平台的高性能手册(第2版).电子工业出版社,2007.4多核程序设计电子书及资料下载：多核程序设计第一章多核技术导论长春工业大学计算机科学与工程学院微处理器发展史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…长春工业大学计算机科学与工程学院并行计算机由一组处理单元组成，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。出现背景:60年代初期，晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。出现规模不大的共享存储多处理器系统，即大型主机（典型代表：IBM360）。60年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了，在处理器内部的应用大大提高了并行计算机系统的性能。两个最主要的组成部分计算节点节点间的通信与协作机制长春工业大学计算机科学与工程学院并行计算机的弗林分类Flynn根据指令流和数据流的不同组织方式，把计算机系统的结构分为以下四类：单指令流单数据流（SingleInstructionstreamSingleDatastream,SISD）单指令流多数据流（SingleInstructionstreamMultipleDatastream,SIMD）多指令流单数据流（MultipleInstructionstreamSingleDatastream,MISD）多指令流多数据流（MultipleInstructionstreamMultipleDatastream,MISD）长春工业大学计算机科学与工程学院并行计算机从系统结构角度分类分布式存储器的SIMD处理机含有多个同样结构的处理单元（PE），通过寻径网络以一定方式互相连接。每个PE有各自的本地存储器（LM）。向量超级计算机（共享式存储器SIMD）集中设置存储器，共享的多个并行存储器通过对准网络与各处理单元PE相连。在处理单元数目不太大的情况下很理想。对称多处理器（SMP）一个计算机上汇集了一组处理器，各处理器之间共享内存子系统以及总线结构。并行向量处理机（PVP）使用定制的高带宽网络将向量处理器连向共享存储器模块使用大量的向量寄存器和指令缓冲器集群计算机由许多连在一起的独立计算机组成，像一个单独集成的计算机资源一样协同工作，用来解决大型计算问题。长春工业大学计算机科学与工程学院片上多核处理器架构片上多核处理器（ChipMulti-Processor，CMP）就是将多个计算内核集成在一个处理器芯片中，从而提高计算能力。按计算内核的对等与否，CMP可分为同构多核和异构多核CPU核心数据共享与同步的通信机制：总线共享Cache结构：每个CPU内核拥有共享的二级或三级Cache，用于保存比较常用的数据，并通过连接核心的总线进行通信。基于片上互连的结构：每个CPU核心具有独立的处理单元和Cache，各个CPU核心通过交叉开关或片上网络等方式连接在一起。给程序开发者带来的挑战长春工业大学计算机科学与工程学院操作系统对多核处理器的支持方法调度与中断对任务的分配进行优化。使同一应用程序的任务尽量在一个核上执行。对任务的共享数据优化。由于CMP体系结构共享二级缓存，可以考虑改变任务在内存中的数据分布，使任务在执行时尽量增加二级缓存的命中率。对任务的负载均衡优化。当任务在调度时，出现了负载不均衡，考虑将较忙处理器中与其他任务最不相关的任务迁移，以达到数据的冲突量小。输入输出系统多核体系处理器中，必须将中断处理分发给一组核处理。存储管理与文件系统库函数做成非阻塞调用方式（需要保证数据同步的机制）使用多线程内存分配长春工业大学计算机科学与工程学院并行计算机体系结构组成并行计算机的各个部分：节点（node）互联网络（interconnectnetwork）内存（memory）内存模块与节点分离内存模块位于节点内部长春工业大学计算机科学与工程学院多级存储体系结构为了解决内存墙（memorywall）性能瓶颈问题。在节点内部的cache称为二级cache（L2cache）。在处理器内部更小的cache成为一级cache（L1cache）。L1cache连接CPU寄存器和L2cache，负责缓存L2cache中的数据到寄存器中。长春工业大学计算机科学与工程学院多级存储体系结构并行计算机的多级存储结构主要包括两个问题：Cache的映射策略，即cache如何从内存中取得数据进行存储；节点内部或者节点之间内存的访问模式。cache原理cache以cache线为基本单位，每条cache包含L个字，每个字8个字节。例如，L=4，则表示cache线包含4*8=32个字节。内存空间分割成块（block），每个块大小与cache线长度一致，数据在内存和cache之间的移动以cache线为基本单位。Fori=1toMA[i]=A[i]+2*B[i]如果操作数存在cache中，称该次访问是命中的，否则，该次操作是“扑空”的。无Cache，访问内存2M次；有cache，访问内存2M/L次长春工业大学计算机科学与工程学院多级存储体系结构cache的映射策略指的是内存块和cache线之间如何建立相互映射关系。直接映射策略（directmappingstrategy）每个内存块只能被唯一的映射到一条cache线中K－路组关联映射策略（K-waysetassociationmappingstrategy）Cache被分解为V个组，每个组由K条cache线组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一条cache线。全关联映射策略（fullassociationmappingstrategy）内存块可以被映射到cache中的任意一条cache线。长春工业大学计算机科学与工程学院并行计算机访存模型UMA（UniformMemoryAccess）模型物理存储器被所有节点共享；所有节点访问任意存储单元的时间相同；发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；各节点的CPU可带有局部私有高速缓存；外围I/O设备也可以共享，且每个节点有平等的访问权利。NUMA（Non-UniformMemoryAccess）模型物理存储器被所有节点共享，任意节点可以直接访问任意内存模块；节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的3倍以上；发生访存竞争时，仲裁策略对节点可能是不等价的；各节点的CPU可带有局部私有高速缓存（cache）；外围I/O设备也可以共享，但对各节点是不等价的。长春工业大学计算机科学与工程学院并行计算机访存模型COMA（Cache-OnlyMemoryAccess）模型各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间利用分布的高速缓存目录D进行远程高速缓存的访问COMA中的高速缓存容量一般都大于2级高速缓存容量使用COMA时，数据开始时可以任意分配，因为在运行时它最终会被迁移到要用到它的地方NORMA（No-RemoteMemoryAccess）模型所有存储器都是私有的；绝大多数NORMA都不支持远程存储器的访问；在DSM中，NORMA就消失了。长春工业大学计算机科学与工程学院并行计算机访存模型并行计算机系统的不同访存模型分类长春工业大学计算机科学与工程学院并行计算模型SIMD同步并行计算模型共享存储的SIMD模型（PRAM模型）PRAM，ParallelRandomAccessMachine分布存储的SIMD模型（SIMD互联网络模型）MIMD异步并行计算模型异步PRAM模型BSP模型LogP模型C3模型长春工业大学计算机科学与工程学院同步并行计算模型SIMD共享存储模型（PRAM模型）PRAM-EREW（Exclusive-ReadandExclusive-Write），不允许同时读和同时写PRAM-CREW（Concurrent-ReadandExclusive-Write），允许同时读但不允许同时写PRAM-CRCW（Concurrent-ReadandConcurrent-Write），允许同时读和同时写优点：适合于并行算法的表达、分析和比较；使用简单，很多诸如处理器间通信、存储管理和进程同步等并行计算机的低级细节均隐含于模型中；易于设计算法和稍加修改便可运行在不同的并行计算机上；有可能加入一些诸如同步和通信等需要考虑的方面。长春工业大学计算机科学与工程学院分布存储模型采用一维线性连接的SIMD模型，简记为SIMD-LC采用网孔连接的SIMD模型，简记为SIMD-MC采用树形连接的SIMD模型，简记为SIMD-TC采用树网连接的SIMD模型，简记为SIMD-MT采用立方连接的SIMD模型，简记为SIMD-CC采用立方环连接的SIMD模型，简记为SIMD-CCC采用洗牌交换连接的SIMD模型，简记为SIMD-SE采用蝶形连接的SIMD模型，简介为SIMD-BF采用多级互联网络连接的SIMD模型，简记为SIMD-MIN长春工业大学计算机科学与工程学院异步计算模型——APRAM模型APRAM特点:每个处理器都有其本地存储器、局部时钟和局部程序处理器间的通信经