\chapter{Implementace dekompozice}
\label{implementace}
\parindent= 30pt

V této kapitole bude představena metoda pro nalezení pokud možno co nejefektivnější dekompozice za pomocí nástrojů představených v předchozích částech práce. Nalezení nejideálnější dekompozice je problém obzvláště u rozsáhlých systémů takřka neřešitelný v nějakém rozumném čase. Abychom mohli říci, že nalezená dekompozice je pro daný automat opravdu nejlepší možná, museli bychom vědět, že žádná jiná dekompozice nedosahuje lepších výsledků. Toho lze (prozatím) dosáhnout jen vyzkoušením všech možných kombinací systémových trojic, kterých však i pro malé automaty existuje veliké množství. 

Kvalitu dekompozice určuje především rozsáhlost nalezených podautomatů a kvantita jejich vzájemné komunikace, ačkoliv na různé obvody mohou být kladeny rozličné požadavky. Obecně však určujícími parametry, kterými se řídí i zde uváděná metoda, bývá počet bloků v jednotlivých sysémech množin, který určuje počet bitů potřebných pro realizaci těchto systémů množin. Přestože by se mohlo zdát, že nemá cenu dekompozice zachovávající v konečném důsledku např. stejný počet výstupních nebo vstupních bitů, ale vedoucí jen k omezení počtu symbolů (např. máme-li 3bity, které tvoří 8 vstupních symbolů, zredukované na 5 symbolů, pro jejichž zakódování jsou stále potřeba 3 bity), je třeba mít na paměti možnost další dekompozice tohoto podautomatu, která by při menším množství symbolů mohla vést k lepším výsledům.

Z důvodu náročnosti hledání vhodných dekompozic byly vytvořeny heuristiky hledající téměř ideální dekompozice bez nutnosti procházení všech kombinací. Z těchto potom vychází i metoda nalezení obecné dvoustupňové (dekomponovaný automat se skládá ze dvou podautomatů) dekmpozice použitá v této práci. Metoda spočívá v nalezení všech SV systémů množin nad množinou stavů, což je jedna z heuristik používaných pro paralelní a sériové dekompozice. Následně se na základě těchto systémů množin vytvoří $\phi_S^i$, ze kterých se poté vytvoří $\phi_I^i$. Tyto se také co nejvhodněji sloučí a pomocí obou systémů se vytvoří výstupní systém množin. Ten se upravuje podle informace potřebné k splnění podmínek dekompozice. Pokud by tato dekompozice nevedla k úspěšnému cíli, je potřeba sloučit jiné bloky, popř. vybrat jiné systémy množin.

Dalším faktorem výrazně ovlivňujícím rychlost a kvalitu dekompozice je také kvalita (optimalizace) kódu programu dekompozici provádějícího. Jelikož se jedná o problém prohledávání určitých prostorů a následné práce s nimi, je vhodné použít při realizaci aplikace teorii grafů a nástroje s ní spojené.

