Hardwarová realizace Petriho sítí

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačů

Bakalářská práce

Hardwarová realizace Petriho sítí Petr Soukup

Vedoucí práce: doc. Ing. Hana Kubátová, CSc. Studijní program: Elektrotechnika a informatika, strukturovaný, Bakalářský Obor: Výpočetní technika 7. ledna 2011

ii

Poděkování Na tomto místě bych chtěl poděkovat doc. Ing. Haně Kubátové, CSc. za cenné rady a připomínky při tvorbě této práce.

iii

iv

Prohlášení Prohlašuji, že jsem svou bakalářskou práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu § 60 zákona č.121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon). V Havlíčkově Brodě dne 7. ledna 2011

……………………………………

v

vi

Abstract This bachelor thesis contains a proposal and implement and the implementation of the model of Petri nets to FPGA. Design model is created and simulation using the program HPSim. The resulting model is divided into component and converted into VHDL. The platform for system design is used Xilinx ISE WebPack 10.1. The result is the visualization into the FPGA Spartan 3E.

Abstrakt Tato práce obsahuje návrh a implementaci modelu Petriho sítě do hradlového pole FPGA. Návrh modelu je vytvořen v programu HPSim a provedena simulace správné funkce. Výsledný model je rozdělen na komponenty a převeden do jazyka VHDL. Jako vývojová platforma je použit návrhový systém Xilinx ISE WebPack 10.1. Výsledkem práce je visualizace modelu do přípravku Spartan 3E.

vii

viii

Obsah

1. Úvod......................................................................................................................................1 2. Popis problému, specifikace cíle........................................................................................3 2.1. Popis řešeného problému.............................................................................................3 2.2 Cíl práce........................................................................................................................3 3. Analýza a návrh řešení........................................................................................................5 3.1. P/T Petriho sítě.............................................................................................................5 3.1.1. Testovací a inhibiční hrany................................................................................6 3.2. Návrh Petriho sítě pomocí programu HPSim...............................................................8 3.2.1 Popis křižovatky v programu HPSim.................................................................8 3.2.2. Řízení semaforů..............................................................................................10 3.2.3. Křižovatka.......................................................................................................10 3.2.4. Popis simulace.................................................................................................12 4. Realizace.............................................................................................................................15 4.1. Popis programovacího jazyka VHDL........................................................................15 4.2. Základní struktura realizovaného modelu..................................................................15 4.3. Popis jednotlivých komponent...................................................................................16 4.3.1. Místo ( Place ).................................................................................................16 4.3.2. Přechod ( Transition )......................................................................................16 4.3.3. Propojení místa a přechodu.............................................................................17 4.3.4. Testovací hrany...............................................................................................17 4.3.5. Inhibiční hrany................................................................................................18 4.3.6. Vjezd automobilů do křižovatky.....................................................................19 4.3.7. Výjez automobilů z křižovatky.......................................................................19 4.3.8. Omezení kapacity místa na jeden token..........................................................19 4.4. Řídící část křižovatky.................................................................................................20 4.4.1. Realizace řídící části křižovatky ...................................................................20 4.5. Systém semaforů........................................................................................................21 4.6. Křižovatka..................................................................................................................22 4.7. Zobrazení průjezdu automobilů a zobrazení semaforů..............................................25 4.7.1. Timer...............................................................................................................26 4.7.2. Připojení Timeru ke komponentám ................................................................27 4.8. Zobrazení textu na LCD displeji................................................................................29 5. Závěr...................................................................................................................................31 6. Literatura...........................................................................................................................33 7. Přílohy................................................................................................................................35

ix

7.1. Úvod do Petriho sítí........................................................................….......................35 7.2. Modelování diskrétních systémů Petriho sítěmi........................................................36 7.2.1. Struktura P/T Petriho sítí.................................................................................37 7.2.2. Incidenční funkce............................................................................................37 7.2.3. Incidenční matice............................................................................................38 7.3. Vlastnosti Petriho sítí.................................................................................................40 7.3.1. Ohraničená síť.................................................................................................40 7.3.2. Živá síť............................................................................................................40 7.3.3. Reverzibilní síť................................................................................................41 7.3.4. Konzervativní síť ...........................................................................................41 7.4. Matematické definice Petriho sítí...............................................................................42 7.5. Popis hardwaru pro realizaci......................................................................................46 7.5.1 Základní architektura obvodu FPGA .............................................................48 8. Obsah přiloženého CD......................................................................................................51

x

Seznam obrázků

Seznam obrázků Obr. 3.1.

Popis značení v Petriho sítích.................................................................................5

Obr. 3.2.

Odpálení přechodu v Petriho síti s ohodnocenými hranami...................................6

Obr. 3.3

Model připojovacího pruhu.....................................................................................7

Obr. 3.4

Kompletní model křižovatky...................................................................................9

Obr. 3.5.

Řídící část semaforu..............................................................................................10

Obr. 3.6.

Křižovatka a očíslování semaforů.........................................................................11

Obr. 3.7.

Část modelu křižovatky.........................................................................................12

Obr. 3.8. Token prošel přechodem T2 a nachází se v místě P3............................................12 Obr. 3.9.

Aktuální stav simulace v křižovatce, přes zeleně označené přechody již token prošel....................................................................................................................13

Obr. 4.1.

Blokové schema realizovaného modelu................................................................15

Obr. 4.2.

Schematické znázornění místa..............................................................................16

Obr. 4.3.

Schematické znázornění přechodu........................................................................16

Obr. 4.4.

Implementace místa a přechodu, odpálením dojde k vyresetování příslušných míst modelu...........................................................................................................17

Obr. 4.5.

Implementace testovací hrany...............................................................................18

Obr. 4.6.

Implementace inhibiční hrany vložením invertoru...............................................18

Obr. 4.7.

Implementace vjezdu automobilu do křižovatky..................................................19

Obr. 4.8.

Implementace výjezdu automobilů z křižovatky...................................................19

Obr. 4.9.

Implementace omezení kapacity...........................................................................19

Obr. 4.10. Část řizení s výstupní testovací hranou.................................................................20 Obr. 4.11. Simulace řídícího okruhu......................................................................................21 Obr. 4.12. Simulace semaforů................................................................................................22 Obr. 4.13. Testovací hrany ze semaforu.................................................................................22 Obr. 4.14. Základní rozvržení směrů křižovatky....................................................................23 Obr. 4.15. Více přechodů do jednoho místa...........................................................................24 Obr. 4.16. Simulace celé křižovatky.......................................................................................25 Obr. 4.17. LED diody přípravku a jejich implementace........................................................26 Obr. 4.18. Časování................................................................................................................26 Obr. 4.19. Průběh simulace komponenty Timer.....................................................................27 Obr. 4.20. Propojení komponenty Timer a Place...................................................................27

xi

Obr. 4.21. Simulace průběhu s použitím signálu SIG............................................................28 Obr. 4.22. Schéma křižovatky s komponentou Timer............................................................28 Obr. 4.23. Blokové schema LCD driveru...............................................................................29 Obr. 4.24. Umístění textu v paměti RAM..............................................................................30 Obr. 4.25. LCD display s textem............................................................................................30 Obr. 7.1.

Distribuce stavu na parcialní stavy........................................................................36

Obr. 7.2.

Odpálení přechodu Petriho sítí..............................................................................36

Obr. 7.3.

P/T Petriho síť.......................................................................................................38

Obr. 7.4.

Základní popis desky Spartan 3E..........................................................................46

Obr. 7.5. Typická struktura obvodu FPGA...........................................................................46 Obr. 7.6.

Struktura konfigurovatelného bloku.....................................................................46

Obr. 7.7.

Základní architektura přípravku Spartan 3E.........................................................49

xii

Kapitola 1- Úvod

1. Úvod Oblast Petriho sítí se nejčastěji uplatňuje při návrhu, modelování a analýze distribuovaných systémů. Jako příklad si můžeme uvést telekomunikační systémy, automatizované průmyslové systémy, databázové systémy. Použití modelovacích schopností Petriho sítí má důležitý význam v této práci, neboťpři vytváření modelu můžu provést analýzu funkčnosti ještě před vlastním reálným návrhem. Reálný návrh je vlastně převod částí Petriho sítě do jazyka VHDL a vytvoření funkčního celku z těchto komponent.

1

Kapitola 1- Úvod

2

Kapitola 2 – Popis problému, specifikace cíle

2. Popis problému, specifikace cíle

2.1. Popis řešeného problému Petriho sítě představují návrh a modelování určité problematiky na teoretické bázi. Stěžejní částí této práce je hardwarová realizace, což znamená převedení prvků Petriho sítě do jazyka VHDL a jejich implementace do hradlového pole přípravku Spartan 3E. Jako vhodný model jsem si zvolil křižovatku se semafory a řídícím okruhem. Pro vlastní návrh jsem zvolil grafický editor HPSim, který umožňuje rychle a intuitivně navrhnout vybraný model. Výsledkem je návržený systém, skládající se z míst, přechodů, testovacích a inhibičních hran. Pro hardwarovou implementaci jsem použil vývojové prostředí Xilinx ISE WebPack 10.1., ve kterém provedu vytvoření projektu s klíčovými komponenty Petriho sítě, převedenými do jazyka VHDL. Výsledný návrh odsimuluji v programu ModelSim pro kontrolu správné funkčnosti a nahraji do hradlového pole zkušebního přípravku Spartan 3E.

