ECRTS2011
HomeDiscover PortoProgramKeynote SpeakersRegistrationVenue & HotelsSatellite WorkshopsWork in ProgressCall for PapersPaper SubmissionImportant DatesOrganizers
CISTER - Research Centre in Real-Time Computing Systems
ISEP / IPP
Porto Cidade Ci?ncia
Porto
Funda??o Calouste Gulbenkian
Funda??o para a Ci?ncia e a Tecnologia - MCTES
Critical Software
Metro do PortoTimeout Porto
Santander Totta
Telef - Transportes por Cabo e Concess?es
Taylor's Port

Program

Program
 

Partitioned real-time scheduling on heterogeneous shared-memory multiprocessors

Martin Niemeier1,  Andreas Wiese2,  Sanjoy Baruah3
1EPFL, 2TU-Berlin, 3UNC

Abstract


We consider several real-time scheduling problems on heterogeneous multiprocessor platforms, in which the different processors share a common memory pool. These include (i) scheduling a collection of implicit-deadline sporadic tasks with the objective of meeting all deadlines; and (ii) scheduling a collection of independent jobs with the objective of minimizing the makespan of the schedule. Both these problems are intractable (NP-hard). For each, we derive polynomial-time algorithms for solving them approximately, and show that these algorithms have bounded deviation from optimal behavior. We also consider the problem of determining how much common memory a platform needs in order to be able to accommodate a specified real-time workload.