main.org

Modelování a simulace

Úvod

Základní pojmy

Systém

Je soubor elementárních částí, které mají mezi sebou určíté vazby.

Model

Napodobenina systému jiným systémem

Modelování

Vyrváření modelů systémů

Simulace

Získávání nových znalostí o systémz experimentováním s jeho modelech

Základní etapy modelování a simulace

1. Vytvoření abstraktního modelu
2. Vytvoření simulačního modelu
3. Verifikace a validace
4. Simulace
5. Analýza a interpretace výsledků

Formální definice systému

Systém $S$ je dvojice \[S = (U, R)\]

kde:

$U$ je konečná množina prvků systému:

\[U = \{u_1, u_2, …, u_N\}\]

Prvek systému $u = (X, Y)$:

$X$ je množina všech vstupních proměnných

$Y$ je množina všech výstupních proměnných

Charakteristika systému $R$ je množina všech propojení

\[R = \bigcup^N_i,j=1 R_ij\]

Propojení prvku $u_i$ s prvkem $u_j$:

\[R_ij \subseteq Y_i × X_j\]

Čas

Rozlišujeme tři typy času:

1. Reálný času Probíháý skutečný děj v reálném systému
2. Modelový čas Časová osa modelu, nemusí být synchronní s reálným časem
3. Strojový čas Čas spotřebovaný na výpočet programu

Časová množina

Množina všech časových okamžiků, ve kterých jsou definovány hodnoty vstupních, stavových a výstupních proměnných prvku systému

Může být diskrétní nebo spojitá[fn:continuous]

Chování systému

Každému časovému průběhu vstupu přiřazuje časový průběh výstupu. Lze definovat jako zobrazení.

Systémy považujeme za systémy se stejným chováním, vyvolají-li stejné podněty u obou systémů stejné reakce.

Izomorfní systémy jsou systémy, kde prvky systémů navzájem můžeme přiřadit 1:1.

Homomorfní systémy jsou systémy, kde prvky systémů navzájem můžeme přiřadit N:1, ale ne naopak.

Okolí systému

Okolí systému zahrnuje vše, co má vliv na chování systému, ale není jeho součástí.

Systémy můžeme rozdělit na uzavřené (nekomunikují s okolím nebo jej zanedbábají) a otevřene (mají definované vstupy a výstupy).

Klasifikace prvků systémů

Klasifikace 1

Prvky se spojitým chováním vs prvky s diskrétním chováním

Klasifikace 2

Prvky s deterministickým chováním vs prvky s nedeterministickým chováním

Klasifikace systémů

Typ systému závisí na typu jeho prvků

Klasifikace 1

Spojité, Diskrétní, Kombinované

Klasifikace 2

Deterministické, nedeterministické

Simulace

Cílem simulace je získat nové informace o chování systému v závislosti na vstupních veličinách a na hodnotách parametrů.

Opakovaně vyhodnocujeme model, tak dlouho, dokud nezískáme dostatek informací o chování systému nebo dokud nenalezneme takové hodnoty parametrů, pro něž má systém žádané chování.

Typy simulace podle modelu

Spojitá, diskrétní, kombinovaná. Kvalitativní, kvantitativní.

Typy simulace podle simulátoru

Na počítači, real-time, paralelní a distribuovaná

Verifikace modelu

Měla by předcházet simulaci. Ověťujeme, zda simulační model odpovídá 1:1 (izomorfně) abstraktnímu modelu.

Validace modelu

Jedná se o jeden z nejobtížnějších problémů modelování. Vyžaduje neustálou konfrontaci informací a modelovaném systému a dat ze simulovaného systému.

Nelze absolutně dokázat přesnost modelu. Pokud chování modelu neodpovídá předpokládanému chování systému, musíme model modifikovat.

Modely

Abstraktní model

Nepostihuje reálný svět v celé komplikovanosti. Zajímá se jen o ohraničené, vhodně zvolené části. Identifikuje vhodné sloky systému.

Pro sestavení abstraktního modelu potřebujeme studovat systém pro určitá kritéria a závislosti, predikovat chování systému za určirých podmínek, analyzovat faktory, které jsou pro činnost systému nejvýznamnější a nalézt takové kombinace parametrů, které vedou k nejlepší odezvě systému.

Simulační model