\section{Nalezení SV systémů množin}
Pro nalezení všech systémů množin s SV je použita metoda definována v \ref{SVsearchDef}. Příklad hledání takovýchto systémů je popsán v př. \ref{SVsearchEx}. Vycházíme-li z předpokladu, že pokud máme několik různých SV systémů množin, kdy každý může bez pomoci ostatních systémů určit svůj vlastní následující stav, je možné je přímo použít pro paralelní dekompozici popř. pro sériovou dekompozici, pokud bychom měli jeden systém s SV a druhý vytvořili tak, aby oba splňovaly podmínky dekompozice. Pokud máme tedy dva systémy množin s SV a spojíme je dohromady (relace +), výsledný systém už sice nebude mít SV, ale bude potřebovat relativně málo informace od ostatních systémů, aby mohl určit následující stav.
\newpage
\begin{example}
\label{SVsearchEx}
Mějme tabulku \ref{SVSearchTab}, reprezentující přechody z jednotlivých stavů při různých vstupních symbolech automatu z Tab. \ref{compSpecFSM}. Potom můžeme vypočítat:
\begin{eqnarray}
\tau_{1,2}^1& = &\{\overline{a,b};\overline{c}\} + \{\overline{a,b};\overline{c}\} = \{\overline{a,b};\overline{c}\} \nonumber \\
\tau_{1,2}^2& = &\{\overline{a,b};\overline{c}\} + \{\overline{a,b};\overline{c}\} = \{\overline{a,b};\overline{c}\} \Rightarrow \textrm{SV systém množin}\nonumber \\
\tau_{1,3}^1& = &\{\overline{a,c};\overline{b}\} + \{\overline{a,c};\overline{a,b}\} = \{\overline{a,b};\overline{a,c}\} \nonumber \\
\tau_{1,3}^2& = &\{\overline{a,c};\overline{a,b}\} + \{\overline{a,b};\overline{a,c}\} = \{\overline{a,b};\overline{a,c}\} \Rightarrow \textrm{ SV systém množin} \nonumber \\
\tau_{2,3}^1& = &\{\overline{b,c};\overline{a}\} + \{\overline{a,c};\overline{b}\} = \{\overline{a,c};\overline{b,c}\} \nonumber \\
\tau_{2,3}^2& = &\{\overline{a,c};\overline{b,c}\} + \{\overline{a,c};\overline{a,b}\} = \{\overline{a,c};\overline{b,c};\overline{b,c}\} \nonumber \\
\tau_{2,3}^2& = &\{\overline{a,c};\overline{b,c}\} + \{\overline{a,c};\overline{a,b}\} = \{\overline{a,c};\overline{b,c};\overline{b,c}\} \nonumber \\
C(\tau_{2,3}^2)& = &\{\overline{a,b,c}\} \nonumber
\end{eqnarray}
\end{example}

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|cc}
\hline 
stav & in 0 & in 1\\
\hline
a & c & a\\
b & c & b\\
c & a & b\\
\hline
\end{tabular}
\end{center}
\caption{Tabulka pro hledání SV systémů množin}
\label{SVSearchTab}
\end{table}

\section{Hledání vhodných systémů množin}
Nalezené SV sytémy množin nad množinou stavů slouží jako základ pro nalezení vhodné dvojice systémových trojic. 

\subsection*{Hledání $\phi_S^1$ a $\phi_S^2$}
Jako systémy množin nad množinou stavů mohou sloužit již dva libovolně SV systémy bez toho, aby potřebovaly jakékoliv propojení, jelikož sami sobě poskytují dostatek informace k výpočtu následujícího stavu. To ale nemusí být vždy výhodné a lze využít faktu, že informace nutná k výpočtu následujícího stavu podautomatu se dá získat i od druhého podautomatu. Zároveň je však třeba snížit komunikaci mezi podautomaty na miminum. 

Metoda zde použitá sčítá a následně aplikuje funkci $C(\phi)$ na všechny možné kombinace nalezených SV systémů množin do té doby, dokud součinem dvou systémů množin nevznikne nový blok, ale dokud se bloky slučují. Dále je třeba si pamatovat nejlepšího dosaženého výsledku a pokud je nově vytvořený systém množin horší, není třeba se jím dále zabývat. Kvalita výsledku je dána velikostí největšího bloku systému a počtem bloků v tomto systémů. Porovnává se součet těchto dvou hodnot a v případě rovnosti také velikost vyšších z těchto hodnot. Pokud je hodnota těchto veličin u nově nalezeného systému množin stejná jako u nejlepšího dosud nalezeného, je třeba s tímto systémem také zacházet jako s možným kandidátem pro dekompozici.

Po nalezení všech nejlepších systémů se vybere takový systém množin, který obsahuje nejvíce relevantní informace. Poté se, pokud je třeba, provede indexace a vytvoří se druhý systém množin (doplňující) tak, aby byla splněna podmínka č. 5 z podmínek platné dekompozice. V tomto novém systému nesmí být v jednom bloku žádné dva stavy takové, které jsou u prvního systému množin také v jednom bloku. 

Po skončení této procedury se pomocí níže popsaných metod vytvoří $\phi_I^i$ a $\phi_{S\times I}^i$. Pokud jsou tyto dvě trojice úspěšné, je vhodné zkusit spojit další bloky těchto rozkladů a otestovat, zda je možné vytvořit platnou dekompozici i z nich. Při slučování je třeba si uvědomit, že je třeba upravit i doplňující systém a i ten kontrolovat, aby se zbytečně nerozrostl. Pokud už nelze žádné bloky spojit, je nalezena finální platná dekompozice.

