 \lstset
    {
    language=C++,
    frame=,
    framesep=8pt,
    backgroundcolor=\color{VeryLightGray},
    basicstyle=\small,
    keywordstyle=\ttfamily\color{DarkGray}\bfseries,
    identifierstyle=\rmfamily \color{RealGray},
    commentstyle=\rmfamily\color{LightGray}\itshape,
    stringstyle=\rmfamily\color{RealGray},
    showstringspaces=false,
    escapechar=\#,
    morekeywords={uint},
%    numbers=left,                   % where to put the line-numbers
%    numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
%    stepnumber=2,                   % the step between two line-numbers. If it's 1 each line will be numbered
%    numbersep=5pt                  % how fare the line-numbers are from the code
    }

\chapter{Popis řešení}%
\label{kap_implementace_mbd}%
Vytvoření softwarového balíku na minimalizaci pomocí MBD je celkově velmi
složitý problém a to zvláště v případě, když jde o originální výtvor bez
použití jiných softwarových knihoven či jiných doplňků. Účelem této kapitoly je
popsat postupy použité v této práci a zdůvodnit je. Jde o tedy o jakési
nahlédnutí pod pokličku celé implementace. Pro jednoduchost zde nebudou popsány
konkrétní používané datové struktury a zdrojové kódy, jejichž stručný
komentovaný výpis je v kapitole \ref{kap_implementace}.

\section{Posloupnost operací při minimalizaci logické funkce pomocí MBD}%
V následujícím výčtu je posloupnost úkonů, které vykonává tato implementace při
minima-lizaci logické funkce. Zároveň jde o kroky, které musí vykonat program,
který je výsledkem této práce (více o něm v kapitole \ref{kap_implementace}).
Některé body jsou podrobněji rozebrány v dalších oddílech této kapitoly.\\

\noindent \textbf{Postup při minimalizaci}:
\begin{enumerate}
\item \textbf{Načtení funkce ze souboru}: Funkce je načtena
z PLA souboru do jeho vnitřní reprezentace. Vnitřní reprezentace PLA je popsána
v kapitole \ref{kap_implementace}.
\item \textbf{Určení pořadí vstupních proměnných}: Pomocí zvolené metody se
určí pořadí vstupních proměnných, které pak bude použito k načtení MBD.
Řazení je prováděno metodami popsanými v kapitole \ref{kap_razeni}
\item \textbf{Načtení funkce do MBD}: Z vnitřní reprezentace PLA souboru
je funkce načtena do MBD a rovnou redukována.
\item \textbf{Dynamické řazení proměnných}: Po načtení je použita metoda
\emph{swap\_down} k přerovnání proměnných.
\item \textbf{Minimalizace funkce}: Je-li požadována minimalizace logické
funkce, pak je provedena v této fázi. Do tohoto bodu spadá i přesměrování
případných hran vedoucích do terminálního uzlu s hodnotou $X$.
\item \textbf{Uložení do souboru}: Funkce je načtena z MBD přes vnitřní
reprezentaci logického výrazu a uložena do PLA souboru.
\end{enumerate}

\bfig
\begin{lstlisting}
Node* APPLY(Node* u1, Node* u2)
{
    Node *low, *high, *n;

    // rekurzivní spuštění APPLY
    low = APPLY(u1->low, u2->low);
    high = APPLY(u1->high, u2->high);

    // redukce: 3. pravidlo
    if (low == high)
        return high;

    // redukce: 2. pravidlo
    if (n = node_hash_tab.find(u1.var_id, low, high))
        return n;

    // uzel je unikátní
    return new Node(u1.var_id, low, high);
}

\end{lstlisting}%
\caption[Implementace operace APPLY]{ \textbf{Implementace operace APPLY.} }%
\label{imp_apply}%
\efig

