Publication
Task Assignment Algorithms for Heterogeneous Multiprocessors
| dc.contributor.author | Raravi, Gurulingesh | |
| dc.contributor.author | Nélis, Vincent | |
| dc.date.accessioned | 2015-01-14T15:37:34Z | |
| dc.date.available | 2015-01-14T15:37:34Z | |
| dc.date.issued | 2014 | |
| dc.description.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 + α × 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 + α times faster. The parameter α 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. | por |
| dc.identifier.doi | 10.1145/2660494 | |
| dc.identifier.uri | http://hdl.handle.net/10400.22/5406 | |
| dc.language.iso | eng | por |
| dc.peerreviewed | yes | por |
| dc.publisher | ACM | por |
| dc.relation.ispartofseries | ACM Transactions on Embedded Computing Systems (TECS);Article No. 159 | |
| dc.relation.publisherversion | http://dl.acm.org/citation.cfm?id=2660494 | por |
| dc.subject | Heterogeneous multiprocessors | por |
| dc.subject | Real-time scheduling | por |
| dc.title | Task Assignment Algorithms for Heterogeneous Multiprocessors | por |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.citation.title | ACM Transactions on Embedded Computing Systems (TECS) - Special Issue on Virtual Prototyping of Parallel and Embedded Systems (ViPES) | por |
| rcaap.rights | closedAccess | por |
| rcaap.type | article | por |