Research On Task Scheduling For Heterogeneous Multi-core Processors

Multi-core processors have become the mainstream since they have betterperformance per watt and larger computational capacity than complex single-coreprocessors. Multi-core processors is divided into homogeneous multi-core andheterogeneous multi-core according to the difference among the system’s corestructure. Since an heterogeneous multi-core processor consists of a mix of fast coresand slow cores, it can better cater for applications with a heterogeneous mix ofworkload. For example, fast, complex cores can be used to execute the serial codesections, while slow, simple cores can be used to crunch numbers in parallel, which ismore power-efficient. The researchers generally believe that the heterogeneousmulti-core processors will become the mainstream, at the same time, heterogeneousmulti-core processor system provides a broad space for the development of taskscheduling and load balancing research.In this paper, we improve the existing task scheduling method and model andpresent a workload-balanced heuristic task scheduling algorithm on heterogeneousmulti-core processors. In order to fully consider load balancing between cores, weimprove our proposed algorithm. The main work of this paper is as follows:(1) we analyze the existing task scheduling method and model, and improve thescheduling model and method. We present a workload-balanced heuristic taskscheduling algorithm, which considers the heterogeneous environment and logicalrelations between tasks. First of all, the algorithm delaminates a task graph withprecedence relations according to in-degree value of tasks, and then allocates thesetasks to corresponding cores. After delamination, tasks of the same layer in thedirected acyclic graph (DAG) have no data dependence and control dependence, andcan be executed in parallel by the corresponding cores. As the cores have differentcomputational capacity, the algorithm gives full consideration of the differencebetween cores. The results show that the load balancing and scheduling length in ourproposed algorithm is superior to the existing task scheduling algorithms, whichimprove the performance of applications on heterogeneous multi-core processors.(2) We analyze the influence factors of load balancing. We find that our proposedalgorithm though can avoid the error accumulation phenomenon, which does notreduce the error of a single nuclear. According to this proble m and considering the influence factors of load balancing we improve our proposed algorithm. The methodis that when the total execution costs of a core are just less than or equal to thereference values of the core we can continue to allocate a task to t he core startingfrom the smallest task in task group scheduling processes. This method can reduce theerror of a single nuclear. In order to further improve the calculation accuracy wedesign an error drop scheduling scheme. The scheme can select cores of big error andcombine tasks which are allocated to the selected cores, and then allocate thecombined tasks to the selected cores again, which can minimize the error of a singlenuclear.