\section{Načítání a redukce MBD}%
Práce s MBD je poměrně ošemetná věc. Prakticky každý úkon v této oblasti má
exponenciální složitost a výjimkou není načítání MBD. Zásadním a jedním z vůbec
největších problémů, který je nutné při impelementaci MBD vyřešit, je načítání
MBD. V každé literatuře je vznik MBD (BDD) popsán pomocí Shannonovy expanze.
Bohužel, takový přístup je v praxi nepoužitelný. Jednak je jeho časová
složitost velká\footnote{$O(2^n)$}, ale také jeho implementace by byla velmi
složitá.\\
\indent Pro účely této práce byl zvolen přístup založený na operaci APPLY.
Každý term se nejprve samostatně převede do vlastního MBD a ty se pak cyklicky
spojují dohromady pomocí operace APPLY s logickým součtem. Pochopitelně, že
časová složitost je totožná s časovou složitostí Shannonovy expanze, ovšem
implementačně jde o velmi jednoduchý úkol. Operace APPLY pracuje rekurzivně - v
každém uzlu se znovu spouští pro oba syny a pak se výsledek dále zpracovává
(jde o procházení grafu do hloubky).\\
\indent Zásadní předností implementace MBD v této práci je to, že \emph{redukce
MBD se provádí} přímo při jeho načítání \emph{v operaci APPLY}. Všechny tři
kroky redukce popsané v kapitole \ref{kap_bdd} tedy není nutné provádět po
načtení MBD. Výhodou tohoto postupu není jenom zmiňované odpadnutí sekundární
redukce MBD, ale také to, že cyklická spouštěná rekurzivní operace APPLY
v~každém kroku vždy pracuje s redukovaným (tedy pro dané pořadí nejmenším
možným) MBD, díky čemuž skutečná složitost načítání MBD je mnohem menší než
$O(2^n)$. K této hranici se MBD skutečné logické funkce přiblíží jen zřídka.
Zjednodušená verze operace APPLY je na obrázku \ref{imp_apply}.\\
\indent Tato implementace operace APPLY ukazuje pouze dvě redukční pravidla. To
první - odstranění redundatních terminálních uzlů, se zde taky provádí, ale
bylo vynecháno\footnote{Je triviální a čtenář si jej snadno domyslí - pokud ne,
více je možné vyčíst v kapitole \ref{kap_implementace}.}. Uplat-nění třetího
redukčního pravidla je, jak patrno z obrázku, rovněž triviální. Nejzajímavější
částí operace APPLY je implementace druhého redukčního pravidla. Aby bylo možné
v rozumném čase prohledat už vytvořený MBD a najít stejný uzel, byla k tomu
použita hashovací \linebreak tabulka\footnote{Nejhorší časová složitost
prohledání hashovací tabulky je díky kolizím $O(n)$ - tedy jako u prohledávání
vektoru. Díky vhodně navrženému generátoru klíčů (aby generoval co nejméně
kolizí) je reálná složitost $O(n/c)$, kde $c$ je konstantní velikost hashovací
tabulky. V případě MBD je nejhorší možné $n$ známé předem, tudíž lze zvolit
vhodné $c$, aby účinnost hashovací tabulky byla pro danou logickou funkci co
nejvyšší.}. Klíče, s jakými jsou uzly do tabulky ukládány, se generují z
identifikátoru proměnné, které uzel patří, a z ukazatelů na $high$ a $low$
podgrafy. Pokud se při operaci APPLY najde uzel s~těmito stejnými ukazateli,
pak operace APPLY vrací místo nově vytvořeného uzlu uzel nalezený. Výhodou
hashovací tabulky není jen to, že umožňuje provádět velmi efektivní redukci
MBD, ale také že jde o lineární reprezentaci, kde jsou jsou jednotlivé uzly
uloženy v~jednorozměrném vektoru. Hashovací tabulka se dále využívá při
minimalizací DCsetu nebo při prohazování přehazování proměnných.


\section{Dynamické řazení proměnných}
K dynamickému řazení je použita metoda swap\_down, jež je důkladně popsána v
kapitole \ref{kap_razeni}. Základní funkcí, jež je ve swap\_down použita, je
\emph{swap}, jež slouží k prohození uzlů, které patří dvou sousedním proměnným.
Při implementaci této metody se přítomnost hashovací tabulky ukázala
jako velká výhoda.\\
\indent Funkce pracuje tak, že při prohazování $x_a^i$ $x^{i+1}_b$ proměnných
$x_a^i$ $x^{i+1}_b$ (s pořadím $i$ a $i+1$) najde postupně všechny uzly
proměnné $x_a^i$. Potom přesměruje jejich rodiče do uzlů proměnných $x^{i+1}_b$
a jejich syny do synů uzlů $x^{i+1}_b$. Syny uzlů proměnné $x^{i+1}_b$
přesměruje do uzlů $x^{i}_a$. Implementace této operace je ve skutečnosti
poměrně složitá operace, ve které lze snadno udělat chybu. Díky hashovací
tabulce je však vyhledávání uzlů velmi snadné.\\
\indent Jiným vylepšením, které umožňuje snadnější implementaci swap, je to, že
si každý uzel uchovává seznam odkazů na své rodiče - tj. ty uzly, které do něho
směřují svou hranu \emph{high} nebo \emph{low}).\\
\indent Zásadním poznatkem, který spolu se dvěma zmiňovanými vylepšeními
umožňuje implementovat funkci swap se složitostí $O(m)$, kde $m$ je počet uzlů
MBD, je fakt, že změny, které po prohození proměnných v MBD vzniknou, se týkají
pouze uzlů proměnných, které se účastnily prohození \ref{Jac93}. Jinými slovy
lze říci, že po prohození uzlů proměnných $x_a^i$ $x^{i+1}_b$ mohou redundatní
uzly vzniknout pouze mezi uzly proměnných $x_a^{i+1}$ $x^{i}_b$, ale zbytek MBD
zůstane nezměněn. Díky této skutečnosti není nutné po prohození proměnných
provádět redukci celého MBD, ale stačí aplikovat redukční pravidla jen na uzly
proměnných $x_a^{i+1}$ a $x^{i}_b$, která se provádí přímo ve funkci swap.


