The Research On The Periodic Mutiframes Tasks Among Heterogeneous Multiprocessors Partitioning Algorithms

The problem of tasks scheduling is one of the basic research in computer science.With the appearance of multiprocessor systems, a new change was proposed in the traditional computer tasks scheduling. The partitioning issue is considered firstly in multiprocessor systems, which determines how to partition a set of given tasks to a collection of processes, making sure every task is executed and balancing the busyness among processes. This problem is more complicated in the situation of heterogeneous multiprocessor systems, because of taking account of difference process capability among processors, so that every process can do its best according to its abilities and every task can take what its need.Currently, though there are plenty of research about the heterogeneous multiprocessor tasks partitioning based on classical periodic tasks model, few study takes notice of the multi-frame character of tasks, which results in analyzing with a single worst-case execution time, pessimistically taking for some tasks set can't be partition which can partition actually.From the classic periodic tasks, based on the study of current heterogeneous multiprocessor tasks partitioning popular algorithms, this paper took the multi-frame character into heterogeneous multiprocessor system, built a new task model: heterogeneous multiprocessor multi-frame periodic real-time tasks model. The model is more generalized than previous models, reflecting the system capability of heterogeneous multiprocessor and the multi-frame character of tasks effectively. In virtue of describing in non-linear programming, the advantage of new model was proved in theoretic. A simulation experiment applied in genetic algorithms was given as well.Firstly, for the heterogeneous multiprocessor multi-frame tasks with AM (Accmulatively Monotonic) property, theoretical analysis showed new tasks model's advantage: partitioning more tasks sets than the pessimistic way. And design a genetic algorithm to slove. To verify theoretical conclusion and the performance of algorithm and for the problem of no uniform platform in heterogeneous multiprocessor tasks partitioning study, an easily extended heterogeneous multiprocessor tasks partitioning evaluating system was implemented. Two methods in this paper: genetic algorithm and Matlab two-steps way were applied in the system for etc. Simulation experiment about AM heterogeneous multiprocessor multi-frame tasks was tested on the evaluating system.Based on the AM heterogeneous multiprocessor multi-frame tasks, to enlarge the range of new model, the general heterogeneous multiprocessor real-time tasks model was discussed. Similar theoretical analysis and genetic algorithm design was given as well.The usability and universality was confirmed through simulation experiment.Both theoretic and experiment showed the model considering multi-frame in heterogeneous multiprocessor can partitioning more tasks sets than using a worst-case execution time pessimistically, more generalized picture real system tasks. The genetic algorithm was simple and easy to applied, achieves reliable results in lower time than traditional ways, can be widely used.