2.2 Cíl práce Cílem této práce je: 1. provést návrh křžovatky pomocí Petriho sítí a) v programu HPSim provést návrh křižovatky b) otestovat funkčnost, provést simulaci 2. provést převod do jazyka VHDL a realizace do základní desky přípravku Spartan 3E a) pomocí Xilinx ISE WebPack provést návrh a odladění projektu b) naprogramování do přípravku Spartan 3E a konečná visualizace projektu

3

Kapitola 2 – Popis Problému, specifikace cíle

4

Kapitola 3 – Analýza a návrh řešení

3. Analýza a návrh řešení Kapitola obsahuje základní seznámení s problematikou Petriho sítí. Jelikož rozsah Petriho sítí přesahuje rámec této kapitoly, uvedu zde základní popis. Podrobnější vysvětlení a popis Petriho sítí jsem odsunul do přílohy bakalářské práce. Před realizací provedu návrh modelu pomocí programu HPSim, kde si ověřím správnou funkčnost modelu a otestuji průběh simulace. Návrh řešení spočívá v realizaci komponent v jazyku VHDL na bázi Petriho sítí. Z těchto komponent je potom složen výsledný model křižovatky.

3.1. P/T Petriho sítě Místo dlouhé teorie jsem zvolil popis Petriho sítí pomocí obr. 3.1., na kterém vidíme část křižovatky nakreslenou pomocí P/T Petriho sítí ( Place/Transition Petri Nets ). Obsahuje místa, přechody, orientované, testovací a inhibiční hrany, použité v této práci.

Obr. 3.1. Popis značení v Petriho sítích 5

Kapitola 3 – Analýza a návrh řešení Dále bych chtěl zmínit, že každá orientovaná hrana sítě je udána svoji vahou, kterou charakterizuje přirozené číslo, určující její násobnost. Tím, že odpálíme přechod, tak z místa odebereme tolik tokenů, kolik je hodnota hrany, která spojuje toto místo s přechodem. Následující místo obrží stejný počet tokenů podle hodnoty příslušné hrany. Hrana, která není v grafu sítě explicitně ohodnocena, má váhu jedna. Blíže nám to charakterizuje obr. 3.2. Každé místo v sítí můžeme určit počátečním značením, které charakterizuje počtem tokenů v tomto místě.

Obr. 3.2. Odpálení přechodu v Petriho sítí s ohodnocnými hranami. Obrázek (a) znázorňuje stav před odpálením, obrázek (b) po odpálení [6] Značení místa může být neomezené, tj. může nabývat libovolné celočíselné hodnoty nebo může být omezeno kapacitou místa. To je dáno celým kladným číslem udávajícím maximální možný počet značek v daném místě. Kapacitní omezení se využívá při modelování situací, kdy chceme vyloučit přeplnění např. vyrovnávací paměti nebo délky fronty. V takovém případě je pravidlo pro provedení přechodu doplněno o podmínku na značení výstupních míst přechodu. Přechod může být proveden, jestliže nebude překročena kapacita jeho některého výstupního místa. [6]

3.1.1. Testovací a inhibiční hrany Testovací hranu používáme pro vstupní podmínky a to v případě, že pro odpal přechodu testovaná podmínka musí být splněna. Důležitá věc je ta, že odpalem přechodu se platnost podmínky nezmění. Počet tokenů se v místě spojeném s přechodem testovací hranou nezmění. V grafické reperezentaci jí označujeme čárkovanou čarou. Testovací hrana může být také jako obyčejná hrana ohodnocená. Pro to, aby byl přechod v aktuálním značení aktivní, je nutné, aby počet tokenů v místě byl alespoň roven hodnotě testovací hrany. [6] Použití testovacích hran nepředstavuje žádné rozšíření simulačních schopností Petriho sítí, ani žádné větší zjednodušení, protože testovací hranu můžeme nahradit přidáním hrany s opačnou orientací. Výhodou jejich použití je jen o něco přehlednější grafická repezentace. [6] Inhibiční hrana ( Inhibitor ) je dodatečná speciální podmínka přechodu reprezentovaná 6

Kapitola 3 – Analýza a návrh řešení dodatečnou vstupní hranou přechodu. Je-li místo spojeno s přechodem inhibitorem, pak je přechod aktivní jen pokud bude ve vstupním místě méně tokenů než je ohodnocení inhibitoru. V grafické reprezentaci ho znázorňujeme jako vstupní hrany, zakončené kolečkem. Inhibiční hrana směřuje výhradně od míst k přechodům. Počet tokenů se v místě spojeném s přechodem inhibitorem nezmění. Modelovací síla Petriho sítí s inhibičními hranami je stejná jako modelovací síla Turingových strojů1. [6] Na obr. 3.3. vidíme zjednodušený model připojovacího pruhu na dálnici, hlavní silnice je vstup A, připojovací pruh vstup B. Vozidla ze vstupu B mohou vjet do místa “pripoj“ jen v případě, že bude na hlavní silnici ( místo P1 ) volno, tzn, místo P1 bude bez tokenu. To nám právě zajišťuje inhibiční hrana mezi místem P1 a přechodem T2. [6]

Obr. 3.3 Model připojovacího pruhu [6]

1

Turingův stroj ( Turing machine ) navrhl anglický matematik Alan M. Turing v roce 1936 jako abstraktní model číslicového počítače. Turingův stroj je podobný konečnému automatu, ale má k dispozici nekonečně velkou paměť díky niž je schopen namodelovat jakýkoliv výpočet ( Churchova teze ). Přestože Churchovu tezi nikdy nebude možné dokázat, je všeobecně považována za platnou.

7


3.2. Návrh Petriho sítě pomocí programu HPSim Pro návrh křižovatky pomocí Petriho sítí byl využit program HPSim [10]. Je to německý grafický editor se základními simulačními schopnostmi pro tvorbu P/T Petriho sítí. HPSim slouží pro návrh a simulaci Petriho sítí v grafické podobě. Po vytvoření modelu můžeme spustit simulaci a to buď v průběžném režimu nebo krokovém režimu. Práce s programem je intuitivní, provedeme výběr místa a přechodu, umístíme je na kreslící plochu a provádíme jejich propojení pomocí hran určených směrem.

3.2.1 Popis křižovatky v programu HPSim Pro popis křižovatky v programu HPSim jsem vycházel z návrhu křižovatky podle [2]. Pro simulaci a analýzu byl vytvořen model, který se skládá z řídící části, která generuje jednotlivé světelné fáze, systému semaforů pro řízení a dále samotného modelu křižovatky, představujícího jednotlivá místa do kterých se mohou auta během svého průjezdu dostat. Křižovatkou budou projíždět automobily, to je v tomto programu realizováno přechody a místy. Vjezd do křižovatky představuje místo s nastavenou kapacitou místa, což nám značí počet aut na simulační cyklus. Výjezd automobilů z křižovatky je realizován také místem, taky kapacitně omezených, ve kterých síť končí a nikam dále už nevede. Dále jsou zde pro každý hlaní směr čtyřramenné křižovatky semafory, které povolují nebo zakazují průjezd automobilů v jednotlivých směrech na klíčových přechodech. Do modelu je potřeba vložit značky jako počáteční stav sítě. Značky ( tokeny ) jsou umístěné v místě P0 řídícího okruhu, ve žlutých barvách všech semaforů a na pozicích vjezdu automobilů do křižovatky. Na následujícím obrázku vidíme kompletní model křižovatky, tokeny jsou zobrazeny jako černá tečka.

8


Obr. 3.4 Kompletní model křižovatky

9


3.2.2. Řízení semaforů Pro řízení semaforu je čas nahrazen přechody a stavy jdoucími za sebou, poněvadž P/T Petriho sítě nejsou schopny vyjádřit pojem čas. Řízení semaforu obsahuje přechody mezi čtyřmi stavy. První stav, jdoucí z místa P0 ve formě testovací hrany povoluje provedení přechodu T23, kterým se provede přepnutí fází na semaforech v křižovatce na zelenou pro semafory č. 2 a č. 4 a červenou pro semafory č.1 a č.3. Tímto je umožněn volný průjezd automobilů ve směru sever-jih a jih-sever. V druhé fázi řízení jde testovací hrana z místa P9 do přechodu T25, po jeho odpálení se přepnou všechny semafory na žlutou barvu. V další fázi z místa P11 jde testovací hrana do přechodu T24, po jeho odpálení se přepnou semafory č. 1 a č. 3 na zelenou barvu a semafory č.2 a č.4 na červenou. Tímto je umožněn průjezd automobilů ze směrů východ-západ a západ-východ. Konečně po dosažení poslední fáze z místa P13 testovací hranou do přechodu T22 po odpálení se provede opět přepnutí všech semaforů na žlutou barvu. Tento cyklus se potom dále neustále opakuje.

