Repository logo
 
Loading...
Thumbnail Image
Publication

Assigning real-time tasks on heterogeneous multiprocessors with two types of processors

Use this identifier to reference this record.
Name:Description:Size:Format: 
REL_Bjorn Andersson_2009_CISTER.pdf212.43 KBAdobe PDF Download

Advisor(s)

Abstract(s)

Consider the problem of scheduling a set of implicitdeadline sporadic tasks on a heterogeneous multiprocessor so as to meet all deadlines. Tasks cannot migrate and the platform is restricted in that each processor is either of type-1 or type-2 (with each task characterized by a different speed of execution upon each type of processor). We present an algorithm for this problem with a timecomplexity of O(n·m), where n is the number of tasks and m is the number of processors. It offers the guarantee that if a task set can be scheduled by any non-migrative algorithm to meet deadlines then our algorithm meets deadlines as well if given processors twice as fast. Although this result is proven for only a restricted heterogeneous multiprocessor, we consider it significant for being the first realtime scheduling algorithm to use a low-complexity binpacking approach to schedule tasks on a heterogeneous multiprocessor with provably good performance.

Description

Keywords

Citation

Research Projects

Organizational Units

Journal Issue

Publisher

IPP-Hurray Group

CC License