Jedná se o abstraktní model zapsaný formou programu v nějakém programovacím jazyce.

Konceptuální modely

Jejich komponenty zatím nebyly přesně popsány. Používají se v počáteční fázi modelování pro ujasnění souvislostí a komunikaci v týmu.

Má formu textu nebo obrázků.

Deklarativní modely

Popisuje přechody mezi stavy systému.

Je definován stavy a událostmi, které způsobí přechod z jednoho stavu do druhého.

Je vhodný především pro diskrétní modely.

Například konečné automaty, petriho sítě.

Funkcionální modely

Grafy zobrazující funkce a proměnné. Uzel grafu je funkce nebo proměnná.

Například systémy hromadné obsluhy, bloková schemata, grafy signálových toků.

Modely popsané rovnicemi

Používají se algebraické, diferenciální, diferenční rovnice.

Mívají podobu neorientovaných grafů.

Například elektrická schemata, systémy dravec kořist, kyvadla, logistické systémy, chaos.

Prostorové modely

Rozdělují systém na prostorově menší ohraničené podsystémy.

Například parciální diferenciální rovnice difuze nebo proudění, celulární automaty, mechanické modely těles.

Multimodely

Složeny z různých typů modelů, obvykle heterogenních.

Například kombinované modely, fuzzy modely, propojené simulační systémy.

Simulační nástroje

Mohou používat klasické programovací jazyky samy o sobě, nebo s využitím knihoven. Existují specializované simulační jazyky (Simula67, Modellica…)

Simulační jazyky

Poskytují prostředky usnadňující efektivní popis struktury a chování modelů a také popis simulačních experimentů.

Výhodou je jednodušší popis modelu a možnost automatické kontroly popisu modelu.

Nevýhodami jsou náklady na vytvoření překladače, údržbu, výuku…

Celkově nejsou příliš používány.

Modelování náhodných procesů

Náhodná proměnná

Náhodná proměnná je taková veličina, která jako výsledek pokusů může nabýt nějakou hodnotu, přičemž předem nevíme jakou.

Rozlišujeme diskrétní a spojité

Náhodné veličiny můžeme zadat distribuční funkcí nebo rozdělením pravděpodobnosti.

Diskrétní rozdělení pravděpodobnosti

Určuje vztah mezi možnými hodnotami náhodné veličiny $x_i$ a jim příslušejícími pravděpodobnostmi $p_i = P(X = x_i)$.

Obecně platí vztah: \begin{equation} ∑_i=1^∞ p_i = 1 \end{equation}

Lze definovat například tabulkou pravděpodobnosti pro všechny možné hodnoty náhodné proměnné, suma všech pravděpodobností musí být 1.

Diskrétní distribuční funkce

Distribuční funkce náhodné veličiny $X$ je funkce: \begin{equation} F(x) = P(X \leq x) \end{equation}

Kde $P(X \leq x) je pravděpodobnost toho, že náhodná veličina X nabude hodnoty menší nebo rovnu zvolenému x.

Platí vztah: \begin{equation} F(x) = ∑_{x_i \leq x} p_i \end{equation}

Kraf distribuční funkce pro diskrétní náhodné proměnné je po částech konstantní.

Distribuční funkce spojité náhodné proměnné

\begin{equation} F(x) = P(X \leq x) = ∫_-∞^x f(x) dx \end{equation}

Distribuční fuknce je neklasající. Roste od 0 do ∞

Pravděpodobnost hodnoty $x$ pro $a \leq x$ a $x \leq b$ je rozdíl hodnot distribuční funkce v bodech $b$ a $a$. Vyjádřeno vzorcem: \begin{equation} P(a \leq X \leq b) = F(b) - F(a) \end{equation}

Hustota pravděpodobnosti spojité náhodné proměnné

• Vždy větší než 0
• Vyjádřena jako derivace distribuční funkce
• Integrál funkce hustoty pravděpodobnosti je vždy 1
• Hodnota pravděpodobnosti pro $x$ mezi $a$ a $b$ je dána jako intergrál hustota pravděpodobnosti mezi $a$ a $b$

Poissonovo rozložení

Diskrétní rozložení udávající počet nějakých událostí za jednotku času. Vzorec: \begin{equation} p_i = \frac{λ^i}{i!} e^-λ, λ > 0, i ∈ {0, 1, 2,…} \end{equation} Kde $E(x) = λ, D(x) = λ$

