Softcraft párhuzamos digitális automaták - alapfogalmak

Ezt a webhelyet olyan emberek látogatják meg, akik nem vitatják azt az elképzelést, hogy a párhuzamosság javítja a rendszer teljesítményét. Ezért a párhuzamosságra való izgatás hiányzik :-). Továbbá nincs ellentmondás az ötletből, hogy az automatikus technológia lehetővé teszi az egyes algoritmusok hatékony végrehajtását.

Szigorúan az összes digitális technológia a digitális automaták elméletének megvalósítása. A kombinációs áramkörök egy digitális állapotú, egy állapotú automaták. Minden memóriaeszköz finom digitális gép. Bármely mikrokontroller és mikroprocesszor egy olyan digitális gép, amely hatalmas számú állapotot tartalmaz, az átmeneteket, melyeket a külső program határoz meg. Hiszen minden számítógép egy olyan digitális gép is, amely még nagyobb számú állapotot tartalmaz.

Sajnos nem lehetséges párhuzamos algoritmusok végrehajtása a fogyasztói és általános mikroprocesszorokra és mikrokontrollerekre. A legjobb esetben a párhuzamosság emulálása javasolt a gyors (emberi) kapcsolási feladatok miatt. Azonban, ha a feladatot kapcsolás prioritások alapján, nem ritka a számítógép lefagy, amikor a feldolgozás nagyon magas prioritású (én XP, például úgy véli, hogy az áll egy új CD - ez a legfontosabb feladat.).

De emlékeztetnünk kell arra, hogy a digitális technológia nem korlátozódik a mikrokontrollerekre és még inkább a számítógépekre. Még mindig vannak különböző rendszerek, laza logika és programozható logika (FPGA). Az utóbbi használatával a lehető legkisebb költséggel bármely architektúrájú eszköz létrehozható. Ezért az összes lehetséges FPGA és CPLD használatával párhuzamos rendszereket hozhat létre.

A mai napig kiderült, hogy nem (vagy inkább nem találtam) egy pontos és kimerítő elméletet, amely leírja a párhuzamos algoritmus és a szintézis leírását. A párhuzamos algoritmusok leírásának különböző módjai vannak, de nincsenek világos módszerek az ezt követő szintézisre. És ha igen, alapvetően mindenféle speciális eset vagy módszer, amelyek nagy hardverköltségeket igényelnek.

De mi akadályozza meg a digitális automaták régi és jó elméletének használatát párhuzamos rendszerek létrehozására? Ezt a posztgraduális iskolába való belépés előtt gondoltam. Gondolkodtam - és úgy döntött, hogy kutatást végez ezen a témában. Így a folyamat a kutatásom én az alábbiak szerint: 1) a tanulmány a jelenlegi elmélet digitális gépek, 2) vizsgálat módon leírni párhuzamos algoritmusok, 3) vegyületet az 1. és 2., valamint 4) végrehajtása a fentiek meghosszabbított alapvonal és a programozható logikai eszközök .

Soros digitális automata - fizikai viselkedés

Amit általában "digitális automatikus gépnek" neveznek, természetesen "soros digitális automata gépet" fogok hívni. Felkéri az OCA rövidítését. De mivel én vagyok a jövőben be „párhuzamos digitális gépek” ugyanazzal az első P, soros I rövidítve CCA - „klasszikus digitális gépek” (ha azonban az elméletem lesz klasszikus van pereoboznachat :-). ).

Tehát mi a legegyszerűbb "digitális gép"? Először is ez egy digitális eszköz. Ezért bináris logikán alapul. Ha bináris logikára épül, az egész eszközt Boole függvényekkel - kötőszavakkal és kötőszavakkal lehet leírni. A műveleteket néhány operanduson végzik. Ezért egy digitális gép olyan eszköz, amely feldolgozza a bemeneti adatokat. Így a digitális gépet a következőképpen lehet leírni:

Az a állapot függ az t időtől és az x (t) bemeneti műveletek aktuális értékétől.

A kamatot a jelenlegi idő mutatja. Szigorúan megfogalmazva, másodpercben mérve (pontosabban, nanoszekundumban). Ezzel az idővel megkülönböztethetjük az állam szopását:

Ábra. 3 Állapotváltás

Amint az a 3. ábrán látható (amely azonban egy kép nélkül világos), egy ideig t a digitális eszköz állapotban van. Azonban a memória rekord értéke a t időben változik. Ez az idő az áramkörön belül lévő jel terjedési idejétől és a memória és logikai elemek sebességétől függ. Ekkor a gép szinte kiszámíthatatlan állapotban van. Természetesen ebben a pillanatban a kimenetek értéke kiszámíthatatlan.

De boldogságunknak ez az idő nagyon kicsi. Ezért általában elhanyagoltak és feltételesen tekinthetők nullnak (legalábbis az áramkör modellezésénél nem gondolják).

Ezért, ha töröljük a t per időintervallumokat. kapunk egy teljesen különálló állapotot az eszközről. Fontos számunkra, hogy megismerjük az idő fizikai jelentését? Nem, nem az. Ezért egy bizonyos 0, 1, 2 sávban mért időt vesz figyelembe :-). Azonban valódi eszköz létrehozásakor ezeket a "sündisznókat" figyelembe veszik.

