Scheduling Constrained-Deadline Parallel Tasks on Two-type Heterogeneous Multiprocessors
Abstract
Consider the problem of scheduling a taskset on a multiprocessor to meet all deadlines. Assume (i) constrained deadline sporadic tasks, i.e., a task generates a sequence of jobs and the deadline of a job is no greater than the minim minter-arrival time of the task that generates the job, (ii) stage parallelism, i.e., a task comprises one or more stages with a stage comprising one or many segments so that segments in the same stage are allowed to execute in parallel and a segment is allowed to execute only if all segments of the previous stage have finished, (iii) two-type heterogeneous multiprocessor platform, i.e., there are processors of two types, type-1 and type-2, and for each task, there is a specification of its execution speed on a type-1 processor and on a type-2 processor, and (iv) intratype migration, i.e., a job can migrate between processors of the same type but for a task, all jobs of this task must execute on the same processor type. We present an algorithm for this problem; it assigns each task to a processor type and then schedules tasks on processors of each type with global-Earliest-Deadline-First. It has pseudo-polynomial time complexity and in our evaluation with randomly-generated task sets with systems up to 256 tasks and 256 processors, the algorithm never took more than 2.5 seconds to finish. We show that the speedup factor of the algorithm is most 5. This is the first algorithm for scheduling parallel real-time tasks on a heterogeneous multiprocessor with provably good performance.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 05, 2015
- Accession Number
- AD1026927
Entities
People
- Bjoern Andersson
- Gurulingesh Raravi
Organizations
- Carnegie Mellon University