Rovnoměrné rozložení

Označujeme $R(a, b)$

Hodnota distribuční funkce lineárně roste mezi body $a$ a $b$. Hodnota funkce hustoty pravděpodobnosti je konstatní.

Exponenciální rozložení

Používá se pro dobu mezi dvěma událostmí.

Diskrétní simulace

Úvod

Diskrétní systém můžeme popsat:

• Programem v programovacím jazyce
• Petriho sítí
• Automaty nebo sítěmi automatů
• Procesními algebrami
• …

Procesy

Proces je posloupnost událostí. Pokud jsou procesy prováděny současně, nazýváme je paralelní. Pokud paralelní procesy provádíme na jednoprocesorovém počítači, jedná se o kvaziparalelní procesy.

V modelovaných systémech často existuje mnoho paralelně probíhajících a vzájemně komunikujících procesů.

Paralelismus

Pro zajištění paralelismu je třeba popsat jednotlivé procesy sekvencí kroků (napsat program). Dále je nutné popsat komunikace procesů – zprávy. Rovněž je nutné vyřešit synchronizace při používání sdílených prostředků.

Petriho sítě

Definice Petriho sítě:

\begin{equation} Σ = (P, T, F, W, C, M_0) \end{equation}

Kde:

• $P$ je množina míst (stavů)
• $T$ je množina přechodů, $P ∩ T = ∅$
• Incidenční relace $F \subseteq (P × T) ∪ (T × P)$
• Váhová funkce $W : F → \{1, 2, …\}$
• Kapacity míst $C : P → N$
• Počáteční značení $M_0 : P → N$

Petriho sítě obvykle zadáváme formou grafu, kde:

• Místa = Kružnice
• Přechody = Obdélníky
• Incidenční relace = Šipky
• Váhová funkce = ohodnocení hran

Systémy hromadné obsluhy

SHO (Queueing systems) jsou systémy obsahující zařízení s frontami, která poskytují obsluhu transakcím.

Typický systém hromadné obsluhy obsahuje:

• Transakce (procesy) a popis jejich příchodů
• Obslužné linky a popis jejich obsluhy
• Fronty různých typů, ve kterých transakce čekají

Při simulaci sledujeme informace o čase stráveném v systému pro konkrétní transakci, doby čekání ve frontách, vytížení obslužných linek. Cílem je odhalit zdržení, optimalizovat výkon …

Vstupní tok požadavků

Obvykle se jedná o proces příchodů do systému. Zadáváme buď střední dobu mezi příchody (exponenciální rozdělení) nebo počet příchodů za jednotku času (Poissonovo rozdělení).

Fronty čekajících požadavků

Vytvoří se, když požadavek chce být obsloužen již obsazeným zařízením. Pro fronty jsou typické:

• Způsob řazení požadavků (FIFO, LIFO, …)
• Způsob výběru požadavků z fronty
• Největší možná délka fronty

Definujeme pojmy:

• Nulová fronta - Požadavek nesmí vstoupit do fronty, jedná se o systém se ztrátami
• Konečná fronta - Omezuje kapacitu fronty
• Fronta s netrpělivými požadavky - Netrpělivý požadavek opouští systém, dojde-li k timeoutu.

Prioritní fronty, priorita obsluhy

U jedné obslužné linky může být více front s různými prioritami, prioritních úrovní může být více. Přicházející požadavky nejsou rovnocenné.

Při příchodu požadavku s vyšší prioritou se stane jedna ze 4 věcí:

1. Započatá obsluha se ukončí
2. Obsluha se přeruší a začne obsluha požadavku s vyšší prioritou. Požadavek, jehož obsluha je přerušena buď opouští systém neobsloužen nebo se znovu vrací do fronty a je obsloužen později.
3. Jsou-li všechny linky obsazeny a u každé je fronta, požadavek se sám rozhodne, do které se zařadí.
4. Vytvářejí-li požadavky jednu společnou frontu, požadavek vstupuje do té linky, která se nejdříve uvolní.

Obslužná síť

Vzniká spojením několika obslužných linek. Může být:

