【摘要】： 隨著多核處理器已經(jīng)成為主流和工業(yè)標(biāo)準(zhǔn),如何在屏蔽底層細(xì)節(jié)簡(jiǎn)化編程的同時(shí)充分利用處理器核間的并行性來(lái)提高程序性能,已經(jīng)成為編程的一個(gè)巨大挑戰(zhàn)。C、C++和Fortran等基于單指令流和統(tǒng)一存儲(chǔ)結(jié)構(gòu)的傳統(tǒng)編程模型已經(jīng)無(wú)法適應(yīng)多核處理器結(jié)構(gòu)�；陬I(lǐng)域的數(shù)據(jù)流編程(Dataflow Programming)模型將媒體應(yīng)用特性與程序設(shè)計(jì)語(yǔ)言相結(jié)合,在簡(jiǎn)化編程的同時(shí),為編譯器在多核處理器下的優(yōu)化提供了大量的并行性,因此受到廣泛的關(guān)注。然而,多核處理器間的通信和同步開(kāi)銷(xiāo)以及大量媒體處理應(yīng)用的實(shí)時(shí)性要求對(duì)程序的性能提出了新的挑戰(zhàn)。針對(duì)以上數(shù)據(jù)流程序所面臨的實(shí)時(shí)性和代碼的高效性等問(wèn)題,本文對(duì)數(shù)據(jù)流程序編譯所涉及的主要關(guān)鍵技術(shù)進(jìn)行了系統(tǒng)研究。 針對(duì)當(dāng)前數(shù)據(jù)流語(yǔ)言的語(yǔ)法不易理解和難以編程的問(wèn)題,設(shè)計(jì)并實(shí)現(xiàn)了一種數(shù)據(jù)流編程語(yǔ)言DFBrook和相應(yīng)的編譯系統(tǒng)原型。DFBrook通過(guò)在標(biāo)準(zhǔn)C語(yǔ)言中擴(kuò)展數(shù)據(jù)流模型,實(shí)現(xiàn)了數(shù)據(jù)流和C語(yǔ)言的混合編程。程序員可以通過(guò)在C語(yǔ)言中嵌入數(shù)據(jù)流代碼來(lái)實(shí)現(xiàn)對(duì)特定程序模塊的數(shù)據(jù)流執(zhí)行。編譯系統(tǒng)對(duì)數(shù)據(jù)流語(yǔ)言進(jìn)行識(shí)別后,利用同步數(shù)據(jù)流圖作為相應(yīng)的中間代碼表示,同時(shí)根據(jù)目標(biāo)系統(tǒng)結(jié)構(gòu)特點(diǎn),對(duì)數(shù)據(jù)流程序進(jìn)行并行優(yōu)化,并生成面向目標(biāo)多核處理器的多線程代碼。 為了減小數(shù)據(jù)流程序在多核處理器上的通信開(kāi)銷(xiāo),提出了一種針對(duì)實(shí)時(shí)數(shù)據(jù)流程序的低通信軟件流水調(diào)度模型。模型利用整數(shù)線性規(guī)劃理論對(duì)軟件流水調(diào)度中的計(jì)算、通信資源以及流水線執(zhí)行的階段等進(jìn)行統(tǒng)一的形式化建模,將低通信軟件流水調(diào)度問(wèn)題表示為一個(gè)整數(shù)線性規(guī)劃問(wèn)題MCRO (Minimizing Communication at Rate-Optimal scheduling),在滿足實(shí)時(shí)應(yīng)用需求的響應(yīng)時(shí)間限制的同時(shí),使處理器核間的通信開(kāi)銷(xiāo)達(dá)到最小。通過(guò)擴(kuò)展MCRO調(diào)度模型,使之適用于DFBrook語(yǔ)言在Cell處理器上的執(zhí)行。將MCRO調(diào)度方法與傳統(tǒng)軟件流水的表調(diào)度List、PAPS (Periodic Admissable Parallel Schedule)以及RO(Rate Optimal)調(diào)度進(jìn)行性能比較,實(shí)驗(yàn)結(jié)果表明,MCRO調(diào)度比表調(diào)度List和PAPS調(diào)度在流水線的計(jì)算速率和通信開(kāi)銷(xiāo)上都有較大的性能改進(jìn),比RO調(diào)度在通信開(kāi)銷(xiāo)上也有較大的性能提高。 為了滿足多核處理器的內(nèi)存受限結(jié)構(gòu),提出了一種面向存儲(chǔ)受限結(jié)構(gòu)的軟件流水調(diào)度方法。方法基于低通信軟件流水調(diào)度模型,對(duì)每個(gè)處理器核的存儲(chǔ)資源進(jìn)行擴(kuò)展建模,將內(nèi)存受限軟件流水的調(diào)度表示為一個(gè)統(tǒng)一的整數(shù)二次規(guī)劃問(wèn)題ROMC (Rate-Optimal with Memory Constraints)。通過(guò)設(shè)計(jì)階段差估計(jì)算法將上述二次規(guī)劃問(wèn)題轉(zhuǎn)化為整數(shù)線性規(guī)劃問(wèn)題,從而將ROMC問(wèn)題分解為一系列的子問(wèn)題,通過(guò)有效地求解每一個(gè)子問(wèn)題,最終得到ROMC問(wèn)題的有效解。同時(shí),設(shè)計(jì)階段賦值調(diào)整算法來(lái)實(shí)現(xiàn)處理器核間的存儲(chǔ)開(kāi)銷(xiāo)平衡。實(shí)驗(yàn)結(jié)果表明,ROMC調(diào)度方法與現(xiàn)有的方法能取得更優(yōu)的調(diào)度結(jié)果。 為了生成高效的軟件流水代碼,提出一種面向多核處理器的軟件流水代碼生成方法和運(yùn)行時(shí)系統(tǒng)設(shè)計(jì)。代碼生成器在模塊化的軟件流水代碼生成框架的基礎(chǔ)上,采用單流水核(kernel-only)代碼模型來(lái)減小代碼開(kāi)銷(xiāo)。同時(shí)基于Cell處理器給出了運(yùn)行時(shí)系統(tǒng)的設(shè)計(jì)方法,詳細(xì)討論了地址轉(zhuǎn)換和同步支持等問(wèn)題,實(shí)現(xiàn)了軟件流水代碼和普通代碼的生成。 面向多核處理器的數(shù)據(jù)流程序軟件流水編譯需要研究的問(wèn)題還很多。在語(yǔ)言的設(shè)計(jì)上,需要進(jìn)一步完善對(duì)數(shù)據(jù)并行的支持、帶狀態(tài)核函數(shù)的定義和動(dòng)態(tài)計(jì)算速率的支持；在調(diào)度模型上,如何實(shí)現(xiàn)對(duì)帶有循環(huán)嵌套的數(shù)據(jù)流程序的軟件流水調(diào)度是進(jìn)一步需要研究的問(wèn)題；在編譯時(shí)間上,如何簡(jiǎn)化規(guī)劃模型,提高求解速度,特別是減小大數(shù)據(jù)量程序的編譯時(shí)間,是另一個(gè)需要進(jìn)一步研究的問(wèn)題。
【圖文】：

