cs554 lect05

Elastic Task Model for Adaptive Rate Control: 

Elastic Task Model for Adaptive Rate Control Giorgio Buttazzo, Giuseppe Lipari, Luca Abeni, Elastic Task Model For Adaptive Rate Control, RTSS 1998.

Outline: 

Outline Introduction Elastic Model Compressing Task Utilization Theoretical Validation Experimental Results Conclusions

Motivation: 

Motivation Classic real-time task models are too rigid For a task i is defined by constant period Ti & exec time Ci in RM & EDF Schedulability guarantee Necessary for stability of critical hard real-time systems

Motivation: 

Motivation More flexibility is required by multimedia & adaptive control applications MPEG encoding/decoding time may vary from frame to frame A deadline miss can degrade QoS but doesn’t cause any catastrophic result Considering as hard real-time task is too pessimistic Underutilize the CPU as WCET >> average exec time

Elastic Task Model (ETM): 

Elastic Task Model (ETM) Treat task periods as springs with given elastic coefficients Increase/decrease task periods to control QoS considering the current load Allow tasks to intentionally change their execution rates to provide different levels of QoS Handle overload situations in a more flexible way

Imprecise computation, (m,k) firm deadlines, and ETM: Which is best?: 

Imprecise computation, (m,k) firm deadlines, and ETM: Which is best? Review Imprecise computation can reduce task exec time by skipping (or spending fewer CPU cycles for) optional parts (m,k) model can drop jobs, i.e., task instances, in a controlled manner Which is best? Always out perform the others? We don’t know.

Imprecise computation, (m,k) firm deadlines, and ETM: Which is best?: 

Imprecise computation, (m,k) firm deadlines, and ETM: Which is best? One model may not work best for every application For even one application, e.g., video streaming, one or the other may show better performance under certain circumstances Which model work best in certain situations? This can be a good course proejct topic (More topics at the end of the talk) Can we develop any model that outperforms these models (in even some specific application)?

Outline: 

Outline Introduction The Elastic Model Compressing Task Utilization Theoretical Validation Experimental Results Conclusions

Task Parameters: 

Task Parameters Computation time Ci (fixed) Nominal period Ti0 Minimum period Timin Maximum period Timax Elastic coefficient ei >= 0 A task = i(Ci, Ti0, Timin, Timax, ei)

Parameter Constraints: 

Parameter Constraints Ti: actual period of task i Ti  [Timin, Timax] Any variation is subject to an elastic guarantee and is accepted only if there exists a feasible schedule in which all the other periods are within their range

Slide11: 

Schedulable by EDF Up = 10/20 + 10/40 + 15/70 = 0.964 < 1 3 reduces its period to 50 Up = 10/20 + 10/40 + 15/50 = 1.05 > 1 Not schedulable Change T1 to 22 and T2 to 45 Up = 0.977 Schedulable!

Example Cont.: 

Example Cont. 3 reduces its period to 40 Schedulable T1 = 35 must be rejected, since there’s no feasible schedule with T1 and T2 within their (min, max) period ranges

Configuration Policy: 

Configuration Policy Implicitly encoded in the elastic coefficients provided by the user Each task is varied based on its current elastic status under the condition that a feasible configuration is found (if there exists one)

More Features: 

More Features The other direction (decompressoin): Task terminates or decreases its rate. Other tasks gain back bandwidth – Increase their rates, if necessary, to improve QoS Hard real-time tasks Ti0 = Timin = Timax

Outline: 

Outline Introduction The Elastic Model Compressing Task Utilization Theoretical Validation of the Model Experimental Results Conclusions

Compressing Task Utilization: 

Compressing Task Utilization Set of periodic task Γ can be divided into: Γf: Set of fixed tasks in which an arbitrary task i in the set consumes it minimum utilization, i.e., its current period Tf = Tfmin Γv: Set of variable tasks that can be still compressed For task v in Γv its current period Tv > Tvmin Period can be increased to reduce utilizaiton U0: Sum of all the nominal utilization (Ci/ Ti0) for the tasks in Γv Uf: Total utilization of the tasks in Γf

Compressing Task Utilization: 

Compressing Task Utilization To achieve the desired utilization Ud < U0, each task in Γv has to be compressed to the following utilization:

Decompression: 

Decompression A task decreases its rate or returns to its nominal period Compressed tasks expand their utilizations according to their elastic coefficients If total utilization is less than utilization bound, then all tasks can return to their nominal periods

Outline: 

Outline Introduction The Elastic Model Equivalence with a Spring System Compressing Tasks’ Utilizations Theoretical Validation of the Model Experimental Results Conclusions

Theoretical Validation: Key Idea: 

If tasks’ periods are changed at opportune instants, the task set remains schedulable and no deadline is missed → Find out when is the opportune time!!! The following lemmas state two properties of the EDF algorithm that are useful for proving the main theorem Theoretical Validation: Key Idea

Lemma 1: 

Lemma 1 In any feasible EDF schedule , the following condition holds: t >0  i[1,n] ri (t)/t >= Up Where Up =  i[1,n] Ci / Ti and ri (t) is the cumulative time executed by all the instances of task i up to t Processor demand analysis

Lemma 2: 

