Theory And Method For Scheduling On Heterogeneous Multicore Systems Considering Communication And Time Constraint

Heterogeneous multicore processors have been widely used in many fields,such as industry,national defense,medical treatment and communication,due to its high performance,flexibility,low cost and low power consumption.It is widely believed that the heterogeneous multicore processor will be the main development trend of future multicore processors.For a large and complex application,in order to improve the performance of computing systems and meet requirements of the application,the application is generally divided into a set of tasks with various features in accordance with certain rules.Consumptions are different for a task executed on different kinds of processing cores.Consumptions for different tasks executed on the same kind of processing cores also vary.For this reason,in order to give full play to the advantages of heterogeneous multicore processors,it is necessary to assign and schedule tasks reasonably.Task assignment is to assign each task to a suitable processing core.In addition to task assignment,task scheduling has to determine the execution order of a task on its processing core.With the proposed demand for “green computing”,issues on cost reduction of resources,energy,budget have obtained concerns and become hot topics in both academia and industry.Efficient task assignment and scheduling algorithms can not only reduce energy and monetary consumed by computing systems,but also degrade the temperature and improve the reliability of computing systems.Most of the existing studies on task assignment and scheduling problems target homogeneous computing systems yet only a few of them target heterogeneous systems.Because of the differences between homogeneous and heterogeneous computing systems,the techniques based on homogeneous computing systems cannot be applied to heterogeneous computing systems efficiently.In the heterogeneous computing environment,periodic real-time tasks and homogeneous communication links are widely discussed.However,the communication and time constraint are not addressed carefully.In real life,many applications demand stringent time performance,such as embedded devices,mobile and communication devices,industrial control,digital multimedia,aerospace,national defense etc.For some applications,if the time requirement cannot be met,it will cause serious consequences.In addition,communication exists and cannot be ignored in many computing systems.Therefore,it is necessary to study the task assignment and scheduling problems on heterogeneous multicore processor systems considering time constraint and communication.This thesis focuses on studying both the task assignment and scheduling problems on heterogeneous multicore systems aiming at minimizing system costs,where the cost is an abstract representation of overheads,such as energy consumption and money mentioned in task assignment and scheduling problems.Assume that the processing cores are sufficient for task assignment study while the processing cores are bounded for task scheduling study.The task assignment and scheduling problems are NP-complete in general case.A given application is firstly modeled as a directed acyclic data flow graph(DADFG),and then the techniques for solving task assignment and scheduling problems under different cases are explored.First of all,this thesis studies the problem of task assignment on heterogeneous multicore systems with considering communication and time constraint(TCTAC).When DADFG for an instance of the TCTAC problem is a simple path and a tree,i.e.,two special cases,two optimal task assignment algorithms are proposed by applying the dynamic programming method.That is,the path assignment algorithm and the tree assignment algorithm.The former is designed to solve the case that DADFG is a simple path while the latter is used to solve the case that DADFG is a tree.Next,for the general case,that is,DADFG for an instance of the TCTAC problem is a directed acyclic graph(DAG),an integer linear programming(ILP)model is formulated to offer optimal solutions and the extended tree assignment algorithm is proposed to obtain near optimal solutions.The time complexity of ILP model grows exponentially with the size of DADFG.When the size of DADFG is large,the ILP model cannot find a solution within acceptable time.The extended tree assignment algorithm is a heuristic,which is proposed to overcome the disadvantage of the ILP model and solve the large-size instances of the task assignment problem efficiently.Then,this thesis studies the problem of task scheduling on heterogeneous multicore systems considering communication under time constraint(TSCT).For the general case,that is,DADFG for an instance of the TSCT problem is a DAG,the ratio and local deadline(RLD)algorithm is proposed to generate near optimal solutions.The RLD algorithm is a heuristic since the general task problem is NP-hard.RLD firstly calculates the priority of each task and identifies its scheduling order.Secondly,according to the given global time constraint,a local time constraint is assigned to each task.Thirdly,each task is scheduled under its local time deadline,and the assignment of the task is determined by a cost-to-time ratio.At last,the relevant parameters are adjusted to obtain more successful scheduling schemes,and the schemes with the minimum cost is selected from all successful scheduling schemes that satisfy the given global time constraint as the final solution.At last,focus on DADFG for an instance of the TSCT problem is a DAG,the improved safe graph grouping(ISGG)algorithm and the ration and local deadline with grouping(RLDG)algorithm are proposed to produce near optimal solutions.The ISGG algorithm serves the RLDG algorithm,divides all tasks of a DADFG into a set of groups with requiring that the number of task in each group is as balanced as possible,and keep the new formed graph consisting of groups directed and acyclic.The purpose of the ISGG algorithm is to reduce the communication overhead and increase flexibility during scheduling.The RLDG algorithm is also a heuristic algorithm,and its main idea is similar to that of the RLD algorithm.The difference is that tasks are scheduled with group as a unit in the RLDG algorithm.Since the RLDG algorithm has an additional grouping step,its time complexity is a little bit higher that of the RLD algorithm.In comparison with the RLD algorithm,the RLDG algorithm can achieve better solutions.The experimental results show that the proposed algorithms in this paper can significantly reduce the total cost which is consumed by the heterogeneous multicore system.