串行算法并行化

1、西南大學(xué)第三屆大學(xué)生數(shù)學(xué)建模競(jìng)賽承諾書我們仔細(xì)閱讀了西南大學(xué)第三屆大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，雖然本次競(jìng)賽采取分散自行答卷的機(jī)制，但在競(jìng)賽開始 后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)夕卜 的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的，如果引用別人的成果或 其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述 方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有 違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們的參賽報(bào)名號(hào)為：題目：串行算法并行化參賽隊(duì)

2、員（簽名）隊(duì)員1:陳艷青隊(duì)員2：稅萍隊(duì)員3:孫偉霞日期：2009-5-3串行算法并行化摘 要本文針對(duì)cpu串行算法并行處理的高效率性問(wèn)題，建立了一個(gè)簡(jiǎn)單的數(shù)學(xué)模型， 即n*n矩陣的乘法。通過(guò)串行算法和并行算法時(shí)間復(fù)雜度的比較，串行算法的時(shí)間復(fù)雜 度為O (n人3)，而并行算法的時(shí)間復(fù)雜度為2logn-1+log(n / logn),在n比較大時(shí)近 似為O(logn)，闡述了串行的并行化處理算法的高效性，并進(jìn)入深入地分析，得到串行 算法并行化的方法。1、問(wèn)題重述從20世紀(jì)40年代開始的現(xiàn)代計(jì)算機(jī)發(fā)展歷程可以分為兩個(gè)明顯的發(fā)展時(shí)代：串行 計(jì)算時(shí)代、并行計(jì)算時(shí)代。由于實(shí)際應(yīng)用對(duì)高性能、低價(jià)格和持續(xù)生

3、產(chǎn)力日益增長(zhǎng)的要 求，并行處理技術(shù)已經(jīng)成為現(xiàn)代計(jì)算機(jī)科研與發(fā)展的關(guān)鍵技術(shù)。并行計(jì)算，是將一個(gè)計(jì) 算任務(wù)分?jǐn)偟蕉鄠€(gè)處理器上并同時(shí)運(yùn)行的計(jì)算方法，雙核CPU從外部看起來(lái)是一個(gè) CPU，但是內(nèi)部有兩個(gè)運(yùn)算核心，它們可以獨(dú)立進(jìn)行計(jì)算工作。在同時(shí)處理多個(gè)任務(wù)的 時(shí)候，多核處理器可以自然地將不同的任務(wù)分配給不同的核心。但只運(yùn)行一個(gè)以常規(guī)的 串行代碼寫成的程序時(shí)，如何將計(jì)算任務(wù)拆分成多個(gè)部分并分解到多個(gè)核心上同時(shí)運(yùn) 行，是我們要考慮的問(wèn)題。由于并不是所有的程序都是易并行的，所以我們需要解決的 問(wèn)題是：a）設(shè)計(jì)一種方法，能將一個(gè)常規(guī)的串行程序分解成兩個(gè)部分，使之能夠在CPU 的兩個(gè)核心上并行運(yùn)算，并且盡量使雙

4、核的運(yùn)算力被充分的利用起來(lái)；b）假設(shè)算法使用C語(yǔ)言寫成，代碼里只有順序執(zhí)行、分支、循環(huán)三種結(jié)構(gòu)；c）假設(shè)只對(duì)整形變量和整形數(shù)組進(jìn)行操作，不需要調(diào)用已有的庫(kù)函數(shù)d）程序中所有的語(yǔ)句只包括簡(jiǎn)單的代數(shù)運(yùn)算、賦值、條件分支語(yǔ)句、循環(huán)語(yǔ)句， 不包括其他語(yǔ)句。2、問(wèn)題分析此問(wèn)題要求對(duì)現(xiàn)成的串行算法進(jìn)行并行化處理，代碼里只涉及順序、分支、循環(huán) 三種結(jié)構(gòu)，所以我們只需要建立一個(gè)簡(jiǎn)單的C程序算法，將能夠使用雙核心并行處理的 部分分解開，使之在cpu的兩個(gè)乃至多個(gè)核心上并行運(yùn)算，其中關(guān)鍵是如何通過(guò)分析簡(jiǎn) 單的代碼，從總的計(jì)算任務(wù)中盡量識(shí)別可獨(dú)立運(yùn)算的部分，并估計(jì)每部分的計(jì)算量從而 達(dá)到合理的把任務(wù)分配到各個(gè)處理器