器為編譯器在代碼調(diào)度、局部存儲(chǔ)分配、通信管理和同步延遲等方面提供了更大的靈活和優(yōu)化空間。圖2.3為目標(biāo)多核處理器結(jié)構(gòu)框圖，該處理器由一個(gè)控制處理器或者主處理器 (Masterprocessor)和若干個(gè)數(shù)據(jù)處理器或者從處理單元 (SlaveproeessingElement)組成。主處理器采用通用的處理器架構(gòu)，具有較高的主頻和2級(jí)。ache結(jié)構(gòu)(類(lèi)似于PowerPC處理核);每個(gè)從處理單元含有一個(gè)局部存儲(chǔ)、DMA和路由設(shè)備Router，局部存儲(chǔ)用于存放在本處理器上運(yùn)行代碼和數(shù)據(jù)，DMA用于在各個(gè)從處理器的局部存儲(chǔ)器間以及局部存儲(chǔ)器與片外主存之間傳輸數(shù)據(jù)。從處理單元只能訪問(wèn)屬于自己的本地存儲(chǔ)單元，因此任何數(shù)據(jù)必須通過(guò)DMA進(jìn)行顯式的傳輸。……熟舜舜 舜舜舜舜 奧奧奧奧奧 奧奧麟麟 DDDMAAAAADMAAAAADMAAA MMMasteFFFFFInterconneCtionnnnnnnnnnnnnnnnnppp代沁 eSSOrrrrrrrrr.只廿嘩hlppp門(mén) 門(mén) 門(mén) 門(mén)門(mén)門(mén) emoryyy圖2.3目標(biāo)多核處理器結(jié)構(gòu)框圖程序一般采用主從方式執(zhí)行:程序開(kāi)始在主處理器上執(zhí)行，主處理器產(chǎn)生線程，將線程的數(shù)據(jù)和代碼調(diào)度到相應(yīng)的從處理單元的局部存儲(chǔ)中，并觸發(fā)從處理器運(yùn)行，從處理器執(zhí)行相應(yīng)的代碼

