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

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

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

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