Research On Task Scheduling Algorithms Based On Fork-Join Task Graphs

Performing parallel computing is an efficient way to improve the performance of computer systems and has become a very attractive computation pattern, which has very extensive applications in the domain of industry, commerce, science, technology and military, etc.-and has many real-life applications. Task scheduling is one of the crucial factors that affect the performance or efficiency of parallel computing. Inappropriate task scheduling schemes will not only make the factually potential computing power of parallel systems unexploited, but also probably reduce the efficiency of parallel systems. Therefore, serving as one of the core problems of parallel systems, the scheduling problem is a hot issue all the time. The scheduling problem of Fork-Join task graphs is a basic problem in the research on scheduling problems of parallel computing and will play a very important role in implementing the compilers of parallel languages and improving the performance of parallel computing. The research on scheduling algorithms based on Fork-Join task graphs will play a critical role in the development and popularization of parallel systems.Aiming at the problem that known scheduling algorithms for Fork-Join task graphs always behave ineffectively in the case of using more processors, the dissertation proposes a greedy scheduling algorithm named TDGS_FJ based on task duplications and the load balance of processors. TDGS_FJ algorithm adopts a greedy strategy in the selection of processors. By analyzing workloads and idle time slots of the used processors, TDGS_FJ algorithm can guarantee the shortest schedule length, meanwhile tries to assign tasks to scheduled processors to balance the loads and minimize the number of processors used. Experimental results show that TDGS_FJ algorithm has better efficiency than classical algorithms such as TDS and TSA_FJ. Additionally the dissertation proposes two algorithms for Join task graphs, named TDGS_J1 and TDGS_J2 respectively, which can produce the shortest schedule length. The experimental results demonstrate that the two proposed algorithms are superior to other compared algorithms in major performance indexes aspects.Aiming at the problem that known scheduling algorithms for Fork-Join task graphs always ignore the communication contention, basing on Fork-Join task graphs in communication contention environments and abandoning the constraint that all communications between processors can be performed concurrently, the dissertation presents a communication contention based scheduling algorithm named CCGS_FJ for scheduling Fork-Join task graphs, which can improve the scheduling performance by serializing the communication edges to integrate the communication awareness into task scheduling. Experimental results show that the proposed algorithm has shorter schedule length and less number of used processors than other compared algorithms, and the more the number of nodes in the task graph is, the more prominence the superiority in the major performances over other compared algorithms is. Therefore, the proposed algorithm may be used in the design of communication-aware scheduling strategies for those situations where the communication requirement is the bottleneck of the performance. Additionally the dissertation proposes two communication contention based algorithms for scheduling Join task graphs, named CCGS_J1 and CCGS_J2 respectively. The analyses indicate their effectivity.Many previous algorithms for scheduling Fork-Join task graphs always assume homogeneous processors and ignore the heterogeneity of processors and the economization on processors in real applications, which leads to low efficiency in practice. Adopting the effective strategies of scheduling algorithms for Fork-Join task graphs in homogeneous systems, the dissertation proposes a heterogeneity based greedy algorithm named HTGS_FJ for scheduling Fork-Join task graphs, which schedules tasks according to the critical task and trys to assign the tasks having the larger amount of the total costs of computation and communication to used faster processors while guaranteeing shorter schedule length and so improves the scheduling performance. Experimental results show that the proposed algorithm has the characteristics of shorter schedule length and less number of used processors, which effectively improves the efficiency of the scheduling algorithm, and so more practicable in heterogeneous systems. The dissertation also proposes two algorithms for scheduling Join task graphs in heterogeneous systems, named HTGS_J1 and HTGS_J2. The analyses demonstrate their effectivity.By applying the techniques of task clustering and task duplication, two efficient algorithms named SCTDS₁ and SCTDS₂ respectively are proposed in this dissertation for scheduling arbitrary task graphs under certain simple and relaxed optimality conditions. SCTDS₁ algorithm adopts the strategy of clustering each join task with the cluster of its favorite immediate predecessor to make the join task start execution at its earliest start time. The clustering scheme of SCTDS₁ algorithm assigns the clusters to corresponding processors, makes each task start execution at its earlieat start time in the clusters where it is scheduled to and so guarantees the shortest schedule length. SCTDS₂ algorithm adopts the clustering strategy that not only selectively merges each join task with other parent tasks besides its favorite immediate predecessor but also selectively merges the ancestor tasks in corresponding clusters of its parent tasks to shorten the communication times and so produces shorter schedule length than other compared algorithms. The optimality conditions of SCTDS₁ algorithm and SCTDS₂ algorithm are simple and easy to be met as compared to other algorithms like TDS and extended TDS, and both the two algorithms have lower time complexity. Experimental results demonstrate that their performances are superior to other compared algorithms. Under simple conditions SCTDS₁ algorithm and SCTDS₂ algorithm can all be applied to Fork-Join task graphs and generate satisfactory results.