A Heuristic Real-Time Parallel Scheduler Based on Task Structures

The development of networksand multi-processor computers has allowed us to solve problems in parallel. The task of efficiently coordinating parallel processors is formidable. This paper presents a heuristic parallel real-time scheduler that analyzes the interactions among the tasks, and builds a parallel schedule that tends to take advantage of those interactions. This work is supported by NSF grant IRI9321324. 1 Introduction The development of networks and multi-processor computers has allowed us to solve problems in parallel. The task of efficiently coordinating parallel processors is formidable. It requires a scheduler to specify which processor to allocate for what problem and when. Existing parallel schedulers can be divided into three categories [1]: graph-theoretic [2] [3], integer 0-1 programming approach [4] and the heuristic approach [5] [6]. Many of these methods use the cost of computation and communications as the schedule objective function, assuming that the duratio..