Mekkora időpontban változik az eszközállapot? Ez általában külső jel. Azt mondják, hogy "az óra" az eszköz működését, "szinkronizálja" az állapotainak változását (sőt, az állapotváltozás szinkronban történik a készülék egészében). Ezért ezt a jelet "órajel pulzusórának" hívják. A megvalósításhoz rendszerint a négyszögű impulzusok generátorát készítik.

Tehát összefoglaljuk (4. ábra). A digitális készülék a f (X) törvény szerint feldolgozza az X bemeneti jeleket, és az Y eredményt adja ki. Ha vannak memóriaelemek, az eszköz állapota a törvénynek megfelelően változik. Az állapotváltozást egy külső jel c kezdeményezi.

Ábra. 4 A digitális eszköz viselkedése

A soros digitális automatika matematikai modell

Matematikai modell esetén a négyszögek, kötőjelek és pontok nem alkalmasak. Ott kell beszélni a formulák nyelvét.

A digitális készüléket a mi esetünkben számos készlet írja le: a X bemeneti műveletek sorozata. Az Y kimenőjelek és az A állapotok készlete.

A bemeneti műveletek sorozata az összes lehetséges kombináció halmaza, amelynek számát a bemeneti szó szélessége határozza meg. Minden lehetséges bemeneti szó a bemeneti ábécét alkotja. Vannak olyan helyzetek (igen, gyakorlatilag alapvetően ez történik), ha nem az összes beviteli ábécét használják.

A kimeneti jelek készletét azok a jelek határozzák meg, amelyeket a gép ad ki. Ezeket a jeleket olyan szavak is leírják, amelyek a kimeneti ábécét alkotják, amely szintén nem használható fel teljesen.

A belső állapotok halmaza a belső memóriaelemek összes lehetséges kombinációjának halmaza. A legtöbb valós esetben a memóriaelemek összes lehetséges kombinációját nem használják. Ez a tulajdonság sikeresen alkalmazza az egyenleteket.

Az összes lehetséges érték közül fontos kiválasztani azt az állapotot, amelyet az automatán először találtak. Rendszerint a bekapcsolás a gépet kiszámíthatatlan állapotba hozza. Ezért külső bemeneti jelet adnak be, amely az automatát egy jól definiált állapotba helyezi. Ez az állapot "kezdeti", és általában 0 (vagy 1 - így klasszikusabban).

Ezen készletek mellett két funkciót kell meghatározni - az átmeneti funkciót és a kimeneti funkciót.

Az átmeneti funkciót már elemezték.

A kimeneti funkció a kimenetek értékét mutatja az aktuális állapot és az aktuális bemeneti paraméterek függvényében:

Ugyanakkor a kimenetek ugyanolyan sikert jelentenek, mint az előző állapot. Ez attól függ, hogy a kimeneti jel keletkezik - az átmenet előtt vagy után. A második esetben egy másik kimeneti funkciót kapunk:

Mivel könnyen kitalálható, az a (t) aktuális időt a (t - 1) előző időtartamon keresztül fejezhetjük ki. Ezzel összefüggésben a (4) képletet alkalmazzuk a modellben.

Tól képletű (4) lehet bizonyos esetekben 4 - 1) függ az állam gép és bemenetek 2) attól függ, csak az állam, 3) függ csak a bemenet és 4) vagy általános függ semmi. A harmadik eset a kombinációs logika. A második eset Moore automaton volt. Az első eset Miles gép. A negyedik eset egy állandó generátor.

Így a klasszikus digitális automata matematikai modelljét a következő rendszer írja le:

Ebben a meghatározott általános képletű (5,1) ismertet több bemeneti szavakat, (5.2) - több kimeneti jelek, (5.3), - több állapotok, (5.4) - a kezdeti állapot, (5,5) - átmenet függvény, (5.6) - O-funkció (5.7 ) - a munka időben való megkülönböztetése.

Párhuzamos digitális automata gép

És most próbáljuk meg párhuzamot teremteni a CCA-val. Hogyan lehet ezt tenni?

Először is nézzük a matematikát. Pontosabban, az egyenletek rendszerében (5). Mi lehet ott megváltoztatni? Vagy, ha több tudományos, mi változhat a rendszerben (5), hogy biztosítsa a párhuzamosságot és az integritás megsemmisítése nélkül, miközben a gépet fekete doboznak tartja változatlanul? Megfejtjük az utolsó gondolatot :-).

A digitális gép fekete dobozként nem változhat. Ez azt jelenti, hogy a CCA egyenértékű OCA-val történő helyettesítésével és viszont fordítva kell a láthatatlanon kívül ("ekvivalencia" ebben az esetben ugyanazokat a funkciókat jelenti) - a felület nem változhat. Ennek következtében a készletek (5.1) és (5.2) nem változnak.

A PCA mint többállomású digitális eszköz koncepciója nem változik. Ezért (5.3) sem változik.

