Transcription
Petri Nets – Lecture 1Chen ChenSep. 28th, 20112011/9/28\course\867-11F\Topic-2.ppt1
Outline History of Petri NetsBasic TerminologiesComparing with FSMPetri Net Properties2011/9/28\course\867-11F\Topic-2.ppt2
Invention of Petri Nets C.A. Petri (1962). Kommunikation mitAutomaten. Ph. D. Thesis. University of Bonn. IEEE Computer Pioneer Award (2008)“For establishing Petri net theory in1962, which not only was cited byhundreds of thousands of scientificpublications but also significantlyadvanced the fields of parallel anddistributed computing”Carl Adam Petri1926 –20102011/9/28\course\867-11F\Topic-2.ppt3
Introduction to Petri NetsTheory A theory of systems for modelingconcurrency and synchronization Feature Graphical representation Simplicity Expressiveness for concurrency andasynchronous operations2011/9/28\course\867-11F\Topic-2.ppt4
History of Petri NetsHack (1972)Free-choice Petri NetsSimple Petri NetsHolt and Commoner (1970)Graphical expression of PNMarked Graph1960C.A. Petri (1962)Invention of Petri NetsChiola, Dutheillet, Franceschinis,S. Haddad. (1991)Well-Formed Coloured NetsR. David & H. Alla (1987)Continuous Petri NetsBail, Alla, David (1991)Hybrid Petri NetsKurt Jensen (1981)Colored Petri Nets19701980Ramchandani (1973)Timed Petri NetsHaddad & Poitrenaud (2007)Recursive Petri NetsRudiger Valk (1998)Elementary Object Nets1990M.K. Molly (1982)Stochastic Petri NetsFirst PNExtension of PNSub-class of PNNormalization of PN2011/9/28ISO/IEC 15909 (2011)Petri Nets Standard\course\867-11F\Topic-2.ppt2000Buchs and Guelfi (1991)Object Oriented Petri Net2010E. P. Dawis, J. F. Dawis,Wei-Pin Koo(2001)Dualistic Petri Nets5
Outline HistoryBasic TerminologiesComparing with FSMPetri Net Properties2011/9/28\course\867-11F\Topic-2.ppt6
Example: Critical Section 3 users try to access the same CS Only one user can access CS each time1 token lockp3place3 tokens 3 userst1p1p2Critical F\Topic-2.ppt7
Example: Critical Section Multiple users try to access the same CS Only one user can access CS each -2.pptp2 One user entered CSThe others have to waitt28
Example: Critical Section Multiple users try to access the same CS Only one user can access CS each 67-11F\Topic-2.pptt2One user completes access.Another one can enter now.9
Example: Producer-ConsumerProducer123Task BufferConsumer AConsumer BProducer produces tasks and put the tasks in the task buffer.Consumers take tasks from the task buffer and execute them.One task can only be executed by one consumer – either A or B.2011/9/28\course\867-11F\Topic-2.ppt10
Example: Producer-ConsumerProducer123Task BufferConsumer AConsumer BProducer produced one task.Either A or B can be fired. But only one will be fired!2011/9/28\course\867-11F\Topic-2.ppt11
Example: Producer-ConsumerProducer123Task BufferConsumer AConsumer BAfter firing A or B, the task is executed.2011/9/28\course\867-11F\Topic-2.ppt12
Example: Producer-ConsumerProducerWhat will happenafter token pushing?Task BufferConsumer AConsumer BPetri NetsDataflow (similar structurebut different semantics)What’s the difference between Petri Nets and Dataflow?2011/9/28\course\867-11F\Topic-2.ppt13
Definition of a Petri Net(Self-reading) A Petri Net is a bipartite graph (P,T,A) thatcomprises of A set of transitions: T A set of places: P A set of directed arcs: Aa transition2011/9/28a place\course\867-11F\Topic-2.ppt14
Firing Rules (Self-reading) 2011/9/28\course\867-11F\Topic-2.ppt15
Petri Net Marking (Selfreading) 2011/9/28\course\867-11F\Topic-2.ppt16
Outline HistoryBasic TerminologiesComparing with FSMPetri Net Properties2011/9/28\course\867-11F\Topic-2.ppt17
Example: Two’s Complement What is two’s complement? How to compute two's complement?2011/9/28\course\867-11F\Topic-2.ppt18
Example: Two's Complement(cont.) What is two's complement? How to compute two's complement? flip all bits, and then plus a carry bit Assume B 110, then -B 001 1 0102011/9/28\course\867-11F\Topic-2.ppt19
Example: Two's Complement(cont.) What is two's complement? How to compute two's complement? flip all bits, and then plus a carry bit Assume B 110, then -B 001 1 010 Compute two's complement of 110 from low bit 2011/9/28flip(0) carry bit 1 1 0 & carry bitflip(1) carry bit 0 1 1flip(1) 0\course\867-11F\Topic-2.ppt20
Example: Two's Complement(cont.)0/00/11/1q1q2R means resetof computationR/RR/R1/0State q1: need to add carry bitflip(0) carry bit 1 1 0 carry bitflip(1) carry bit 0 1 1State q2: no need to add carry bit2011/9/28flip(0) 1flip(1) 0\course\867-11F\Topic-2.ppt21
Example: FSM (cont.)0/00/11/1q1q2R/RR/R1/0Now try to compute two's complement of 1102011/9/28\course\867-11F\Topic-2.ppt22
Example: FSM (cont.)123450/00/11/1q1q2R/RR/R1/0Two's complement of 110 is 0102011/9/28\course\867-11F\Topic-2.ppt23
Example: FSM (cont.)1Input sequence : R11Output sequence: 0Computing from low bitR indicates reset23450/00/11/1q1q2R/RR/R1/0Two's complement of 110 is 0102011/9/28\course\867-11F\Topic-2.ppt24
Example: FSM (cont.)1Input sequence : R1Output sequence: 10Computing from low bitR indicates reset23450/00/11/1q1q2R/RR/R1/0Two's complement of 110 is 0102011/9/28\course\867-11F\Topic-2.ppt25
Example: FSM (cont.)1Input sequence : ROutput sequence: 010Computing from low bitR indicates reset23450/00/11/1q1q2R/RR/R1/0Two's complement of 110 is 0102011/9/28\course\867-11F\Topic-2.ppt26
Example: FSM (cont.)123450/00/11/1q1q2R/RR/R1/0Two's complement of 110 is 0102011/9/28\course\867-11F\Topic-2.ppt27
Finite State Machine (FSM)Self-reading 2011/9/28\course\867-11F\Topic-2.ppt28
Important Features of FSMWhat are the features?2011/9/28\course\867-11F\Topic-2.ppt29
Important Features of FSMWhat are the features?FSM is always at a single active state!A single input event triggers state transition!2011/9/28\course\867-11F\Topic-2.ppt30
Important Features of FSMWhat are the features?FSM is always at a single active state!How to represent multiple active statesas a single active state?A single input event triggers state transition!How to represent synchronizationbetween multiple states?2011/9/28\course\867-11F\Topic-2.ppt31
Another Example: 2-StagePipeline ModelingInput sequenceOutput sequenceUnit1Unit2 Unit I (I 1,2)ready to outputbusybcEach unit can be modeledby a three-state FSMaready for input2011/9/28\course\867-11F\Topic-2.ppt32
Another Example: 2-StagePipeline Modeling (cont.)Input sequenceOutput sequenceUnit1Unit2How to model the two units together in FSM?2011/9/28\course\867-11F\Topic-2.ppt33
Another Example: 2-StagePipeline Modeling (cont.)Input sequenceOutput sequenceUnit1Unit2How to model the two units together in FSM?– cross-functional statesState aa’: Unit1 is ready for input & Unit2 is ready for inputState ba’: Unit1 is busy & Unit2 is ready for inputState ca’: Unit 1 is ready to output & Unit2 is ready for input State cc’: Unit 1 is ready to output & Unit 2 is ready to output2011/9/28\course\867-11F\Topic-2.ppt34
Another Example: 2-StagePipeline Modeling (cont.)ab’aa’ac’ba’bb’ca’bc’cc’The structure of the FSM for 2-stage pipelinemodeling. Inputs and outputs are 5
Problems of FSM Modelingof the Pipeline Number of states grows exponentially withthe number of stages The identity of the individual stage lost The structure information is obscured Concurrency / synchronization informationcannot be represented2011/9/28\course\867-11F\Topic-2.ppt36
Try Again: 2-Stage PipelineModeling by PNInput sequenceOutput sequenceUnit1Unit2 Unit I (I 1,2)Done with processingbusyready to outputEach unit can be modeledby 3 places and 3 transitionsOutput resultPickup input data2011/9/28\course\867-11F\Topic-2.pptready for input37
Try Again: 2-Stage PipelineModeling by PN (cont.)Output sequence PipelineInput sequenceUnit1Unit2PNDone with processingDone with processingready to outputbusybusyready to outputOutput resultPickup input dataready for input2011/9/28Unit1 transfers intermediateresult to Unit2\course\867-11F\Topic-2.pptready for input38
Try Again: 2-Stage PipelineModeling by PN (cont.)Unit1Unit2Done with processingbusyDone with processingready to outputready to outputbusyOutput resultPickup input dataUnit1 transfers intermediateready for inputresult to Unit2ready for inputScenario: D1 in the entrance of Unit1D2 in the entrance of Unit12011/9/28\course\867-11F\Topic-2.ppt39
Try Again: 2-Stage PipelineModeling by PN (cont.)Unit1Unit2Done with processingbusyDone with processingready to outputready to outputbusyOutput resultPickup input dataUnit1 transfers intermediateready for inputresult to Unit2ready for inputScenario: D1 being processed by Unit1D2 in the entrance of Unit12011/9/28\course\867-11F\Topic-2.ppt40
Try Again: 2-Stage PipelineModeling by PN (cont.)Unit1Unit2Done with processingbusyDone with processingready to outputready to outputbusyOutput resultPickup input dataUnit1 transfers intermediateready for inputresult to Unit2ready for inputScenario: D1 is done by Unit1D2 in the entrance of Unit12011/9/28\course\867-11F\Topic-2.ppt41
Try Again: 2-Stage PipelineModeling by PN (cont.)Unit1Unit2Done with processingbusyDone with processingready to outputready to outputbusyOutput resultPickup input dataUnit1 transfers intermediateready for inputresult to Unit2ready for inputScenario: D1 being processed by Unit2D2 in the entrance of Unit12011/9/28\course\867-11F\Topic-2.ppt42
Try Again: 2-Stage PipelineModeling by PN (cont.)Unit1Unit2Done with processingbusyDone with processingready to outputready to outputbusyOutput resultPickup input dataUnit1 transfers intermediateready for inputresult to Unit2ready for inputScenario: D1 is done by Unit2D2 being processed by Unit12011/9/28\course\867-11F\Topic-2.ppt43
Try Again: 2-Stage PipelineModeling by PN (cont.)Unit1Unit2Done with processingbusyDone with processingready to outputready to outputbusyOutput resultPickup input dataUnit1 transfers intermediateready for inputresult to Unit2ready for inputScenario: Result of D1 is outputted by Unit2D2 is done by Unit12011/9/28\course\867-11F\Topic-2.ppt44
Try Again: 2-Stage PipelineModeling by PN (cont.)Unit1Unit2Done with processingbusyDone with processingready to outputready to outputbusyOutput resultPickup input dataUnit1 transfers intermediateready for inputresult to Unit2ready for inputScenario: Result of D1 is outputted by Unit2D2 being processed by Unit22011/9/28\course\867-11F\Topic-2.ppt45
Try Again: 2-Stage PipelineModeling by PN (cont.)Unit1Unit2Done with processingbusyDone with processingready to outputready to outputbusyOutput resultPickup input dataUnit1 transfers intermediateready for inputresult to Unit2ready for inputScenario: Result of D1 is outputted by Unit2D2 is done by Unit22011/9/28\course\867-11F\Topic-2.ppt46
Try Again: 2-Stage PipelineModeling by PN (cont.)Unit1Unit2Done with processingbusyDone with processingready to outputready to outputbusyOutput resultPickup input dataUnit1 transfers intermediateready for inputresult to Unit2ready for inputScenario: Result of D1 is outputted by Unit2Result of D2 is outputted by Unit22011/9/28\course\867-11F\Topic-2.ppt47
Conclusion: Compare PNwith FSM PN is powerful in constructing compositemachines. FSM must do cross product. PN is powerful in expressing concurrency.(FSM cannot express concurrency). PN is powerful in expressing pt48
Outline HistoryBasic TerminologiesComparing with FSMPetri Net Properties2011/9/28\course\867-11F\Topic-2.ppt49
Petri Net Properties ReachabilitySafeness and y2011/9/28\course\867-11F\Topic-2.ppt50
Definition of a Petri Net (Self-reading) A Petri Net is a bipartite graph (P,T,A) that comprises of A set of transitions: T A set of places: P A set of directed arcs: A. 2011/9/28 \course\867-11F\Topic-2.ppt 14. a transition. a place