Obr. 3.5. Řídící část semaforu

3.2.3. Křižovatka Značky v každém místě křižovatky představují auta, které projíždějí daným směrem. Vstupní místa vjezdu automobilů do křižovatky ( P35, P78, P46, P81, P49, P75, P56, P72 ) jsou nastavena na kapacitu 20 aut. Výstupní místa výjezdu automobilů z křižovatky jsou kapacitně omezena na 100. Průjezd aut křižovatkou je možný v přímém směru a odbočením doprava. Bezpečnost průjezdu aut je zajištěna tím, že jsou všechny místa ( vyjma výše jmenovaných ) kapacitně omezena na 1, což znamená, že v jednom místě může být maximálně jeden automobil.

10


Obr. 3.6. Křižovatka a očíslování semaforů

Na obr. 3.7. vidíme jednu část křižovatky, která se nám opakuje čtyřikrát a na které si popíšeme její funkci. Automobil se po vjezdu do křižovatky dostane do místa P47, ze kterého po odpálení přechodu T58 odbočuje doprava a druhým pruhem do místa P77, ze kterého po odpálení přechodu T48 pokračuje rovně.Toto nám je umožněno navíc za předpokladu, že svítí zelená světla na semaforu č.4, tzn. testovacími hranami, jdoucímí do těchto zmíněných přechodů. Navíc v místech P61 a P62 nesmí být auto, toto nám zajišťují inhibiční hrany, vedené z těchto míst do přechodů T48 a T58. Auto jedoucí ze směru západ-východ z místa P61 do místa P38, odpálením přechodu T41, tak mají přednost před automobily v místě P47 a P77, protože inhibiční hrany, které jdou z místa P61 do přechodů T63, T58 provedení těchto přechodů zakazují. Navíc tento průjezd je umožněn signálem červené na semaforu č.4 pro auta jedoucí z jihu.

11


Obr. 3.7. Část modelu křižovatky

3.2.4. Popis simulace Vlastní simulaci navrženého modelu spustíme tak, že v menu na liště zvolíme "Simulation" a vybereme "Sim Mode". Automaticky se nám otevře okno s o stavu naší sítě během simulace. Okno zavřeme a na liště se nám zobrazí ikony pro spuštění simulačního programu a to buď v automatickém nebo krokovém módu. Tím se začnou pohybovat jednotlivé tokeny mezi jednotlivými místy sítě a mi si můžeme zkontrolovat korektnost průběhu simulace. Rychlost průběhu simulace lze korigovat posuvníkem v horní části lišty. Aktuální průchod tokenu přechodem se nám zvýrazní zelenou barvou. Ukázky simulace vidíme na obr. 3.8. a obr. 3.9.

Obr. 3.8. Token prošel přechodem T2 a nachází se v místě P3

12


Obr. 3.9. Aktuální stav simulace v křižovatce, přes zeleně označené přechody již token prošel

13


14

Kapitola 4 - Realizace

4. Realizace

4.1. Popis programovacího jazyka VHDL Jako programovací jazyk byl zvolen jazyk VHDL. Zkratka znamená Very High Speed Intergrated Circuits Hardware Description Language a je to jazyk vysoké úrovně navržený speciálně pro účely popisu návrhu a simulace velmi rozsáhlých číslicových obvodů a systémů. Jedná se tedy o jazyk pro popis hardware. Výhodou tohoto jazyka jsou jeho bohaté vyjadřovací schopnosti a nezávislost číslicového systému popsaného jazykem VHDL na cílové technologie jeho realizace nebo výroby. Vytvořený kód v tomto jazyce ještě navíc prochází syntézou, jejichž výsledkem bude zapojení z hradel a klopných obvodů [15]. Jazyk VHDL byl vyvinut v osmdesátých letech na popud US. Ministerstva Obrany a v roce 1987 bylo ustanoveno jako IEEE 1076 standard. V roce 1994 byl tento standard rozšířen a dnes jako IEEE standard 1076 1993, označovaný také jako VHDL - 93. VHDL je stále dále vyvíjeno s pracovním značením VHDL – 200x [17].

4.2. Základní struktura realizovaného modelu Zjednodušené blokové schéma realizovaného systému vidíme na obr.4.1. Celý návrhu systému je možno rozdělit na řídící okruh, vlastní síť se systémem semaforů a výstup na LED diody a LCD display.

Obr. 4.1. Blokové schema realizovaného modelu

15


4.3. Popis jednotlivých komponent Celý systém řízení křižovatky se skládá z několika klíčových komponent. Předně je třeba uvést komponenty vycházející z principu fungování Petriho sítí a jejich převodu do VHDL. Při popisu jednotlivých komponent jsem vycházel z bakalářské práce podle [1].

4.3.1. Místo ( Place ) Pro implementaci místa použijeme klopný obvod typu D, který obsahuje vstup hodinového signálu a resetovací vstup. Princip činnosti je takový, že máme na vstupu D log 1 ( příchozí token ), po příchodu náběžné hrany hodin signalu clock dojde k přesunu log 1 na výstup Q ( odchod tokenu ). V rámci implementace této práce není nutné implementovat do tohoto obvodu pomocný čítač tokenů, protože příjde a odejde vždy jeden token. Omezení kapacity místa bude znázorněno později. Více tokenů v jednom místě by znamenalo kolizi automobilů. V návrhu se také nachází speciální typ místa, v němž je na počátku token. Implementováno pomocí automatu, jehož počátečním stavem je jednička. Jakmile token odejde z místa, přejde automat do následujícího stavu, fungujícího jako klasické místo.

Obr. 4.2. Schematické znázornění místa

4.3.2. Přechod ( Transition ) K vytvoření přechodu stačí hradlo AND. Podle principu logického součinu platí, že aby se na výstupu objevila log 1 ( došlo k odpálení přechodu ), musí být log 1 na všech jeho vstupech. Implementačně jsou vstupem tohoto hradla všechny výstupní hrany všech vstupních míst přechodu.

Obr. 4.3. Schematické znázornění přechodu 16

Kapitola 4 - Realizace Prostým pospojováním těchto dvou prvků nám síť samozřejmě fungovat nebude. Pro korektní funkci musíme provést drobné úpravy. V první řadě musí být vytvořena zpětná vazba z přechodu zpět do místa, aby místo vědělo, jestli token odešel přes přechod. Hodnota log 1 musí zůstat v místě do doby, než dojde k odpálení přechodu Na vstupu místa musí být předřazeno hradlo OR, které má funkci udržování log 1 do doby, než dojde k odpálení přechodu. Výstup z přechodu ( hradlo AND ) jde do dalších míst a navíc je použit k resetu všech vstupních míst daného přechodu, což nám zaručí, že po odpálení přechou dojde k vyresetování daného místa.

4.3.3. Propojení místa a přechodu

Obr. 4.4. Implementace místa a přechodu, odpálením dojde k vyresetování příslušných míst modelu

4.3.4. Testovací hrany Rozšířením modelovacích schopností Petriho sítí jsou testovací a inhibiční hrany. Testovací hrana nám určuje vstupní podmínku pro splnění přechodu. Co se týče samotné implementace těchto hran, tak v modelu zajišťují splnění klíčových přechodů pro vjezd automobilů do křižovatky a jsou směrovány od světel semaforu k těmto přechodům. Důležitým poznatkem je, že tyto hrany neodebírají token ( neresetují místo ). Implementačně to znamená, že resetovací vstup konkrétního místa není zapojen. Orientační ukázku zapojení můžeme vidět na obr. 4.5.

17


Obr. 4.5. Implementace testovací hrany

4.3.5. Inhibiční hrany Implmentace inhibiční hrany v modelu se provede negací signálu, což můžeme znázornit vložením invertoru mezi místo a přechod. Pokud je v tomto místě log 1 značící token, tak přes invertor se k přechodu dostane log 0, což neumožní hradlu AND provedení ( odpálení ) přechodu.

Obr. 4.6. Implementace inhibiční hrany vložením invertoru Model Petriho sítě představuje křižovatku, musíme proto také vyřešit vjezd a výjezd automobilů. K tomuto jsou imlementovány dvě komponenty. Jedna zajišťuje vjezd automobilů do křižovatky, druhá výjez automobilů z křižovatky ven.

18


4.3.6. Vjezd automobilů do křižovatky Vstupní místo vjezdu automobilů do křižovatky je implementováno tak, že na vstup místa je neustále připojena log 1 a nedochází k resetování místa. To nám zajišťuje, že automobily přijíždí neustále. V simulačním programu HPSim je tato situace vyřešena jednoduše kapacitním omezením místa.

