Research Of Minimization Problem For The Makespan Of Task In GPU

With the rapid development of graphics processor unit (GPU) technology, the GPU has a high degree of parallelism and flexible programmability, which makes the GPU has been extensively studied and applied in the field of general purpose computing and parallel processing. GPU has become a new important calculation,many problems on the GPU need further study.For GPU, users tend to focus on the time when all the tasks on the GPU resources complete. For a set of tasks, its Makespan is the the total time needed for tasks are scheduled in the stream processors inside the device. How to get the scheduling in the GPU resources which can obtain the shortest completion time, and calculate the task completion time on the stream processors will greatly affect the utlization of GPU resources. Currently,the related researchs are few.Firstly, according to the main features of the GPU architecture, we establish the Makespan optimization scheduling model. Then we proposed a multi-stream processor algorithms, and prove that the algorithm in the worst case does not exceed2times of the optimal solution. In addition, a improved algorithm the structure was given for the dual-stream processor structure whose experiments show that the algorithm has better efficiency. The other hand, the task processes on a single GPU stream processors, which itself is in parallel by multiple smaller-grained sub-tasks to complete. In accordance with the actual characteristics of the problem, we establish put forward a calculation method which give pessimistic results of a task in the stream processor, this method can be used as the theoretical upper limit of the actual problem, then we use the two-dimensional line planning problem equations, gives the accurate calculation results. Finally, we raise a method having common advantages of two methods to deal with the easy calculation problem.In the simulation, we designed contrast tests for scheduling and results of the calculation. The experimental results show that multi-stream processor scheduling algorithm obtain good results, while in the dual-stream processor environment, the improved algorithm is more excellent than the previous algorithm. Two-dimensional linear programming method has high accuracy, but the computing time will be large when the scale of the problem reaches a certain amount. The third method got both the accuracy and the speedness.