logging in or signing up cs554 lect06 Raulo Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 196 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: January 10, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript CS 554Introduction to Real-Time Embedded SystemsProfessor Kyoung Don KangLecture 6September 14, 2006: CS 554 Introduction to Real-Time Embedded Systems Professor Kyoung Don Kang Lecture 6 September 14, 2006Single Semester-Long Prject vs. Programming Assignments: Single Semester-Long Prject vs. Programming Assignments Students can work in teams for projects No teamwork is allowed for programming assignments 1st programming assignment will be available in a few days If you are under pressure, it will be safer to do programming assignments If you are interested in RT research including sensor networks, do a project Pick a topic among the ones to be discussed today (or find your own topic), find a team if possible, and discuss with meSingle Prject vs. Programming Assignments: Single Prject vs. Programming Assignments Decide whether you will do a project or programming assignments and email the TA and me your decision by Sept 26 If you are doing a project, let Ke and me know your topic and team membersProject 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 slidePrject 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 http://ecos.sourceware.org/ uc/OS-II Commercial, open-source RT kernel Easy to use and runs in Windows environment http://www.ucos-i.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.phpProject Idea 2: Project Idea 2 Tweak a soft real-time middleware For example, you can apply imprecise computation, (m,k) firm deadline, or elastic task model to handle dynamic workloads and QoS requirements DSRT: Dynamic Soft Real Time CPU Scheduler 2.0 (middleware) http://cairo.cs.uiuc.edu/software/DSRT-2/dsrt-2.html Runs in Windows or LinuxProject 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 RTDB testbed implemented on top of an open source embedded DB called Berkeley DB Possible projects (Pick one) 1. Make the home-made simulator or testbed more structured/easier-to-use; 2. Support distributed RT transaction processing; 3. Make the RTDB testbed to interact with wireless sensors; OR 4. Investigate how to handle RTDB specific issues such as data freshness or data conflicts properly, while supporting timing guarantees? (PhD level project)Project Idea 4: Project Idea 4 Power-aware real-time routing in wireless sensor networks Usually a packet takes the shortest path to the destination No need for a packet to arrive at the destination earlier than its deadline Take an alternate path to reduce power consumption when there’s enough slack Network simulation in ns-2Project Idea 5: Project Idea 5 Differentiated real-time routing in WSNs Initially assign a deadline for a packet based on distance or number of hops Define the criticality for each periodic data flow e.g., less critical flows can be more elastic Schedule packets in a velocity monotonic manner Maximum (#hops/deadline) → Highest priorityProject Idea 5: Project Idea 5 When a router is backlogged, adapt the deadlines according to the elastic coefficients 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-2Project Idea 6: Project Idea 6 Play with TinyOS or TinySec Try to extend or implement your protocol on top of it You can use TOSSIM even if you don’t have access to real sensorsProject Idea 7: Project Idea 7 Remote control of robots on Mars (simulation) You can find the problem description and simulator here! (RTSS 2005 Programming Competition) Feedback Control Real-Time Scheduling: Feedback Control Real-Time Scheduling C. Lu, J.A. Stankovic, G. Tao, and S.H. Son, Design and Evaluation of a Feedback Control EDF Scheduling Algorithm, IEEE Real-Time Systems Symposium (RTSS'99), December 1999. Motivation for Feedback control Scheduling: Motivation for Feedback control Scheduling Open-loop scheduling paradigms perform perform poorly in unpredictable dynamic systems where the workload cannot be accurately modeled Many complex applications, e.g., robotics and agile manufacturing, are dynamic and operate in a non-deterministic environment where precise workload is not known Challenging to build real-time systems providing predictable performance in a highly uncertain environment Feedback control can support the target performance even when the workload varies dynamically via graceful QoS degradation in a feedback loopMotivation: Motivation Apply control theoretic approaches to real-time performance management Feedback control is well known for its robustness, e.g., cruise control or chemical reactor control, in the presence of disturbances Doesn’t need a precise system model If the precise system model is known, feedback control is not necessary Dynamically adapt the system behavior to achieve the targe performance (also called set point) in the feedback loopFeedback Control Concepts: Feedback Control Concepts Set-point: Target performance to achieve, e.g., 1% deadline miss ratio Measured perf: Actual perf, e.g., actual (deadline) miss ratio, measured at the current sampling period Error = set-point – measured perf = target miss ratio – current miss ratio Controller Controlled RT System + - Setpoint Measured Perf. Error Control SignalFeedback Control Loop: Feedback Control Loop Periodically measure and compare the perf to the set point to determine the error Controller computes the control signal based on the error and controlled system model Actuator, e.g., admission controller or QoS manager, change the value of the manipulated variable to control the system FC-EDF Architecture: FC-EDF ArchitectureMiss Ratio Control Model : Miss Ratio Control Model At kth sampling instant, miss ratio is: m(k) = m(k-1) + g(k) ∆u(k-1) where m(k-1) is the miss ratio at the (k-1)th sampling period, g(k) is the miss ratio gain, and ∆u(k-1) is the utilization adjustment by admission control and QoS adaptation at the (k-1)th sampling periodMiss Ratio Control Model: Miss Ratio Control Model Instead of considering time-varying miss ratio gain g(k), they took G = maximum (miss ratio/unit load increase) 0.9 1 1.1 1.2 1.3 ... Load Miss RatioMiss Ratio Control Model: Miss Ratio Control Model Replace g(k) with G m(k) = m(k-1) + g(k)∆u(k-1) → m(k) = m(k-1) + G∆u(k-1) Take z-transform to convert to frequency domain M(z) = z-1M(z) + z-1∆U(z) M(z) = (G/z-1) ∆U(z) Transfer function T(z) = output/input = M(z)/U(z) = G/z-1 Utilization Control Model: Utilization Control Model Miss ratio controller itself is not stable MR controller is saturated when utilization is less than 1 when EDF is used In their later work, they added utilization controller Utilization controller works when U ≤ 1, miss ratio controller works when U > 1 Turn on/off util/MR controller when U ≤ 1 Turn on/off MR/util controller when U > 1Controller Tuning: Controller Tuning Given the control model shown in the previous slide, apply Root Locus model to graphically tune the controller in Matlab to support the stability & specified transient performance such as the overshoot and settling time We will fully discuss techniques for feedback control of QoS next time Any Questions?: Any Questions? You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
cs554 lect06 Raulo Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 196 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: January 10, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript CS 554Introduction to Real-Time Embedded SystemsProfessor Kyoung Don KangLecture 6September 14, 2006: CS 554 Introduction to Real-Time Embedded Systems Professor Kyoung Don Kang Lecture 6 September 14, 2006Single Semester-Long Prject vs. Programming Assignments: Single Semester-Long Prject vs. Programming Assignments Students can work in teams for projects No teamwork is allowed for programming assignments 1st programming assignment will be available in a few days If you are under pressure, it will be safer to do programming assignments If you are interested in RT research including sensor networks, do a project Pick a topic among the ones to be discussed today (or find your own topic), find a team if possible, and discuss with meSingle Prject vs. Programming Assignments: Single Prject vs. Programming Assignments Decide whether you will do a project or programming assignments and email the TA and me your decision by Sept 26 If you are doing a project, let Ke and me know your topic and team membersProject 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 slidePrject 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 http://ecos.sourceware.org/ uc/OS-II Commercial, open-source RT kernel Easy to use and runs in Windows environment http://www.ucos-i.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.phpProject Idea 2: Project Idea 2 Tweak a soft real-time middleware For example, you can apply imprecise computation, (m,k) firm deadline, or elastic task model to handle dynamic workloads and QoS requirements DSRT: Dynamic Soft Real Time CPU Scheduler 2.0 (middleware) http://cairo.cs.uiuc.edu/software/DSRT-2/dsrt-2.html Runs in Windows or LinuxProject 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 RTDB testbed implemented on top of an open source embedded DB called Berkeley DB Possible projects (Pick one) 1. Make the home-made simulator or testbed more structured/easier-to-use; 2. Support distributed RT transaction processing; 3. Make the RTDB testbed to interact with wireless sensors; OR 4. Investigate how to handle RTDB specific issues such as data freshness or data conflicts properly, while supporting timing guarantees? (PhD level project)Project Idea 4: Project Idea 4 Power-aware real-time routing in wireless sensor networks Usually a packet takes the shortest path to the destination No need for a packet to arrive at the destination earlier than its deadline Take an alternate path to reduce power consumption when there’s enough slack Network simulation in ns-2Project Idea 5: Project Idea 5 Differentiated real-time routing in WSNs Initially assign a deadline for a packet based on distance or number of hops Define the criticality for each periodic data flow e.g., less critical flows can be more elastic Schedule packets in a velocity monotonic manner Maximum (#hops/deadline) → Highest priorityProject Idea 5: Project Idea 5 When a router is backlogged, adapt the deadlines according to the elastic coefficients 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-2Project Idea 6: Project Idea 6 Play with TinyOS or TinySec Try to extend or implement your protocol on top of it You can use TOSSIM even if you don’t have access to real sensorsProject Idea 7: Project Idea 7 Remote control of robots on Mars (simulation) You can find the problem description and simulator here! (RTSS 2005 Programming Competition) Feedback Control Real-Time Scheduling: Feedback Control Real-Time Scheduling C. Lu, J.A. Stankovic, G. Tao, and S.H. Son, Design and Evaluation of a Feedback Control EDF Scheduling Algorithm, IEEE Real-Time Systems Symposium (RTSS'99), December 1999. Motivation for Feedback control Scheduling: Motivation for Feedback control Scheduling Open-loop scheduling paradigms perform perform poorly in unpredictable dynamic systems where the workload cannot be accurately modeled Many complex applications, e.g., robotics and agile manufacturing, are dynamic and operate in a non-deterministic environment where precise workload is not known Challenging to build real-time systems providing predictable performance in a highly uncertain environment Feedback control can support the target performance even when the workload varies dynamically via graceful QoS degradation in a feedback loopMotivation: Motivation Apply control theoretic approaches to real-time performance management Feedback control is well known for its robustness, e.g., cruise control or chemical reactor control, in the presence of disturbances Doesn’t need a precise system model If the precise system model is known, feedback control is not necessary Dynamically adapt the system behavior to achieve the targe performance (also called set point) in the feedback loopFeedback Control Concepts: Feedback Control Concepts Set-point: Target performance to achieve, e.g., 1% deadline miss ratio Measured perf: Actual perf, e.g., actual (deadline) miss ratio, measured at the current sampling period Error = set-point – measured perf = target miss ratio – current miss ratio Controller Controlled RT System + - Setpoint Measured Perf. Error Control SignalFeedback Control Loop: Feedback Control Loop Periodically measure and compare the perf to the set point to determine the error Controller computes the control signal based on the error and controlled system model Actuator, e.g., admission controller or QoS manager, change the value of the manipulated variable to control the system FC-EDF Architecture: FC-EDF ArchitectureMiss Ratio Control Model : Miss Ratio Control Model At kth sampling instant, miss ratio is: m(k) = m(k-1) + g(k) ∆u(k-1) where m(k-1) is the miss ratio at the (k-1)th sampling period, g(k) is the miss ratio gain, and ∆u(k-1) is the utilization adjustment by admission control and QoS adaptation at the (k-1)th sampling periodMiss Ratio Control Model: Miss Ratio Control Model Instead of considering time-varying miss ratio gain g(k), they took G = maximum (miss ratio/unit load increase) 0.9 1 1.1 1.2 1.3 ... Load Miss RatioMiss Ratio Control Model: Miss Ratio Control Model Replace g(k) with G m(k) = m(k-1) + g(k)∆u(k-1) → m(k) = m(k-1) + G∆u(k-1) Take z-transform to convert to frequency domain M(z) = z-1M(z) + z-1∆U(z) M(z) = (G/z-1) ∆U(z) Transfer function T(z) = output/input = M(z)/U(z) = G/z-1 Utilization Control Model: Utilization Control Model Miss ratio controller itself is not stable MR controller is saturated when utilization is less than 1 when EDF is used In their later work, they added utilization controller Utilization controller works when U ≤ 1, miss ratio controller works when U > 1 Turn on/off util/MR controller when U ≤ 1 Turn on/off MR/util controller when U > 1Controller Tuning: Controller Tuning Given the control model shown in the previous slide, apply Root Locus model to graphically tune the controller in Matlab to support the stability & specified transient performance such as the overshoot and settling time We will fully discuss techniques for feedback control of QoS next time Any Questions?: Any Questions?