Berkeley ELENG C249A - An Improved Compile-Time Scheduling Algorithm for Mixed Data-Control Embedded Software - D465630

Home> Schools> University of California, Berkeley> Electrical Engineering (ELENG) > ELENG C249A> An Improved Compile-Time Scheduling Algorithm for Mixed Data-Control Embedded Software

Berkeley ELENG C249A - An Improved Compile-Time Scheduling Algorithm for Mixed Data-Control Embedded Software

School name University of California, Berkeley

Course Eleng C249a- Introduction to Embedded Systems

Pages 23

Download Save

Unformatted text preview:

An Improved Compile-Time Scheduling Algorithm for Mixed Data-Control Embedded SoftwareIntroduction (System & Process)Introduction (System & Process)Introduction (Task)Introduction (Schedule & Scheduling)Preliminaries (Petri net)Preliminaries (ECS)Preliminaries (UCPN)Slide 9OverviewSchedule (I)Schedule (II)Schedule (examples)Scheduling AlgorithmCan we improve?FirabilityCyclic firing sequenceStill aheadScheduling Algorithm (example)Improvement conditionsPost-processingAlgorithm – Priorities of ECSsAlgorithm – Basic steps1An Improved Compile-Time Scheduling Algorithm for Mixed Data-Control Embedded Software Cong Liu, Xuanming DongUniversity of California, BerkeleyYoshi Watanbe, Alex Kondratyev Cadence Berkeley Lab11/20/20012Introduction (System & Process)System: a set of concurrent processesProcess: a sequential program specified in FlowCCommunications with environmentInput ports: (controllable, uncontrollable)Output portsCommunications between processesUnidirectional channels Process AProcess AProcess BProcess BEnvironmentEnvironment3Introduction (System & Process)4Introduction (Task)Task: a sequential program reacting to an event of an uncontrollable input port.5Introduction (Schedule & Scheduling)Schedule: a representation of all possible execution flows of the tasks that can be executed with finite memory for arbitrary input streams.Static scheduling Data computing onlyTotal order of operations at compile-timeQuasi-static scheduling Data computing & Control Data-dependent: IF - THEN-ELSE, FOR loopsSynchronization-dependent: SELECTMost order of operations at compile-timeDynamic scheduling Real-time controlsOrder of operations only at run-time6Preliminaries (Petri net)Petri net: a tuple (P,T,F,Mo)P: places, T: transitions, F: (TP)(PT)  N, weightsMo: initial marking, M: P  N, markingM[p]: the number of tokens at p in MM’[p] = M[p] – F(p,t) + F(t,p), p  P, t  TRepresented by a directed bipartite graphSource transition: F (p,t) = 0,  p  PSink transition: F (t,p) = 0,  p  PReachability tree7Preliminaries (ECS)Equal conflict set (ECS): a set of equal conflict transitionsEqual conflict: if F(p,ti) = F(p,tj),  p  PSpecial case: the set of source transitions, F(p,t) = 0Properties If ti is enabled, then tj is enabled,  ti, tj  ECSThe firing of ti disables the firing of other transitions in the same ECS,  ti  ECSNot equal conflictEqual conflict8Preliminaries (UCPN)Choice place: a place with more than one successor transitionEqual choice place: a choice place whose successor transitions are all in the same ECSUnique place: a choice place with only one successor transition can be enabled in any reachable marking Unique-choice Petri net (UCPN): A PN in which all choice places are either unique or equal 2Equal place Unique placeChoice place9Preliminaries (UCPN)Why choose UCPN as the MoC?Static data flow (SDF): no data-dependent controlBoolean data flow (BDF): undecidableOther variations of data flow graphs: multi-rateFree choice Petri net (FCPN)Multiple rate channelSynchronization-dependent control10OverviewSystem Specification(FlowC)System Specification(FlowC)Petri Net (UCPN)Petri Net (UCPN)Compilation & LinkingCompilation & LinkingSchedule (Tree)Schedule (Tree)Code (Segments)Code (Segments)SchedulingSchedulingCode generationCode generationOptimization(reduce code size)PROCESS GetData (Inport IN….) {Float sum;While (…) {…sum=0;for (…) {READ …;WRITE…;…} …}…}PROCESS Filter (Inport DATA….) {Float c,d;;for (…) {SELECT (….) {CASE DATA;READ …;WRITE…;…}…}…}11Schedule (I) Definition: a directed graph (V,E)Vertex  MarkingEdge  TransitionPropertiesExactly one node (vertex) for MoThe set of transitions associated with the outgoing edges of node v is an ECS enable at M(v)M(v)  M(w), for each edge [v,w]Each node has at least one path to an await nodeEach await node is on at least one cycleT([v,w])12Schedule (II)Single source schedule (SSS) If the same uncontrollable source transition is associated for all the await nodes of a scheduleIndependency of SSSCompound schedule13Schedule (examples)14Scheduling Algorithm Create the root r and set M(r) = MoCreate a node v and an edge [r, v] Associate the transition t1 to the edge, and a marking with v, s.t. M(r)  M(v) holdsCall function EP (v,r), if return r, schedule found, then call post-processing and terminate.Termination condition: the irrelevance criteriont115Can we improve?Key observations There exists the same firing sequence from await nodes, but not generally trueReusing firing sequences can reduce code sizeBig questionsHow could you identify these sequences of transitions?Firability: Is a given sequence of transitions firable at this await node?If it is firable, is there a guarantee that it will return to the initial node (marking)?How to implement it in the algorithm?How much does the new algorithm improve?16FirabilityIncidence matrix A[aij], aij = F(tj,pi) - F(pi,tj)State equationMk+1= Mk + Aukwhere: uk = [0…010…0], the kth element is 1Firability in UCPNA transition is firable at Mk, iff Mk+1  0.A sequence of transitions is firable, iff all transitions are firable, i.e. Mk  0, k=1,…n17Cyclic firing sequenceCyclic firing sequence: A firing sequence is fired from a marking M and the marking obtained after the firing is also MX is a cyclic firing sequence  A  x = 0A : the incidence matrix X = [n1,…, nk], ni = the NO. of occurrences of transition tiPropositionIf x is the cyclic firing sequence from await node M1, and firable from await node M2, then x is also a cyclic firing sequence from M2.18Still aheadIdentify repeated firable sequence beyond cyclic firing sequences Supporting theories: propositions and their proofsAlgorithm implementationExperiment From SSS to compound schedule19Root(0)v1(p1)V12(p2p2)baV13(p1p1p2)v2(p2)V10(p1p2)baV11(p1)d{d}{b,c}{a}{a}{d}{b,c}{a}{a}aCycle!Irrelevant!dV4(0)Cycle!Irrelevant!Return EP=root, ECS={d}EP=v1, ECS={d}bcV3(p3)aV5(p1p3){a}cV7(p3p3)V6(p2p3)V8(p3)d{b,c}{a}V9(p1)eEP=root, ECS={d}Scheduling Algorithm (example)20Improvement conditionsImprovement conditionsMore than one ECS are enabled at at least one node

View Full Document