A diszkrét időváltozás fogalma nem változik - (5.7) nem változik.

Ha gondolnánk, a párhuzamosság ebben az esetben az aktus adott pillanatában meglévő aktív jelenlétének jelenlétét jelenti, ellentétben a CCA-nál aktívakkal. Ez azt jelenti, hogy az egyenletek (5.4), (5.5) és (5.6) változik, ha egy állapot aktív:

Mit jelent (6.1)? Ez azt jelenti, hogy több állam aktív lehet a kezdeti időpontban. (6.2): ​​az egyidejűleg aktív állapotok halmazának függvénye egy adott időpontban az előző diszkrét időből aktív és aktív bemeneti jelekből. (6.3) jelentése a kimeneti értékek függése az egyidejűleg aktív állapotok és bemeneti jelek halmazára.

A rendszer (6) megváltoztatja a digitális gép interfészét? Nyilvánvaló, hogy nincs, mivel az interfészt a halmazok (5.1) és (5.2) határolják.

Az állapotváltozás egyszerre történik (6.2. Egyenlet).

Külső reszetjelzéssel az automatika átkerül egy kezdeti állapotra (egyenlet (6.1)).

Így szerezte meg az OCA modelljét. A (6) rendszer (5) hozzáadásával a rendszerhez (5), valamint számos szükséges átnevezéssel a PCA matematikai modelljét adjuk meg:

A szimbólum az aktív állapotok halmazát jelöli. Ez a készlet nem lehet egybeesik az egész állapotcsoporttal, amint azt a (7.4.) Megjegyzi (ha ez így volt, akkor ismét a kombinációs logikáról volt szó).

A rendszer (7) elegendő-e az OCA leírásához? Nyilvánvaló, igen.

Azonban nyilvánvaló a számítógép, amely matematikai absztrakciókkal működik. Ha veszünk egy feladatot (pl www.softcraft.ru/auto/ka/fil/), rögtön érezni egyfajta tehetetlenség - ez az, hogy mekkora szükség van, hogy töltse ki a papírt, és hogy egy byte ezeket a csomagokat, hogy leírja a készülék működését!

Ha állapotdiagrammal próbálkozik, akkor nem lesz könnyű - a diagram teljesen olvashatatlan.

Nyilvánvaló, hogy egyszerűsítéseket és általánosságokat kell bevezetni.

Jó lenne bevezetni az ilyen népszerű programozó folyamatokat és szálakat szálakkal, cserepufferrel, zászlókkal, szemaforokkal.

Figyelembe véve ezt, ezt a modellt "absztrakt matematikai modellnek" nevezem. Csak "modellt" fogok hívni, ami elérhető egy személy számára.

Mindez igazán valós :-). Ráadásul a cikk írásakor már létezett egy olyan modell (a modellezési környezetben - több pénz nem volt elég).

Tehát van egy matematikai absztrakció, amely kifejezve valamilyen módon - egy állapotdiagram, egy mátrix, egy átmeneti táblázat vagy valami más. Mi a teendő?

Tekintsük a CCA szintézisét.

Ha laza logikáról beszélünk, akkor a memória elemeket választjuk ki, az állapotokat kódoljuk. Ezután a megszerzett állapotoknál egy átmeneti függvény és egy kimeneti funkció jön létre. Az egyszerűsítés a Boole függvények szintjén történik. Aztán vettem egy csomó elemeket „és”, „vagy”, „nem”, és beindítja a dekódert és ez mind egy lezárt kis szörnyek :-).

Szerencsére van egy kényelmesebb (de nem olcsóbb) mód a programozható logikai eszközök használatára. Vegyük az egyik a hardver leíró nyelvek - a Verilog vagy VHDL (abban az időben az írás, a többi népszerű nyelvek még nem is létezik), - leírja a viselkedését a készülék végre tesztelés és hibakeresés, szintetizált, és végül megvalósítja. Az egész folyamat jóval kevesebb időt vesz igénybe, mint az előző.

Mindez az OCA-ra vonatkozik. Ugyanezeket a műveleteket hajtják végre, kivéve, hogy a képletek és a listák sokkal jobban megszereznek. De a kód is szintetizálható és megvalósítható.

Meg kell jegyeznünk egy ilyen részletet. Modern FPGA tervezték a szintézis digitális automata -, hogy van egy pár sor órajellel és reset, amely rövidebb, mint a másik vonal, valamint közvetlenül jut a memória elemeket. Ennek kapcsán az ilyen eszközök szintézise kissé leegyszerűsödik. Ez elérhető az OCA-hoz is.

Ebben a tanulmányban az OCA absztrakt matematikai modelljét tekintettük, amely szintetizálható. A szintézis folyamatának összetettsége nem magasabb, mint a CCA szintézise.

A digitális automatika egy ismerős koncepció egy digitális eszközfejlesztő számára. Következésképpen a PCA-k használata sokkal érthetőbb és egyszerűbb, mint például a Petri-hálók használata.

További cikkeket terveznek, amelyek kiemelik a későbbi tanulmányokat.