Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.22/5405
Título: Task assignment algorithms for two-type heterogeneous multiprocessors
Autor: Raravi, Gurulingesh
Andersson, Björn
Nélis, Vincent
Bletsas, Konstantinos
Palavras-chave: Heterogeneous multiprocessors
Real-time scheduling
Resource augmentation bound
Data: 2014
Editora: Springer
Relatório da Série N.º: Real-Time Systems;Vol. 50, Issue 1
Resumo: 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.
Peer review: yes
URI: http://hdl.handle.net/10400.22/5405
DOI: 10.1007/s11241-013-9191-3
ISSN: 0922-6443
1573-1383
Versão do Editor: http://link.springer.com/article/10.1007%2Fs11241-013-9191-3
Aparece nas colecções:ISEP – CISTER – Artigos

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ART5_CISTER_2014.pdf1,39 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.