基于多核系统的并行算法和实例分析

《基于多核系统的并行算法和实例分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于多核系统的并行算法和实例分基于多核系统的并行算法和实例分析析免费的午餐结束了免费的午餐结束了并行时代已经到来并行时代已经到来频率提升受到限制频率提升受到限制多核多核CPUCPU成为主流并向着更多的核发展成为主流并向着更多的核发展为什么我们需要并行计算？为什么我们需要并行计算？更快的完成计算（更低的延迟）更快的完成计算（更低的延迟）处理更大规模的问题（更高的吞吐量）处理更大规模的问题（更高的吞吐量）为什么并行计算是一个难题为什么并行计算是一个难题本质上说并行计算是一种优化的手段本质上说并行计算是一种优化的手段糟糕的并行算法在并行化上所产生的额外开销常糟糕的并行算法在并行

2、化上所产生的额外开销常常大于计算本身常大于计算本身没有一种方法可以自动的把串行程序并行化没有一种方法可以自动的把串行程序并行化没有银弹没有银弹————库、框架、语言、开发工具库、框架、语言、开发工具如何应对？如何应对？算法是并行计算的灵魂算法是并行计算的灵魂用并行的思想重新思考算法用并行的思想重新思考算法并行算法的核心问题并行算法的核心问题任务分解任务分解基于时间的分解基于时间的分解PipelinePipeline将任务在时间上分解为若干独立的步骤，为每个步骤都赋予一个执行单元，所有的执行单元一起协同工作就构成了流水线。一个简单的4级指令流水线的例子：流水线工作的时序图：Pip

3、elinePipeline的优缺点的优缺点优点优点很容易将串行算法转换为流水线算法很容易将串行算法转换为流水线算法非常有效的提升任务吞吐量非常有效的提升任务吞吐量适合在硬件上实现适合在硬件上实现缺点缺点不能降低单个任务的计算时间不能降低单个任务的计算时间流水线级数是固定的，不具流水线级数是固定的，不具ScalabilityScalability一般情况下不适合于软件实现一般情况下不适合于软件实现基于空间的分解基于空间的分解MapReduceMapReduce将一个任务在空间上划分为若干独立的子任务，应用将一个任务在空间上划分为若干独立的子任务，应用MapMap操作同时计

4、算这些子任务，最后用操作同时计算这些子任务，最后用ReduceReduce操作将操作将计算结果合并。计算结果合并。MapReduce的基本框架：Node1DecomposeNode2ReduceNoden任务分解需要考虑的问题任务分解需要考虑的问题任务之间的独立性任务之间的独立性任务的粒度任务的粒度粒度太大，容易出现负载不均衡粒度太大，容易出现负载不均衡粒度太小，并行化的粒度太小，并行化的OverheadOverhead会影响性能会影响性能并行环境下的内存问题并行环境下的内存问题内存访问对处理器来说是一种内存访问对处理器来说是一种IOIO有有IOIO就有时序，小心同步问题就有

5、时序，小心同步问题避免使用锁避免使用锁锁的开销往往很大锁的开销往往很大容易出错容易出错定制并行环境下的内存分配器定制并行环境下的内存分配器CacheCache的影响的影响任务的分解要考虑如何利用好任务的分解要考虑如何利用好cachecache避免避免false-sharingfalse-sharing共享内存共享内存VSVS消息传递消息传递共享内存共享内存所有的核心可以访问在同一地址空间的内存所有的核心可以访问在同一地址空间的内存高性能的数据共享高性能的数据共享需要小心的同步内存的访问需要小心的同步内存的访问适用于多线程模型适用于多线程模型消息传递消息传递每个

6、任务有独立的内存地址空间每个任务有独立的内存地址空间使用收发消息来实现任务之间的数据交换使用收发消息来实现任务之间的数据交换通讯的代价很大通讯的代价很大适用于分布式系统适用于分布式系统抽象内存抽象内存IOIO模型模型ScattervsGatherScattervsGatherScatterScatterfor(i=0;i

7、用一些技巧来避免使用锁同步常用的并行计算库介绍常用的并行计算库介绍OpenMPOpenMP语言级的并行扩展，使用简单语言级的并行扩展，使用简单对对parellel_forparellel_for提提供供了了良良好的好的支持支持缺缺乏乏对线程和内存的对线程和内存的控控制制机机制制TBBTBB基于基于C++C++模模板板库库功功能能强强大，提大，提供供了了丰富丰富的并行化模式的并行化模式(parallel_for,(par