Publication
Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes
| dc.contributor.author | Andersson, Björn | |
| dc.contributor.author | Raravi, Gurulingesh | |
| dc.date.accessioned | 2015-01-15T12:18:35Z | |
| dc.date.available | 2015-01-15T12:18:35Z | |
| dc.date.issued | 2014 | |
| dc.description.abstract | 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. | por |
| dc.identifier.doi | 10.1145/2660495 | |
| dc.identifier.uri | http://hdl.handle.net/10400.22/5414 | |
| dc.language.iso | eng | por |
| dc.peerreviewed | yes | por |
| dc.publisher | ACM | por |
| dc.relation.ispartofseries | ACM Transactions on Embedded Computing Systems (TECS);Vol. 13 Issue 5 | |
| dc.relation.publisherversion | http://dl.acm.org/citation.cfm?doid=2660459.2660495 | por |
| dc.subject | Algorithms | por |
| dc.subject | Performance | por |
| dc.subject | Theory | por |
| dc.subject | Cutting planes | por |
| dc.subject | Heterogeneous multiprocessors | por |
| dc.subject | Linear programming | por |
| dc.subject | Real-time scheduling | por |
| dc.title | Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes | por |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.citation.endPage | 160:25 | por |
| oaire.citation.startPage | 160:1 | por |
| oaire.citation.title | ACM Transactions on Embedded Computing Systems (TECS) - Special Issue on Risk and Trust in Embedded Critical Systems, Special Issue on Real-Time, Embedded and Cyber-Physical Systems, Special Issue on Virtual Prototyping of Parallel and Embedded Systems (ViPES) | por |
| rcaap.rights | closedAccess | por |
| rcaap.type | article | por |