Obr. 4.7. Implementace vjezdu automobilu do křižovatky

4.3.7. Výjez automobilů z křižovatky Výjezd je koncipován tak, že resetovací signál je trvale připojen na nulu, tzn. jakmile dorazí token ( příjezd auta ), tak se automaticky smaže. Tímto se implementuje výjezd automobilů z křižovatky.

Obr. 4.8. Implementace výjezdu automobilů z křižovatky

4.3.8. Omezení kapacity místa na jeden token Výstup místa je propojen s přechodem ( hradlo AND ) před vstupem tohoto místa a je znegován. Tímto nemůže dojít k odpálení jeho vstupního přechodu a „nasunutí“ dalšího tokenu do tohoto místa.

Obr. 4.9. Implementace omezení kapacity

19


4.4. Řídící část křižovatky Řídící část je realizována jako posloupnost míst a přechodů jdoucí za sebou. Vstupem této komponenty je pouze hodinový signál.Výstupy komponenty jsou testovací hrany vycházející z předem daných míst a jdoucí do klíčových přechodů T23, T25, T24 a T22. Tyto přechody pak signál dále rozvádějí do míst označených jako barvy semaforu. Z přechodu T23 ( první fáze ) nám výstupní hrany směřují do semaforu a zajišťují rozsvícení zelených a červených světel. Semafor č.2 jako zelená, do semaforu č.3 jako červená, do semaforu č.1 jako červená a do semaforu č.4 jako zelená. Vždy jsou volné směry proti sobě a zbylé dva mají červenou. Z přechodu T25 (druhá fáze ) jdou signály na žlutá světla všech semaforů. Z přechodu T24 ( třetí fáze ) dochází k přepínání semaforů tak, že kde původně byla zelená, tak tam je červená a naopak. Z přechodu T22 ( čtvrtá fáze ) se semafory přepínají na žlutou barvu. Takhle se to opakuje celé dokola jako nekonečná smyčka. Vyplnění jednotlivých fází místy a přechody nám zaručí určitou časovou prodlevu. Časová prodleva tímto způsobem je samozřejmně možná pouze v simulaci. Při realizaci do přípravku je nutné implementovat komponentu, která nám zaruční zpomalený průchod přes místa a přechody.

4.4.1. Realizace řídící části křižovatky V programu Xilinx ISE vytvořena komponenta řízení, která se skládá z klíčových komponent Place ( místo ), Transition ( přechod ) a Start_Place ( počáteční pozice s tokenem – místo P0). Výstupy z této entity jsou čtyři signály F1, F2, F3, F4, které jdou do přechodů T23, T25, T24, T22. Hrany mezi místy a přechody jsou označeny pomocnými signály H, pomocí kterých namapujeme spojení řídícího okruhu. S realizací této komponenty jsem nezaznamenal vážnější problém.

Obr. 4.10. Část řizení s výstupní testovací hranou Pro otestování správné funkce řídícího systému byl k VHDL souboru vytvořen testbench 20

Kapitola 4 - Realizace soubor. Vstupem je hodinový signál t_clk a výstupem jsou výstupní signály z řízení t_f1, t_f2, t_f3, t_f4. Korektní výsledek simulace můžeme vidět na obr. 4.11.

Obr. 4.11. Simulace řídícího okruhu

4.5. Systém semaforů V křižovatce jsou instalovány čtyři semafory, které umožňují průjezd vozidel všemi dovolenými směry. V programu Xilinx je vytvořena komponenta semafor, kde společně s komponentou řízení má hlavní funkci pro řízení celé křižovatky. V této komponentě jsou implementovány signály Z1,C1,Z2,C2,Z3,C3,Z4,C4, které slouží jako výstupní signály ze semaforu pro umožnění nebo zakázání průjezdu automobilů v křižovatce. Semafory jsou vlastně další místa v křižovatce, pomocí nichž a určených přechodů se rozvádí signály zelené a červené barvy ve formě testovacích hran na klíčové přechody v křižovatce. Pří realizaci nebyl zaznamenán vážnější problém. Správná funkčnost je opět ověřena pomocí programu ModelSim, kde průběhy signálů vidíme na obr.4.12. Vstupem je hodinový signál a výstupem jsou červené a zelené signály čtyř semaforů: t_z1 – zelená ze semaforu 1, t_c1 -červená ze semaforu 1, t_z2 – zelená ze semaforu 2, t_c2 -červená ze semaforu 2, t_z3 – zelená ze semaforu 3, t_c3 -červená ze semaforu 3, t_z4 – zelená ze semaforu 4,t_c4 -červená ze semaforu 4. V prvním cyklu vidíme volný průjezd ze směrů východ-západ a západ-východ ( t_z1 a t_z3 v log1 ) a stop pro směry sever-jih a jih-sever ( t_c2 a t_c4 v log1 )

21


Obr. 4.12. Simulace semaforů Na obr. 4.13. vidíme signál červené do přechodu T63 a signál zelené do přechodů T48 a T58.

Obr. 4.13. Testovací hrany ze semaforu

4.6. Křižovatka Průjezd křižovatkou je v každém směru povolen přímo a doprava. Schematicky je to znázorněno na obr. 4.14. Vstupní místa křižovatky nám simulují vjezd automobilů, což je implementováno tak, že je neustále na vstupu log 1 a reset není zapojen. Tímto dosáhneme toho, že auta přijíždí 22

Kapitola 4 - Realizace neustále. Na konci každé části křižovatky jsou konečná místa, simulující odjezd automobilů. Implementováno tak, že výstup je připojen na reset a s každým výstupem se provede resetování příslušného místa.

Obr. 4.14. Základní rozvržení směrů křižovatky

V celém modelu křižovatky není jenom přímé propojení míst a přechodů. Vzhledem k různým a křížícím se jízdních směrů dochází k situacím, kdy nelze jednoduše provést mapování, je třeba použít drobných úprav. Zde si vypíšeme a znázorníme určité situace v systému křižovatky. Jedna ze situací je ta, kdy se více jízdních pruhů schází v jeden. Na obr. 4.15. jdou do místa P55 výstupy ze tří přechodů T64, T30 a T59. Provedeme mapování místa P55 s tím, že jako vstupní signál bude označení vstupu I_P55, do kterého nasměrujeme výstupy z těchto přechodů s použitím logické funkce OR. I_P55 <= O_T59 or O_T30 or O_T64 or O_T67

23


Obr. 4.15. Více přechodů do jednoho místa Dále na obr. 4.15. vidíme, že do přechodu T59 vstupují inhibiční hrany z míst P63 a P64 a také signál zelené barvy od semaforu č.1. Tedy průjezd křižovatkou ze směru vychod-vpravo bude možný za předpokladu, že z jihu nebudou v místech P63 a P64 žádná vozidla a na semaforu bude zelená barva. Opět výpis pomocí logických funkcí NOT a AND. I_T59 <= O_P37 and (not O_P55) and (not O_P63) and (not O_P64) and O_Z1; Na obr. 4.16. z programu ModelSim můžeme vidět celý průběh simulace křižovatky. Jsou zde výstupy směrů průjezdu křižovatkou a signály zelené barvy pro všechny směry. Simulace nám ukazuje dva průjezdy křižovatkou.

24


Obr. 4.16. Simulace celé křižovatky Průjezd automobilu ze směru sever a jih, rovně a doprava

Zelená barva na semaforech ve směru sever-jih a jih-sever

4.7. Zobrazení průjezdu automobilů a zobrazení semaforů Dlouho jsem přemýšlel, jak implementovat do přípravku zobrazení průjezdu automobilů křižovatkou a zobrazení semaforů. Vyřešil jsem to tak, že jsem si zvolil kontrolní přechody a z těch vyvedu signál na LED diody. Pro směr západ-východ to je přechod T50, pro směr východ-západ to je přechod T51, pro směr jih-sever to je T52 a pro směr sever-jih to je T53. Na přípravku Spartan 3E, kde je celkem 8 LED diod, budou pro toto zobrazení vyhrazeny 4 zelené LED diody přípravku pro čtyři přímé směry v křižovatce, jsou označeny LED_JR, LED_SR, LED_VR, LED_ZR.Zbylé čtyři zelené LED diody jsou pro zobrazení zelených světel na semaforu pro příslušný směr jízdy, označených LED_Z1, LED_Z2, LED_Z3,LED_Z4. Zapojení těchto LED diod přípravku je provedeno ve ucf soubor, kterým se výstupní signály namapuje přímo na piny přípravku Spartan 3E. Myslím si, že takto provedená visualizace je plně dostačující. Více diod na přpravku není k dispozici, navíc nějaké zapojení tak, aby jedna dioda měla více zobrazovacích funkcí by působilo hodně nepřehledně.

25


Obr. 4.17. LED diody přípravku a jejich implementace

