Hierarchical scheduling and allocation of multirate systems on heterogeneous multiprocessors
Yanbing Li, Wayne H. Wolf · 1997
This paper describes new algorithms for system# level software synthesis# namely the scheduling and al# location of a set of complex tasks running at multiple rates on a heterogeneous multiprocessor. The tasks may have precedenceconstraints within them. The multiprocessor may becomposedofboth programmable and #xed#function processing elements and may have arbitrary interconnect topology. Our hierarchical algo# rithm takes advantage of the hierarchical structureof the system#s task graph to hierarchically allocate and schedule processes on the multiprocessor to meet the hardreal#time constraints on the tasks. Multimedia is an important application of our algorithm. 1 Introduction This paper describes a new# hierarchical algorithm for software synthesis of multi#rate systems on mul# tiprocessors. Starting from a task graph# which de# scribes the process structure of a system whichmust meet periodic deadlines which occur at several di#er# ent rates# our algorithm allocates processes to...