Compile-Time Task Scheduling using a Fuzzy Inference System

H. Li, M. Fisher, and M. Razaz (UK)


Task scheduling, multiprocessor, fuzzy inference system.


It is well known that task scheduling is an NP-complete problem, therefore many heuristics have been developed to find near optimal results under different constraints. Most heuristic scheduling algorithms prioritise tasks based on one heuristic but when scheduling tasks for multiprocessors experimental result show that using one heuristic is not always the best approach. Our research shows that processing gains can be achieved by applying different rules depending on the structure of the directed acyclic graph (DAG). In this paper, we propose a new strategy that uses a fuzzy inference system (FIS), for scheduling tasks from the ready list. The FIS calculates the priority for each ready task using membership functions generated a-priori from a set of training data using an Adaptive Neuro-Fuzzy Inference System (ANFIS). The results of our experiments show that the ANFIS can capture characteristics of specific DAG structures and generate suitable membership functions. The new task scheduling algorithm achieves similar results to those produced by a heuristic scheduling algorithm that has been selected to give optimal performance for a specific DAG.

Important Links:

Go Back