The Research Of A Scheduling Algorithm For Heterogeneous Multiprocessor Multi-frame Periodic Task Based On Ant Colony Algorithm

With advantages of high efficiency and low cost, heterogeneous multiprocessorshave been widely used in embedded systems, multimedia applications and many otherfields. It is becoming a critical problem to assign tasks to fixed number of processingunits efficiently and reasonably so that the total cost of heterogeneous multiprocessorsystems are minimized. With the continuous enhancement of heterogeneity ofheterogeneous processing units and increase of task complexity, task schedulingalgorithms for heterogeneous multiprocessors are facing more severe challenges.Currently, the max processing time of task is adopted generally for classicalperiodic task scheduling in the research of heterogeneous multi-core system whichdon’t consider the multi-frame feature of task model much. This case can make someschedulable tasks to be unschedulable mistakenly. For sloving the problems ofincomplete descricption of periodic tasks in current model and high complexity oftime in existing multi-frame scheduling algorithm, based on classical periodic taskscheduling and associated with the multi-frame feature of tasks, this paper proposed atask scheduling algorithm which uses ant colony and genetic algorithm to improve thereal-time and accuracy of multi-frame periodic tasks in the heterogeneous multi-coresystem. The main work is as follows:As traditional task model might take for some tasks set can’t be partition whichcan partition actually for lack of considering multi-frame features, an accumulativelymonotonic heterogeneous multiprocessor multi-frame periodic task model isestablished. This model has the advantage of partitioning more tasks and reflects theheterogeneity of the processing platform multi-frame features of the tasksconcentratedly. Afterwards, the feasibility of multi-frame task scheduling iselaborated from the perspectives of processor usage and task response time.Combined with heterogeneous multi-core multi-frame periodic task model, anant colony algorithm based scheduling algorithm, the ACGO scheduling algorithm, isdesigned. The algorithm in the traditional ant colony algorithm based on the followingimprovements：reproduction, crossover and mutation are introduced into the antcolony algorithm to enhance the converging rate and global search capability. Toimprove the self-adaptability of the algorithm, pheromone updating strategy ismodified by dynamically adjusting the pheromone residual according to the progressof the algorithm convergence. Additionally, a deterministic search approach is introduced into the algorithm to accelerate the converging rate of the heuristicmethod.In order to verify the performance of the ACGO scheduling algorithm, articledesign and implement a simulation system that based on this simulation to achieveACGO scheduling algorithm and correlation algorithm, carried out a comparativeassessment of the feasibility and run-time at the same time. Experimental results showthat model considering multi-frame in heterogeneous multiprocessor can partitioningmore tasks sets than using a worst-case execution time pessimistically, moregeneralized picture real system tasks. The ACGO algorithm was simple and easy toapplied, achieves reliable result in lower time than tradition ways, have certain value.