Name: | Description: | Size: | Format: | |
---|---|---|---|---|
346.92 KB | Adobe PDF |
Advisor(s)
Abstract(s)
Consider the problem of assigning real-time tasks on a heterogeneous multiprocessor platform comprising two different
types of processors — such a platform is referred to as two-type platform. We present two linearithmic timecomplexity
algorithms, SA and SA-P, each providing the follow- ing guarantee. For a given two-type platform and a
given task set, if there exists a feasible task-to-processor-type assignment such that tasks can be scheduled to meet
deadlines by allowing them to migrate only between processors of the same type, then (i) using SA, it is guaranteed to
find such a feasible task-to- processor-type assignment where the same restriction on task migration applies but given a
platform in which processors are 1+α/2 times faster and (ii) SA-P succeeds in finding 2 a feasible task-to-processor
assignment where tasks are not allowed to migrate between processors but given a platform in which processors are
1+α/times faster, where 0<α≤1. The parameter α is a property of the task set — it is the maximum utilization of
any task which is less than or equal to 1.
Description
Keywords
Citation
Publisher
IEEE