4.7.1. Timer Aby bylo možné na přípravku korektně zobrazit visualizaci projektu, je nutné realizovat komponentu, která provede na základě vstupního hodinového signálu výstupní povolovací signál SIG, kterým s pomocí hlavního kmitočtu bude použit k řízení. Komponenta funguje tak, že je v ní implementován čítač, který na základě hodinového signálu provádí čítání až do určité nastavené hodnoty. Až této hodnoty dosáhne, provede se nastavení signálu SIG na log 1 a zároveň se provede vynulování čítače a čítá se znovu. Přípravek Spartan 3E má kmitočet 50 Mhz, což znamená periodu 20ns. Použil jsem 25-ti bitový čítač s nastaveným čítáním do hodnoty 24999999, tím vychází takt signalu SIG na 0.5s. Důležité je, že se pro řízení bude používat stále signál CLK, výstup z komponenty Timer bude fungovat jako povolovací signál, aby byla zaručena synchronnost návrhu.

Obr. 4.18. Časování

26

Kapitola 4 - Realizace Výsledek simulace vidíme na obr. 4.19, kde clk je hodinový signál a v určité fázi je signál sig v log 1. Pro účely simulace jsem použil 4-bitový čítač, aby nebyl problém se zobrazením simulace, protože by se musel nastavit dlouhý časový rozsah.

Obr. 4.19. Průběh simulace komponenty Timer

4.7.2. Připojení Timeru ke komponentám Napřed jsem implementoval signal SIG do komponenty místa ( place ), který bude spolu s hlavním hodinovým signálem zajišťovat korekní průběh. Na obr. 4.20 můžeme vidět propojení komponenty Place s komponentou Timer.

Obr. 4.20. Propojení komponenty Timer a Place Komponenta Place reaguje jak na hodinový signál CLK, tak na signál SIG. Je-li doměnka správná, můžeme vidět na následující simulaci, kde jsem nasimuloval dva funkční stavy místa.

27


Obr. 4.21. Simulace průběhu s použitím signálu SIG Na vstupu obvodu je token (log1), na výstupu se objeví až při příchodu signálu SIG1

Na vystupu je log 0 při současném signálu reset a SIG1

Signal SIG jsem implementoval do projektu, nejprve do komponenty Place, kde podle simulace byl průběh signálu v pořádku. Potom jsem provedl mapování komponenty do návrhu a rozvod signál SIG do všech komponent návrhu tak, aby společně s hodinovým signálem CLK zajišťoval korektní průběh časování. Avšak složitost modelu křižovatky mi zatím v tomto okamžiku nedovolila korektní dokončení a simulaci. Na obr. 4.22. můžeme vidět orientační blokové schéma křižovatky s komponentou timer.

Obr. 4.22. Schéma křižovatky s komponentou timer

28


4.8. Zobrazení textu na LCD displeji Při realizaci této kapitoly jsem vycházel z [8]. Zobrazovací jednotka přípravku Spartan 3E je LCD display pod označením Sitronix ST7066U, který zobrazuje znaky ve dvou řadách po šestnácti znacích. V tomto projektu bude sloužit k zobrazování požadovaných informací pro jednotlivé směry jízdy automobilu. Bude probíhat zobrazení textu: car north free – volný vjezd automobilů ze severu, car south free – volný vjezd automobilů z jihu, car west free - volný vjezd automobilů ze západu, car east free - volný vjezd automobilů z východu.

Obr. 4.23. Blokové schema LCD driveru [8] Popis signálů: OPER – požadovaná operace LCD_E - read⁄write enable pulse, na ostatních vstupech platná data a display je může začít

zpracovávat LCD_RS - register select, příkaz nebo znak LCD_RW - read⁄write, nastavení LCD do režimu čtení⁄zápis RDY - display připraven ASCII - kód znaku⁄pozice kurzoru VLD - potvrzení vstupních signálů

Komponenty LCD driveru: conf_drv.vhd - slouží ke konfiguraci LCD displeje, tzn. nastavení pozice kurzoru, automatický posun atd. lcd_init_drv.vhd - slouží k inicializaci displeje, zajišťuje automat, nutný průběh inicializační

29

Kapitola 4 - Realizace sekvence dle manualu pro Spartan 3E [21] conv8to4.vhd – konfigurační komponenta pro přenos dat, 8b příkaz je rozložen na dva 4b přenosy rozložené do 1 µs. time_drv.vhd – slouží pro správné časování kvůli rychlosti LCD displeje, zajišťuje automat lcd_text – zobrazení samotného textu, uloženého v blokové paměti Samotné zobrazení využívá blokovou paměť BlockRam. Pro Spartan 3E jsem vybral jako nejvhodnější RAMB16_S9 bez využití paritního bitu, kde číslo 9 specifikuje datovou šířku prvního a druhého portu o velikosti 9 bitů. Paměť je synchronní. Kód je uložen v paměti a jeho výpis se provádí pomocí čítače. Realizovaná komponenta používá blokovou paměť pro uložení textu, který se bude zobrazovat na LCD displeji. Tento text je uložen v blokové paměti fromou ASCII znaků v hexadecimálním tvaru. Implementaci v paměti vidíme na obr. 4.24.

Obr. 4.24. Umístění textu v paměti RAM Výpis znaku z blokové paměti provádí automat. Automat přečte adresu a provede výpis ascii textu, instrukce konce textu je označena FF. Tato komponenta ještě není implementována do křižovatky, funguje samostatně s výpisem prvního textu.Na obr. 4.25. vidíme výsledný text zobrazený na LCD.

Obr. 4.25. LCD display s textem

30

Kapitola 5 - Závěr

5. Závěr Podle vytyčených cílů na začátku této práce se mi podařilo provést návrh modelu v programu HPSim. Výsledkem je systém křižovatky se semafory a řídícím okruhem, který byl úspěšně odsimulován. Dále jsem realizoval převod jednotlivých komponent Petriho sítě do jazyka VHDL. V návrhovém systému Xilinx ISE jsem založil projekt křižovatky, kde jsem provedl spojení jednotlivých komponent v jeden funkční celek, provedl výstupy na LED diody a naprogramoval do přípravku Spartan 3E. Dále jsem realizoval LCD driver pro zobrazování informací o stavu sítě, avšak tato komponenta ještě není implementována do systému křižovatky, funguje pouze samostaně se zobrazením prvního uloženého textu. Pro výslednou visualizaci je potřeba zpomalit běh aplikace, aby bylo možno sledovat výstupy na LED diody v reálném čase. Navrhl jsem způsob, jak realizovat zpomalení, a to pomocí komponenty Timer. Úspěšně se mi ji podařilo odsimulovat a realizovat samostatně, ve spojení s kompletním návrhem křižovatky ještě plně funkční není. Jako další pokračování této práce bych viděl doladění projektu s touto komponentou, provedení simulace a odzkoušení funkčnosti na přípravku Spartan 3E. Pro zpracování této bakalářské práce jsem nastudoval část oblasti Petriho sítí, programovací jazyk VHDL, práci s návrhovým systémem Xilinx ISE a dokumentací k přípravku Spartan 3E. Díky této práci jsem měl možnost se seznámit se zajímavým a obsáhlým tématem hardwarové realizace Petriho sítí.

31

Kapitola 5 - Závěr

32

Kapitola 6 - Literatura

6. Literatura [1]

Jaroslav Fibinger: Implementace modelu křižovatky v hradlovém poli, Bakalářská práce ČVUT 2009

[2]

Oleksandr Snopkov: Formalizace návrhového procesu s využitím Petriho sítí, Bakalářská práce ČVUT 2007

[3]

Comtel - Katedra telekomunikační techniky ČVUT

[4]

Uživatelský manuál přípravku Spartan 3E

[5]

Češka, M.: Petriho sítě. Brno, CERM 1994

[6]

Úvod do modelování procesů Petriho sítěmi, skriptum ČVUT, Fakulta dopravní, 2008, autoři: Šárka Voráčková, Martin Pěnička, Jaroslav Veselý

[7]

Webové stránky předmětu X36LOB

[8]

Webové stránky předmětu Syntéza Integrovaných Elektronických Systémů , Doc. Ing. Pavel Hazdra, Csc., Dostupné webové stránky, prosinec 2010

[9]

Oficiální stránky firmy Xilinx , Dostupné webové stránky, prosinec 2010

[10]

Oficiální stránky programu HPSim , Dostupné webové stránky, prosinec 2010

[11]

Petriho sítě na stránkách University of Hamburg, Germany, Dostupné webové stránky, prosinec 2010

[12]

Fakulta informačních technologií Brno, Dostupné webové stránky, prosinec 2010 http://www.fit.vutbr.cz/study/courses/PES/public/

[13]

http://hw.cz/Teorie-a-praxe/Dokumentace/ART365-Nebojte-se-FPGA.html Dostupné webové stránky, prosinec 2010

[14]

http://dce.felk.cvut.cz/hanzalek/prednasky/ Hanzálek, Z.: Petriho sítě. Praha, FEL CVUT, Dostupné webové stránky, prosinec 2010,

[15]