• Otevřená – Výměna požadavků mezi sítí a okolím
• Uzavřená – Nedochází k výměně požadavků s okolím
• Smíšená – Pro některé typy požadavků je otevřená, pro jiné uzavřená

Statické vlastnosi obslužné sítě jsou definovány počtem a charakteristikou obslužných linek a topologií obslužné sítě.

Dynamické vlastnosti jsou definovány charakteristikami procesů příchodů, obsluhy, přechodu mezi linkami a strategií obsluhy požadavků v obslužných linkách.

Klasifikace SHO

Standard stučného a přehledného vyjádření typu SHO používá tři hlavní hlediska:

• X - Typ procesu popisujícího příchod požadavků k obsluze
• Y - Zákon rozložení délky obsluhy
• c - Počet dostupných obslužných linek.

Například systém M/M/1 značí Poissonovo rozložení příchodu požadavků, exponenciální dobu obsluhy a 1 obslužnou linku.

Modelování SHO

Popisujeme procesy v systému, stav obslužných linek a front a průběh obsluhy transakcí v zařízeních.

Podle kapacity linek rozlišujeme:

• Zařízení – kapacita 1
• Sklady – kapacita > 1

Modelujeme-li více zařízení stejného typu, pak každé zařízení má vlastní frontu, nebo k zařízením vede jedna fronta.

SIMLIB

V knihovně simlib definujeme následující prostředky pro diskrétní modelování:

• Process – Modelování procesů
• Event – Modelování událostí
• Facility – Obslužná linka s výlučným přístupem
• Store – Obslužná linka s kapacitou
• Queue – Fronta
• Statistiky

Při modelování je ve funkci main potřeba zavolat funkci Init, která inicializuje simulátora a nastaví počáteční a koncový modelový čas.

Pro zahájení simulace se využívá funkce Run.

Modelový čas programu reprezenutjeme globální proměnnou double Time, která je ovládána výhradně jádrem simulátoru a nelze do ní zapisovat.

SIMLIB poskytuje generátory pseudonáhodných čísel:

• double Random() – Rovnoměrné rozdělení mezi 0, 1
• double Uniform(double L, double H) – Rovnoměrné rozdělení mezi L a H
• double Exponential(double E) – Exponenciální rozdělení se středem E
• double Normal(double M, double S) – Normální rozložení se středem M a rozptylem S.

Použití událostí je provedeno následovně:

class Udalost : public Event {
        void Behavior() {
            // Příkazy události
            Activate(Time + e); // Periodicky aktivovat po čase e
        }
}
(new Udalost)->Activate(); // Naplánuje na čas Time (okamžitě)
(new Udalost)->Activate(t); // Naplánuje na čas Time + t

Generování transakcí se provádí vytvořením události generátoru, která ve svém těle aktivuje nové procesy. Například takto:

class Generator : public Event {
        void Behavior() {
                (new Proc)->Activate(); // Vytvoří a aktivuje nový proces
                Activate(Time+Exponential(2)); // Znovu se aktivuje za čas udaný exponenciálním rozložením
        }
}

Procesy jsou odvozeny za abstraktní třídy Process:

class Transakce : public Process {
        public:
        Transakce (parametry) { // Konstruktor
                // Inicializace
        }

        void Behavior() {
                // Popis chování programu
        }
}

Po aktivaci procesu se volá metoda Behavior. Provádění je přerušeno při čekání ve frontě (funkce Seize, Enter) nebo při explicitním volání funkce Wait(dt), kde dt je doba čekání.

Algoritmus next event a kalendář událostí

Kalendář je uspořádaná datová struktura uchovávající aktivační záznamy budoucích událostí. Každá naplánovaná budoucí událost má v kalendáři záznam obsahující aktivační čas, prioritu a samotnou událost. Kalendář umožňuje výběr prvního záznamu s nejmenším aktivačním časem a vkládání/rušení aktivačních záznamů.

Pseudokód:

// Inicializace času, kalendáře, modelu
while ( !empty(kalendar) ) {  // Dokud je kalendář neprázdný
    item_t item = kalendar.pop();  // Vybere první prvek kalendáře
    if ( item.aktivacni_cas > T_END ) {  // Prvek by se měl aktivovat po konci simulace
        End();  // Ukončení
    }
    SetTime(item.aktivacni_cas);  // Nastaví čas na aktivační čas události
    Execute(item);  // Provede popis chování události.
}

