Research On Task Scheduling For Universal Heterogeneous Computing Platform

With the advancement of Computer and Internet Science,all trades and professions have turned to "Internet +" and digitalization,which has led to a sharp increase in the number of digital users and the volume of data.Therefore,big data computing is facing brand-new demands and challenges.Traditional computing systems and platforms based on a single type of computing resources are incapable of meeting the increasingly complex and everchanging application requirements.In this context,a universal heterogeneous computing platform appeared on demand.It is widely used in scientific computing,deep learning,signal processing,cloud computing,etc.,and has achieved remarkable effects.The large-scale computing resources of it provide the foundation for the mass data computing.And the diversified types of computing resources enable different tasks to be delivered to that are good at.It is very important for the universal heterogeneous computing platform to make good use of its resources to perform computing tasks,in order to obtain the best performance and meet the needs of users.And this is the significance of task scheduling research.Some studies on task scheduling for the universal heterogeneous computing platform are carried out in this thesis.We mainly focus on improving the most important performance metrics in scheduling,called scheduling length.From the perspectives of the ideal static environment and the actual runtime environment of the universal heterogeneous platform,the research is carried out by establishing models,defining problems,conducting theoretical analyses and experimental simulations.The main work of this thesis is summarized as follows:Oriented to an ideal static scheduling environment for universal heterogeneous computing platforms,a heuristic task scheduling algorithm that is sensitive to communication overhead is proposed,named Communication-Sensitive EFT(CSEFT)algorithm.Specifically,we follow the table heuristic task scheduling process and define a new scheduling priority.The idea of offsetting the greater communication overhead at the cost of a certain amount of redundant calculation overhead is adopted,and some tasks are duplicated or bound to obtain better performance.Some simulation experiments are carried out,and the CSEFT algorithm is compared with several traditional task scheduling algorithms in terms of scheduling length,scheduling length ratio,and speedup ratio,etc.The results show that the CSEFT algorithm is superior to them in these performances.Facing the dynamic runtime environment in universal heterogeneous computing platforms,an online scheduling algorithm is proposed in this thesis,named Advance Selective Rescheduling(ASR)algorithm,which partly alleviates the problem that the uncertainty in the runtime environment leads to the degradation of the scheduling length performance.Based on the information of prediction and real-time judgment,the ASR algorithm determines whether it is necessary to reschedule the remaining tasks in order to ensure the scheduling length performance.Then,based on the ASR algorithm,a two-stage scheduling scheme combining online and offline is proposed in this thesis,as a supplement to further improve the scheduling length performance.Simulation experiments are carried out on the proposed algorithm and scheme,while describing the uncertainty in the runtime environment.From the results,it can be seen that the ASR algorithm and the "offline + online" two-stage scheduling scheme perform well in the runtime environment.