Embedded System Design And Synthesis Types Of Reliability

Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Taxonomy Definitions Central areas of real-time study Taxonomy of real-time systems Taxonomy Definitions Central areas of real-time study Static Task arrival times can be predicted. Static (compile-time) analysis possible. Allows good resource usage (low processor idle time proportions). Sometimes designers shoehorn dynamic problems into static formulations allowing a good solution to the wrong problem. Dynamic Static 30 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Soft Embedded System Design and Synthesis 31 Taxonomy Definitions Central areas of real-time study Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Hard Dynamic Periodic More slack in implementation Bounded Unbounded Multi rate Static (compile-time) analysis only for simple cases. arrival possible interval arrival interval Timing may be suboptimal without being incorrect Even then, the portion of required processor utilization efficiency goes to 0.693. Periodic Problem formulation can be much more complicated than hard real-time Aperiodic In many real systems, this is very difficult to apply in reality (more on this later). Soft Hard Single rate Multi rate Bounded arrival interval Unbounded arrival interval Two common (and one uncommon) methods of dealing with non-trivial soft real-time system requirements Use the right tools but don’t over-simplify, e.g., We assume, without loss of generality, that all tasks are independent. Periodic Static Dynamic Taxonomy Definitions Central areas of real-time study Aperiodic Single rate Dynamic Embedded System Design and Synthesis Soft real-time Task arrival times unpredictable. Static Robert Dick Soft Hard Single rate Set somewhat loose hard timing constraints Informal design and testing Formulate as optimization problem Aperiodic Multi rate Bounded arrival interval Unbounded arrival interval If you do this people will make jokes about you. 32 Robert Dick Embedded System Design and Synthesis Periodic Static Dynamic Soft Hard Single rate 33 Robert Dick Embedded System Design and Synthesis Aperiodic Multi rate Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Bounded arrival interval Taxonomy Definitions Central areas of real-time study Hard real-time Unbounded arrival interval Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Taxonomy Definitions Central areas of real-time study Periodic Each task (or group of tasks) executes repeatedly with a particular period. Difficult problem. Some timing constraints inflexible. Allows some nice static analysis techniques to be used. Simplifies problem formulation. Matches characteristics of many real problems. . and has little or no relationship with many others that designers try to pretend are periodic. 34 Robert Dick Embedded System Design and Synthesis 35 Robert Dick Embedded System Design and Synthesis

Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Taxonomy Definitions Central areas of real-time study Periodic Single-rate Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Taxonomy Definitions Central areas of real-time study Periodic Multirate Multiple periods. One period in the system. Can use notion of circular time to simplify static (compile-time) schedule analysis E. L. Lawler and D. E. Wood. Branch-and-bound methods: A survey. Operations Research, pages 699–719, July 1966. Simple. Inflexible. This is how a lot of wireless sensor networks are implemented. Co-prime periods leads to analysis problems. 36 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Embedded System Design and Synthesis 37 Taxonomy Definitions Central areas of real-time study Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Periodic Other Robert Dick Embedded System Design and Synthesis Taxonomy Definitions Central areas of real-time study Aperiodic It is possible to have tasks with deadlines less than, equal to, or greater than their periods. Also called sporadic, asynchronous, or reactive Results in multi-phase, circular-time schedules with multiple concurrent task instances. Bounded arrival time interval permits resource reservation Implies dynamic Unbounded arrival time interval impossible to deal with for any resource-constrained system If you ever need to deal with one of these, see me (take my code). This class of scheduler is nasty to code. 38 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Embedded System Design and Synthesis 39 Taxonomy Definitions Central areas of real-time study Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Definitions Robert Dick Embedded System Design and Synthesis Taxonomy Definitions Central areas of real-time study Task Task Processor Some operation that needs to be carried out Graph representations Atomic completion: A task is all done or it isn’t Deadline violation Non-atomic execution: A task may be interrupted and resumed Cost functions 41 Robert Dick Embedded System Design and Synthesis 42 Robert Dick Embedded System Design and Synthesis

Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Taxonomy Definitions Central areas of real-time study Processor Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Taxonomy Definitions Central areas of real-time study Task/processor relationship WC exec time (s) Tooth Processors execute tasks Distributed systems Road FIR Contain multiple processors Inter-processor communication has impact on system performance Communication is challenging to analyze Matrix 7.7E 6 . 330E 9 . 4.1E 6 . 310E 3 . IBM One processor type: Homogeneous system IDT Po we rPC Multiple processor types: Heterogeneous system Ims ys Cjip 236 40 405 41 MH GP 00 z MH 266 z MH z 79R C3 Relationship between tasks, processors, and costs E.g., power consumption or worst-case execution time 43 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Embedded System Design and Synthesis 44 Taxonomy Definitions Central areas of real-time study Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Cost functions Robert Dick Embedded System Design and Synthesis Taxonomy Definitions Central areas of real-time study Back to real-time problem taxonomy: Jagged edges Some things dramatically complicate real-time scheduling These are horrific, especially when combined Mapping of real-time system design problem solution instance to cost value Data dependencies Unpredictability Distributed systems I.e., allows price, or hard deadline violation, of a particular multi-processor implementation to be determined These are irksome Heterogeneous processors Preemption 45 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Embedded System Design and Synthesis 46 Taxonomy Definitions Central areas of real-time study Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Central areas of real-time study Robert Dick Embedded System Design and Synthesis Taxonomy Definitions Central areas of real-time study Allocation, assignment, and scheduling How does one best Analyze problem instance specifications Allocation, assignment and scheduling E.g., worst-case task execution time Operating systems and scheduling Select (and build) hardware components Distributed systems and scheduling Select and produce software Scheduling is at the core or real-time systems study Decide which processor will be used for each task Determine the time(s) at which all tasks will execute 48 Robert Dick Embedded System Design and Synthesis 49 Robert Dick Embedded System Design and Synthesis

Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Taxonomy Definitions Central areas of real-time study Allocation, assignment, and scheduling Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Operating systems and scheduling How does one best design operating systems to In order to efficiently and (when possible) optimally minimize Support sufficient detail in workload specification to allow good control, e.g., over scheduling, without increasing design error rate Price, power consumption, soft deadline violations Under hard timing constraints Design operating system schedulers to support real-time constraints? Providing guarantees whenever possible For all the different classes of real-time problem classes Support predictable costs for task and OS service execution This is what I did for a Ph.D. 50 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Embedded System Design and Synthesis 51 Taxonomy Definitions Central areas of real-time study Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Distributed systems and scheduling . and their schedules Why view problem in this manner? Task deadline violations are bounded (when possible). Without having a concrete definition of the problem . and minimized when no bounds are possible How is one to know if an answer is correct? More subtly, how is one to know if an answer is optimal? Embedded System Design and Synthesis 53 Taxonomy Definitions Central areas of real-time study Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Optimization Taxonomy Definitions Central areas of real-time study Slight abuse of notation here, functionality requirements are actually just constraints for systems in which computation nodes may be separated by vast distances such that Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Embedded System Design and Synthesis The design of a real-time system is fundamentally a cost optimization problem Minimize costs under constraints while meeting functionality requirements The assignment of tasks to processing nodes. Robert Dick Robert Dick The value of formality: Optimization and costs How does one best dynamically control 52 Taxonomy Definitions Central areas of real-time study Robert Dick Embedded System Design and Synthesis Definitions Scheduling methods Example scheduling applications Graph extensions J J1/3 J1/3 3 kb 0 kb 0 kb J2/3 Thinking of a design problem in terms of optimization gives design team members objective criterion by which to evaluate the impact of a design change on quality. Know whether your design changes are taking you in a good direction J2/3 K1/3 0 kb J3/3 K1/3 3 kb 9 kb 9 kb 0 kb 0 kb 0 kb J3/3 K2/3 3 kb K2/3 0 kb K a) conventional K3/3 b) pre and post computation 0 kb K3/3 c) streaming Allows pipelining and pre/post-computation In contrast with book, not difficult to use if conversion automated 54 Robert Dick Embedded System Design and Synthesis 57 Robert Dick Embedded System Design and Synthesis

Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Definitions Scheduling methods Example scheduling applications Problem definition A B Definitions Scheduling methods Example scheduling applications Types of scheduling problems E C D Discrete time – Continuous time Hard deadline – Soft deadline Unconstrained resources – Constrained resources Uni-processor – Multi-processor B D C minimize completion time A E PE 0 PE 1 Homogeneous processors – Heterogeneous processors Free communication – Expensive communication Independent tasks – Precedence constraints Homogeneous tasks – Heterogeneous tasks Given a set of tasks, One-shot – Periodic Single rate – Multirate a cost function, and a set of resources, Non-preemptive – Preemptive decide the exact time each task will execute on each resource 58 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Off-line – On-line Embedded System Design and Synthesis 59 Definitions Scheduling methods Example scheduling applications Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Discrete vs. continuous timing Robert Dick Embedded System Design and Synthesis Definitions Scheduling methods Example scheduling applications Hard deadline – Soft deadline System-level: Continuous Operations are not small integer multiples of the clock cycle Tasks may have hard or soft deadlines High-level: Discrete Hard deadline Operations are small integer multiples of the clock cycle Task must finish by given time or schedule invalid Implications: Soft deadline If task finishes after given time, schedule cost increased System-level scheduling is more complicated. . . . . . however, high-level also very difficult. Can we solve this by quantizing time? Why or why not? 60 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Embedded System Design and Synthesis 61 Definitions Scheduling methods Example scheduling applications Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Real-time – Best effort Robert Dick Embedded System Design and Synthesis Definitions Scheduling methods Example scheduling applications Unconstrained – Constrained resources Why make decisions about system implementation statically? Allows easy timing analysis, hard real-time guarantees Unconstrained resources If a system doesn’t have hard real-time deadlines, resources can be more efficiently used by making late, dynamic decisions Can combine real-time and best-effort portions within the same specification Additional resources may be used at will Constrained resources Limited number of devices may be used to execute tasks Reserve time slots Take advantage of slack when tasks complete sooner than their worst-case finish times 62 Robert Dick Embedded System Design and Synthesis 63 Robert Dick Embedded System Design and Synthesis

Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Definitions Scheduling methods Example scheduling applications Uni-processor – Multi-processor Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Definitions Scheduling methods Example scheduling applications Homogeneous – Heterogeneous processors Uni-processor All tasks execute on the same resource Homogeneous processors This can still be somewhat challenging However, sometimes in P Heterogeneous processors All processors are the same type There are different types of processors Usually N P-complete Multi-processor There are multiple resources to which tasks may be scheduled Usually N P-complete 64 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Embedded System Design and Synthesis 65 Definitions Scheduling methods Example scheduling applications Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Free – Expensive communication Robert Dick Embedded System Design and Synthesis Definitions Scheduling methods Example scheduling applications Independent tasks – Precedence constraints NEG Free communication Data transmission between resources has no time cost DCT IOP Expensive communication Data transmission takes time Increases problem complexity Generation of schedules for communication resources necessary Usually N P-complete FIL FT Independent tasks: No previous execution sequence imposed Precedence constraints: Weak order on task execution order 66 Robert Dick Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Embedded System Design and Synthesis 67 Definitions Scheduling methods Example scheduling applications Reliable embedded system design and synthesis Realtime systems Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Homogeneous – Heterogeneous tasks Robert Dick Embedded System Design and Synthesis Definitions Scheduling methods Example scheduling applications One-shot – Periodic NEG time IOP DCT FIL FT 68 Homogeneous tasks: All tasks are identical One-shot: Assume that the task set executes once Heterogeneous tasks: Tasks differ Periodic: Ensure that the task set can repeatedly execute at some period Robert Dick Embedded System Design and Synthe

26 Robert Dick Embedded System Design and Synthesis Reliable embedded system design and synthesis Scheduling Overview of real-time and embedded operating systems Embedded application/OS time, power, and energy estimation Homework Algorithm correctness Appropriate responses to transient faults Appropriate responses to permanent faults