Accession Number:

ADA614630

Title:

Scheduling Constrained-Deadline Parallel Tasks on Two-type Heterogeneous Multiprocessors

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST

Report Date:

2015-01-13

Pagination or Media Count:

14.0

Abstract:

Consider the problem of scheduling a taskset on a multiprocessor so that all deadlines are met. 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 minimum inter-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. This algorithm has pseudo-polynomial time complexity and speedup factor at most 5. This is the first algorithm for scheduling parallel real-time tasks on a heterogeneous multiprocessor with provably good performance.

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE