Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Andersson, Björn; Raravi, Gurulingesh

http://hdl.handle.net/10400.22/5414

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
ART13_CISTER_2014.pdf		355.04 KB	Adobe PDF	Download

Send Feedback

Authors

Andersson, Björn

Raravi, Gurulingesh

Abstract(s)

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.