Research And Exploration On Priority-Based Just-in-Time Scheduling Algorithms

With the development of Internet-based computing,more resources can be utilized by a scientific workflow application with complex construction,which is commonly represented by Direct Acyclic Graph(DAG,for short).As a result,execution efficiency of such application can be significantly improved.However,this kind of application will face a more complicated and uncertain execution environment at the same time.Such an uncertain environment weakens the performance of static task scheduling algorithms and inspire the development of just-in-time scheduling algorithms.Just-in-time algorithms emphasize maximizing the parallelism of ready tasks in the process of scheduling so that the application can make full use of resources at every moment.Although just-in-time algorithms can fight against uncertainty brought from application execution environments,some of them have the drawback of possibly overlooking global optimization because a decomposition phase and a composition phase to a DAG are included in the procedures of these algorithms.For the situations illustrated above,a priority-based heuristic approaches(PB,for short)and its variants have been proposed.These approaches have characteristics of a smart design,taking an overall view of the whole DAG and being capable of dealing with arbitrary DAGs.They have gotten great results in the past experiments and exhibited obvious advantages over their competitors.As a expansion of previous work,this thesis does some modification and exploration to these algorithms.The main research works from this thesis are concluded as follows:(1)This thesis describes the priority-based level heuristic approach(PBL,for short)as a modification version to PB.With detailed analysis on given cases,this thesis discusses a severe problem that PB will face an affordable time consuming in some extreme situations when producing task scheduling sequence.Then the reasons are explained why a level-based approach is adopted to initialize and update quotients to solve this problem.This thesis makes a powerful demonstration that PBL and its variants can gain a more reasonable time consuming by a deep analysis in complexity and a clear exhibition to the results of time consuming experiments on four kinds of DAGs.(2)This thesis makes a further exploration to PBL and its variants.(Note that PB and PBL have the same scheduling performance.)In the experiments with a simulation application execution environment,the configuration gets more various than previous works.The results of these experiments indicate that PBL algorithm and its variants get a good performance with given DAG cases.At the same time,it is worth mentioning that many analyses on the performance of scheduling algorithm rely on the results from experiments on simulation execution environment.In this thesis,experiments carried out under a parallel runtime scheduling and execution framework(PaRSEC,for short)are introduced to test PBL and other related algorithms in a real application execution environment.The experimental results indicate that PBL and APBL outperform other algorithms in such a real execution environment.Through the work described in this thesis,PBL and its variants make a further improvement on time consuming together with remaining the advantage position of PB and its corresponding variants in the aspect of scheduling performance.