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

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

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

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