Pinker J., Poupa M, : Číslicové systémy a jazyk VHDL, BEN – technická literatura, Praha 2006, 1. vydání

[16]

Jiří Král: Řešené příklady ve VHDL – hradlová pole FPGA pro začátečníky, BEN – technická literatura, Praha 2010

[17]

http://www.vhdl.org/vhdl-200x/ Dostupné webové stránky, prosinec 2010

[18]

http://amber.feld.cvut.cz/fpga/ Dostupné webové stránky, prosinec 2010

[19]

http://www.digilentinc.com/ Dostupné webové stránky, prosinec 2010

[20]

http://www.xilinx.com/support/documentation/data_sheets/ds312.pdf DataSheet Spartan 3E, prosinec 2010

[21]

http://www.digilentinc.com/Data/Products/S3EBOARD/S3EStarter_ug230.pdf Dostupné webové stránky firmy Digilentinc, prosinec 2010

[22]

http://www.xilinx.com/itp/xilinx5/data/docs/lib/lib0371_355.html Dostupné webové stránky Xilinx pro BlockRam, prosinec 2010

33

Kapitola 6 - Literatura

34

Kapitola 7 - Přílohy

7. Přílohy

7.1. Úvod do Petriho sítí Při zpracovávání kapitol 7.1., 7.2., 7.3., 7.4. jsem vycházel ze zdrojů [5],[6]. Petriho sítěmi je označována široká škála matematických modelů, které umožňují grafický popis paralelismu informační závislosti a konfliktů moderních distributivních systémů. Srozumitelnost a analyzovatelnost Petriho sítí je dána jejich jednoduchostí. Model je popsán místy ( places ), která obsahují stavovou informaci ve formě tokenů a přechody ( transitions ), které představují možné změny stavů. Místa jsou s relevantními přechody spojeny hranami ( arcs ). Významná výhoda tohoto modelovacího nástroje je možnost grafického vyjádření a možnost simulovat graficky dynamické chování modelu. Jako klasické Petriho sítě můžeme označit C/E Petriho sítě ( Condition Event PN ), které jsou z hlediska vyjadřovacích schopností nejslabší. Odpovídají síle konečných automatů a každé místo může obsahovat pouze jeden token. Jako další to jsou P/T Petriho sítě ( Place Transition PN ), které umožňují do každého místa umístit více než jeden token. Navíc pomocí inhibičních hran se vyjadřovací síla těchto sítí zvýší na úroveň Turingova stroje. Rozšíření klasických Petriho sítí o možnost popisu časových vztahů či datových typů poskytují tzv. Petriho sítě vyšší úrovně ( high-level Petri net ). Jsou to Barevné Petriho sítě ( Coloured PN ), Hiearchické Petriho sítě ( Hiearchial PN ), Objektové Petriho sítě ( Object – oriented PN ), Časované Petriho sítě ( Timed PN ), Stochastické Petriho sítě ( Stochastic PN ), Frontové Petriho sítě. Výhody Petriho sítě vyšší úrovně oproti základním Petriho sítím jsou často porovnávány s výhodami a možnostmi vyšších programovacích jazyků ve srovnání s jazyky symbolických instrukcí. Petriho sítě poprvé představil Carl Adam Petri, německý matematik a počítačový vědec, v roce 1962 ve své disertační práci Kommunikation mit Automaten. V sedmdesátých letech se velmi rychle ukázalo, že se jedná o jeden z nejlepších a nejvhodnějších jazyků pro popis, modelování a analýzu systémů, ve kterých se vyskytují synchronizační, komunikační a zdroje sdílející procesy. Nicméně pokusy praktického použití Petriho sítí ukázaly jejich dvě nevýhody. Prvním je chybějící koncept práce s daty. Z tohoto důvodu se vznikající modely stávají nepřiměřeně veliké, protože veškerá manipulace s daty musí být prezentována přímo do struktury sítě. Druhou nevýhodou je chybějící hierarchický koncept a proto není možno stavět velké modely z množiny menších sub-modelů s dobře definovaným vzájemným rozhraním. Rozvoj vyšších Petriho sítí v 70-tých letech 20. století a rozvoj hierarchických Petriho sítí v druhé polovině 80-tých let odstranily výše zmiňované nevýhody. Barevné Petriho sítě jsou jedním ze dvou nejznámějších typů vyšších Petriho sítí. Obsahují jak jak integraci datových struktur, tak možnost hierarchické dekompozice. Pojem Petriho sítě byl tak postupně obohacován a zobecňován tak, aby jeho modelovací schopnost vyhověla praktickým 35

Kapitola 7 - Přílohy potřebám.

7.2. Modelování diskrétních systémů Petriho sítěmi Petriho síť lze chápat jako automat, který definuje chování systému posloupnosti událostí a odpovídajícími stavovými změnami systému. V případě konečných automatů byl stav systému jednoznačně určen prvkem množiny stavů. V případě Petriho sítí je okamžitý stav modelovaného systému konstituován určitými parciálními stavy spojenými s příslušnými místy sítě. Pokud daný systém rozložíme na subsystémy, potom je nutné popsat kombinaci stavů jednotlivých subsystémů tzv. parciálními stavy.

Obr. 7.1. Distribuce stavu na parcialní stavy

Obr. 7.2. Odpálení přechodu

Znázorněná distribuce stavů s1 a s2 na parciální stavy, které jsou vyjádřeny doplňujícími vlastnostmi a podmínkami a spojení těchto podmínek s událostmi systému je základní myšlenkou popisu diskrétního systému Petriho sítí. Parciální stavy, graficky zobrazené jako malé kružnice, se nazývají místa ( places ). Vzory možných událostí jsou modelovány spojením míst s přechody ( transitions ). Přechod označujeme v grafu obdélníkem. Aktuální stav systému je definován umístěním tzv. tokenů ( značek ), což graficky vyznačujeme tečkami v kružnicích. Přítomnost značky v místě modeluje zkutečnost, že daný aspekt stavu je v tomto okamžiku splněn. Každý přechod má definovaná vstupní a výstupní místa, což je v grafu vyjádřeno orientovanými hranami. Tím je deklarováno, které aspekty stavu podmiňují výskyt odpovídajících událostí (enabling rule ) a které aspekty jsou výskytem této události ovlivněny ( firing rule ). Událost může být uskutečněna jen v případě, že jsou všechny vstupní podmínky splněny. Uskutečnitelné události odpovídají v Petriho sítích aktivním přechodům, tedy přechod je aktivní jen pokud všechny vstupní místa obsahují značky. Uskutečněním události se změní vstupní a výstupní aspekty, tj. provedením přechodu ( firing rule ) se odstraní tokeny ze vstupních míst ( vstupní podmínky přestanou platit ) a umístí se nové žetony do vstupních míst ( uplatní se nové podmínky ).

36


7.2.1. Struktura P/T Petriho sítí Petriho sítě jsou vždy přesně definovanou matematickou strukturou s jasně určenou syntaxí i sémantikou. Pro přehlednější formulace budeme v dalším textu používat následující značení. P = {p1, p2, …, pn} je konečná neprázdná množina míst ( places ) T = {t1, t2, …, tm} je konečná neprázdná množina přechodů ( transitions ) Aktuální stav systému, popsaného Petriho sítí je určen rozmístěním tokenů v místech. Definice: Značení sítě je funkce, která každému místu přiřadí celé nezáporné číslo z: P→ N0

7.2.2. Incidenční funkce Počet vstupních podmínek v místech nutných pro odpálení daného přechodu je dán hodnotou hrany vstupující do uzlu. Tuto hodnotu označujeme jako zpětnou incidenční funkci. Hodota hrany vstupující do uzlu určuje současně počet tokenů, které budou z daného místa odebrány, bude-li přechod odpálen. Definice: Počet tokenů odebraných z místa p odpálením přechodu t je zpětná incidenční funkce I - ( p,t ). Podobně počet tokenů, které odpálením přechodu přidáme do výstupního místa přechodu nazýváme dopředná incidenční funkce I + ( p,t ). Definice:

Petriho síť je uspořádaná pětice ( P,T,I +,I -,z0 )

•

P = {p1, p2, …, pn} je konečná neprázdná množina míst

•

T = {t1, t2, …, tm} je konečná neprázdná množina přechodů

•

množiny P,T jsou disjunktní P ∩ T = 0

•

I +,I - jsou icidenční funkce P x T → N0

•

z0: P→ N0 je počáteční značení

Petriho síť jsme definovali jako stroj, který odpalováním přechodů postupně mění označení sítě. Pokud rozpozná v reprezentaci aktuálního stavu systému, že jsou splněny podmínky pro odpal nějakého přechodu, nahradí aktuální značení jiným, odpovdajícím incidenčním funkcím daného přechodu. Přechod se projevuje pouze lokálně, zbytek reprezentace systému zůstáva nezměněn.

37


