An Improved Compile Time Scheduling Algorithm for Mixed Data Control Embedded Software Cong Liu Xuanming Dong University of California Berkeley Yoshi Watanbe Alex Kondratyev Cadence Berkeley Lab 11 20 2001 1 Introduction 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 A Process B Environment 2 Introduction System Process 3 Introduction Task Task a sequential program reacting to an event of an uncontrollable input port 4 Introduction 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 Quasi static scheduling Data computing only Total order of operations at compile time 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 time 5 Preliminaries 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 tree 6 Preliminaries 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 ECS Not equal conflict Equal conflict 7 Preliminaries 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 2 Equal place Unique place Choice place 8 Preliminaries 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 control 9 Overview System Specification FlowC Compilation Linking 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 Petri Net UCPN Optimization reduce code size Scheduling Schedule Tree Code generation Code Segments 10 Schedule I Definition a directed graph V E Vertex Marking Edge Transition Properties Exactly one node vertex for M o The set of transitions associated with the outgoing edges of node v is an ECS enable at M v M v T v w 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 cycle 11 Schedule 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 schedule 12 Schedule examples 13 Scheduling 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 t1 Call function EP v r if return r schedule found then call post processing and terminate Termination condition the irrelevance criterion 14 Can 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 15 Firability Incidence matrix A aij aij F tj pi F pi tj State equation Mk 1 Mk A uk where 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 n 16 Cyclic 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 17 Still ahead Identify repeated firable sequence beyond cyclic firing sequences Supporting theories propositions and their proofs Algorithm implementation Experiment From SSS to compound schedule 18 Scheduling Algorithm example a Root 0 EP root ECS d EP v1 ECS d a b c a v1 p1 c b a d v2 p2 d b c a d V10 p1p2 b V3 p3 a b c a d a a a V4 0 V5 p1p3 b c Cycle Return V6 p2p3 V7 p3p3 V12 p2p2 V13 p1p1p2 EP root e ECS d d Irrelevant Irrelevant V9 p1 V8 p3 V11 p1 Cycle 19 Improvement conditions Improvement conditions More than one ECS are enabled at at least one node marking or state Each transition in these ECSs can lead to a cycle Best for schedules with a lot of await nodes 20 Post processing Post processing Retain only part of the created tree The root and its child children are retained A node is w is retained iff Its parent v is retained Or the transition T v w ECS v Create a cycle for each leaf 21 Algorithm Priorities of ECSs ROOT AW1 AW2 AW3 AW4 CURRENT ECSi AW1 ECSj AW2 AW3 AW4 22 Algorithm Basic steps Step1 Build up the schedule tree to identify all cyclic firing sequences from to await nodes Step2 Assign priorities to associated ECSs Definition An ECS is said to be associated to a firing sequence if one of its transitions appears in the firing sequence Step3 The priority of an ECS of node w is the maximum of priorities of ECSs of node v if t v w Step4 In the post processing retain node w if the transition t v w ECS v which has the highest priority 23
View Full Document
Unlocking...