5、上。最大的一個(gè)問(wèn)題就是模型求解，考慮一些改進(jìn) 的近似算法求解是得到結(jié)果的關(guān)鍵。3、模型建立、求解及結(jié)果分析為了具體說(shuō)明串行算法的并行化處理，就以”n*n ”矩陣的乘法為例建立模型：常規(guī)串行算法就是把數(shù)據(jù)存在數(shù)組里面，然后根據(jù)嵌套的for循環(huán)來(lái)求解n*n矩陣 的乘法，代碼如下：有A、B、C三個(gè)矩陣；C為A、B相乘的結(jié)果double sum;for(i=0;in;i+)for(j=0;jn;j+)sum = 0;for(k=0;kn;k+)sum += Ai*n+k*Bj*n+k;Ci*col+colpos+j = sum;它的時(shí)間復(fù)雜度為0(抄3)。但是如果在一臺(tái)處理機(jī)數(shù)為M3 / logn的P

6、RAM上，用 O(logn)時(shí)間就可以完成兩個(gè)n*n矩陣的乘法。設(shè)A和B為輸入矩陣，假定最初可用的PE數(shù)為n人3個(gè)，后來(lái)降為n人3 / logn個(gè)。假設(shè)內(nèi)存由三維陣列組成，將A、B存入其中兩個(gè)平面。假設(shè)了 PE的三維地址指標(biāo)。PE(i，j，k)，0kn-1可用來(lái)計(jì)算輸出矩陣的第(i， j)項(xiàng)，0忍i，j忍n-1，n是2的幕。第一步，對(duì)應(yīng)于每個(gè)輸出的n乘積項(xiàng)用n個(gè)PE在0(1)時(shí)間內(nèi)進(jìn)行計(jì)算。第二步，這些乘積項(xiàng)用O(logn)時(shí)間相加產(chǎn)生一個(gè)輸出。所用的PE總數(shù)為M3, 結(jié)果存在C(i，j，0)中(0忍i，j忍n-1)。假定這里的PRAM采用的是CREW策略。Step 1：Read A(i，k)

7、Read B(k，j)Compute A(i， k)XB(k,j)Store in C(I,j,k)Step 2：LnRepeat LL / 2If (k1)thenbeginRead A(i, k)Read A(i, k)Compute C(i,j,k)+C(i,j,k,k+l)Store in C(i,j,k)EndUntil (l=1)上述是每個(gè)PE(i, j, k)要執(zhí)行的程序。所有nA3個(gè)PE對(duì)nA3乘法進(jìn)行并行運(yùn)算。 但對(duì)完成(抄3-抄2 )加法最多只有nA3/2個(gè)PE處于工作狀態(tài)。為了將PE數(shù)降為n人3 / logn，可采用nXnXn / logn的PE陣列。每個(gè)PE負(fù)責(zé)計(jì)算lo

8、gn個(gè)乘積項(xiàng)并將它們求和。第一步很容易改寫產(chǎn)生n / logn個(gè)部分和，每一個(gè)部分和由logn次乘法和(logn-1) 次加法完成。我們有數(shù)組 C(i, j, k), 0忍i, j忍n-1, Okn / logn-1，它們可在 log(n / logn) 時(shí)間內(nèi)完成求和，所以將第一步和第二步所花的時(shí)間相加，我們就得到總執(zhí)行時(shí)間為 2logn-1+log(n / logn),在 n 比較大時(shí)近似為 O(logn)。由上述可以明顯得知，并行化處理要比串行處理更高效，如果串行算法并行化了, 那么，即使并行的效率只有一半，實(shí)際效率就會(huì)由0.05%提高到50%，即實(shí)際計(jì)算能力 提高了 1000倍！即便并行化的效率只有十分之一，實(shí)際效率也會(huì)由0.05%提高到10%, 即實(shí)際計(jì)算能力提高了 200倍！參考文獻(xiàn)：胡明，高慶獅，高小宇，串行算法并行化基礎(chǔ)，科學(xué)出版社，2008-6-1陳