面向多核系統(tǒng)的程序并行化方法.pdf

1、由于集成電路工藝技術(shù)的縮微化和應(yīng)用需求，高性能微處理器將多個(gè)處理器單元集成到單芯片上來(lái)實(shí)現(xiàn)處理器性能的提升和功耗的減少。但要充分利用多核系統(tǒng)所提供的硬件資源，必須解決應(yīng)用程序的并行化編程問(wèn)題。然而，應(yīng)用程序的并行化編程問(wèn)題非常復(fù)雜。1)長(zhǎng)期以來(lái)大多數(shù)程序員都采用串行的編程模型和編程語(yǔ)言；2)大量現(xiàn)存的應(yīng)用程序和算法描述均是采用串行語(yǔ)言編寫(xiě)；3)面對(duì)不同的應(yīng)用程序和多處理器系統(tǒng)結(jié)構(gòu)，尋求通用的并行編程模型十分困難。因此，到目前為止研究人員

2、還沒(méi)有較好的方法來(lái)解決應(yīng)用程序的并行化編程。
　　 我們針對(duì)上述并行化編程的困難，提出一種面向C程序的編程并行化方法，由程序員指導(dǎo)，工具輔助，實(shí)現(xiàn)半自動(dòng)化的開(kāi)發(fā)源程序的并行性。該方法結(jié)合流應(yīng)用程序的特點(diǎn)，通過(guò)關(guān)注多層循環(huán)結(jié)構(gòu)來(lái)開(kāi)發(fā)應(yīng)用程序中隱藏的并行性，提出了既適用于任務(wù)并行模式，又適用于流水并行模式的并行策略。
　　 本文提出的并行編程方法包括四個(gè)步驟。1)對(duì)源代碼進(jìn)行程序分析，結(jié)合典型數(shù)據(jù)運(yùn)行驅(qū)動(dòng)剖析和依賴分析，獲取

3、應(yīng)用程序的執(zhí)行開(kāi)銷、條件分支選擇、函數(shù)調(diào)用關(guān)系、存儲(chǔ)占用、函數(shù)訪問(wèn)的變量以及依賴關(guān)系等信息，建立任務(wù)依賴圖模型。2)對(duì)任務(wù)依賴圖模型進(jìn)行變換，消除其中的控制依賴和冗余迭代間數(shù)據(jù)依賴，聚合環(huán)狀依賴，以生成適于調(diào)度的有向無(wú)環(huán)圖。3)進(jìn)行任務(wù)調(diào)度，為任務(wù)設(shè)置兩級(jí)優(yōu)先級(jí)，任務(wù)映射過(guò)程中充分考慮分支任務(wù)的互斥性。采用啟發(fā)式方法，通過(guò)反饋優(yōu)化，逐步求精，獲取并行化方案。4)封裝任務(wù)，生成可執(zhí)行代碼，在多核平臺(tái)上進(jìn)行性能的評(píng)估。
　　 我們選

4、用T264解碼程序和AES加密程序?yàn)閷?shí)驗(yàn)對(duì)象，分別在2核、4核和8核的硬件平臺(tái)上進(jìn)行評(píng)估。本文提出的并行化方法在8核平臺(tái)上，AES和T264相對(duì)于單核處理器分別有5.12和5.62的加速比。實(shí)驗(yàn)結(jié)果證明了本方法的有效性和良好的可擴(kuò)展性。
　　 本文所提出的并行化方法繼承了以往的并行化研究的經(jīng)驗(yàn)，采用啟發(fā)式框架，同時(shí)兼具自己的特色：1)定義了任務(wù)依賴圖(task dependence graph，TDG)模型。該模型適用于任何應(yīng)用

5、程序，能夠有效表示程序中的控制依賴和數(shù)據(jù)依賴。2)針對(duì)存在錯(cuò)綜復(fù)雜依賴關(guān)系的任務(wù)圖模型提出一種有別于傳統(tǒng)聚合消除法的變換規(guī)則。分別對(duì)分支、循環(huán)和迭代問(wèn)依賴采用不同的技術(shù)，能夠有效解除環(huán)狀依賴。3)將動(dòng)態(tài)優(yōu)先級(jí)與靜態(tài)優(yōu)先級(jí)相結(jié)合。動(dòng)態(tài)優(yōu)先級(jí)保證了關(guān)鍵路徑上的任務(wù)總能被優(yōu)先處理，而靜態(tài)優(yōu)先級(jí)綜合考慮了任務(wù)的計(jì)算開(kāi)銷和存儲(chǔ)占用情況。任務(wù)到處理器的映射方法以盡量減少的執(zhí)行時(shí)間為優(yōu)化目標(biāo)，還考慮了存在分支選擇的情況。4)不僅僅對(duì)任務(wù)并行模式進(jìn)行了