Spojitá simulace

Úvod

Spojíté systémy jsou popsány:

• Soustavami obyčejných diferenciálních rovnic
• Soustavami algebraických rovnic
• Algebraicko-diferenciálními rovnicemi
• Blokovými schematy
• Parciálními diferenciálními rovnicemi
• Grafy signálových toků
• Elektrickými schematy
• …

Soustavy diferenciálních rovnic mogou být popsány maticově:

\begin{align*} \frac{d}{dt}\vec{w}(t) &= A(t)\vec{w}(t) + B(t)\vec{x}(t)
\vec{y}(t) &= C(t)\vec{w}(t) + D(t)\vec{x}(t) \end{align*}

kde $\vec{x}$ je vektor vstupů, $\vec{w}$ je vektor stavových proměnných, $\vec{y}$ je vektor výstupů a A, B, C, D jsou matice koeficientů.

Koeficienty mohou být nezávislé na čase (stacionární systémy), časové proměnné, konstanty (lineární systémy), nelineární funkce.

Převod rovnic vyššího řádu

Rovnice vyššího řádu musíme převést na soustavu rovnic prvního řádu, pro které máme vhodné numerické metody.

Metoda snižování řádu derivace

1. Osamostatníme nejvyšší řád derivace
2. Zapojíme všechny integrátory za sebe a ke vstupu prvního připojíme pravou stranu

Podmínka: nesmí být derivace vstupů

Příklad \begin{align*} y” - 2y’ + y &= x
y” &= 2y’ - y’ + x \ y’ &= ∫ y” \ y &= ∫ y’ \end{align*}

Metoda snižování řádu derivace má typický tvar plokového schématu.

Je nutné dát pozor na počáteční podmínky.

Metoda postupné integrace

Vhodná pro rovnice s derivacemi vstupů.

1. Osamostatníme nejvyšší řád derivace
2. Postupně integrujeme rovnice a zavádíme nové stavové podmínky
3. Vypořítáváme nové počáteční podmínky

Příklad \begin{align*} p^2y &= p^2x + p(3x-2y) + (2x-y)
py &= px + (3x-2y) + \frac{1}{p}(2x-y) \text{, proměnná $w_1 = \frac{1}{p}(2x-y)$} \ py &= px + 3x-2y + w_1 \ y &= x + \frac{1}{p}(3x - 2y + w_1) \text{, proměnná $w_2 = \frac{1}{p}(3x - 2y + w_1)$} \ y &= x + w_2 \ \ w_1 &= \frac{1}{p}(2x-y) \text{, $w_1(0) = y’(0) - x’(0) - 3x(0) + 2y(0)$} \ w_2 &= \frac{1}{p}(3x-2y+w_1) \text{, $w_2(0) = y(0) - x(0)$} \ y &= x + w_2

\end{align*}

Numerické metody

Potřebujeme metody pro řešení obyčejných diferenciálních rovnic prvního řádu a řešení algebraických rovnic (hledání kořenů, řešená rychlých smyček)

Hledáme řešení rovnice:

\begin{equation} y’ = f(t,y) \end{equation}

které má tvar:

\begin{equation} y(T) = y_0 + ∫_0^T f(t,y)dt \end{equation}

Na počítači je řešení aproximováno v bodech $t_0, t_1, t_2,…$.

Definujeme integrační krok $h_i = t_i+1 - t_i$

Rozlišujeme metody jednokrokové (vycházejí jen za aktuálního stavu) a vícekrokové (používají historii stavů a vstupů).

Dále dělíme metody na explicitní (výsledek získán dosazením do vzorce) a implicitní (vyžaduje řešení algebraických rovnic v každém kroku).

Runge-Kutta 2. řádu

\begin{align*} k_1 &= hf(t,y(t))
k_2 &= hf(t + \frac{h}{2}, y(t) + \frac{k_1}{2}) \ y(t+h) &= y(t) + k_2 \end{align*}

#define SIZE 2

// Popis spojitého systému
// Vstupy: t = začátek kroku
//         y = stavový vektor (výstupy integrátoru)
// Výstup: yin = vektor derivací (vstupy integrátoru)
void f(double t, double *y, double *yin);