7.2.3. Incidenční matice Incidenční funkce lze zapsat do tzv. incidenční matice. Do řádků píšeme hodnoty vztahující se k jednomu místu, záhlaví sloupců je určeno všemi přechody. Prvky zpětné incidenční matice jsou všechny zpětné incidenční funkce a analogicky dopředná incidenční matice je tvořena hodnotami dopředných incidenčních funkcí. Definice: Nechť má Petriho síť n míst P = {p1, p2, …, pn} a m přechodů T = {t1, t2, …, tm}. Zpětná incidenční matice C- typu n x m je určena c -ij = I - ( pi, tj ), ∀pi ∈ P, tj ∈ T Dopředná incidenční matice C+ typu n x m je tvořena c +ij = I + ( pi, tj ), ∀pi ∈ P, tj ∈ T Incidenční matice C je definována jako rozdíl C = C+ - C-

Obr. 7.3. P/T Petriho síť Přechod je aktivní v aktuálním značení, pokud jsou všechny vstupní podmínky splněny. Na obr. 7.3. jsou v aktuálním značení aktivní přechody T1 a T3. Přechod je v daném značení uskutečněn jen pokud není počet značek ve vstupních místech daného přechodu menší než váhy příslušných hran. Definice: Přechod t je aktivní ( proveditelný ) v aktuálním značení z, pokud pro všechna místa sítě platí z ( pi ) ≥ Ι − ( pi , t ); i = 1... n.

38

Kapitola 7 - Přílohy Pro určení aktivních přechodů v daném ohodnocení použijeme zpěnou incidenční matici. Hodnoty zpětných incidenčních funkcí daného přechodu jsou zapsány pod sebe do příslušného sloupce. Porovnáním složek vektoru aktuálního ohodnocení z a vektoru sloupce zpětné incidenční matice příslušejícího k přechodu t zjistíme, zda z ( pi ) ≥ Ι − ( pi , t ); i = 1... n. Pokud modelovaná síť nemá vlastní cykly, pak můžeme k určení aktivních přechodů využít přímo incidenční matici. Záporné prvky se vztahují ke zpětné incidenční matici, určují počet tokenů nutných pro odpalení. Kladné představují dopředné incidenční funkce a určují počet tokenů, které do míst přidáme. Definice: Nechť tj je přechod Petriho sítě s incidenční maticí C. Sloupec incidenční matice příslušející danému přechodu, tzn. j-tý sloupec nazveme vektorem přechodu. Tj = ( c1j, c2j, …, cnj ). Na obr. 7.3. máme vytvořenou P/T Petriho síť. Pořadí míst i přechodů ponecháme tak, jak je určeno jejich jménem. V záhlaví řádků jsou místa P0, P1, P2, P3, v záhlaví sloupců jsou všechny přechody T0, T1, T2, T3, T4, T5. Hodnoty hran vedoucích z míst k přechodům tvoří zpětnou incidenční matici C-. Dopředná incidenční matice C+ je tvořena hodnotami hran vycházejících z přechodů.

C- =

2 0 0 0 0 0

0 0 0 0 1 0

-2 0 0 0 1 0

0 1 0 1 0 0

2 0 0 0 0 0

2 -1 0 -1 0 0

0 0 0 0 1 1 0 0 2 0 0 0

C+ =

0 1 1 0 0 1 0 0 0 2 0 0

C =

0 1 1 0 -1 0 0 0 -2 2

0 0

Vektor počátečního ohodnocení je tvořen počty tokenů v místech při stejném pořadí míst z 0 = ( 1,2,0,0 ). V počátečním ohodnocení z0 = ( 1,2,0,0 ) Petriho sítě na obr. 7.3. je přechod T1 aktivní, protože druhý sloupec zpětné incidenční matice má všechny složky menší než příslušné složky z0. ( Ι − ( P0, T1 ), Ι − ( P1, T1 ), Ι − ( P2, T1 ), Ι − ( P3, T1 ) ) = ( 0,1,0,0 ) Síť obsahuje vlastní smyčku mezi přechodem T5 a mástem P2, proto pro určení aktivity přechodu T5 nemůžeme použít vektor přechodu. Vektor přechodu T5 je nulový (poslední sloupec C), což by znamenalo, že je aktivní v každém značení. Pro přechod s vlastní smyčkou musíme požít zpětný vektor přechodu, tj. sloupec ve zpětné incidenční matici C - . U zbývajících přechodů využijeme podmínku t + z > 0, tj. zjistíme, zda všechny složky součtu vektoru přechodu a aktuálního značení jsou kladné. Z toho nám vyplývá, že v počátečním ohodnocení z0 = ( 1,2,0,0 ) jsou aktivní přechody T1 a T3.

39


7.3. Vlastnosti Petriho sítí Pří návrhu kritických aplikací je důležitá formální analýza, je třeba popsat všechny dosažitelné stavy. Na úrovni abstraktního modelu máme navíc možnost prokázat funkčnost a bezchybnost systému ještě před jeho praktickou realizací. Po vytvoření grafického modelu Petriho sítě máme možnost prokázat, jaké má systém vlastnosti.

7.3.1. Ohraničená síť Definice: Místo p Petriho sítě nazýváme ohraničené, jestliže existuje přirozené číslo h takové, že v každém dosažitelném značení je počet tokenů v místě p nejvýše h. ∀zi ; z ( p ) ≤ h Petriho síť je ohraničená ( omezená ), pokud jsou ohraničená všechna její místa. 1ohraničené sítě nazýváme bezpečné sítě. Bezpečnost sítě zaručuje, že počet tokenů žádného místa v libovolném značení nepřevíší 1. Tyto sítě označujeme také jako binární. Tohle omezení je využito i v této práci.

7.3.2. Živá síť Definice: Nechť je dána Petriho síť, z0 je její počáteční značení. Přechod t nazveme •

živý na úrovni 0, nebo-li mrtvý, jestliže neexistuje dosažitelné značení, ve kterém by byl přechod aktivní

•

živý na úrovni 1, jestliže existuje posloupnost odpálených přechodů, které bude alespoň jednou aktivní

•

živý na úrovni 2, jetliže existuje posloupnost odpálených přechodů, ve které bude alespoň k krát aktivní

•

živý na úrovni 3, jetliže existuje posloupnost odpálených přechodů, ve které bude počet výskytů přechodu t neomezený

•

živý na úrovni 4, nebo-li živý, jestliže z každého dosažitelného značení sestrojíme posloupnost odpálených přechodů, ve které bude t alespoň jednou aktivní

Model systému pomocí Petriho sítě může skrývat možnost mrtvého stavu ( deadlock ). Tento stav je dosažitelné značení, ve kterém žádný přechod není aktivní. Jinak také řečeno, Petriho síť je živá, jestliže jsou živé všechny její přechody.

40


7.3.3. Reverzibilní síť Definice: Petriho síť nazveme reverzibilní, pokud ke každému dosažitelnému značení existuje posloupnost odpálených přechodů, ve kterém je počáteční značení aktivní. Mnohé systémy obsahují procesy s cyklicým charakterem jako jsou např. výrobní proces, obsluhy zákazníka apod. se opakují cyklicky.

7.3.4. Konzervativní síť Definice: Síť, ve které je v každém dosažitelném značení konstantní součet počtu tokenů nazýváme striktně konzervativní. ∀zk ; ∑zk ( pi ) = konst Součet tokenů ve všech místech sítě musí být konstantní. Striktně konzervativní síť také poznáme přímo z matice incidence. Při každém odpalu musí vzniknout tolik tokenů ( značek ), kolik jich odpal spotřeboval.

41


7.4. Matematické definice Petriho sítí Petriho síť lze také charakterizovat jako matematický stroj s přesně definovanou syntaxí a sémantikou. Zde si uvedeme základní matematické definice Petriho sítí. Definice 1. Trojici N = (P, T, F) nazýváme sítí, jestliže (1) P a T jsou disjunktní množiny a (2) F ⊆ (P×T)∪(T × P) je binární relace Množina P se nazývá množinou míst (Places) sítě N, množina T množinou přechodů (Transitions) sítě N a relace F tokovou relací (Folow relation) sítě N. Grafem sítě nazveme grafovou reprezentaci relace F Grafem sítě je bipartitiní orientovaný graf s množinou uzlů P ∪T vrcholů. Definice 2. Nechť N = (P, T, F) je sít’. (1) Pro všechna x∈(P ∪T ) •x

= {y | yFx} se nazývá vstupní množinou (preset) prvku x

x• = {y | xFy} se nazývá výstupní množinou (postset) prvku x Nechť X ⊆ (P∪ T) je

Zřejmě pro každé x, y∈(P ∪T) platí : x ∈ • y ⇔ y ∈ x• (2) Uspořádaná dvojice ∈ P×T se nazývá vlastní cyklus (self-loop), jestliže pFt ∧ tFp . Neobsahuje-li N vlastní cyklus, pak se nazývá čistou sítí (pure net).

42