Lemma 2 In any feasible EDF schedule , the following condition holds: t >0  i[1,n] ci(t) ≤  i[1,n] [vi(t) – t]Ui Where Ui = Ci / Ti, ci (t) is the remaining execution time of the current instance of task i at time t, and vi (t) is the next release time of i greater than or equal to t

Theorem 1: 

Theorem 1 Given a feasible task set Γ, with total utilization factor Up =  i[1,n] Ci/Ti ≤ 1, if at time t all the periods are increased from Ti to T’i ≥ Ti, then for all L > 0, D(t, t+L) ≤ LU’ p Where D(t1, t2) is the total processor demand of Γ in [t1, t2] and U’p =  i[1,n] Ci/T’i

What does the theorem mean?: 

What does the theorem mean? Periods can be increased immediately, but The period of a task can be decreased only at its next release time Example in the next slide

Slide26: 

D Miss! Orignally, 3/10 + 2/3 = 0.96 < 1 After changing periods at t =14: 3/5 + 2/6 = 0.96 If T1 is immediately changed at t = 14, D miss at t = 16

Outline: 

Outline Introduction The Elastic Model Equivalence with a Spring System Compressing Tasks’ Utilizations Theoretical Validation of the Model Experimental Results Conclusions

Outline: 

Outline Introduction The Elastic Model Equivalence with a Spring System Compressing Tasks’ Utilizations Theoretical Validation of the Model Experimental Results Conclusions

Conclusions: 

Conclusions Periodic tasks can change their execution rates to adapt QoS Remaining tasks can canautomatically adapt their peroids to keep the system underloaded Policy is encoded in the elastic coefficient Useful for supporting both multimedia and adaptive control applications, in which the execution rates of some computational activities have to be dynamically tuned as a function of the current system

Single Semester-Long Prject vs. Programming Assignments: 

Single Semester-Long Prject vs. Programming Assignments Students can work in teams for projects Programming assignments are individual – No teamwork is allowed 1st programming assignment will be available in this week If it’s your first time to real-time emebedded systems or your are under pressure, it will be safer to do programming assignments If you are interested in RT research, do a project Pick a topic among the ones to be discussed today (or identify your own topic), find a team if possible, and discuss with me

Single Semester-Long Prject vs. Programming Assignments: 

Single Semester-Long Prject vs. Programming Assignments Decide whether you will do a project or programming assignments by Sept 26 and let the TA and me know about your decision If you are doing a project, let the TA and me knwo about your topic, team members, etc.

Project Idea 1: 

Project Idea 1 Verify if real-time scheduling theory, e.g., RM, EDF, priority inheritance/ceiling, really works Tweak a RT kernel in your way to improve schedulability, reduce overhead/kernel complexity, or make it more configurable... Some open source real-time embedded kernels are in the next slide

Prject Idea 1: 

Prject Idea 1 Open source RT/embedded kernels eCos (embedded configurable OS) Open source, royalty-free RTOS Can be installed in Linux or Windows (with Cygwin) Highly configurable – How does configurability make a RTOS better? Performance optimization & memory footprint minimization http://ecos.sourceware.org/ uc/OS-II Commercial, open-source RT kernel Easy to use and runs in Windows environment http://www.ucos-ii.com/products/rtos/kernel/rtos.html Book: http://www.amazon.com/MicroC-OS-II-Kernel-CD-ROM/dp/1578201039 L4 Kernel http://l4ka.org/projects/pistachio/ia32/gettingstarted.php

Project Idea 2: 

Project Idea 2 Compare imprecise computation model, (m,k) firm deadline model & ETM for a multimedia application Qualitative analysis: Which is more applicable? Why? Experiments to support your arguments DSRT: Dynamic Soft Real Time CPU Scheduler 2.0 http://cairo.cs.uiuc.edu/software/DSRT-2/dsrt-2.html Middleware that works with either Windows or Linux

Project Idea 3: Real-Time Database: 

Project Idea 3: Real-Time Database We have a home-made simulator written in C++ We also have a preliminary version of a testbed implemented on top of an open source DB called Berkeley DB Choose to do a simulation or real DB implementation 1. Make the home-made simulator or testbed more structured/easier-to-use or make one of them to support distributed RT transaction processing; OR 2. Make the RTDB testbed to interact with wireless sensors; OR 3. How to handle RTDB specific issues such as data freshness or data conflicts properly, while supporting timing guarantees?;

Project Idea 4: 

Project Idea 4 Power-aware real-time routing Shortest path to minimize the delay No need for a packet to arrive at the destination earlier than the deadline Take an alternate path to reduce power consumption given enough slack – Just-in-time scheduling + power management You can use network simulation in ns-2

Project Idea 5: 

Project Idea 5 Differentiated real-time routing Initially assign a deadline for a packet based on distance or number of hops Define the criticality for each periodic data flow Criticality could be indicated by an elastic cofficient such that less critical flows are more elastic Schedule packets in an EDF manner When a router is backlogged, adapt the deadlines of elastic packets (according to the elasticity constraints) Piggyback the adaptation info as part of ACK message Eventually propagate to the source Forward less urgenet packets through an alternate path Network simulation via ns-2

Project Idea 6: 

Project Idea 6 Remote control of robots on Mars (simulation) You can find the problem description and simulator here!

Any Questions?: 

Any Questions?