Accession Number:

AD1026927

Title:

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

Personal Author(s):

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA PITTSBURGH United States

Report Date:

2015-05-05

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.

Descriptive Note:

Conference Paper

Supplementary Note:

Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS '16, 19 Oct 2016, 21 Oct 2016,

Pages:

0117

Descriptors:

Identifiers:

Subject Categories:

Communities Of Interest:

Modernization Areas:

Distribution Statement:

Approved For Public Release;

Contract Number:

FA8721-05-C-0003

File Size:

2.00MB

View The Document