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

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

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

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

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

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