《OpenMP并发排序算法实现.doc》由会员分享，可在线阅读，更多相关《OpenMP并发排序算法实现.doc（20页珍藏版）》请在三一文库上搜索。
1、-范文最新推荐- OpenMP并发排序算法实现 摘要：本首先介绍了并发的意义是为了迎接多核时代的到来和对计算速度和效率的追求。阐述了采用线程化方法的四个步骤，并略述了并发编程核心内容与实现方法。其次，解释了为什么在设计中全部使用OpenMP线程化库，以及多线程程序设计中的8条简单规则。然后利用这些工具和规则，对奇偶换位排序算法，希尔排序算法、快速排序算法、堆排序算法进行了并发化，略述了他们的串行算法，以串行算法为出发点，进行逐步并发，通过不断改进，使得并发算法能适用于不同的环境。最后，从效率、简单性、可移植性、可伸缩性这四个设计要素来进行分析，切实地提高了运算的效率。12236关键词：并发；排
2、序； OpenMP；设计要素权衡；Concurrent sorting algorithm implementationAbstract: This paper first introduces a concurrent meaning in order to meet the multi-core era and the pursuit of computing speed and efficiency . Described the four steps with the thread method , and outlines the concurrent programming of
3、the core content and implementation . Secondly , it explains why , in the design of all OpenMP threaded libraries , as well as multi-threaded programming , 8 Simple Rules . Then use these tools and rules on parity transposition sorting algorithm , Hill sorting algorithms , Quicksort algorithm concur
4、rency , and outlines the serial algorithm , stepwise concurrent serial algorithm as a starting point , through continuous improvement makes concurrent algorithm can be applied to different environments . Finally, from the efficiency , simplicity , portability , scalability to analyze these four desi
5、gn elements and effectively improve the efficiency of operations .Keywords:concurrent ; sort；OpenMP ；Design elements of trade-offs 4.3.1串行算法简述244.3.2快速排序并发算法详述274.4堆排序284.4.1串行算法简述284.4.2并发算法315分析335.1奇偶换位排序335.2希尔排序345.3快速排序355.4堆排序366结论38致谢39参考文献401绪论1.1课题的目的和意义课题目的通过并发排序算法的实现，提高排序算法的速度。通过在多核处理器上编
6、写并发排序程序，可以获得何种程度的性能提升？最理想的情况是：当在双核处理器上运行并发程序时，总的执行时间将减半，在4核处理器上运行时降为1/4，在8核处理器上运行时降为1/8，依次类推。这听上去似乎比新一代处理器降低20%30%运行时间的情况要更好。然而，如果想要使代码充分发挥多核处理器的优势，那么需要付出一定的努力。此外，通常很少有代码能够达到理想情况下的性能提升程度。事实上，随着处理器数量的增加，性能提升的程度实际上可能在逐渐降低。不过，如果编写出高质量的并发多线程程序，那么还是可以获得不错的性能提升，反过来可以解释为什么不能获得性能提升。更理想的情况是，如果开发出的并发算法在8核，16核
7、或者更多核的处理器上运行时，能够获得与在双核或者4核上运行时一样大的性能提升度，那么将更好。课题的意义人们对计算机系统提供更强的计算能力的需求总是不断增长的，需要很高计算速度的领域包括科学和工程问题的数值建模和模拟。这些问题常需要对大量数据进行很多次重复计算以得到有效结果。此外，计算必须在“合理”的时间内完成。在制造领域，工程计算和模拟如果可能的话必须在几秒或者几十秒内完成。在设计环境中，如果进行一次模拟需要有两星期才能得到结果通常是不可以接受的。因为只有模拟完成时间足够短时，设计者方可高效地工作。当系统变得更加复杂时，就需要增加更多的时间对系统进行模拟。有一些应用的问
8、题的计算对时间有特定的期限（最著名的要数气象预报），花两天时间来获取当地第二天精确的天气预报将使这种预报毫无意义。某些研究领域，如对大型DNA结构建模以及进行全球天气预报均属于巨大挑战性问题。 因为OpenMp侧重于数据分解方法，可以将大型数据集上的循环线程化，因此很适合使用在排序算法上，所以在本课题中，我将使用OpenMp技术来实现并发的排序算法。1.2.2超线程技术每个单位时间内，CPU只能处理一个运行绪，以这样的单位进行，如果想要在单位时间内处理超过一个的运行绪是不可能的，除非是有两个核心处理单元。双核心技术是将两个一样的CPU放置于一个封装内（或直接将两个CPU做成一个芯片），而英特尔
9、的HT技术是在CPU内部仅复制必要的资源、让CPU模拟成两个逻辑核心；也就是一个实体核心，两个逻辑核心，在单位时间内处理两个运行绪，模拟双核心运作。Intel自Pentium开始引入超标量、乱序运行（en:Out-of-order_execution）、暂存器重命名（en:Register renaming）、多指令解码器等特性；这些特性的原理是让CPU拥有大量资源以增加指令运行效率，可是在现实中这些资源经常闲置；为了有效利用这些资源，就干脆再增加一些资源来运行第二个运行绪，让这些闲置资源运行另一个运行绪，而且CPU只要增加少数资源就可以模拟成两个逻辑核心。1.2.3睿频加速技术因特尔睿频加速
10、技术可以按需提供更高性能，如果处理器检测到功耗和温度低于限值，则其主频将提高，为活跃的处理器内核增加性能。因特尔睿频加速技术也可以进一步提高主频，即使在运行单线程软件如常用的办公应用时也不例外，如果所有内核均处于活跃状态，并且处理器运行指标低于限值时，因特尔睿频技术也能发挥作用，以此来使CPU始终处于高性能状态。1.2.4云技术云计算（英文：Cloud computing），是一种基于互联网的计算方式，通过这种方式，共享的软硬件资源和信息可以按需提供给计算机和其他设备。整个运行方式很像电网。 2.2采用线程化方法的4个步骤第一步：找出并发性在应用程序的串行代码中已经包含了设计和编写等步骤，因此
11、可以很清楚地知道这个应用程序所具备的功能。同样，还知道在指定的输入参数下将产生怎样的输出。现在，你需要找出哪些代码可以通过线程模型来实现，也就是找出在应用程序中包含了独立计算的代码。如果对这个应用程序非常熟悉，那么就能很快地找出这些代码。如果不太熟悉，那么可以通过对程序执行性能进行分析以找出可能包含独立计算的热点位置。热点是指一段包含了大量操作的代码。在性能分析器中，可以将在计算中消耗的时间作为判断是否为热点的标准。在找出程序中执行时间消耗最多的位置后，就可以开始执行这些位置上的代码，并判断它们是否可以并发执行。然而，消耗最多执行时间并非一定就意味着代码可以被修改为并发执行，必须通过对代码的算
12、法进行分析来判断在这段代码中是否包含足够高的独立性以支持并发执行。尽管如此，通过搜索应用程序中执行时间消耗最多的代码部分，还是可以达到事半功倍的效果。如果我们花一个月的时间来编写、测试并且调优一段占串行时间75%的代码，那么肯定比对一段仅占串行执行时间2%的代码进行相同工作所获得的效果要好得多。第二步 设计与实践：采用线程来实现算法在找出了独立的计算后，就需要考虑如何将串行代码修改为并发代码。这个步骤也正是并发的核心。第三步 测试正确性：检测并修复在线程化是引入的错误在对应用程序的代码进行修改时，很可能会引入新的错误。因此，对于在串行程序中增加代码可以穿件和控制多个线程的情况来说，也不例外，多
13、线程的程序在测试中可能会暴露出问题，也可能不会。即便你已经将这个程序正确地运行了数百次，但当在另一个新系统上运行该程序时，仍有可能出现错误，当然也可能仍不出错。有时候，虽然代码在正常运行时发现了一个错误，但是在调试器（甚至是一个能够感知线程的调试器）下运行代码时，仍可能出现无法定位问题，这是因为调试器的但不执行特性可能会掩盖正在分析的错误。通过printf语句（这也是所有调试工具中最常使用的方法）来输出变量的值则可能修改线程交替执行的时间，因此同样可能隐藏错误。 对线程化代码进行调优通常归结为识别出一些问题情况，包括：同步对象上发生竞争，分配到每个线程上的计算量不均衡，在调用线程化API时开销
14、过多，或者并行完成的工作量不足以弥补对代码线程化时产生的开销。与线程化错误一样，同样有一些工具可以帮助诊断和找出这些性能问题。然而，同样要问清楚，用线程来改写代码可能正式造成性能瓶颈的主要原因。通过将串行计算分解为不同的部分并将它们分配到多个线程上，那些曾经被精心调优过的串行执行可能无法获得像以前一样的性能。此外，还可能引入以下导致性能下降的错误，如伪共享、低效的内存访问模式或者总线过载等。要想找出这种类型的错误，需要借助一些在查找这类串行性能错误时使用的技术。2.3并发编程核心内容与实现方法并发编程的核心内容是指计算机能够以任何顺序来执行的独立计算。例如在代码中可独立执行的循环迭代和函数调用
15、都属于独立计算。从串行代码中提取出并发工作可以分配到多个线程上（或者相互协作的进程上），并且可以在多核处理器中的任何一个核上运行（或者在单核处理器上运行，此时需要将不同的独立计算换入/换出处理器核，从而形成一种并行执行的假象）。然而，在一个程序中，并非各个计算部分都是独立的，因此你仍然需要处理各个并发工作之间的串行执行工作。要想将并发工作分配到多个线程上，你需要调用一些实现了线程化机制的库函数，这些额外的函数调用将增加并发执行的开销，因为在最初的串行代码中并不包含这些函数调用。任何为了控制和协调线程而增加的额外代码，尤其是调用线程化库函数的代码，同样是一种开销。此外，你还需要增加一部分代码来判
16、断计算是应该继续执行，还是应该获取更多的工作或者在满足指定的条件时触发其他线程，这也是我们需要考虑的开销。不仅如此，我们还需要增加一些代码专门用来确保等量的工作分配到每个线程上。这种线程之间的负载均衡可以使线程不会处于空闲状态并浪费系统资源，这同样被认为是一种开销。在并发代码中必须尽可能地将上述开销维持在最低水平。要想获得最大程度的性能提升并且使并发代码实现尽可能高的可伸缩性，那么分配到每个线程的工作就要足够多，以便减少或者掩盖由于这些开销而带来的负面影响。 当然，我们的最终目的都是为了通过减少程序的执行时间来提升程序的性能，或者使程序能够在给定的时间里处理更多的数据。你需要清楚地意识到在并发
17、编程中存在的各种危险和陷阱，以及如何避免或者纠正它们，只有这样才能编写出执行正确并且性能令人满意的应用程序。2.4哪些算法不能并行虽然并行算法能提高程序的性能，但是也不是所有的算法都能从串行的改为并行算法的，以下即是一些不能改为并行的串行算法。2.4.1带有状态的算法首先无法并发执行的算法就是带有某个状态的算法，函数或者过程。也就是说，需要从上一次执行保持到下一次执行的某个东西。由于每一个执行过程都依赖于某一个状态，因此这种算法无法被并行化。2.4.2递推算法在循环中的递推关系需要将某些信息从上一次迭代送入到下一次迭代。比如ai=ai+1+bi这种代码就无法被并行化，他每一次迭代都依赖于上一次
18、迭代。2.4.3归纳变量归纳变量是指，在每经过一次循环的时候都会递增的变量。通常这些变量与循环迭代器变量之间不存在一一映射的关系。比如蕾西ak+i=fk,r,i之类的函数调用，就几乎不可能被并行化处理。2.4.4归约算法归约算法是指将一组数据通过某种符合操作归约为一个简单的标量值。要消除这种依赖性，计算必须是可结合和可交换的，比如加法计算，乘法计算以及其他逻辑运算。不过如果算法并不是可结合和可交换的，比如除法运算，那这个归约计算就不能并行化。2.4.5循环体间的依赖性如果在当前的迭代中需要使用到之前迭代的结果，那么就会出现循环体间的依赖型。通常，这种情况表现为，在赋值计算的左边和右边都是用了数
19、组中的同一个元素，并且在右边有一个向后引用，比如ai=bi-5+dosomethingi。因为这种循环的迭代操作并不是完全独立的，因此无法被并行化。 规则3：尽早考虑通过增加处理器的数量来获得可伸缩性可伸缩性是衡量程序在应对系统资源或者数据集规模变化时（通常是增加，如增加处理器核的数量，内存大小，以及总线速度等）表现出来行为好坏的手段。随着处理器核数不断增加，必须写出灵活的代码以充分发挥这些处理器核带来的优势。规则4：尽可能使用线程安全的库如果热点位置上的计算可以通过调用某个库函数来执行，那么应该考虑使用库函数而不是自己编写代码。不过在这个过程中，确保所有的库函数调用对线程安全是十分重要的。在
20、使用某个库函数之前应该参考帮助文档来了解这个库函数是否是线程安全的，不然就需要增加同步机制来保护对资源的访问。规则5：使用正确的多线程模型如果多线程库还不足以满足程序中所有并发需求，并且必须采用用户自行控制的线程时，那么要尽可能使用满足的多线程模型（如OpenMP）而不是直接使用线程，直接使用线程能获得对线程化实现的更精细的控制，然后对一个计算密集的循环并行，或者无需直接使用线程就可以获得同样的灵活性，那么就不需要画蛇添足，实现越复杂，那么就越容易犯错，并且在今后维护代码时也越困难。OpenMP侧重于数据分解方法，尤其可以将大型数据集上的循环线程化，然而，即使这是可以在程序中引入的唯一一种并行
21、，也还可能存在其他一些外部需求使得无法使用OpenMP，在这种情况下，就需要使用OpenMP来建立并发原型，并估计可能获得的性能提升，可伸缩性以及在修改串行代码时需要付出的工作量。规则6：永远不要假设程序会按照某种特定的顺序执行虽然在串行算法中，很容易预测一条语句执行完后的下一条语句，不过在并发编程中，线程的执行顺序是不确定的，由操作系统来控制的。这就意味着并没有任何一种可靠的方式能够预测多个线程之间的执行顺序。因此在编程中要时刻记住不能假设程序会按某种顺序执行。 由于在创建和销毁线程时存在巨大的消耗，因此一些高性能的编译器在遇到第一个并行区域是创建一个线程组，在执行完合并操作后将这组线程置入
22、睡眠状态，然后当再次遇到分支操作时将唤醒这些线程。对于C/C+来说，OpenMP将使用pragma指令。OpenMP中所有pragma宏都带有一个前缀#pragma omp，之后是一个OpenMP结构以及一个或多个修饰这个结构的字句。要在程序中定义一个并行区域，使用#pragma omp parallel 这个pragma后面可以跟一条语句，也可以是一个包含在大括号内的代码块。当程序在执行过程中遇到这条语句时，它将fork出一组线程，每个线程都将执行该并行区域中的所有语句，并且在执行该区域中的最后一条语句时对所有线程进行合并。在许多程序的循环中都包含了大量的独立运算。通过使用OpenMP中的工
23、作共享结构，可以将这些循环迭代操作分解为多个子区间，并将它们分配到多个线程上并行执行。parallel for结构将定义一个新的并行区域，该区域就是紧跟在这个pragma后面的for循环，它将对循环迭代进行分解并分配到这组线程上。在执行完所分配的迭代操作后，线程会在并行区域末尾的隐式栅栏处停下来，并等待与其他线程执行合并操作。我们将parallel for结构分解为两部分，一个parallel结构和一个for结构，二者在词法上必须被包含在一个并行区域内。当线程组需要执行的是并行工作而不是循环迭代时，可以使用这种分开的形式。还可以将一个schedule子句附加到循环工作共享结构上，以控制如何将迭
24、代分配到线程的过程。静态调度方式将把循环迭代分解为多个子区间，然后将这些子区间分配到多个线程并执行；如果子区间的数量多于线程的数量，那么将使用轮询调度方法。动态调度方式将为每个线程分配一个迭代子区间，线程在执行完一个迭代子区间后，将又获得一个新的子区间，直到所有子区间都被分配完毕。对于静态调度方式和动态调度方式来说，都有一个可选参数chunk，用于控制在每个子区间中包含的迭代操作数量。 3.2设计线程库的说明众所周知，线程化库分为隐式线程化库和显式线程化库，隐式线程化库中又有OpenMP，intel threading building blocks，显式线程化库中又有pthread，Windows pthread等等，基于下文提到的简单规则5，以及上述阐述的OpenMP强大功能，本次课程设计所有的线程化库，全部使用OpenMP，本文其他部分将不再做过多赘述。 OpenMP并发排序算法实现(9): 19 / 20