Publication
Task assignment algorithms for two-type heterogeneous multiprocessors
| dc.contributor.author | Raravi, Gurulingesh | |
| dc.contributor.author | Andersson, Björn | |
| dc.contributor.author | Nélis, Vincent | |
| dc.contributor.author | Bletsas, Konstantinos | |
| dc.date.accessioned | 2015-01-14T12:23:00Z | |
| dc.date.available | 2015-01-14T12:23:00Z | |
| dc.date.issued | 2014 | |
| dc.description.abstract | Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors—such a platform is referred to as two-type platform. We present two low degree polynomial time-complexity algorithms, SA and SA-P, each providing the following guarantee. For a given two-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then (i) using SA, it is guaranteed to find such an assignment where the same restriction on task migration applies but given a platform in which processors are 1+α/2 times faster and (ii) SA-P succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which processors are 1+α times faster. The parameter 0<α≤1 is a property of the task set; it is the maximum of all the task utilizations that are no greater than 1. We evaluate average-case performance of both the algorithms by generating task sets randomly and measuring how much faster processors the algorithms need (which is upper bounded by 1+α/2 for SA and 1+α for SA-P) in order to output a feasible task assignment (intra-migrative for SA and non-migrative for SA-P). In our evaluations, for the vast majority of task sets, these algorithms require significantly smaller processor speedup than indicated by their theoretical bounds. Finally, we consider a special case where no task utilization in the given task set can exceed one and for this case, we (re-)prove the performance guarantees of SA and SA-P. We show, for both of the algorithms, that changing the adversary from intra-migrative to a more powerful one, namely fully-migrative, in which tasks can migrate between processors of any type, does not deteriorate the performance guarantees. For this special case, we compare the average-case performance of SA-P and a state-of-the-art algorithm by generating task sets randomly. In our evaluations, SA-P outperforms the state-of-the-art by requiring much smaller processor speedup and by running orders of magnitude faster. | por |
| dc.identifier.doi | 10.1007/s11241-013-9191-3 | |
| dc.identifier.issn | 0922-6443 | |
| dc.identifier.issn | 1573-1383 | |
| dc.identifier.uri | http://hdl.handle.net/10400.22/5405 | |
| dc.language.iso | eng | por |
| dc.peerreviewed | yes | por |
| dc.publisher | Springer | por |
| dc.relation.ispartofseries | Real-Time Systems;Vol. 50, Issue 1 | |
| dc.relation.publisherversion | http://link.springer.com/article/10.1007%2Fs11241-013-9191-3 | por |
| dc.subject | Heterogeneous multiprocessors | por |
| dc.subject | Real-time scheduling | por |
| dc.subject | Resource augmentation bound | por |
| dc.title | Task assignment algorithms for two-type heterogeneous multiprocessors | por |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.citation.endPage | 141 | por |
| oaire.citation.startPage | 87 | por |
| oaire.citation.title | Real-Time Systems | por |
| oaire.citation.volume | 50 | por |
| rcaap.rights | openAccess | por |
| rcaap.type | article | por |