\subsection*{Hledání $\phi_I^1$ a $\phi_I^2$}
V této fázi již máme $\phi_S$. Vstupní systém množin se potom hledá testováním, zda systémy množin $\phi_I^i$, kde jsou vždy spojeny dva bloky z $\phi_I(0)$, tvoří se systémy množin z minulého kroku systémové páry I - S. Takto se otestují všechny dvojice vstupních symbolů a pokud u některé dvojice je test úspěšný, mohou se tyto symboly spojit. Pokud je test úspěšný u dvou dvojic symbolů, kde jeden ze symbolů je společný oběma dvojicím, mohou se sloučit jen pokud je test úspešný i pro druhé vstupní symboly.

Takto by se však mohlo postupovat, pokud by se pracovalo jen s SV systémy množin a neimportovala se žádná další informace. Po otestování všech dvojic a případném poslučování všech možných systémů množin, vyberou se opět dva nejslibnější a s těmi se vytváří $\phi_{S\times I}^i$. Pokud je dekompozice platná, opět se zkouší sloučit další bloky a opět ověřovat platnost dekompozice.

\subsection*{Hledání $\phi_{S\times I}^1$ a $\phi_{S\times I}^2$}
Jak vyplývá z označení, systém množin $\phi_{S\times I}$ vznikne součinem systémů množin nad stavy a vstupními symboly, popř. ještě importované informace. 

Po vytvoření tzv. základního systému množin $\phi_{S\times I}$ je třeba zkontrolovat, jestli splňuje 1. podmínku platné dekompozice. Pokud ne, je třeba zkontrolovat, zda je možné získat potřebnou informaci z druhého podautomatu (musí být možné ji získat jen ze součinu $\phi_S^i$ a $\phi_I^i$). Pokud to možné není, dekompozice nemůže být platná a musí se vybrat jiné systémy množin.

Pokud však je možné informaci získat, popř. pokud není žádná třeba, je třeba otestovat zda platí podmínka č. 4. Pokud neplatí opět nemůže existovay platná dekompozice této dvojice podautomatů. Pokud ano, dekompozice bude platná, a je možné se stejně jako u předchozích případů pokusit se spojit další bloky $\phi_{S\times I}^i$ tak, aby stále byla splněna podmínka č. 1. 

\subsection*{Hledání optimálního množství importované informace}
Pokud je potřeba importovat nějakou informaci, je vhodné importovat jen minimální množství této informace. Proto se sloučí ty bloky výstupního systému množin, které nenesou relevantní informaci. Maximální možná importovaná informace je pak dána součinem vstupních a stavových systémů množin obou podautomatů. Pokud tedy není požadovaná informace v tomto součinu, je třeba zvolit jiné systémy množin.

\subsection*{Příklad hledání systémové trojice}
Pro příklad procesu hledání vhodných trojic zde použiji dekompozici uvedenou v sekci \ref{incDecExSec}. Nejprve si vytvoříme tabulku přechodů (viz př. \ref{SVsearchEx} a viz Tab. \ref{dekompExTab}). 
\newpage
\noindent Pomocí metody nalezení všech SV systémů množin získáme:
\begin{eqnarray}
\phi_{1,2}& = &\{\overline{a,b};\overline{d,e};\overline{c}\} \nonumber \\
\phi_{1,3}& = &\{\overline{a,b};\overline{a,c};\overline{d,e}\} \nonumber \\
\phi_{1,4}& = &\{\overline{a,b};\overline{a,d};\overline{d,e};\overline{c}\} \nonumber \\
\phi_{1,5}& = &\{\overline{a,d,e};\overline{a,b};\overline{c}\} \nonumber \\
\phi_{2,3}& = &\{\overline{a,b};\overline{b,c};\overline{d,e}\} \nonumber \\
\phi_{2,4}& = &\{\overline{a,b,d};\overline{d,e};\overline{c}\} \nonumber \\
\phi_{2,5}& = &\{\overline{a,b,d,e};\overline{c}\} \nonumber \\
\phi_{3,4}& = &\{\overline{a,b,d,};\overline{c,d};\overline{d,e}\} \nonumber \\
\phi_{3,5}& = &\{\overline{a,b,d,e};\overline{c,e}\} \nonumber \\
\phi_{4,5}& = &\{\overline{a,b};\overline{d,e};\overline{c}\} \nonumber
\end{eqnarray}

