基于多核系統(tǒng)的并行算法和實(shí)例分析

《基于多核系統(tǒng)的并行算法和實(shí)例分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、基于多核系統(tǒng)的并行算法和實(shí)例分析免費(fèi)的午餐結(jié)束了并行時(shí)代已經(jīng)到來頻率提升受到限制多核CPU成為主流并向著更多的核發(fā)展為什么我們需要并行計(jì)算？更快的完成計(jì)算（更低的延遲）處理更大規(guī)模的問題（更高的吞吐量）為什么并行計(jì)算是一個(gè)難題本質(zhì)上說并行計(jì)算是一種優(yōu)化的手段糟糕的并行算法在并行化上所產(chǎn)生的額外開銷常常大于計(jì)算本身沒有一種方法可以自動(dòng)的把串行程序并行化沒有銀彈——庫、框架、語言、開發(fā)工具如何應(yīng)對(duì)？算法是并行計(jì)算的靈魂用并行的思想重新思考算法并行算法的核心問題任務(wù)分解基于時(shí)間的分解Pipeline將任務(wù)在時(shí)間上分解為若干獨(dú)立的步驟，為每個(gè)步驟都

2、賦予一個(gè)執(zhí)行單元，所有的執(zhí)行單元一起協(xié)同工作就構(gòu)成了流水線。一個(gè)簡單的4級(jí)指令流水線的例子：流水線工作的時(shí)序圖：Pipeline的優(yōu)缺點(diǎn)優(yōu)點(diǎn)很容易將串行算法轉(zhuǎn)換為流水線算法非常有效的提升任務(wù)吞吐量適合在硬件上實(shí)現(xiàn)缺點(diǎn)不能降低單個(gè)任務(wù)的計(jì)算時(shí)間流水線級(jí)數(shù)是固定的，不具Scalability一般情況下不適合于軟件實(shí)現(xiàn)基于空間的分解MapReduce將一個(gè)任務(wù)在空間上劃分為若干獨(dú)立的子任務(wù)，應(yīng)用Map操作同時(shí)計(jì)算這些子任務(wù)，最后用Reduce操作將計(jì)算結(jié)果合并。MapReduce的基本框架：任務(wù)分解需要考慮的問題任務(wù)之間的獨(dú)立性任務(wù)的粒度粒度太大，容

3、易出現(xiàn)負(fù)載不均衡粒度太小，并行化的Overhead會(huì)影響性能并行環(huán)境下的內(nèi)存問題內(nèi)存訪問對(duì)處理器來說是一種IO有IO就有時(shí)序，小心同步問題避免使用鎖鎖的開銷往往很大容易出錯(cuò)定制并行環(huán)境下的內(nèi)存分配器Cache的影響任務(wù)的分解要考慮如何利用好cache避免false-sharing共享內(nèi)存VS消息傳遞共享內(nèi)存所有的核心可以訪問在同一地址空間的內(nèi)存高性能的數(shù)據(jù)共享需要小心的同步內(nèi)存的訪問適用于多線程模型消息傳遞每個(gè)任務(wù)有獨(dú)立的內(nèi)存地址空間使用收發(fā)消息來實(shí)現(xiàn)任務(wù)之間的數(shù)據(jù)交換通訊的代價(jià)很大適用于分布式系統(tǒng)抽象內(nèi)存IO模型ScattervsGather

4、Gather是并行化友好的內(nèi)存IO，而Scatter不是在設(shè)計(jì)并行算法時(shí)，考慮用Gather代替Scatter在用Scatter時(shí)，使用一些技巧來避免使用鎖同步Scatterfor(i=0;i

5、llel_scan,parallel_pipline…)，并行化容器，輕量級(jí)鎖等等…實(shí)現(xiàn)一個(gè)最簡單的并行計(jì)算框架namespaceParallel{structKernel{virtualvoidExecute(intindex)=0;};voidInitialize(intmaxThread=-1);voidDestroy();voidFor(intfrom,intto,Kernel*kernel);intWorkerCount();intCurrentWorkerId();};一個(gè)簡單的例子：數(shù)組求和串行版本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();}性能比較問題任務(wù)粒度太小存在false-sharing改進(jìn)一下fl