GPU中針對任務(wù)完工時間最小化問題的研究.pdf

1、隨著圖形處理器(GPU)技術(shù)快速發(fā)展，GPU已經(jīng)具有高度的并行性以及靈活的可編程性，這使得GPU在通用計算和并行處理領(lǐng)域得到了廣泛研究和應(yīng)用。GPU作為一種新的計算主體，具有深入研究的價值。
　　對于GPU，用戶往往更關(guān)注于所有任務(wù)在GPU資源上總完成時間。對于一組任務(wù)集合，在GPU設(shè)備中的完工時間(Makespan)指的是從任務(wù)開始執(zhí)行到所有任務(wù)執(zhí)行完畢所需要的總時間。對于任務(wù)集合如何在GPU內(nèi)部多個流處理器之間調(diào)度，以最小化完

2、工時間，以及如何計算一個流處理器上任務(wù)完成時間等問題，目前國內(nèi)外相關(guān)研究工作較少，本文針對這兩方面問題，提出了相應(yīng)的解決方法，對提高GPU資源利用率具有極其重要的意義。
　　本文首先根據(jù)GPU結(jié)構(gòu)的主要特點，建立了一個關(guān)于最小化完工時間的模型，提出了一個使任務(wù)集在GPU多個流處理器之間總完工時間最小的調(diào)度算法，并且從理論上證明了該算法在最壞情況下的結(jié)果不會超過最優(yōu)解的2倍。此外，針對目前比較常見的GPU結(jié)構(gòu)，提出了一個針對兩個流處

3、理器下的改進算法，并通過實驗證明了該算法具有更好的效率。另一方面，本文根據(jù)問題實際特點，針對流處理器上任務(wù)由多個子任務(wù)并行執(zhí)行的特點，提出了三種計算任務(wù)完工時間的方法。首先提出了一種悲觀計算方法，該方法可計算實際問題可能達到的理論上限;然后，使用二維線性規(guī)劃方法為問題建立了方程組，給出了精確計算結(jié)果;最后結(jié)合前兩種方法建立了一種易處理問題的優(yōu)化計算方法。
　　在模擬試驗環(huán)節(jié)，對本文提出的調(diào)度算法和計算方法設(shè)計了對比試驗。實驗結(jié)果顯