Kdybychom vybrali systém množin $\phi_{2,5}$, který má jen dva bloky. Je na přvní pohled vidět, že pro splnění 5. podmínky je třeba rozlišit mezi stavy \emph{a,b,d,e}, z čehož plyne, že systém rozkladů bude mít 4 bloky (např (a,c),(b),(d),(e)). Pro 4 bloky je zpotřebí 2 bitů, kdežto pro zakódování $\phi_{2,5}$ jen jeden, proto se pokusíme takto vyšetřit i ostatní systémy množin.

\begin{table}[ht]
\begin{center}
\begin{tabular}{c|cccc}
\hline 
stav & 00 & 01 & 10 & 11\\
\hline
a & a & a & a & c\\
b & a,b & a & a & c\\
c & b & a & a & c\\
d & d & a & a & c\\
e & d,e & a & a & c\\
\hline
\end{tabular}
\end{center}
\caption{Tabulka přechodů pro FSM zadaný tab. \ref{incompSpecFSMDec}}
\label{dekompExTab}
\end{table}

Jako vhodný pár byly tedy nakonec vybrány $\phi_S^1 = \{\overline{a1,b};\overline{a2,c};\overline{d,e}\}$ a $\phi_S^2 = \{\overline{a1,c,d};\overline{a2,b,e}\}$.  Podobným způsobem se potom hledají $\phi_I$. Opět použijeme tabulku \ref{dekompExTab} (první řádek lze považovat za oba indexované stavy a indexy \emph{i} a \emph{j} označují pořadí vstupního symbolu dle hodnoty), tentokrát však procházíme dvojice vstupů a porovnáváme množiny stavů podle $\phi_S$. Tímto způsobem dostaneme pomocí $\phi_S^1$:

\begin{eqnarray*}
\phi_{1,2}& = &\{\overline{a,d,e};\overline{a,b}\} \nonumber \\
\phi_{1,3}& = &\{\overline{a,d,e};\overline{a,b}\} \nonumber \\
\phi_{1,4}& = &\{\overline{a,b,c};\overline{d,c,e}\} \nonumber \\
\phi_{2,3}& = &\{\overline{a,b,c,d,e}\} \nonumber \\
\phi_{2,4}& = &\{\overline{a,c}\} \nonumber \\
\phi_{3,4}& = &\{\overline{a,c}\} \nonumber \\
\end{eqnarray*}
\newpage
Z tohoto můžeme poznat, že bez obavy ze ztráty potřebné informace můžeme spojit bloky vstupních symbolů 2,3 a 4, resp. 01,10 a 11, jelikož kombinace těchto symbolů vždy vedou do nějakého bloku $\phi_S$, kdežto kombinace s prvním symbolem 00 nikoliv. Lze také zkusit spojit bloky, které nelze bezpečně spojit, potom se ale musí informace potřebná k rozlišení stavů neležících v jednom bloku získat z druhého podautomatu.

Zbývající systémy množin $\phi_{S\times I}^1$ a $\phi_{S\times I}^2$ se získají součinem v předchozích krocích vytvořených systémů množin. Jako kontrolu je třeba vyzkoušet, zda tyto systémy množin tvoří S $\times$ I - S rozkladové páry (platí 1. podmínka). V tomto případě zjistíme, že systém množin $\phi_{S\times I}^2$ potřebuje dodatečnou informaci pro splnění podmínky. Tuto informaci snadno zjistíme nalezením bloků, které nevyhovují podmínce a jejich následným rozkladem a určením informace, která tímto rozkladem vznikla. Tato informace je dostupná z $\phi_{S\times I}^1$, lze ji proto importovat a dekompozice je platná.

Pokud platí 1. podmínka, je třeba otestovat, zda platí 4. podmínka, tj. že se dá jednoznačně spočítat výstupní symbol. Pokud je i toto splněno, lze zkoušet spojovat různé kombinace bloků pro snížení počtu výstupních symbolů a tím pádem zlepšení dekompozice. je však nutné kontrolovat, zda výstupní systém množin stále obsahuje informaci potřebnou pro druhý podautomat.

