Environment Modeling in QuasiStatic Scheduling EE249 Project Donald Chai Mentors Alex Kondratyev Yoshi Watanabe Outline Motivation Method for QSS Problems Environment Modeling Conclusions Environment Modeling in QSS 2 Motivation Schedule some set of processes on one CPU Dynamic scheduling requires overhead for communication and context switching Static scheduling minimizes context switching overhead scheduling for BDF is undecidable QSS is a compromise somewhat like cooperative multitasking by inserting sleeps Environment Modeling in QSS 3 QSS Input Specification comes in FlowC YAPI framework Sequential processes communicate over FIFO channels a process may READ WRITE SELECT nondeterministically from a set of ready input ports Environment Modeling in QSS 4 QSS Algorithm FlowC descriptions are translated into a Petri Net The Petri Net is partitioned into single source schedules QSS is a game between the scheduler and the environment Environment Modeling in QSS 5 Example A system that is not schedulable Is schedulable in the right environment From Claris Cortadella Kondratyev Lavagno Passerone Watanabe INT2002 Environment Modeling in QSS 6 Environment Model Input ports may be fully uncontrollable or fully controllable No known relation between inputs Output ports are always fully controllable Environment Modeling in QSS 7 Problems Boundedness previous example Deadlock two processes B A sequenced by the environment into A B Interference arbitration Environment Modeling in QSS 8 Environment Modeling is the trace containment relation Assume guarantee proof rule states The form we should use is asymmetric Sysabs is QSS schedulable Environment Modeling in QSS 9 Approaches Assume some environment during scheduling check this Construct an abstract environment correct by construction Restrict the power of our model of computation Environment Modeling in QSS 10 Assume then Guarantee Try and see Basically we generate a trace of the assumptions made Not very robust and very compute intensive Environment Modeling in QSS 2 4 11 Guarantee First The environment is abstracted using a set of reduction rules Can be done via trace algebra projection but may be overkill Environment Modeling in QSS 12 Example I Arbiter Module Arbiter Process Environment Modeling in QSS 13 Example II SELECT is reduced Environment Modeling in QSS More reductions 14 Expressiveness Processes look like FCPNs free choice from if statements When add READs and SELECTs looks more like asymmetric choice Environment Modeling in QSS 15 Future Work Partitioning is used extensively for equivalence checking of circuits What would be good places to partition the environment Environment Modeling in QSS 16
View Full Document
Unlocking...