Research On Key Techniques Of Task Scheduling Based On Multi-core Distributed Environment

Along with the development of multi-core technology, the number of processing cores inthe processor has been increasing rapidly. In order to take full advantage of the huge amountof parallel computing resources, a highly efficient task scheduling mechanism is needed. Thispaper focuses on the research on key techniques of task scheduling based on multi-coredistributed environment, which has helped get to the shortest total execution time of theparallel tasks through reasonable scheduling tasks to each processing core.Firstly, this paper elaborated on the structural characteristics of multi-core processorsfrom the development of multi-core processor structure and classification, and further studiedthe research status and problems of task scheduling that we’ve been facing under thedistributed environment. And then for static task scheduling, this paper proposed one taskscheduling algorithm for multi-core processors, and the other algorithm for multi-coreclusters; for dynamic task scheduling, this paper designed a dynamic load balancing modelbased on multi-core processors, and proposed a independent tasks scheduling algorithm ontree-based computing environments for heterogeneous multi-core clusters.The main research work of this paper can be summarized as follows:(1) This paper studied the problems of multi-task static scheduling based on theenvironment of a multi-core processor.With the rapid growth of the quantity of processing cores in one processor, how toefficiently use these processing cores to get a minimum task execution time becomes the goalof task scheduling based on multi-core processors. In order to achieve this goal, the author hasbeen studying in two different aspects: How to reduce the communication cost among taskswhich were allocated to different processing cores; how to allocate tasks to improve theutilization of processing cores. This paper built a scheduling model based on the DAG, andthen proposed a task scheduling algorithm which combined task clustering with taskduplication technology. The algorithm includes three steps: firstly, changing task Graph fromDAG to in-tree graph; secondly according to in-tree graph, generating scheduling group or set;lastly adjusting scheduling set according to the number of processing cores. With taskreplication and clustering technology, the algorithm has reduced communication overheadamong tasks. Meanwhile the task completion time is kept a relatively lower value by using theload threshold, the load among cores is balanced and the utilization of processing cores isimproved. The time complexity of the algorithm is no more than several classical algorithms. Compared to genetic algorithm simulation experiment data shows that the proposed algorithmcan obtain near-optimal solutions in a relatively shorter time, and with the increasement ofcommunication overhead among tasks, the proposed algorithm shows a better performance.(2) This paper studied the task scheduling problem for multi-core clusters.With the architecture of high-performance general microprocessor into the multi-core era,multi-core processors have been increasingly used in cluster systems. Due to the introductionof multi-core processors, multi-core clusters include a two-level storage mechanism andthree-layer communication structure, which made the task scheduling problem for multi-coreclusters more complicated. In order to efficiently carry out the task allocation in a multi-corecluster, firstly, we built a task allocation model based on DAG, and then based on thetwo-level storage structure of multi-core clusters, this paper proposed a two-round taskscheduling algorithm, which scheduled tasks by level. According to the algorithm, theprocesses are assigned to processor nodes in the first round and the threads of processes areassigned to processing cores in the second round respectively. Towards three-layercommunication structure of multi-core clusters, in order to reduce the communicationoverhead, and achieve the earliest start time of current task, each round operation includestwo strategies: clustering strategy and adjust strategy. By reducing the inter-taskcommunication overhead， The algorithm minimizes the task scheduling length; Thealgorithm maintains load balancing between the two-level processing nodes by the loadthreshold, which improves the utilization of the processing core. Through comparison withrelated work, we can see that the time complexity of the algorithm is not more than similaralgorithms; three sets of comparative experiments show that the normalized schedule lengthof the proposed algorithm is less than the other two classic algorithms, and withCCR(communication to computation ratio) value being increased in DAG, the superiority ofthe proposed algorithm is prominent.(3) This paper studied the five elements that affect the dynamic load balancing ofmulti-core processors.Because dynamic load balancing algorithm can adapt to changes of nod loads, it is muchmore flexible and effective than static algorithm. However, dynamic algorithm will generatemore overhead than the static algorithm due to needs of collecting and analyzing stateinformation, but usually the cost is worthwhile. Based on the research on the problems of loadbalancing and scheduling for multiprocessors, according to the characteristics of CMP, wecarried out a detailed analysis of the various factors that affect the load balancing ofmulti-core processor. According to the above research, this paper proposes a formaldescription of a general model: utilizing a quintuple <the load balancing environment, taskattribute, load evaluation, scheduling strategy, evaluation criterion of dynamic loadbalancing> to express load balancing scheduling problem based on CMP. The modelcompletely expresses various elements of dynamic load balancing. The model provides comprehensive theoretical study guidance for research on dynamic load balancing onmulti-core processor.(4) This paper studied the independent task dynamic scheduling problem forheterogeneous multi-core clusters.The task scheduling mechanism based on homogeneous multi-core processor assignstasks to each processing core due to the number of tasks, but the task scheduling mechanismbased on heterogeneous multi-core assigned tasks to the processing cores which areappropriate for running the tasks according to the different properties of the task. The taskscheduling mechanism based on homogeneous multi-core processor assigns tasks to eachprocessing core due to the number of tasks, but the task scheduling mechanism based onheterogeneous multi-core assigned tasks to the processing cores which are appropriate forrunning the tasks according to the different properties of the task. Because processing core isheterogeneous, it increases the difficulty of the task scheduling. In this paper tree-basedmaster-slave model is applied to heterogeneous multi-core cluster, and each computing nodecorresponds to a processing core. This paper has researched and analyzed the classicindependent task scheduling problems and the master-slave tree-based computingenvironment, which built a pre-processing mechanism, through that we can gain the optimalnumber of tasks assigned to each core, real-time network communication ability among thecores and Real-time calculation ability of each processing core with load. Throughcomprehensive analyzing communication ability and calculation ability, we can obtainquantitative limit coefficient, which is used to evaluate the performance of the pros and consfor the target processing core. The paper proposed two heuristic algorithms based on theoptimal task scheduling scheme: a prior-limit-coefficient heuristic algorithm and aprior-bandwidth heuristic algorithm. Using the SimGrid platforms, this paper constructed andimplemented these two algorithms, and the experimental results show that the proposed twoalgorithms are better than Min-Min algorithm, and with the increasing number of tasks, theproposed algorithm shows more performance advantage than Min-Min algorithm.