Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.22/3541
Título: Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors
Autor: Raravi, Gurulingesh
Andersson, Björn
Bletsas, Konstantinos
Palavras-chave: Bin packing
Heterogeneous multiprocessors
Real-time scheduling
Data: 2013
Editora: Springer
Relatório da Série N.º: Real-Time Systems; Vol. 49, Issue 1
Resumo: Consider the problem of partitioned scheduling of an implicit-deadline sporadic task set on heterogeneous multiprocessors to meet all deadlines. Each processor is either of type-1 or type-2. We present a new algorithm, FF-3C, for this problem. FF-3C offers low time-complexity and provably good performance. Specifically, FF-3C offers (i) a time-complexity of O(n⋅max(m,logn)+m⋅logm), where n is the number of tasks and m is the number of processors and (ii) the guarantee that if a task set can be scheduled by an optimal partitioned-scheduling algorithm to meet all deadlines then FF-3C meets all deadlines as well if given processors at most 11−α times as fast (referred to as speed competitive ratio) and tasks are scheduled using EDF; where α is a property of the task set. The parameter α is in the range (0,0.5] and for each task, it holds that its utilization is no greater than α or greater than 1−α on each processor type. Thus, the speed competitive ratio of FF-3C can never exceed 2. We also present several extensions to FF-3C; these offer the same performance guarantee and time-complexity but with improved average-case performance. Via simulations, we compare the performance of our new algorithms and two state-of-the-art algorithms (and variations of the latter). We evaluate algorithms based on (i) running time and (ii) the necessary multiplication factor, i.e., the amount of extra speed of processors that the algorithm needs, for a given task set, so as to succeed, compared to an optimal task assignment algorithm. Overall, we observed that our new algorithms perform significantly better than the state-of-the-art. We also observed that our algorithms perform much better in practice, i.e., the necessary multiplication factor of the algorithms is much smaller than their speed competitive ratio. Finally, we also present a clustered version of the new algorithm.
Descrição: A preliminary version of this paper appeared in Proceedings of the 31st IEEE Real-Time Systems Symposium, 2010, pp. 239–248.
Peer review: yes
URI: http://hdl.handle.net/10400.22/3541
ISSN: 0922-6443
Versão do Editor: http://link.springer.com/article/10.1007%2Fs11241-012-9161-1
Aparece nas colecções:ISEP – CISTER – Artigos

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ART1_Raravi_2013.pdf1,96 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.