Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.22/5414
Título: Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes
Autor: Andersson, Björn
Raravi, Gurulingesh
Palavras-chave: Algorithms
Performance
Theory
Cutting planes
Heterogeneous multiprocessors
Linear programming
Real-time scheduling
Data: 2014
Editora: ACM
Relatório da Série N.º: ACM Transactions on Embedded Computing Systems (TECS);Vol. 13 Issue 5
Resumo: 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.
Peer review: yes
URI: http://hdl.handle.net/10400.22/5414
DOI: 10.1145/2660495
Versão do Editor: http://dl.acm.org/citation.cfm?doid=2660459.2660495
Aparece nas colecções:ISEP – CISTER – Artigos

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ART13_CISTER_2014.pdf355,04 kBAdobe PDFVer/Abrir    Acesso Restrito. Solicitar cópia ao autor!


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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