REJOIN
REal-time scheduling on multicore processors: addressing two open problems JOINtly
| 1 year (Jun 2010 to May 2011) | |
| Summary: | The objectives of this project is to study the following two problems: P1. Multiprocessor Global Feasibility Analysis - Arbitrary-Deadline Tasks; P2. Resource sharing on Multiprocessor Systems. The main challenge with respect to P1 is that optimal scheduling for the problem P1 requires knowledge of future job arrivals. It has recently been shown [1] that no optimal solution exist for problem P1 even for the slightly more restricted model of sporadic tasks. Creating non-optimal algorithms is worthwhile though. Problem P2 is non-trivial because normal uniprocessor solutions, Priority-Inheritance Protocol (PIP) and Priority Ceiling Protocol (PCP, perform poorly. The former (PIP) allows a large degree of parallel execution but there are many situations when a lower priority task inherits a much higher priority and this can happen multiple times and this cause delays to a medium priority task. The latter (PCP) severely limits parallel execution. Because of the poor performance PIP and PCP, new solutions to P2 must be devised. References [1] N. Fisher, J. Goossens, and S. Baruah. Optimal Online Multiprocessor Scheduling of Sporadic Real-Time Tasks is Impossible. Real-Time Systems 45(1), pp 26-71. 2010. |
| Funding: | Global: 7KEUR, CISTER: 7KEUR |
| Sponsors: |  |
| Partners: | |
| Contact Person at CISTER: | Björn Andersson |
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Journal Papers
Provably good task assignment on heterogeneous multiprocessor platforms for a restricted case but with a stronger adversary HURRAY-TR-110901
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas23rd Euromicro Conference on Real-Time Systems (ECRTS11), ACM SIGBED Review. 6 to 8, Jul, 2011, Volume 8, Issue 3, pp 19-22. Porto, Portugal.Work-In-Progress Session
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas23rd Euromicro Conference on Real-Time Systems (ECRTS11), ACM SIGBED Review. 6 to 8, Jul, 2011, Volume 8, Issue 3, pp 19-22. Porto, Portugal.Work-In-Progress Session
PDFPreemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound HURRAY-TR-110105
Konstantinos Bletsas, Björn AnderssonReal-Time Systems, Springer US. Jul 2011, Volume 47, Issue 4, pp 319-355.
Konstantinos Bletsas, Björn AnderssonReal-Time Systems, Springer US. Jul 2011, Volume 47, Issue 4, pp 319-355.
A preliminary idea for an 8-competitive, log2 DMAX + log2 log2 (1/U) asymptotic-space, interface generation algorithm for two-level hierarchical scheduling of constrained-deadline sporadic tasks on a uniprocessor HURRAY-TR-110201
Björn AnderssonSIGBED Review, ACM. Mar 2011, Volume 8, Issue 1, pp 22-29. New York, NY, U.S.A..
Björn AnderssonSIGBED Review, ACM. Mar 2011, Volume 8, Issue 1, pp 22-29. New York, NY, U.S.A..
Provably Good Multiprocessor Scheduling with Resource Sharing HURRAY-TR-100901
Björn Andersson, Arvind EaswaranReal-Time Systems Journal, Springer US. Oct 2010, Volume 64, Issue 2, pp 153-156.
Björn Andersson, Arvind EaswaranReal-Time Systems Journal, Springer US. Oct 2010, Volume 64, Issue 2, pp 153-156.
Conference or Workshop Papers/Talks
Provably Good Scheduling of Sporadic Tasks with Resource Sharing on a Two-type Heterogeneous Multiprocessor Platform (Corrected version) HURRAY-TR-110904
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas15th International Conference On Principles Of Distributed Systems (OPODIS'11), Springer Berlin Heidelberg. 12 to 16, Dec, 2011, 7109, pp 528-543. Toulouse, France.
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas15th International Conference On Principles Of Distributed Systems (OPODIS'11), Springer Berlin Heidelberg. 12 to 16, Dec, 2011, 7109, pp 528-543. Toulouse, France.
Global-EDF Scheduling of Multimode Real-Time Systems Considering Mode Independent Tasks HURRAY-TR-110703
Vincent Nélis, José Marinho, Björn Andersson, Stefan M. Petters23rd Euromicro Conference on Real-Time Systems (ECRTS '11), IEEE. 6 to 8, Jul, 2011, pp 205-214. Porto, Portugal.
Vincent Nélis, José Marinho, Björn Andersson, Stefan M. Petters23rd Euromicro Conference on Real-Time Systems (ECRTS '11), IEEE. 6 to 8, Jul, 2011, pp 205-214. Porto, Portugal.
A conjecture about provably good task assignment on heterogeneous multiprocessor platforms but with a stronger adversary HURRAY-TR-110502
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas23rd Euromicro Conference on Real-Time Systems (ECRTS'11). 6 to 8, Jul, 2011, Work-In-Progress Session. Porto, Portugal.
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas23rd Euromicro Conference on Real-Time Systems (ECRTS'11). 6 to 8, Jul, 2011, Work-In-Progress Session. Porto, Portugal.
Two-type Heterogeneous Multiprocessor Scheduling: Is there a Phase Transition? (Extended Abstract) HURRAY-TR-110503
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas2nd International Real-Time Scheduling Open Problems Seminar (RTSOPS 2011). 5, Jul, 2011. Porto, Portugal.
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas2nd International Real-Time Scheduling Open Problems Seminar (RTSOPS 2011). 5, Jul, 2011. Porto, Portugal.
Intra-Type Migrative Scheduling of Implicit-Deadline Sporadic Tasks on Two-Type Heterogeneous Multiprocessor HURRAY-TR-110402
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011). 19 to 23, Jun, 2011. Nymburk, Czechia.
Gurulingesh Raravi, Björn Andersson, Konstantinos Bletsas10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011). 19 to 23, Jun, 2011. Nymburk, Czechia.
Maximizing Contention-Free Executions in Multiprocessor Scheduling HURRAY-TR-110401
Jinkyu Lee, Arvind Easwaran, Insik Shin17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2011). 11 to 14, Apr, 2011, pp 235-244. Chicago, U.S.A..
Jinkyu Lee, Arvind Easwaran, Insik Shin17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2011). 11 to 14, Apr, 2011, pp 235-244. Chicago, U.S.A..
A preliminary idea for an 8-competitive, log2 DMAX + log2 log2 (1/U) asymptotic-space, interface generation algorithm for two-level hierarchical scheduling of constrained-deadline sporadic tasks on a uniprocessor HURRAY-TR-101005
Björn Andersson3rd Workshop on Compositional Theory and Technology for Real-Time Embedded Systems, ACM New York. 30, Nov, 2010, 8, pp 22-29. San Diego, U.S.A..
Björn Andersson3rd Workshop on Compositional Theory and Technology for Real-Time Embedded Systems, ACM New York. 30, Nov, 2010, 8, pp 22-29. San Diego, U.S.A..
Assigning Real-Time Tasks on Heterogeneous Multiprocessors with Two Unrelated Types of Processors HURRAY-TR-100505
Björn Andersson, Gurulingesh Raravi, Konstantinos Bletsas31st IEEE Real-Time Systems Symposium (RTSS 2010), Springer US. 30, Nov to 3, Dec, 2010, 49, pp 29-72. San Diego, U.S.A..
Björn Andersson, Gurulingesh Raravi, Konstantinos Bletsas31st IEEE Real-Time Systems Symposium (RTSS 2010), Springer US. 30, Nov to 3, Dec, 2010, 49, pp 29-72. San Diego, U.S.A..
LLF Schedulability Analysis on Multiprocessor Platforms HURRAY-TR-100902
Jinkyu Lee, Arvind Easwaran, Insik Shin31st IEEE Real-Time Systems Symposium (RTSS 2010), IEEE. 30, Nov to 3, Dec, 2010, pp 25-36. San Diego, U.S.A..
Jinkyu Lee, Arvind Easwaran, Insik Shin31st IEEE Real-Time Systems Symposium (RTSS 2010), IEEE. 30, Nov to 3, Dec, 2010, pp 25-36. San Diego, U.S.A..
Online Robust Optimization Framework for QoS Guarantees in Distributed Soft Real-Time Systems HURRAY-TR-100903
Jinkyu Lee, Insik Shin, Arvind EaswaranACM and IEEE International Conference on Embedded Software (EMSOFT 2010), ACM New York. 24 to 29, Oct, 2010, pp 89-98. Scottsdale, U.S.A..Part of ESWEEK 2010.
Jinkyu Lee, Insik Shin, Arvind EaswaranACM and IEEE International Conference on Embedded Software (EMSOFT 2010), ACM New York. 24 to 29, Oct, 2010, pp 89-98. Scottsdale, U.S.A..Part of ESWEEK 2010.
Conjecture about global fixed-priority preemptive multiprocessor scheduling of implicit-deadline sporadic tasks: The utilization bound of SM-US(sqrt(2)-1) is sqrt(2)-1 HURRAY-TR-100512
Björn Andersson1st International Real-Time Scheduling Open Problems Seminar (RTSOPS 2010). 6, Jul, 2010. Brussels, Belgium.In conjunction with the 22th Euromicro Intl Conference on Real-Time Systems
Björn Andersson1st International Real-Time Scheduling Open Problems Seminar (RTSOPS 2010). 6, Jul, 2010. Brussels, Belgium.In conjunction with the 22th Euromicro Intl Conference on Real-Time Systems
A preliminary idea for an 8-competitive, log2 DMAX + log2 log2 (1/U) asymptotic-space, interface generation algorithm for two-level hierarchical scheduling of constrained-deadline sporadic tasks on a uniprocessor HURRAY-TR-091203
Björn AnderssonWorkshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2009). 1, Dec, 2009. Washington, D.C., U.S.A..
Björn AnderssonWorkshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2009). 1, Dec, 2009. Washington, D.C., U.S.A..