GPU中針對(duì)任務(wù)完工時(shí)間最小化問(wèn)題的研究
發(fā)布時(shí)間：2018-10-25 19:49
【摘要】：隨著圖形處理器(GPU)技術(shù)快速發(fā)展,GPU已經(jīng)具有高度的并行性以及靈活的可編程性,這使得GPU在通用計(jì)算和并行處理領(lǐng)域得到了廣泛研究和應(yīng)用。GPU作為一種新的計(jì)算主體,具有深入研究的價(jià)值。 對(duì)于GPU,用戶往往更關(guān)注于所有任務(wù)在GPU資源上總完成時(shí)間。對(duì)于一組任務(wù)集合,在GPU設(shè)備中的完工時(shí)間(Makespan)指的是從任務(wù)開始執(zhí)行到所有任務(wù)執(zhí)行完畢所需要的總時(shí)間。對(duì)于任務(wù)集合如何在GPU內(nèi)部多個(gè)流處理器之間調(diào)度,以最小化完工時(shí)間,以及如何計(jì)算一個(gè)流處理器上任務(wù)完成時(shí)間等問(wèn)題,目前國(guó)內(nèi)外相關(guān)研究工作較少,本文針對(duì)這兩方面問(wèn)題,提出了相應(yīng)的解決方法,對(duì)提高GPU資源利用率具有極其重要的意義。 本文首先根據(jù)GPU結(jié)構(gòu)的主要特點(diǎn),建立了一個(gè)關(guān)于最小化完工時(shí)間的模型,提出了一個(gè)使任務(wù)集在GPU多個(gè)流處理器之間總完工時(shí)間最小的調(diào)度算法,并且從理論上證明了該算法在最壞情況下的結(jié)果不會(huì)超過(guò)最優(yōu)解的2倍。此外,針對(duì)目前比較常見的GPU結(jié)構(gòu),提出了一個(gè)針對(duì)兩個(gè)流處理器下的改進(jìn)算法,并通過(guò)實(shí)驗(yàn)證明了該算法具有更好的效率。另一方面,本文根據(jù)問(wèn)題實(shí)際特點(diǎn),針對(duì)流處理器上任務(wù)由多個(gè)子任務(wù)并行執(zhí)行的特點(diǎn),提出了三種計(jì)算任務(wù)完工時(shí)間的方法。首先提出了一種悲觀計(jì)算方法,該方法可計(jì)算實(shí)際問(wèn)題可能達(dá)到的理論上限；然后,使用二維線性規(guī)劃方法為問(wèn)題建立了方程組,給出了精確計(jì)算結(jié)果；最后結(jié)合前兩種方法建立了一種易處理問(wèn)題的優(yōu)化計(jì)算方法。 在模擬試驗(yàn)環(huán)節(jié),對(duì)本文提出的調(diào)度算法和計(jì)算方法設(shè)計(jì)了對(duì)比試驗(yàn)。實(shí)驗(yàn)結(jié)果顯示,多流處理器調(diào)度算法能夠獲得較好的完工時(shí)間結(jié)果,而雙流處理器環(huán)境下的改進(jìn)算法則比前一個(gè)算法更加優(yōu)秀。在任務(wù)在流處理器上完成時(shí)間計(jì)算上,二維線性規(guī)劃方法的精確度較高,但當(dāng)問(wèn)題達(dá)到一定規(guī)模量后,其計(jì)算所需時(shí)間將會(huì)較大。而易處理計(jì)算問(wèn)題上的優(yōu)化計(jì)算算法則可以兼顧精確度和速度。
[Abstract]:With the rapid development of graphics processor (GPU) technology, GPU has a high degree of parallelism and flexible programmability, which makes GPU widely studied and applied in the field of general computing and parallel processing. GPU is a new computing subject. It has the value of further study. GPU, users tend to focus more on the total completion time of all tasks on GPU resources. For a set of tasks, the completion time (Makespan) in a GPU device is the total time required from the start of the task to the completion of all tasks. At present, there are few researches on how to schedule the task set between multiple stream processors in GPU to minimize the completion time and how to calculate the task completion time on a stream processor. In view of these two problems, this paper puts forward the corresponding solutions, which is of great significance to improve the utilization of GPU resources. In this paper, according to the main characteristics of GPU architecture, a model for minimizing the completion time is established, and a scheduling algorithm is proposed to minimize the total completion time between multiple GPU stream processors. It is proved theoretically that the result of the algorithm in the worst case is not more than 2 times of the optimal solution. In addition, an improved algorithm based on two stream processors is proposed for the current GPU architecture, and the experimental results show that the algorithm is more efficient. On the other hand, according to the practical characteristics of the problem, this paper proposes three methods to calculate the completion time of the task, aiming at the parallel execution of the task by multiple sub-tasks on the stream processor. In this paper, a pessimistic calculation method is proposed, which can calculate the theoretical upper limit of practical problems, and then the equations are established by using two-dimensional linear programming method, and the exact calculation results are given. In the end, an optimization method for solving the problem is established by combining the first two methods. In the simulation experiment, a comparative test is designed for the scheduling algorithm and calculation method proposed in this paper. Experimental results show that the multi-stream processor scheduling algorithm can obtain better completion time results, while the improved algorithm in the dual-stream processor environment is better than the previous one. The precision of two-dimensional linear programming method is high when the task is completed on the stream processor, but when the problem reaches a certain scale, the computing time will be longer. The optimal calculation algorithm on the easy-processing problem can take into account the accuracy and speed.
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP332
本文編號(hào)：2294657
[Abstract]:With the rapid development of graphics processor (GPU) technology, GPU has a high degree of parallelism and flexible programmability, which makes GPU widely studied and applied in the field of general computing and parallel processing. GPU is a new computing subject. It has the value of further study. GPU, users tend to focus more on the total completion time of all tasks on GPU resources. For a set of tasks, the completion time (Makespan) in a GPU device is the total time required from the start of the task to the completion of all tasks. At present, there are few researches on how to schedule the task set between multiple stream processors in GPU to minimize the completion time and how to calculate the task completion time on a stream processor. In view of these two problems, this paper puts forward the corresponding solutions, which is of great significance to improve the utilization of GPU resources. In this paper, according to the main characteristics of GPU architecture, a model for minimizing the completion time is established, and a scheduling algorithm is proposed to minimize the total completion time between multiple GPU stream processors. It is proved theoretically that the result of the algorithm in the worst case is not more than 2 times of the optimal solution. In addition, an improved algorithm based on two stream processors is proposed for the current GPU architecture, and the experimental results show that the algorithm is more efficient. On the other hand, according to the practical characteristics of the problem, this paper proposes three methods to calculate the completion time of the task, aiming at the parallel execution of the task by multiple sub-tasks on the stream processor. In this paper, a pessimistic calculation method is proposed, which can calculate the theoretical upper limit of practical problems, and then the equations are established by using two-dimensional linear programming method, and the exact calculation results are given. In the end, an optimization method for solving the problem is established by combining the first two methods. In the simulation experiment, a comparative test is designed for the scheduling algorithm and calculation method proposed in this paper. Experimental results show that the multi-stream processor scheduling algorithm can obtain better completion time results, while the improved algorithm in the dual-stream processor environment is better than the previous one. The precision of two-dimensional linear programming method is high when the task is completed on the stream processor, but when the problem reaches a certain scale, the computing time will be longer. The optimal calculation algorithm on the easy-processing problem can take into account the accuracy and speed.
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP332
【參考文獻(xiàn)】
相關(guān)期刊論文 前2條
1 吳恩華,柳有權(quán);基于圖形處理器(GPU)的通用計(jì)算[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2004年05期
2 吳恩華;圖形處理器用于通用計(jì)算的技術(shù)、現(xiàn)狀及其挑戰(zhàn)[J];軟件學(xué)報(bào);2004年10期
，本文編號(hào)：2294657
本文鏈接：http://sikaile.net/kejilunwen/jisuanjikexuelunwen/2294657.html
最近更新
教材專著
