REHEAT
Real-time scheduling on heterogeneous multicore architectures
| FCOMP-01-0124-FEDER-010045 PTDC/EIA-CCO/105716/2008 3 years (Feb 2010 to Jan 2013) http://www.cister.isep.ipp.pt/activities/REHEAT | |
| Summary: | Parallel processing platforms are spreading at an unprecedented rate. Traditionally, parallel processing platforms were used to reduce the execution time of a large computational job such as predicting the weather but now they are also used in low-end systems and embedded real-time systems thanks to the availability of multicore processors. And those systems are often comprised of a large number of independent tasks. Designers are well-aware that processing units specialized for a specific function can offer a significant performance boost. For example, the rendering of a scene in computer graphics can be done much faster with a graphics processor than with a general purpose processor. Network processors, digital signal processors, SIMD arrays, etc. offer similar advantages. Consequently, heterogeneous multicores now enjoy a period of widespread use. Virtually all major semiconductor companies are offering or have declared plans to offer heterogeneous multicores; see IBM Cell or upcoming AMD Fusion and Intel Larrabee. Although the processor cores in such a heterogeneous multicore are different and each type offers its own distinct advantage for various workloads, the trend is to make the processor cores generic. They are programmable and typically they are Turing complete. For example, a graphics processor can be used (and often offers good performance) for some computations that are not computer graphics operations, such as sorting and numerical vector calculations. We can therefore expect that the computational workhorse for both desktop and embedded computer systems in the near future will be a heterogeneous multicore; just like the single-core processor was in the past and just like the multicore with several identical processor cores is today. The use of heterogeneous multicore processors in real-time systems is complicated however by the fact that the real-time scheduling theory with provably good real-time scheduling algorithms is not well-developed for such platforms. Therefore, this project aims to create provable good real-time scheduling algorithms for heterogeneous multicores. |
| Funding: | Global: 130KEUR, CISTER: 130KEUR |
| Sponsors: |     |
| Partners: | |
| Contact Person at CISTER: | Björn Andersson |
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Journal Papers
Compositional Multiprocessor Scheduling: the GMPR interface CISTER-TR-140101
Artem Burmyakov, Enrico Bini, Eduardo TovarReal-Time Systems, Springer US. May 2014, Volume 50, Issue 3, pp 342-376. U.S.A..
Artem Burmyakov, Enrico Bini, Eduardo TovarReal-Time Systems, Springer US. May 2014, Volume 50, Issue 3, pp 342-376. U.S.A..
PDF
Zip ArchiveAssigning Real-Time Tasks on Heterogeneous Multiprocessors with Two Unrelated Types of Processors HURRAY-TR-120712
Gurulingesh Raravi, Björn Andersson, Konstantinos BletsasReal-Time Systems (RTS), Springer. Jan 2013, Volume 49, Issue 1, pp 29-72.
Gurulingesh Raravi, Björn Andersson, Konstantinos BletsasReal-Time Systems (RTS), Springer. Jan 2013, Volume 49, Issue 1, pp 29-72.
Enhancing the Real-time Capabilities of the Linux Kernel HURRAY-TR-120701
Paulo Baltarejo Sousa, Nuno Pereira, Eduardo TovarACM SIGBED Review - Special Issue on the 24th Euromicro Conference on Real-Time Systems (ACM SIGBED Rev), ACM. Nov 2012.
Paulo Baltarejo Sousa, Nuno Pereira, Eduardo TovarACM SIGBED Review - Special Issue on the 24th Euromicro Conference on Real-Time Systems (ACM SIGBED Rev), ACM. Nov 2012.
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
Preemption-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..
Multiprocessor Real-Time Scheduling Considering Concurrency and Urgency HURRAY-TR-100101
Jinkyu Lee, Arvind Easwaran, Insik Shin, Insup LeeSIGBED Review - Special Issue on the Work-in-Progress (WIP) Session at the 2009 IEEE Real-Time Systems Symposium (RTSS), Article No 5, ACM. Jan 2010, Volume 7, Issue 1. New York, NY, U.S.A..This article was selected as one of the top 5 from among 24 papers in the Work-in-Progress session of RTSS 2009.
Jinkyu Lee, Arvind Easwaran, Insik Shin, Insup LeeSIGBED Review - Special Issue on the Work-in-Progress (WIP) Session at the 2009 IEEE Real-Time Systems Symposium (RTSS), Article No 5, ACM. Jan 2010, Volume 7, Issue 1. New York, NY, U.S.A..This article was selected as one of the top 5 from among 24 papers in the Work-in-Progress session of RTSS 2009.
Finding an Upper Bound on the Increase in Execution Time Due to Contention on the Memory Bus in COTS-Based Multicore Systems HURRAY-TR-100104
Björn Andersson, Arvind Easwaran, Jinkyu LeeSIGBED Review, Special Issue on the Work-in-Progress (WIP) Session at the 2009 IEEE Real-Time Systems Symposium (RTSS), Article No 4. Jan 2010, Volume 7, Issue 1. New York, U.S.A..This article was selected as one of the top 5 from among 24 papers in the Work-in-Progress session of RTSS 2009.
Björn Andersson, Arvind Easwaran, Jinkyu LeeSIGBED Review, Special Issue on the Work-in-Progress (WIP) Session at the 2009 IEEE Real-Time Systems Symposium (RTSS), Article No 4. Jan 2010, Volume 7, Issue 1. New York, U.S.A..This article was selected as one of the top 5 from among 24 papers in the Work-in-Progress session of RTSS 2009.
Conference or Workshop Papers/Talks
A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors HURRAY-TR-120903
Gurulingesh Raravi, Vincent Nélis33rd IEEE Real-Time Systems Symposium (RTSS 2012), IEEE. 4 to 7, Dec, 2012, pp 117-126. San Juan, Puerto Rico.
Gurulingesh Raravi, Vincent Nélis33rd IEEE Real-Time Systems Symposium (RTSS 2012), IEEE. 4 to 7, Dec, 2012, pp 117-126. San Juan, Puerto Rico.
Real-Time Scheduling with Resource Sharing on Uniform Multiprocessors HURRAY-TR-120902
Gurulingesh Raravi, Vincent Nélis, Björn Andersson20th International Conference on Real-Time and Network Systems (RTNS 2012), ACM New York. 8 to 9, Nov, 2012, pp 121-130. Pont à Mousson, France.
Gurulingesh Raravi, Vincent Nélis, Björn Andersson20th International Conference on Real-Time and Network Systems (RTNS 2012), ACM New York. 8 to 9, Nov, 2012, pp 121-130. Pont à Mousson, France.
The Generalized Multiprocessor Periodic Resource Interface Model for Hierarchical Multiprocessor Scheduling HURRAY-TR-121002
Artem Burmyakov, Enrico Bini, Eduardo Tovar20th International Conference on Real-Time and Network Systems (RTNS 2012), ACM. 8 to 9, Nov, 2012, pp 131-139. Pont à Mousson, France.
Artem Burmyakov, Enrico Bini, Eduardo Tovar20th International Conference on Real-Time and Network Systems (RTNS 2012), ACM. 8 to 9, Nov, 2012, pp 131-139. Pont à Mousson, France.
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.
On the implementation of real-time slot-based task-splitting scheduling algorithms for multiprocessor systems HURRAY-TR-110903
Paulo Baltarejo Sousa, Konstantinos Bletsas, Eduardo Tovar, Björn Andersson13th Real-Time Linux Workshop. 20 to 22, Oct, 2011, pp 207-218. Prague, Czechia.
Paulo Baltarejo Sousa, Konstantinos Bletsas, Eduardo Tovar, Björn Andersson13th Real-Time Linux Workshop. 20 to 22, Oct, 2011, pp 207-218. Prague, Czechia.
WCET Analysis Considering Contention on Memory Bus in COTS-Based Multicores HURRAY-TR-111001
Dakshina Dasari, Vincent Nélis, Björn Andersson16th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 2011). 5 to 9, Sep, 2011, Work-In-Progress Session. Toulouse, France.
Dakshina Dasari, Vincent Nélis, Björn Andersson16th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 2011). 5 to 9, Sep, 2011, Work-In-Progress Session. Toulouse, France.
Practical Aspects of Slot-Based Task-Splitting Dispatching in its Schedulability Analysis HURRAY-TR-110404
Paulo Baltarejo Sousa, Konstantinos Bletsas, Björn Andersson, Eduardo Tovar17th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011), IEEE. 28 to 31, Aug, 2011, 1, pp 224-230. Toyama, Japan.
Paulo Baltarejo Sousa, Konstantinos Bletsas, Björn Andersson, Eduardo Tovar17th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011), IEEE. 28 to 31, Aug, 2011, 1, pp 224-230. Toyama, Japan.
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.
Implementing Slot-Based Task-Splitting Multiprocessor Scheduling HURRAY-TR-110704
Paulo Baltarejo Sousa, Björn Andersson, Eduardo Tovar6th IEEE International Symposium on Industrial Embedded Systems (SIES 11), IEEE. 15 to 17, Jun, 2011, pp 256-265. Vasteras, Sweden.
Paulo Baltarejo Sousa, Björn Andersson, Eduardo Tovar6th IEEE International Symposium on Industrial Embedded Systems (SIES 11), IEEE. 15 to 17, Jun, 2011, pp 256-265. Vasteras, Sweden.
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..
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
Implementing Multicore Real-Time Scheduling Algorithms Based on Task Splitting Using Ada 2012 HURRAY-TR-100301
Björn Andersson, Luis Miguel Pinho15th International Conference on Reliable Software Technologies (Ada-Europe 2010), Springer Berlin Heidelberg. 14 to 18, Jun, 2010, pp 54-67. Valencia, Spain.
Björn Andersson, Luis Miguel Pinho15th International Conference on Reliable Software Technologies (Ada-Europe 2010), Springer Berlin Heidelberg. 14 to 18, Jun, 2010, pp 54-67. Valencia, Spain.
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..
Technical Reports
Implementing Slot-Based Task-Splitting Multiprocessor Scheduling HURRAY-TR-100504
Paulo Baltarejo Sousa, Björn Andersson, Eduardo Tovar16, May, 2010.
Paulo Baltarejo Sousa, Björn Andersson, Eduardo Tovar16, May, 2010.
A 12*(1+|R|/(4m))-speed algorithm for scheduling constrained-deadline sporadic real-time tasks on a multiprocessor comprising m processors where a task may request one of |R| sequentially-reusable shared resources HURRAY-TR-100201
Björn Andersson, Arvind Easwaran3, Feb, 2010.
Björn Andersson, Arvind Easwaran3, Feb, 2010.
Assigning Real-Time Tasks on Heterogeneous Multiprocessors with Two Types of Processors HURRAY-TR-091104
Björn Andersson, Konstantinos Bletsas3, Nov, 2009.
Björn Andersson, Konstantinos Bletsas3, Nov, 2009.