一次循環(huán)迭代作為一個(gè)任務(wù)，被分成若干階段，，各個(gè)階段在不同的處理器上執(zhí)行，當(dāng)一個(gè)處理器完成了它負(fù)責(zé)的階段后，結(jié)果就作為輸入傳送到流水線中的下一個(gè)處理器。圖3.2給出了一個(gè)基于多核處理器的軟件流水調(diào)度例子，圖左邊為一個(gè)數(shù)據(jù)依賴(lài)圖，Kl執(zhí)行后利用DMA，將數(shù)據(jù)傳給K2執(zhí)行，圖右邊為對(duì)應(yīng)的流水線的調(diào)度表。計(jì)算任務(wù)被分為3個(gè)階段，第0個(gè)處理器核執(zhí)行任務(wù)的第一個(gè)階段Kl后，開(kāi)始立即啟動(dòng)一個(gè)新任務(wù)，流水線開(kāi)始是空的。在第0個(gè)處理器核完成處理后，結(jié)果用DM人傳輸?shù)降?處理器核
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2010
【分類(lèi)號(hào)】：TP332

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 林進(jìn),張兆慶,祝明發(fā);基于SIMD機(jī)器的優(yōu)化數(shù)據(jù)傳輸?shù)牟⑿醒h(huán)分割[J];計(jì)算機(jī)學(xué)報(bào);1998年07期

2 吳少剛,章隆兵,蔡飛,顧麗紅,唐志敏;機(jī)群Open MP系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J];計(jì)算機(jī)學(xué)報(bào);2004年07期

3 姜偉華,梅超,郭一,朱嘉華,臧斌宇,朱傳琪;一種針對(duì)多媒體擴(kuò)展指令集和實(shí)際多媒體程序的自動(dòng)向量化方法[J];計(jì)算機(jī)學(xué)報(bào);2005年08期

4 張兆慶，喬如良;PORT：并行優(yōu)化重構(gòu)工具集[J];計(jì)算機(jī)學(xué)報(bào);1994年12期

5 陳永健,舒繼武,李建江,王鼎興;OpenMP指導(dǎo)語(yǔ)句全局嵌套類(lèi)型的靜態(tài)分析及應(yīng)用(英文)[J];軟件學(xué)報(bào);2005年02期

6 劉_";范彬;吳承勇;張兆慶;;數(shù)據(jù)流Java并行程序設(shè)計(jì)模型的設(shè)計(jì)、實(shí)現(xiàn)及運(yùn)行時(shí)優(yōu)化[J];軟件學(xué)報(bào);2008年09期

本文編號(hào)：2682451