Kapitola 7 - Přílohy (3) Prvek x∈(P ∪T ) se nazývá izolovaný, jestliže • x ∪ x• = Ø. Definice 3. 6-tici N = (P, T, F, W, K, M0) nazýváme P/T Petriho sítí ( Place/Transition Petri Net ), jestliže (1) (P, T, F) je konečná sít’ (2) W : F→ N\{0} je ohodnocení hran grafu sítě určující váhu každé hrany (3) K : P→ N∪{ω}je zobrazení specifikující kapacitu (i neomezenou) každého místa (4) M0 : P→ N∪{ω}je počáteční značení míst sítě respektující kapacity míst, tj. M0(p)≤ K(p) pro všechna p∈P. Dále budeme Petriho sítí rozumět P/T Petriho sít’. Následující definice vymezuje přesně pravidla pro provádění přechodů Petriho sítě. Definice 4. Nechť N = (P, T, F, W, K, M0) je Petriho sít’. (1) Zobrazení M : P→ N∪{}se nazývá značení (Marking) Petriho sítě N, jestliže ∀p∈P : M(p) ≤ K(p) Nechť M je značení Petriho sítě N. (2) Přechod t ∈T je proveditelný (enabled) při značení M, stručněji M-proveditelný (M-enabled), jestliže ∀p ∈ •t : M(p) ≥ W(p, t) ∀p ∈ t• : M(p) ≤ K(p) -W(t, p) (3) Je-li přechod t ∈T proveditelný při značení M, pak jeho provedením získáme následné značení M` ke značení M, které je definováno takto:

43


Provedení přechodu t ( transition firing ) ze značení M do značení M ' zapisujeme symbolicky: M [t 〉 Μ ' (4) Označme symbolem [M 〉 nejmenší množinu různých značení sítě N takovou, že platí: (a) M ∈ [M 〉 (b) je-li M1 ∈ [M 〉 a pro nějaké t ∈ Τ platí M1 [t 〉 Μ2 ∈ [M 〉 Množina [M 〉 se nazývá množinou dosažitelných značení ( reachability set ) ze značení M; množina [M0 〉 dosažitelných značení z počátečního značení se nazývá množinou dosažitelných značení sítě N. Definice 5. Petriho sít’ N = (P, T, F, W, K, M0) se nazývá bezkontaktní (contact-free), jestliže pro všechna M∈[M0 〉 a pro všechna t ∈T platí: Jestliže ∀p ∈ •t: M( p) ≥W( p,t), pak přechod t je proveditelný při značení M , tj. ∀p ∈ t• :M( p) ≤ K( p) −W(t, p). Pokud je sít’ bezkontaktní, pak máme zaručeno, že při provedení přechodu nedojde k překročení kapacity místa.

44

Kapitola 7 - Přílohy Definice 6. Nechť N = (P, T, F, W, K, M0) je Petriho sít’. Místo p∈ P se nazývá bezpečné místo (safe place), jestliže platí: ∀M ∈ [M0 〉 : M(p) ≤ 1 Je-li každé místo Petriho sítě N bezpečné, pak N se nazývá bezpečnou Petriho sítí (safe Petri net). Bezpečnost (safeness) sítě tedy zaručuje, že počet značek žádného místa v libovolném stavu Petriho sítě nepřevýší hodnotu 1. Definice 7. Nechť N = (P, T, F, W, K, M0) je Petriho sít’. Místo p∈ P se nazývá k-omezené (k-bounded), jestliže platí: ∃k ∈ N :∀M ∈[M 〉 : M(p) ≤ k 0 Místo p se nazývá omezené, je-li k-omezené pro určité k ∈ N . Je-li každé místo Petriho sítě N omezené, pak N se nazývá omezenou Petriho sítí (bounded Petri net). Definice 8. Nechť N = (P, T, F, W, K, M0) je Petriho síť a v : P → N vektor. Síť N je konzervativní vzhledem k váhovému vektoru v jestliže platí:

Petriho síť nazveme konzervativní, je-li konzervtivní vzhledem k váhovému vektoru v > 0. ( v > 0 ⇔ ∀p ∈ P: v(p) > 0 ). Definice 9. Nechť N = (P, T, F, W, K, M0) je Petriho sít’. Značení ∈ 〉 0 M [M je živé, jestliže pro všechna t ∈T existuje značení M`∈[M〉 takové, že přechod t je M`- proveditelný. Jsou-li všechna značení z 〉 0 [M živá, pak Petriho sít’ N se nazývá živá Petriho sít’ (live Petri net).

45


7.5. Popis hardwaru pro realizaci Při zpracování kapitoly 7.5. jsem vycházel ze zdrojů [13], [19], [20], [21], [22]. Pro visualizaci výsledného programu jsem si zvolil přípravek Spartan 3E. Je to moderní deska od firmy Xilinx vhodná pro výslednou realizaci tohoto projektu. Na obrázku vidíme základní popis důležitých součástí desky. Integrované obvody řady Spartan vyráběné firmou Xilinx jsou rozsáhlé, vysoce výkonné programovatelné obvody typu FPGA s širokým rozsahem použití. Deska je plně kompatibilní se všemi verzemi Xilinx ISE nástroji včtetně volně dostupného WebPacku.

Obr. 7.4. Základní popis desky Spartan 3E

46

Kapitola 7 - Přílohy Základní charakteristika obvodu Xilinx XC3S500E Spartan 3E FPGA • • •

232 využitelných I/O 320 pinové FBGA pouzdro více než 10.000 logických buněk

•

Xilinx 4 Mbit Flash konfigurační paměť PROM

•

Xilinx 64 makrobuněk XC2C64A CoolRunner CPLD

•

64 MByte ( 512 Mbite ) DDR SDRAM paměti, x16 datové rozhraní, 100+ MHz

•

16 MByte ( 128 Mbit ) paralelní NOR Flash Paměti ( Intel StrataFlash )

•

16 Mbit⁄s SPI sériové Flash ( STMicro )

•

LCD display, 16 znaků, 2 řádky

•

PS⁄2 port pro myš či klávesnici

•

VGA výstup pro display

•

10⁄100 Ethernet

•

dvojice 9 pinových RS–232 portů ( 1xDTE+1xDCE )

•

vestavěné rozhraní pro debugging připojitelné pomocí USB

•

50 MHz vnitřní oscilátor

•

SHA–1 propojená se sériovou EEPROM pamětí pro kontrolu bitového toku

•

Hirose FX2 rozšiřující konektor

•

trojice Digilent 6 pinových rozšiřujících konektorů

•

4 vstupový D⁄A konvertory

•

2 vstupový A⁄D konvertory s programovatelným předzesílením

•

port pro ChipScope Soft Touch debugging

•

otočný spínač s tlačítkovou funkcí

•

8 indikačních LED diod

•

4 přepínače⁄posuvné

•

4 spínače⁄tlačítka

•

SMA vstup pro externí zdroj taktu

•

8 pinová patice pro přídavný oscilátor

47


7.5.1 Základní architektura obvodu FPGA Obvody typu FPGA (Field Programmable Gate Array) mají z programovatelných obvodů nejobecnější strukturu a obsahují nejvíce logiky. Současné největší obvody FPGA obsahují až 6 milionů ekvivalentních hradel (typické dvouvstupové hradlo NAND). Typickou strukturu obvodu FPGA znázorňuje následující obrázek.

Obr. 7.5. Typická struktura obvodu FPGA [13] Bloky označené IOB (Input/Output Block) představují vstupně-výstupní obvody pro každý v-v pin FPGA. Tyto bloky obvykle obsahují registr, budič, multiplexer a ochranné obvody. Bloky LB (Logic Block) představují vlastní programovatelné logické bloky. Všechny bloky mohou být různě propojeny globální propojovací maticí. Nejpoužívanější struktura konfigurovatelného logického bloku je znázorněna na následujícím obrázku.

Obr. 7.6. Struktura konfigurovatelného bloku [13] FPGA obvykle umožňují propojit některé signály logických bloků přímo se sousedním bez nutnosti využívat globální propojovací matici. Takovéto spoje mají mnohem menší zpoždění

48

Kapitola 7 - Přílohy a umožňují tak realizovat například rychlé obvody šíření přenosu, což je nezbytné pro sčítačky nebo násobičky. Kromě bloků znázorněných na předchozích obrázcích integrují výrobci do FPGA další prvky. Většina moderních FPGA obsahuje několik bloků rychlé synchronní statické paměti RAM. Velmi často obvody FPGA obsahují PLL (Phase Locked Loop) nebo DLL (Delay Locked Loop) pro obnovení charakteristik hodinového signálu, případně pro násobení nebo dělení jeho frekvence.

Obr. 7.7. Základní architektura přípravku Spartan 3E [21]

49


50

Kapitola 8 – Obsah CD

8. Obsah přiloženého CD Adresář Doc – text práce ve verzi odt a pdf Adresář Project – projekty v návrhovém systému Xilinx ISE WebPack 10.1. Adresář HPSim – editor HPSim a navržený model křižovatky

51

Hardwarová realizace Petriho sítí

Recommend Documents