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

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

1、基于多核系统的并行算法和实例分析免费的午餐结束了并行时代已经到来频率提升受到限制多核CPU成为主流并向着更多的核发展为什么我们需要并行计算？更快的完成计算（更低的延迟）处理更大规模的问题（更高的吞吐量）为什么并行计算是一个难题本质上说并行计算是一种优化的手段糟糕的并行算法在并行化上所产生的额外开销常常大于计算本身没有一种方法可以自动的把串行程序并行化没有银弹——库、框架、语言、开发工具如何应对？算法是并行计算的灵魂用并行的思想重新思考算法并行算法的核心问题任务分解基于时间的分解Pipeline将任务在时间上分解为若干独立的步骤，为每个步骤都

2、赋予一个执行单元，所有的执行单元一起协同工作就构成了流水线。一个简单的4级指令流水线的例子：流水线工作的时序图：Pipeline的优缺点优点很容易将串行算法转换为流水线算法非常有效的提升任务吞吐量适合在硬件上实现缺点不能降低单个任务的计算时间流水线级数是固定的，不具Scalability一般情况下不适合于软件实现基于空间的分解MapReduce将一个任务在空间上划分为若干独立的子任务，应用Map操作同时计算这些子任务，最后用Reduce操作将计算结果合并。MapReduce的基本框架：任务分解需要考虑的问题任务之间的独立性任务的粒度粒度太大，容

3、易出现负载不均衡粒度太小，并行化的Overhead会影响性能并行环境下的内存问题内存访问对处理器来说是一种IO有IO就有时序，小心同步问题避免使用锁锁的开销往往很大容易出错定制并行环境下的内存分配器Cache的影响任务的分解要考虑如何利用好cache避免false-sharing共享内存VS消息传递共享内存所有的核心可以访问在同一地址空间的内存高性能的数据共享需要小心的同步内存的访问适用于多线程模型消息传递每个任务有独立的内存地址空间使用收发消息来实现任务之间的数据交换通讯的代价很大适用于分布式系统抽象内存IO模型ScattervsGather

4、Gather是并行化友好的内存IO，而Scatter不是在设计并行算法时，考虑用Gather代替Scatter在用Scatter时，使用一些技巧来避免使用锁同步Scatterfor(i=0;i

5、llel_scan,parallel_pipline…)，并行化容器，轻量级锁等等…实现一个最简单的并行计算框架namespaceParallel{structKernel{virtualvoidExecute(intindex)=0;};voidInitialize(intmaxThread=-1);voidDestroy();voidFor(intfrom,intto,Kernel*kernel);intWorkerCount();intCurrentWorkerId();};一个简单的例子：数组求和串行版本floatserial_sum(

6、constfloat*numbers,intcount){floatsum=0;for(inti=0;i

7、->numbers=numbers;ZeroMemory(results,sizeof(results));}voidExecute(intindex){results[Parallel::CurrentWorkerId()]+=numbers[index];}floatReduce(){  floatsum=0;for(inti=0;i

8、r(0,count,&kernel);returnkernel.Reduce();}性能比较问题任务粒度太小存在false-sharing改进一下fl