The Research Of Scheduling Algorithm For Fine Granularity Task Set In Heterogeneous System

As the development of heterogeneous multi-core processor, the task schedulingon heterogeneous mulit-core system has become a hot spot. When scheduling finegranularity task sets, The scheduling algorithms adjusting to normal task set’s havemany defects such as unbalanced load, too much idle time, low parallelism andredundant tasks ect. All of the problems infect the performance of multi-core system.The research of this paper is to solve these problems.Firstly, this paper proposed a new algorithm called HCDUL to schedule finegranularity task sets. HCDUL has four phases: cluster phase, priority calculation andready nodes list building phase, task scheduling phase and upper lever nodesduplication phase. Through cluster phase, the expenses of communication becomelower. In the process of scheduling, HCDUL update ready nodes list dynamically andresort the list in real time. When sorting the list, the CP nodes have the highestpriority. Through duplicating the upper level nodes, the expenses of communicationbecome lower further. And thus make the child nodes’ earliest start time smaller. Andthus come to abridge the end time of the whole task set.In order to solve the problem of redundant tasks, we propose another algorithmcalled HDO in this paper. Firstly, HDO looks for redundant tasks and delete them.Secondly, HDO calculate the earliest start time of redundant tasks’ child nodes, andfinally, HDO revise the nodes. Through eliminating redundant tasks, the lastingnodes’ earliest start times are ahead. Eliminating redundant tasks not only save theprocessor’s resource, but also abridge the scheduling length.Randomly generated graphs are used in the experiment. When scheduling finegranularity graphs, compared with HEFT and HCNF algorithms, HCDUL has lowerSLR and higher Speedup. As the same, a lardge number of randomly generated graphsare used in verifying HDO. The results of HCNF and HCDUL optimized by HDOhave smaller SETR.