Font Size: a A A

Hybrid Heuristic Ant Colony Algorithm For Task Scheduling On Heterogeneous CMP

Posted on:2015-06-15Degree:MasterType:Thesis
Country:ChinaCandidate:D H ZhangFull Text:PDF
GTID:2348330518471678Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Heterogeneous multiprocessors integrated with more than one type kernel on a chip, will play different types of core strengths,to accelerate the execution of the program and reduce power consumption. To exploit heterogeneity and parallel capability of heterogeneous CMP,this paper present new dependent task scheduling algorithms which suitable for heterogeneous CMP platform, to improve the efficiency of task scheduling and to improve utilization and throughput of system resource. Effective task scheduling will be an important and realistic hot issues.By analyzing multi-core processors and its task scheduling algorithm, this paper presents a hybrid heuristic ant colony optimization algorithms for task scheduling on heterogeneous CMP,called H2IACOTS. This algorithm presents a two-phase step: The first phase implements a heuristic list-based algorithm, called CPOP,to generate to generate a sub-optional schedule, to inject into the initial distribution of pheromone of the ant colony optimization algorithm. In the second phase, the ant colony optimization algorithm proceed to evolve shorter schedules because of its positive feedback and the convergence efficiency advantages. To further improve the efficiency of the algorithm, this paper introduce mutations characteristic of genetic algorithm to improve the efficiency of local search. This algorithm takes the advantage of both the exploration power of the heuristic list-based and ACO in task scheduling problem,so it can effectively reduce the search space of ACO while not sacrificing the search quality, and introduce mutations characteristic of genetic algorithm to improve the efficiency, to improve the performance of the entire population and reduce the computing time.In order to prove the feasibility and efficiency of the task algorithms on heterogeneous system, experiments using randomly generated set of task graph into three categories with different characteristics and different hardware conditions that the processor core number as the algorithm test input simulation to achieve convergence speed and performance of the algorithm in Matlab platform. Experimental results show that: Compared with existing algorithms, the new algorithm can always find the optimal or suboptimal solutions for dependent tasks scheduling problems in heterogeneous multi-core processor,that the time when the execution of all the tasks were completed was the shortest, and it has good stability and scalability, and at the same time can provide a good reference for related research.
Keywords/Search Tags:Heterogeneous multi-core processor, task scheduling, ant colony algorithm, genetic algorithm
PDF Full Text Request
Related items