并行计算作业一

并行编程模型1.概述并行编程模型是并行计算，尤其是并行软件的基础，也是并行硬件系统的导向。并行编程模型可以按照以下几种方式进行表述：（1）数据并行和任务并行：根据并行程序是强调相同任务在不同数据单元上并行，还是不同任务在相同或不同数据上实现并行执行，可以将并行性分为两类：数据并行和任务并行。由于数据并行能获得的并行粒度比任务并行高，因此可以扩展并行机上的大多数程序采取数据并行方式。但是任务并行在软件工程上有很重要的作用，它可以使不同的组件运行在不同的处理单元集合上，从而获得模块化设计。人们越来越趋向予将并行程序组织成为由数据并行组件组成的任务并行组合物。（2）显式并行和隐式并行：并行编程系统可以根据支持显式或隐式并行编程模型来对其进行分类。显式并行系统要求编程人员直接制定组成并行计算的多个并发控制线程的行为；隐式并行系统允许编程人员提供一种高层的、指定程序行为但不显示表示并行的规范，它依赖于编译器或底层函数库来有效和正确地实现并行。越来越普遍的一种做法就是将算法设计的复杂性集成到函数库上，这样可以通过一系列对函数库的调用来开发应用程序。通过这种方式，可以在一种显式并行框架中获得隐式并行的某些好处。（3）共享存储和分布存储：在共享存储模型中，程序员的任务就是指定一组通过读写共享存储进行通信的进程的行为。在分布存储模型中，进程只有局部存储，它必须使用诸如消息传递或远程过程调用等机制来交换信息。很多多核处理器体系结构都同时支持这两种模型。共享存储体系结构下的并行编程模型主要是共享变量编程模型，它具有单地址空间、编程容易、可移植性差等特点，其实现有OpenMP和Pthreads等。分布式存储体系结构下的并行编程模型主要有消息传递编程模型和分布式共享编程模型两种:消息传递编程模型的特点是多地址空间、编程困难、可移植性好，其实现有MPI,PVM等;分布式共享编程模型是指有硬件或软件的支持，在分布式体系结构下实现的具有共享变量编程模型特点的编程模型。后者可以分别按照硬件或软件的实现分为DSM和SVM,其实现有TreadMark和JiaJia等，目前研究热点的分割全局地址空间(PGAS)模型的研究有UPC等代表，具有很强的发展潜力。2.并行编程模型的性的评价指标(1)时间：程序串行运行时间是指在串行计算机上，程序从开始到运行结束所用的时间。并行运行程序是从并行计算开始时刻到最后的处理器完成运算所经过的时间。(2)总并行开销：并行系统的开销函数或总开销为由所有处理器话费的总时间，除去在单个处理器上求解相同问题时最快的串行算法所需要的时间。所有处理器所用总时间减去完成有用工作所花费的时间，剩余部分即是开销。(3)加速比：在单个处理器上求解问题所花的时间与用p个相同处理器并行计算机求解同一问题所花时间之比。(4)效率：处理器被有效利用部分时间的度量，它定义为加速比与处理器数目的比率。在理想的并行系统中，加速比等于p，效率等于1。实际上，加速比小于p而效率在0和1之间，它依赖于处理器被利用的效率。(5)成本：并行运行时间与所用处理器数目的乘积。成本反映每个处理器求解问题所花费时间的总和。另外，移植性、伸缩性和对各类语言的支持度也是评价指标。3．影响并行编程模型性能的关键因素多核处理器系统采用单芯片多处理器核的设计，这些处理器核相互独立，每个拥有一套完整的硬件执行环境，可以同时执行多道指令。在高速缓存设计方面，每个核拥有独立的片上缓存和共享的最后一级缓存。基于多核处理器的系统特征，影响并行程序性能的因素主要包括存储带宽、片上缓存一致性和负载均衡。（1）存储带宽。在多核系统中，最后一级缓存是被各个核所共享的，如果位于同核上的多个线程同时对不同的数据集进行操作，将会导致最后一级缓存与主存之间频繁地传送数据。由于在主存和缓存之间传送数据的速度远小于CPU的计算速度，因此有限的存储带宽成为了影响多核环境下并行程序性能的瓶颈。（2）片上缓存一致性。所谓片上缓存一致性，是指多核系统中各个核的片上缓存位于相同存储空间上的数据必须保持一致。虽然多核系统共享的cache体系结构在最后一级cache上减少了cache一致性问题，但由于每个核都拥有独立的cache，很可能出现一个核上的cache数据和另一个核上不一致的现象，这通常发生在位于不同核上运行的两个线程写入位于同一cache行上的两个数据，即使某个线程所需的位于某个cache块中的数据没有被重写过，但存储系统还是会把该cache块标记无效，这就是通常意义上的伪共享问题Ⅲ。如果这样的多个核同时写入位于同一cache行上数据的操作非常频繁，将会严重影响程序的性能。（3）负载均衡。在多核系统中，各核负载是否均衡也是影响程序性能的一个重要因素。如果出现某一核上在进行计算的同时另一核空闲等待的情况，那么这样的负载是不均衡的，多核资源的利用率是不高的。4.关键因素的相关优化技术及分析比较(1)如何减少有限存储带宽上的竞争。对于多个核同时在一个大数据集上进行操作的情况，如果数据集的大小超过最后一级共享缓存的容量，由于不同核操作的数据不同，将会在主存和高速缓存之间频繁地传送数据，我们使用cache块技术有效减少不必要的数据传送捌。即将一个大的数据集划分为多个比最后一级缓存容量小的子数据集，在各核上运行的线程对一个子数据集计算完毕后，继续对下一个子数据集进行计算，直到所有子数据集计算完毕为止。使用cache块技术虽然会增加同步开销，但可以有效减少存储竞争，提升程序性能。图所示是在二级缓存为2MB的双核CPU环境下不同大小数据集上进行500次循环读写操作分别采用cache块技术和简单平均划分数据集的运行时间对比。从图中我们可以看到一旦数据集大小超过了最后一级缓存的容量，由于各核上执行的是反复读写的操作，导致了在主存和最后一级缓存之间频繁地传送数据，而采用cache块划分的并行处理方式就能有效减少不必要的数据传送，提升程序性能。(2)如何减少片上缓存的一致性。如前所述，片上缓存的不一致性是由于多核处理器环境下不同核上的线程对处于同一cache行上的数据进行写操作，导致硬件逻辑将cache块标记为无效而在主存与cache传送数据所带来的开销。通常情况下有两种方法可以处理这样的问题，一个是将不同核上需要经常执行写操作的数据分配到不同的cache行上，另一个是将不同线程操作的共享变量拷贝到本地局部变量中，这样就不会导致某一核对某一地址数据进行写操作时导致其他核片上缓存失效的情况发生。(3)如何使各核负载均衡。多核环境下程序在各核上任务分配是否均衡在很大程度上影响着程序的性能。对于一个给定的任务，如果各核工作负载均衡，可以更充分地利用多核资源，提升程序性能。比如对于有I／0操作的任务，可以将计算任务和I／0任务合理地分配给各核，而不是某一个核上计算任务过多，而某一个核上I／0任务过多导致CPU过多地去等待。具体的方法可以使用线程的亲属属性，即将某一线程绑定到一个具体的核上去运行。5.小结本文首先对编程模型的定义以及分类进行了描述，把当前的编程模型的种类进行了概述。然后对并行编程模型的性能的评价指标进行了详细的描述，通过性能指标来判断不同编程模型的优缺点。有许多影响并行编程模型功能的因素，通过这些因素来制定相关的优化技术，从而来改善并行编程模型的性能。参考文献：1.AkhtefS,RobertJ．多核程序设计技术——通过软件多线程提升性能【M】．北京：电子工业出版社。2007．2.MPI与OpenMP并行程序设计（C语言版），MichaelJ.Quinn著，陈文光等译，清华大学出版社。3.并行计算综论，JackDongarra等著，莫则尧等译，电子工业出版社。4.并行计算系列丛书，陈国良，高等教育出版社。5.并行计算导论（中、英文版均有），AnanthGrama等著，机械工业出版社。