HomePublicationsJournal Paper

Task assignment algorithms for heterogeneous multiprocessors
Ref: CISTER-TR-140510       Publication Date: Nov 2014

Abstract:
Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising a constant number (denoted by 't') of distinct types of processors --- such a platform is referred to as a 't-type platform'. We present two algorithms, LPGim and LPGnm, each providing the following guarantee. For a given t-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet their deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then (i) LPGim succeeds in finding such an assignment where the same restriction on task migration applies (intra-migrative) but given a platform in which only one processor of each type is (1 + a*(t-1)/t) times faster and (ii) LPGnm succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which every processor is (1+a) times faster. The parameter 'a' is a property of the task set; it is the maximum of all the task utilizations that are no greater than one. To the best of our knowledge, for t-type heterogeneous multiprocessors, (i) for the problem of intra-migrative task assignment, no previous algorithm exists with a proven bound and hence, our algorithm, LPGim, is the first of its kind and (ii) for the problem of non-migrative task assignment, our algorithm, LPGnm, has superior performance compared to state-of-the-art.

Gurulingesh Raravi

,

Vincent Nélis

Document:

View
PDF Download
PDF