// Krok metody Runge-Kutta 2. řádu
// Vstupy : t počáteční čas
//          h délka kroku
//          y stavový vektor
// Výstup : y nový stavový vektor
void RK2step(double t, double h, double *y) {
    double yin[SIZE];  // Vstup integrátoru
    double ystart[SIZE]; // Počáteční stav

    double k1[SIZE];
    double k2[SIZE];

    int i;

    for (i = 0; i < SIZE; i++) {
        ystart[i] = y[i];
    }

    f(t, y, yin);  // yin = f(t, y(t))

    for (i = 0; i < SIZE; i++) {
        k1[i] = h * yin[i];  // k1 = h * f(t, y(t))
        y[i] = ystart[i] + k1[i] / 2;  // y(t) + k1/2
    }

    f(t + h / 2, y, yin);  // yin = f(t+h/2, y(t)+k1/2)

    for (i = 0; i < SIZE; i++) {
        k2[i] = h * yin[i];  // k2 = h * f(ft+h/2, y(t)+k1/2)

        // Result :
        y[i] = ystart[i] + k2[i];
    }
}

int main(void) {
    double y[SIZE] = {0,1};
    double stepsize = 0.1;

    double t = 0;

    while (t < 20) {
        RK2step(t, stepsize, y);
        t += stepsize;
    }
}

Runge-Kutta 4. řádu

\begin{align*} k_1 &= hf(t, y(t))
k_2 &= hf(t + \frac{h}{2}, y(t) + \frac{k_1}{2}) \ k_3 &= hf(t + \frac{h}{2}, y(t) + \frac{k_2}{2}) \ k_4 &= hf(t + h, y(t) + k_3) \ y(t+h) &= y(t) + \frac{k_1}{6} + \frac{k_2}{3} + \frac{k_3}{3} + \frac{k_4}{6} \end{align*}

Vlastnosti integračních metod

Chyba

1. Lokální – zaokrouhlovací (round-off) nebo chyba aproximace (truncation)
2. Akumulovaná

Stabilita

Stabilita numerického řešení, vliv velikosti integračního kroku na stabilitu. Některé metody mají malou oblast stability.

Tuhé systémy

Tuhé systémy mají problém velmi rozdílných časových konstant. Například:

\begin{equation} y” + 101y’ + 100y = 0 \end{equation}

Pro tuhé systémy se používájí speciální integrační metody.

Nelze použít zkrácení kroku, vede k akumulaci chyb a malé efektivitě výpočtu.

Výběr integrační metody

Obvykle vyhovuje některá varianta metody Runge-Kutta 4. řádu. Nespojitosti ve funkci popisující systém snižují efektivitu vícekrokových metod. Pro ověření správosti je třeba vyzkoušet různé integrační metody a různé velikosti kroku. Existuje horní limit velikosti kroku.

Rychlé smyčky

Cyklus v grafu závislosti funkčních bloků. Dá se řešit speciálním blokem, který (například iteračně řeší algebraické rovnice) nebo přepracováním na model bez smyček (například vložení integrátoru).

SIMLIB

SIMLIB definuje automatickou konstrukci výrazových stromu pmocí třídy Expression.

Vybrané třídy a funkce v SIMLIB

