WIXLIB

Reliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkTaxonomyDefinitionsCentral areas of real-time studyTaxonomy of real-time systemsTaxonomyDefinitionsCentral areas of real-time studyStaticTask 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 staticformulations allowing a good solution to the wrong problem.DynamicStatic30Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkSoftEmbedded System Design and Synthesis31TaxonomyDefinitionsCentral areas of real-time studyReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkHardDynamicPeriodicMore slack in implementationBoundedUnboundedMulti rateStatic (compile-time)analysisonly for simplecases.arrival possibleintervalarrivalintervalTiming may be suboptimal without being incorrectEven then, the portion of required processor utilization efficiencygoes to 0.693.PeriodicProblem formulation can be much more complicated than hardreal-timeAperiodicIn many real systems, this is very difficult to apply in reality(more on this later).SoftHardSingle rateMulti rateBoundedarrival intervalUnboundedarrival intervalTwo common (and one uncommon) methods of dealing withnon-trivial soft real-time system requirementsUse the right tools but don’t over-simplify, e.g.,We assume, without loss of generality, that all tasks tionsCentral areas of real-time studyAperiodicSingle rateDynamicEmbedded System Design and SynthesisSoft real-timeTask arrival times unpredictable.StaticRobert DickSoftHardSingle rateSet somewhat loose hard timing constraintsInformal design and testingFormulate as optimization problemAperiodicMulti rateBoundedarrival intervalUnboundedarrival intervalIf you do this people will make jokes about you.32Robert DickEmbedded System Design and SynthesisPeriodicStaticDynamicSoftHardSingle rate33Robert DickEmbedded System Design and SynthesisAperiodicMulti rateReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkBoundedarrival intervalTaxonomyDefinitionsCentral areas of real-time studyHard real-timeUnboundedarrival intervalReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkTaxonomyDefinitionsCentral areas of real-time studyPeriodicEach task (or group of tasks) executes repeatedly with aparticular 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 thatdesigners try to pretend are periodic.34Robert DickEmbedded System Design and Synthesis35Robert DickEmbedded System Design and Synthesis

Reliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkTaxonomyDefinitionsCentral areas of real-time studyPeriodic Single-rateReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkTaxonomyDefinitionsCentral areas of real-time studyPeriodic MultirateMultiple 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.36Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkEmbedded System Design and Synthesis37TaxonomyDefinitionsCentral areas of real-time studyReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkPeriodic OtherRobert DickEmbedded System Design and SynthesisTaxonomyDefinitionsCentral areas of real-time studyAperiodicIt is possible to have tasks with deadlines less than, equal to, orgreater than their periods.Also called sporadic, asynchronous, or reactiveResults in multi-phase, circular-time schedules with multipleconcurrent task instances.Bounded arrival time interval permits resource reservationImplies dynamicUnbounded arrival time interval impossible to deal with for anyresource-constrained systemIf you ever need to deal with one of these, see me (take my code).This class of scheduler is nasty to code.38Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkEmbedded System Design and Synthesis39TaxonomyDefinitionsCentral areas of real-time studyReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkDefinitionsRobert DickEmbedded System Design and SynthesisTaxonomyDefinitionsCentral areas of real-time studyTaskTaskProcessorSome operation that needs to be carried outGraph representationsAtomic completion: A task is all done or it isn’tDeadline violationNon-atomic execution: A task may be interrupted and resumedCost functions41Robert DickEmbedded System Design and Synthesis42Robert DickEmbedded System Design and Synthesis

Reliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkTaxonomyDefinitionsCentral areas of real-time studyProcessorReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkTaxonomyDefinitionsCentral areas of real-time studyTask/processor relationshipWC exec time (s)ToothProcessors execute tasksDistributed systemsRoadFIRContain multiple processorsInter-processor communication has impact on system performanceCommunication is challenging to analyzeMatrix7.7E 6.330E 9.4.1E 6.310E 3.IBMOne processor type: Homogeneous systemIDTPowerPCMultiple processor types: Heterogeneous tionship between tasks, processors, and costsE.g., power consumption or worst-case execution time43Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkEmbedded System Design and Synthesis44TaxonomyDefinitionsCentral areas of real-time studyReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkCost functionsRobert DickEmbedded System Design and SynthesisTaxonomyDefinitionsCentral areas of real-time studyBack to real-time problem taxonomy:Jagged edgesSome things dramatically complicate real-time schedulingThese are horrific, especially when combinedMapping of real-time system design problem solution instance tocost valueData dependenciesUnpredictabilityDistributed systemsI.e., allows price, or hard deadline violation, of a particularmulti-processor implementation to be determinedThese are irksomeHeterogeneous processorsPreemption45Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkEmbedded System Design and Synthesis46TaxonomyDefinitionsCentral areas of real-time studyReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkCentral areas of real-time studyRobert DickEmbedded System Design and SynthesisTaxonomyDefinitionsCentral areas of real-time studyAllocation, assignment, and schedulingHow does one bestAnalyze problem instance specificationsAllocation, assignment and schedulingE.g., worst-case task execution timeOperating systems and schedulingSelect (and build) hardware componentsDistributed systems and schedulingSelect and produce softwareScheduling is at the core or real-time systems studyDecide which processor will be used for each taskDetermine the time(s) at which all tasks will execute48Robert DickEmbedded System Design and Synthesis49Robert DickEmbedded System Design and Synthesis

Reliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkTaxonomyDefinitionsCentral areas of real-time studyAllocation, assignment, and schedulingReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkOperating systems and schedulingHow does one best design operating systems toIn order to efficiently and (when possible) optimally minimizeSupport sufficient detail in workload specification to allow goodcontrol, e.g., over scheduling, without increasing design error ratePrice, power consumption, soft deadline violationsUnder hard timing constraintsDesign operating system schedulers to support real-timeconstraints?Providing guarantees whenever possibleFor all the different classes of real-time problem classesSupport predictable costs for task and OS service executionThis is what I did for a Ph.D.50Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkEmbedded System Design and Synthesis51TaxonomyDefinitionsCentral areas of real-time studyReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkDistributed systems and scheduling. and their schedulesWhy 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 possibleHow 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 Synthesis53TaxonomyDefinitionsCentral areas of real-time studyReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy entral areas of real-time studySlight abuse of notation here, functionality requirements areactually just constraintsfor systems in which computation nodes may be separated by vastdistances such thatReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkEmbedded System Design and SynthesisThe design of a real-time system is fundamentally a costoptimization problemMinimize costs under constraints while meeting functionalityrequirementsThe assignment of tasks to processing nodes.Robert DickRobert DickThe value of formality: Optimization and costsHow does one best dynamically control52TaxonomyDefinitionsCentral areas of real-time studyRobert DickEmbedded System Design and SynthesisDefinitionsScheduling methodsExample scheduling applicationsGraph extensionsJJ1/3J1/33 kb0 kb0 kbJ2/3Thinking of a design problem in terms of optimization gives designteam members objective criterion by which to evaluate the impact ofa design change on quality.Know whether your design changes are taking you in a good directionJ2/3K1/30 kbJ3/3K1/33 kb9 kb9 kb0 kb0 kb0 kbJ3/3K2/33 kbK2/30 kbKa) conventionalK3/3b) pre and post computation0 kbK3/3c) streamingAllows pipelining and pre/post-computationIn contrast with book, not difficult to use if conversion automated54Robert DickEmbedded System Design and Synthesis57Robert DickEmbedded System Design and Synthesis

Reliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkDefinitionsScheduling methodsExample scheduling applicationsProblem definitionABDefinitionsScheduling methodsExample scheduling applicationsTypes of scheduling problemsECDDiscrete time – Continuous timeHard deadline – Soft deadlineUnconstrained resources – Constrained resourcesUni-processor – Multi-processorBDCminimize completion timeAEPE 0PE 1Homogeneous processors – Heterogeneous processorsFree communication – Expensive communicationIndependent tasks – Precedence constraintsHomogeneous tasks – Heterogeneous tasksGiven a set of tasks,One-shot – PeriodicSingle rate – Multiratea cost function,and a set of resources,Non-preemptive – Preemptivedecide the exact time each task will execute on each resource58Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkOff-line – On-lineEmbedded System Design and Synthesis59DefinitionsScheduling methodsExample scheduling applicationsReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkDiscrete vs. continuous timingRobert DickEmbedded System Design and SynthesisDefinitionsScheduling methodsExample scheduling applicationsHard deadline – Soft deadlineSystem-level: ContinuousOperations are not small integer multiples of the clock cycleTasks may have hard or soft deadlinesHigh-level: DiscreteHard deadlineOperations are small integer multiples of the clock cycleTask must finish by given time or schedule invalidImplications:Soft deadlineIf task finishes after given time, schedule cost increasedSystem-level scheduling is more complicated. . . . . however, high-level also very difficult.Can we solve this by quantizing time? Why or why not?60Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkEmbedded System Design and Synthesis61DefinitionsScheduling methodsExample scheduling applicationsReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkReal-time – Best effortRobert DickEmbedded System Design and SynthesisDefinitionsScheduling methodsExample scheduling applicationsUnconstrained – Constrained resourcesWhy make decisions about system implementation statically?Allows easy timing analysis, hard real-time guaranteesUnconstrained resourcesIf a system doesn’t have hard real-time deadlines, resources canbe more efficiently used by making late, dynamic decisionsCan combine real-time and best-effort portions within the samespecificationAdditional resources may be used at willConstrained resourcesLimited number of devices may be used to execute tasksReserve time slotsTake advantage of slack when tasks complete sooner than theirworst-case finish times62Robert DickEmbedded System Design and Synthesis63Robert DickEmbedded System Design and Synthesis

Reliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkDefinitionsScheduling methodsExample scheduling applicationsUni-processor – Multi-processorReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkDefinitionsScheduling methodsExample scheduling applicationsHomogeneous – Heterogeneous processorsUni-processorAll tasks execute on the same resourceHomogeneous processorsThis can still be somewhat challengingHowever, sometimes in PHeterogeneous processorsAll processors are the same typeThere are different types of processorsUsually N P-completeMulti-processorThere are multiple resources to which tasks may be scheduledUsually N P-complete64Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkEmbedded System Design and Synthesis65DefinitionsScheduling methodsExample scheduling applicationsReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkFree – Expensive communicationRobert DickEmbedded System Design and SynthesisDefinitionsScheduling methodsExample scheduling applicationsIndependent tasks –Precedence constraintsNEGFree communicationData transmission between resources has no time costDCTIOPExpensive communicationData transmission takes timeIncreases problem complexityGeneration of schedules for communication resources necessaryUsually N P-completeFILFTIndependent tasks: No previous execution sequence imposedPrecedence constraints: Weak order on task execution order66Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkEmbedded System Design and Synthesis67DefinitionsScheduling methodsExample scheduling applicationsReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkHomogeneous – Heterogeneous tasksRobert DickEmbedded System Design and SynthesisDefinitionsScheduling methodsExample scheduling applicationsOne-shot – PeriodicNEGtimeIOPDCTFILFT68Homogeneous tasks: All tasks are identicalOne-shot: Assume that the task set executes onceHeterogeneous tasks: Tasks differPeriodic: Ensure that the task set can repeatedly execute atsome periodRobert DickEmbedded System Design and Synthesis69Robert DickEmbedded System Design and Synthesis

Reliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkDefinitionsScheduling methodsExample scheduling applicationsSingle rate – MultirateReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded application/OS time, power, and energy estimationHomeworkDefinitionsScheduling methodsExample scheduling applicationsPeriodic graphstimetime3 copies3 copiesperiod 20 msperiod 20 msdeadline 20 msperiod 30 msperiod 30 msdeadline 40 ms2 copiessystem hyperperiod 60 msSingle rate: All tasks have the same periodMultirate: Different tasks have different periods2 copiessystem hyperperiod 60 msComplicates schedulingCan copy out to the least common multiple of the periods(hyperperiod)70Robert DickReliable embedded system design and synthesisRealtime systemsSchedulingOverview of real-time and embedded operating systemsEmbedded appli

33 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 De nitions Central areas of real-t