home · mobile · calendar · colloquia · 2005-2006 · 

Colloquium - Devi

Soft Real-Time Scheduling on Multiprocessors
University of North Carolina at Chapel Hill

A real-time system has to meet certain timing constraints (or deadlines) to be correct. Two trends influencing the design of real-time systems are currently emerging. First, multiprocessors are becoming quite common. This is evidenced by the availability of affordable symmetric multiprocessor platforms (SMPs) and the emergence of multicore architectures. Second, real-time systems are becoming increasingly complex, many have workloads that necessitate a multiprocessor platform, and the number of applications for which soft real-time guarantees are sufficient is growing. Examples include some tracking systems, signal-processing systems, and multimedia systems. Due to the above trends, multiprocessor-based software designs, including soft real-time system designs, will be inevitable in the future.

However, most prior research on real-time scheduling on multiprocessors has focused only on hard real-time systems, in which no deadline may ever be missed. To meet such stringent timing requirements, theoretically optimal scheduling algorithms tend to migrate process threads across processors frequently and also make certain simplifying assumptions that may not hold in practice. Hence, unlike in the case of uniprocessors, optimal real-time scheduling algorithms for multiprocessors are often considered impractical. On the other hand, suboptimal algorithms that are more practical require workload restrictions that can approach roughly 50% of the available processing capacity. This may be overkill for soft real-time systems, which can tolerate deadline misses by bounded amounts, and hence allow for a tradeoff between timeliness and improved resource utilization. Thus, to facilitate less-expensive implementations of soft real-time systems on multiprocessors, it is necessary that the tradeoff offered by such systems be leveraged to enable the use of less complex and more flexible algorithms in a resource-efficient manner. In this talk, I will discuss some multiprocessor-based real-time scheduling results obtained towards this end. Specifically, I will discuss some suboptimal but more efficient scheduling algorithms, and results that show that these algorithms can guarantee bounded tardiness on multiprocessors while requiring no restrictions on workload, except that it not exceed the available processing capacity.

Hosted by Dirk Grunwald.
The speaker is a candidate for a faculty position in the Department of Computer Science.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)