• Constant
• Parameter
• Variable
• Function, Sin, Exp …
• Integrator
• Sampler
• SetStep(minstep, maxstep
• SetAccuracy(abs, rel)
• SetMethod

Kombinovaná simulace

Úvod

Spojuje diskrétní a spojitou simulaci. Řeší problém kombinace událostí a numerické integrace. Detekuje změny stavových podmínek a na jejich základě způsobuje stavovou událost. Musí provádět zkracování kroku, aby došlo k dokročení na stavovou událost.

Stavové podmínky

Stavovou událost nelze naplánovat, stane se po dosažení zadané hodnoty spojité veličiny. Může nastat problém detekce stavové události na základě nepřesnosti výpočtu nebo při použití příliš dlouhého kroku (překročení).

Algoritmus řízení simulace pro kombinovanou simulaci

// Inicializace stavu a podmínek
// ...

while (Time < t_end) {
    state.save();  // Uložení stavu
    time.save();  // Uložení času

    IntegrateStep();  // Krok numerické integrace
    time += t;  // Posun času

    cond.check(); // Vyhodnocení podmínek

    if ( cond.changed() ) {
        if (step <= min_step) {
            cond.confirm();  // Potvrzení změn podmínek
            event();  // Stavová událost
            step = step_standard;  // Nastavení velikosti kroku na běžnou velikosti
        }
        else {
            state.restore();  // Obnovení stavu
            time.restore();  // Obnovení času

            step = step / 2;  // Zkrácení kroku
            if ( step < min_step ) {
                step = min_step;  // Dokročení
            }
        }
    }
}

Tento pseudokód patří do algoritmu next-event místo příkazu Time = next_event_time.

SIMLIB

Pro vyjádření stavových podmínek se používají speciální abstraktní třídy:

• Condition – Detekuje jakoukoli změnu
• ConditionUp – Detekuje změnu z false na true
• ConditionDown – Detekuje změnu z true na false

Odvozené třídy definují metodu void Action() s popisem stavové události.

Simulace číslicových systémů

Dle úrovně popisu můžeme dělit:

• Elektrické – Tranzistory, rezistory, kondenzátory
• Logické – Hradla, klopné obvody
• Meziregistrové přenosy – Čítače, řadiče, ALU
• Systémové – Procesory, paměti, periferie

Modely signálů se dělí podle hodnot, kterých může signál nabývat. Nejčastěji se používají dvouhodnotové, třáhodnotové, pětihodnotové a devítihodnotové (VHDL std_logic).

V číslicových systémech modelujeme zpoždění. Zpoždění může být nulové, jednotkové, přiřaditelné nebo přesné.

Simulační algoritmus je řízen událostmi. Může nastat problém velkého množství událostí v kalendáři. Řešením je selektivní sledování pomocí dvoufázového algoritmu, který vyhodnocuje jen prvky, které jsou ovlivněny změnou na vstupu.

Zjednodušený algoritmus řízení simulace číslicových obvodů

Dokud jsou v kalendáři události, vybírej včechny plánované události na čas T. Aktualizuj hodnoty signálu, přidej všechny prvky připojené k signálu do množiny M. Následně pro všechny prvky v množině M vyhodnoť a pokud dojde ke změně jeho výstupu, naplánuj novou událost.

Celulární automaty

Úvod

Celulární automat je typicky diskrétní systém, obsahující následující prvky:

• Buňky (cell) – Základní element, který může být v jednom z konečného množství stavů.
• Pole buněk (lattice) – N-rozměrné pole, které může být nekonečné.
• Okolí (neighbourhood) – Liší se počtem a pozicí okolních buněk, se kterými spolupracuje.
• Pravidla (rules) – Funkce stavu buňky a jejího okolí definující nový stav buňky v čase.

Mezi základní typy okolí patří Von Neumannovo 4-okolí, Mooreovo 8-okolí a Margolovo okolí.

Celulární automat s konečným polem buněk musí definovat okrajové podmínky. Mezi typy okrajových podmínek patří periodické (na okraji je hodnota buňky na opačném okraji), pevné (na okraji je pevně zvolená hodnota), adiabatické (na okraji je hodnota vedlejší buňky) a reflektivní (na okraji je hodnota předposlední buňky).

Celulární automaty se mohou implementovat několika způsoby:

1. Přímá implementace – Každá buňka uložena zvlášť v poli
2. Implementace vyhledávací tabulkou – Tabulka obsahuje jen nenulové buňky
3. SIMD styl implementace – Více buněk v jedné proměnné, použití bitových operací
4. Hash life implementece – Cachované, velmi optimalizované

Obecné vlastnosti CA

Konfigurací CA rozumíme stav všech buněk. Stav se vyvíjí v čase a prostoru podle zadaných pravidel. Čas i prostor jsou diskretizovány. Počet stavů buňky je konečný. Buňky jsou identické. Následující stav buňky závisí pouze na aktuálním stavu.

Třídy CA

1. Po konečném počtu kroků dosáhnou ustáleného stavu
2. Dosáhnou periodického opakování nebo zůstanou stabilní
3. Chaotické chování, výsledné posloupnosti konfigurací tvoří fraktální útvary
4. Kombinace běžného a chaotického chování. Nejsou reverzibilní

Footnotes

[fn:continuous] Na číslicovém počítači se vždy diskretizuje