\section{Implementace metody}
Jak již bylo řečeno výše, úspěšnost celé metody je závislá na optimalizaci a kvalitě zdrojového kódu aplikace. Na jednu stranu to klade vysoké nároky na autora kódu, na druhou stranu to umožňuje značně ovlivňovat rychlost a kvalitu dekompozice bez úpravy metody jen s pomocí optimalizace kódu.

Program realizující uvedenou metodu je napsán v jazyce C++. Při spouštění programu je třeba zadat cestu ke zdrojovému souboru ve formátu KISS 2 (popsán např. v \cite{hrdy01}). Program se skládá z těchto modulů:

\subsection*{Main}
Modul \emph{main} obsahuje základní části programu, kontroluje správnost parametrů a volá jednotlivé obsluhující metody.

\subsection*{Bit}
Třída \emph{Bit} popsaná v modulu \emph{bit} reprezentuje pole bitů. Ačkoliv standardní knihovna C++ obsahuje dva nástroje pro práci s bity, pro potřebu této práce jsou tyto metody nedostatečné, jelikož pracují pouze s hodnotami \emph{0} nebo \emph{1} a není zde označení pro \emph{don't care} stav. Samotná třída Bit potom obsahuje také nástroje pro porovnávání bitů a hlavně úpravu dvou vektorů bitů tak, aby pokud obsahují don't care stavy a umožňují takovou úpravu byly shodné.

\subsection*{FSM}
\emph{FSM} je modul obsahující třídu, která reprezentuje konečný automat. Mimo této také obsahuje třídu \emph{Symbol}, který reprezentuje řádek a obsahuje čtyři položky reprezentující vstupní a výstupní symbol objektem typu \emph{Bit}, vnitřní stav a následující stav datovým typem \emph{int}.

Modul obsahuje funkce pro práci s automatem jako přidání řádku, zjištění velikosti automatu apod. Hlavně se ale stará o soudržnost všech údajů o automatu dostupných (zapouzdřuje tato data).

\subsection*{Lexan a Synan}
Modul \emph{lexan} obsahuje lexikální analyzátor, který čte znaky vstupního souboru. \emph{Synan} obsahuje syntaktický analyzátor, který tyto znaky zpracovává a přidává řádky do objektu typu \emph{FSM}.

\subsection*{Information}
Modul \emph{information} obsahuje třídu Inf reprezentující základní informaci. Třída tedy obsahuje dva celočíselné stavy a nástroje pro práci s ní. V dalších modulech jsou potom objekty typu Inf udržovány v kontejneru \emph{std::set}, který umožňuje rychlé vyhledávání a je tedy vhodný pro uchování velkého množství informace, často potřebné v průběhu procesu dekompozice.

\subsection*{Block}
\emph{Block} obsahuje předpis pro vytvoření objetku Block. Obsahuje pole celočíselných hodnot představující jednotlivé řádky automatu, které jsou v bloku uloženy a identifikátor reprezentující buď vstupní a výstupní symboly pomocí objektu typu \emph{Bit} nebo stavy pomocí objektu \emph{State}, definovaný v modulu \emph{Block} a reprezentující číslo stavu, popř. jeho index.

\subsection*{Part}
Modul \emph{part} obsahuje třídu reprezentující systém množin buď nad stavy nebo nad bity. Bloky jsou zde uloženy v kontejneru \emph{std::vector}. Třída obsahuje také nástroje potřebné pro snadnou práci se systémy množin, jako nalezení bloku, velikost (počet bloků) systému apod.

\subsection*{Decomposition}
Modul \emph{decomposition} obsahuje veškeré nástroje realizující dekompozici metodou popsanou výše. V~tomto modulu se hledají systémové trojice, testuje se platnost dekompozice, hledají SV systémy a pod. 

\subsection*{Output}
V tomto modulu se vezmou výsledné systémy množin a sestaví se z nich podautomaty a logické funkce potřebné pro dekompozici. Také obsahuje metodu vypisující tyto části do souborů typu KISS 2.

\subsection*{ }
Výstupem programu a tedy celého procesu dekompozice jsou především dva soubory ve formátu KISS 2 \emph{aut1} a \emph{aut2}, představující oba podautomaty. Dále jsou součástí výstupu soubory s funkcemi představujícími vstupní a výstupní blok \emph{in\_bl}, resp. \emph{out\_bl}. Pokud jsou podautomaty propojené, jsou součástí výstupu také funkce realizující toto propojení \emph{con1} a \emph{con2}.