Improved static multiprocessor scheduling using cyclic task graphs: A genetic approach

Genetic algorithms have successfully been applied to multiprocessor task graph scheduling. In these previous attempts the schedules are constructed from directed acyclic task graphs. However, recurrent applications such as real-time control and digital signal processing can be expressed as directed cyclic task graphs. This paper presents a method for transforming a cyclic task graph into several alternate acyclic task graphs, The benefits of this are demonstrated through an example where the task graphs become easier to schedule through restructuring. Thus, the new task graphs result in better load balancing and less inter-processor traffic than the acyclic task graphs traditionally used. A genetic algorithm has been used to search for the task graph and schedule that best fit a particular application and hardware configuration. The results are encouraging.