Research Leader:

Other PIs and Researchers:

Konstantinos Bletsas
Arvind Easwaran (PI)
Paulo Baltarejo Sousa
Gurulingesh Raravi
Dakshina Dasari

Synopsys

Multicores are spreading at an unprecedented rate. Today, a multicore processor is the default choice in server/desktop/laptop computers and it is increasingly used in embedded computer systems (such as cellular phones, in-vehicle electronics and medical instrumentation).

The use of multicores in embedded systems is complicated by the fact that many embedded computer systems have real-time requirements, that is, the time at which a program produces its result is as important as the result itself. The time at which a program computes its result depends on how computer resources (processor cores, memory, bus bandwidth, I/O devices, etc.) are shared among programs and therefore the scientific community has created a toolkit of algorithms for scheduling programs on a single processor so that the program executes at the right time. Unfortunately, scheduling programs at the right time on a multicore is currently not well understood; in particular, there is no such well-established toolkit for multiprocessors.

Researchers at CISTER/IPP-HURRAY are currently developing scheduling algorithms and proof techniques which makes it possible to prove at design time that deadlines will be met at run-time, even if the exact time when programs request to execute is unknown.

Ongoing Research

Multicores with identical processor cores

Real-time scheduling on a single processor has enjoyed great successes during the recent four decades, starting with the development of rate-monotonic which was used in the computer that put the first man on the moon. Those decades of developments of scheduling theory for a single processor have made it possible to (i) schedule tasks with few preemptions and small time-complexity of dispatching, (ii) schedule implicit-deadline tasks to meet deadlines even at high processor utilization (69% and 100%), (iii) schedule arbitrary-deadline tasks and (iv) schedule tasks with the aforementioned properties but also to share data between tasks. Unfortunately such results are not available for the computer platform that matters the most today: the multiprocessor implemented on a single chip, also called multicore. Therefore, researchers at CISTER work on the development of those results as part of a national project called RESCORE (Real-time scheduling on multicores).

The multicore processor is a standard building block in systems design (both desktop and embedded computing) today. Multicores with different types of processor cores (heterogeneous multicores) have also been synthesized for specific applications (for example cellular phones). A recent trend however is that heterogeneous multicores are becoming commoditized (the IBM Cell processor and fusion of general purpose processor and graphics processors are good examples of this trend). They are available at low prices, and they are becoming more and more general-purpose processing devices. Therefore, researchers at CISTER work on the development of those results as part of a national project called REHEAT (Real-time scheduling on heterogeneous multicore architectures). 

Projects & Leadership

International Projects

We are one of the core partners in the European network of Excellence ARTISTDesign.

National Projects

We have been granted one of the largest grants in the area of Electrical Engineering and Computer Science from the Portuguese Science Council (FCT) for our project RESCORE.

We have been granted one grant in the area of Electrical Engineering and Computer Science from the Portuguese Science Council (FCT) our project REHEAT.

International Leadership

Seminar at Carnegie-Mellon University in Pittsburgh, PA, USA:  "Recent results on real-time scheduling on Multiprocessors", December 9, 2008.

Invited talk at ARTISTDesign Workshop on Multicores: Theory and Practice, Kaiserslautern, Germany: "Partitioning++", October 28, 2008.

Relevant Publications

1. The RTCSA'06 Paper provides a multiprocessor scheduling algorithm which can be configured such that it is optimal and among all optimal multiprocessor scheduling algorithms, it is the one with the fewest preemptions;
2. The ECRTS'08 Paper provides (based on the RTCSA'06 paper) an algorithm for scheduling sporadic tasks;
3. The RTSS'08 Paper provides (based on the ECRTS'08 paper) an algorithm for scheduling arbitrary-deadline sporadic tasks;
4. In the RTAS'09 Paper we proposed a new idea ("Notional Processors") which is useful for creating multiprocessor scheduling algorithms with high utilization bound and few preemptions;
5. In the RTSS'09 Paper we presented an improvement to the idea of "Notional Processors" for increasing the utilization bound;
6. In the RTSS'09 Paper we presented a resource sharing protocol with the prominent feature of allowing large degrees of parallel execution (which allows multicores to be used efficiently) yet maintaining low amounts of blocking.