\section{Přesměrování hran vedoucích do terminálního uzlu s hodnotou $X$}
V tomto úkolu není vůbec žádný zádrhel a jde o implementačně velmi jednoduchou
úlohu. Jednoduše se najdou všechny uzly, jejichž jedna hrana směřuje do uzlu s
hodnotou $X$, a~provede se jedno z přesměrování popsaných v kapitole
\ref{kap_minimalizace}. Problémem zde je, že se musí následně provést redukce
MBD, která odstraní vzniklé redundance.

%\pagebreak
\bfig
\begin{lstlisting}
void get_pla(PLA& pla, Node* n)
{
    PLA low, high;

    pla.get_pla(low, n->low);   // získá PLA pro podgraf low
    pla.get_pla(high, n->high); // získá PLA pro podgraf high

    pla.merge(low, high);       // spojení obou PLA
    pla.minimize();             // boolevská minimalizace
}
\end{lstlisting}%
\caption[Implementace booleovské minimalizace]{ \textbf{Implementace booleovské
minimalizace.} Funkce ukládá logickou funkci do vnitřní reprezentace formátu
PLA, jelikož minimalizátor ESPRESSO pracuje právě s formátem PLA. Minimalizátor
ESPRESSO je spuštěn ve funkci PLA::minimize().
}%
\label{imp_get_pla}%
\efig
\section{Boolevská minimalizace}
Boolevská minimalizace popsaná v kapitole \ref{kap_minimalizace} se provádí
prakticky stejně, jak je zde napsáno. Jediný rozdíl je v tom, že MBD neprochází
od terminálního uzlu s hodnotou $1$, nýbrž rekurzivně od kořene pomocí
algoritmu prohledávání do hloubky. Celý algoritmus je znázorněn na obrázku
\ref{imp_get_pla}. Složitost tohoto procházení je $O(2^n)$, kde $n$ je počet
vstupních proměnných.



%\section{Problémy implementace}


\bfig
    \includegraphics[height=4cm]{img/mbd-prek.png}
    \hskip 1.5cm
    \includegraphics[height=4cm]{img/mbd-prek-reseni.png}
    \caption[Řešení překrývání termů z $f_{on}$ a $f_{dc}$]{ \textbf{Řešení překrývání
    termů z $f_{on}$ a $f_{dc}$}. Obrázek \emph{a)} ukazuje mapu funkce $f(x_0,x_1,x_2)$,
    kde $f_{on}=x_0$ a $f_{dc}=x_1x_2$ (zvýrazněno šedivě). Tímto způsobem \emph{vidí}
    MBD logic-kou funkci. Průnik $f_{on}$ a $f_{dc}$ je v $f_{p}=x_0x_1x_2$.
    Obrázek \emph{b)} zobrazuje vyloučení průniku z $f_{on}$, který se rozpadne na
    $f_{on}=x_0\bar{x_1}+x_0x_1\bar{x_2}$. Termům z $f_{dc}$ byla dána přednost,
    tak se zde nic neměnilo.
    }
    \label{imp_x_prekryv}
\efig

\section{Problém překrývajících se termů}%
Při načítání funkcí s DCsetem do jednoho diagramu, se může objevit problém,
který by se dal nazvat \uv{překrývající se termy}.\\
\indent Máme-li funkci $f(x_0,x_1,x_2)$, která se skládá z $f_{on}=x_0$ a
$f_{dc}=x_1x_2$, pak jeden z těchto termů zastíní při načtení funkce do MBD ten
druhý. Při načítání MBD se totiž obě funkce chovají jako dvě plně určené
logické funkce ($f=f_{on}+f_{dc}$), jediný rozdíl je v tom, že poslední hrana
termu z $f_{dc}$ vede do uzlu s hodnotou $X$ místo $1$. Tento rozdíl však MBD
nebere v úvahu. V současné verzi je možné z překrývajících se termů vybrat
pouze jeden, s tím že druhý úplně zanikne. Bohužel samotná struktura MBD jiné
řešení nenabízí. V této práci byla dána přednost termům z DCsetu, které se v
MBD prosadí na úkor termů z ONsetu.\\
\indent Jedinou možností, jak získat plně korektní řešení, je analyzovat
logickou funkci na vstupu, nalézt průniky mezi termy z $f_{on}$ a $f_{dc}$ a
odstranit je - tj. rozdělit některé termy, aby průniky neobsahovaly. Pokud
chceme upřednostnit termy z $f_{dc}$, pak průniky vyjmeme z $f_{on}$. Celou
operaci demonstruje s využitím map obrázek \ref{imp_x_prekryv}.




%
%\btab
%\begin{tabular}{cc}
%\toprule
%Krok & Akce & Popis\\
%\midrule
%1. krok & Načtení funkce z PLA souboru & fsdfsdfs\\
%2. krok & $0$\\
%$X$ & $X$\\
%\bottomrule
%\end{tabular}
%
%\etab
