 \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{Řazení vstupních proměnných}
\label{kap_razeni}%
\indent Jak už bylo řečeno dříve, velikost výsledného MBD (tj. počet jeho
vnitřních uzlů), je silně závislý na pořadí, v jakém se jednotlivé vstupní
proměnné zpracovávají při načítání MBD.\\
\indent Bez nadsázky lze říci, že nalezení alespoň dobrého, když ne nejlepšího
pořadí, je největší problém, který se v této oblasti vyskytuje. Rozdíl ve
velikosti MBD při různém pořadí vstupních proměnných ilustruje
obrázek~\ref{var_ord}.\\

\noindent Maximální možná velikost MBD je $o(2^n)$, kde $n$ je počet vstupních
proměnných. Taková situace může nastat v případě, že je zvoleno nevhodné pořadí
proměnných. Důsledky objemného MBD jsou zjevné. MBD se díky jeho paměťové
náročnosti nemusí podařit načíst a velký MBD generuje velký počet výstupních
termů, což je v rozporu s úkoly kladenými na minimalizaci logické funkce. V
této souvislosti je vhodné připomenout, že velikost MBD se při použití jakkoliv
nevhodného pořadí vstupních proměnných zvětšuje pouze do šířky a nikoliv do
výšky. Maximální výška MBD s jakkoliv špatným pořadím vstupních proměnných
je právě rovna počtu vstupních proměnných.\\
\indent Problém, který způsobuje vznik velkých MBD, se nazývá
\emph{partitioning} \cite{Alo01} - česky \emph{oddělení, rozdělení}. Velmi
stručně řečeno jde o to, že proměnné, které jsou obsaženy v jednotlivých
termech, jsou při načítání MBD zpracovávány ve velkém vzájemném odstupu, což
dokumentuje obrázek \ref{var_ord}. Úkolem metod na určení pořadí proměnných je
zajistit, aby pořadí proměnných, které se vyskytují v jednom termu, nebylo
příliš odlišné, aby proměnné nebyly příliš vzdálené.\\
\indent Problém \emph{oddělení} se vyskytuje především u funkcí, jejichž
jednotlivé termy nejsou tvořeny literály \emph{všech} proměnných.


\section{Metody používané pro řazení proměnných}
Metody, které se zabývají určováním pořadí vstupních proměnných, se dělí do
dvou základních skupin: na \emph{statické} a \emph{dynamické}.\\
\indent \emph{Statické} metody určují pořadí proměnných přímo ze zadání logické
funkce. Naproti tomu \emph{dynamické} metody pracují s již vytvořeným MBD a
manipulací s ním se ho snaží zmenšit.

\subsection{Statické metody řazení}%
\indent Ačkoliv nejsou statické metody tak účinné jako dynamické, jsou
nezbytnou součástí každého softwarového balíku na práci s MBD. Jejich úkolem je
nalézt nějaké vyhovující pořadí, které by umožnilo MBD alespoň načíst.\\
\indent Složitost nejlepšího známého algoritmu určujícího nejlepší pořadí je
$O(n^23^n)$ \cite{Fri87}, což je podstatné vylepšení oproti hledání pořadí
hrubou silou, jehož časová složitost je $O(n!2^n)$. Bohužel časová složitost
této metody je stále příliš vysoká na to, aby ji bylo možné použít v praxi.\\
\indent Existuje řada heuristik, které tento problém řeší s polynomiální nebo
dokonce lineární složitostí. Často používaná a citovaná je například metoda
MINCE \cite{Alo01}. Její implementace je však velmi složitá. V softwarovém
balíku, jehož se týká tento dokument, jsou implementovány dvě implementačně
snadné heuristiky: FORCE \cite{Alo03} a STAT, která byla objevena při práci na
tomto softwarovém balíku.\\
\emph{\small Pozn.: Autorovi této práce nebylo v době jejího vytváření známo,
že by někdo takovou metodu dříve implementoval či popsal.}

\bfig
    \includegraphics[height=10cm]{img/mbd-ord-good.png}
    \hskip 2cm
    \includegraphics[height=10cm]{img/mbd-ord-bad.png}
    \caption[MBD pro různá pořadí vstupních proměnných]{\label{var_ord} \textbf{MBD pro
    různá pořadí vstupních proměnných.} Logická funkce~$y=x_0x_1+x_2x_3+x_4x_5$
    je načtena nejdříve s pořadím proměnných $P_1=(x_0,x_1,x_2,x_3,x_4,x_5)$ a
    následně s~pořadím proměnných $P_2=(x_1,x_3,x_5,x_0,x_2,x_4)$. }
\efig

\paragraph{Metoda FORCE} Tento přístup vychází z \emph{nějakého} prvotního pořadí
proměnných, které se pomocí iterací pokouší vylepšit. Jako metriku používá tzv.
celkový \emph{span} (česky \emph{rozpětí}). Span je definován jako největší
rozdíl pořadí dvou proměnných v jednom termu. Celkový span je pak součet spanů
všech termů. Například pro funkci $y$ z obrázku \ref{var_ord} je její celkový
span pro pořadí $P_1$ $Span(y,P_1)=1+1+1=3$ a pro $P_2$ je $Span(y,P_2)=3+3+3=9$.\\
\indent Algoritmus funguje tak, že nejdříve pro každý term spočítá tzv.~
\emph{center~of~gravity}~(COG - česky střed gravitační síly) a pak pro každou
proměnnou vypočítá z jednotlivých COG její lepší pořadí. Tento postup se pak
opakuje do té doby, kdy se celkový span přestane zlepšovat. Detailní popis
metody je v \cite{Alo03}.\\

\noindent Časová složitost FORCE je $O((|K|+|V|\log|V|)\log|V|)$, kde $|K|$ je
počet termů a $|V|$ počet vstupních proměnných.

\paragraph{Metoda STAT} Tento přístup se na celý problém dívá statistickým pohledem.
Velmi zjednodu-šeně řečeno, algoritmus STAT pracuje tak, že proměnné, jejichž
literály se nacházejí v největším počtu termů, dává co nejblíže k sobě a co
nejblíže k začátku pořadí. V praxi se postupuje tak, že se pro každou proměnnou
určí počet termů, v nichž se vyskytuje její literál, a proměnné se seřadí
sestupně podle počtu výskytu literálů.\\

\noindent \textbf{Algoritmus STAT}:
\begin{enumerate}%
    \item $C_n = |K_n|;$
    \item $order(n) = sort(C_1,...,C_n)$,
\end{enumerate}%
%\hskip 20pt%
\noindent kde $K_n$ je množina termů obsahujících proměnnou s~indexem $n$,
$C_n$ je počet výskytů proměnné s~indexem $n$, $sort(...)$ provádí sestupné
řazení proměnných podle počtu jejich výskytů a $order(n)$ je výsledné pořadí
proměnných. Tato metoda vychází z předpokladu, že proměnné, které se nejčastěji
vyskytují v termech logické funkce, budou s největší pravděpodobností
i velmi blízcí sousedé.\\
\indent Obrovskou výhodou této metody je, že nevychází z žádného původního
pořadí a tudíž nemůže uvíznout v žádném \emph{mělkém} lokálním minimu. Pro
stejnou reprezentaci logické funkci určí vždy stejné pořadí. Problém takto
definované metody STAT je v tom, že nedokáže určit pořadí proměnných, pokud
mají stejné četnosti výskytu. Například pro funkci z obrázku~\ref{var_ord} by
vhodné pořadí určit nedokázala.\\
\indent Z toho důvodu je STAT vylepšena o jednu nadstavbu, které se říká
\emph{Výběr nejlepšího souseda} (\emph{Best neighbour selection} - BNS). Ta
pracuje tak, že v množině už seřazených proměnných ještě přerovná ty proměnné,
které mají stejný počet výskytů. Algoritmus postupuje od proměnných s nejnižším
pořadím k proměnným s nejvyšším pořadím a za každou proměnnou se snaží vložit
takovou proměnnou, která s nimi byla nejčastěji obsažena ve stejných termech.
Toto vylepšení už získá dobré pořadí proměnných i pro funkci $y$ z
obrázku~\ref{var_ord}.\\

%\begin{center}%
%\begin{tabular}{cl}%
%\toprule
%\multicolumn{2}{c}{\textbf{Algoritmus - BNS}}\\
%\midrule
%    1. & $i=0$ \\
%    2. & $s=BNS(order(i))$\\
%    3. & $if (C_i == C_s)~then~order(i+1)=s$\\
%    4. & $i=i+1$\\
%    5. & $if (i<n)~then~goto~2.$\\
%\bottomrule%
%\end{tabular}%
%\end{center}
%\hskip 15pt%

\noindent \textbf{Algoritmus STAT - BNS}:
\begin{enumerate}%
    \item $i=0$
    \item $s=BNS(order(i))$
    \item $if (C_i == C_s)~then~order(i+1)=s$
    \item $i=i+1$
    \item $if (i<n)~then~goto~2.$,
\end{enumerate}%

\noindent kde funkce $BNS(v)$ určí pro každou proměnnou $v$ jejího nejlepšího
souseda.\\

\noindent Celková složitost upraveného algoritmu STAT je~$O(|K||V| + |V|\log|V|
+ |V|)$, což je, byť zanedbatelně, horší než u FORCE.

\subsection{Dynamické metody řazení}%
Dynamické metody pracují už s hotovým MBD, jehož velikost postupně snižují.
Základní ope-rací, která se v této oblasti používá, je tzv. \emph{swap}
(prohození) proměnných, které jsou v pořadí vedle sebe. Kvalita prohození se
měří počtem vnitřních uzlů v MBD - čím je jich méně, tím je výsledek lepší.\\
\indent Na operaci prohození jsou založeny všechny dynamické metody.
Nejznámější heuristikou je tzv. sifting (prosévání) \cite{Rud93}, který je
implementován v balíku CUDD \cite{Som06}. Vznikla i řada dalších metod
založených na genetických algoritmech, simulovaném ochlazování a dalších
stochastických metodách \cite{Jac93}, které mají za úkol zamezit uvíznutí
algoritmu v lokálním minimu. V této práci byl zvolen tzv. hladový přístup,
který se pádu do lokálního minima nebrání a naopak do něho rychle směřuje.

\paragraph{Hladový přístup} Tento elementární postup byl popsán důkladně v \cite{Jac93}.
Je variantou známého hladového algoritmu \cite{wk_hl}, který v každém svém
kroku vybírá stav s nejlepší ohodnocením.\\
\indent V této práci je implementována metoda prohazování \emph{swap\_down}
\cite{Jac93}, jejíž hlavní část je pomocí pseudo C++ kódu zobrazena na obrázku
\ref{swap_down}. Skládá se ze dvou smyček, z nichž vnitřní (for) provádí
postupné prohazování sousedních proměnných\footnote{Je-li index $i$ i proměnné
$x^i$ její pořadí v seznamu proměnných, pak proměnné $x^{i-1}$ a $x^{i+1}$ jsou
jejími \emph{sousedy} (samozřejmě pokud vůbec existují).} v MBD (\emph{swap})
od první v pořadí do poslední. Pokud takové prohození zmenší velikost MBD, pak
se tento stav ponechá, jinak se vrací do staré \uv{neprohozené} podoby. Vnější
smyčka (\emph{while}) pracuje do té doby, dokud ta vnitřní má nějaký účinek.

\bfig%
\begin{lstlisting}
    while (improved)
    {
        improved = false; old_size = mbd->size();
        for (i=0; i < mbd->get_input_var_num()-1; i++)
        {
            mbd->swap(i, i+1);          // prohození sousedních proměnných

            if (mbd->size() < old_size)
            {
                improved = true;        // nový MBD je menší
                old_size = mbd->size();
            }
            else mbd->swap(i, i+1);     // nový MBD je větší, prohoď nazpět
        }
    }
\end{lstlisting}%
\caption[Hlavní smyčka metody swap\_down]{\textbf{Hlavní smyčka metody
swap\_down.}}%
\label{swap_down}%
\efig

%\newpage
%\section{Experimenty}%
%Dříve než budou předvedeny výsledků testů a měření je nutné vysvětlit, co a za
%jakým se měřilo. Zásadním úkolem testů bylo zjistit, jak se MBD chová při
%načítání logické funkce za různého pořadí vstupních proměnných a tím zároveň
%prozkoumat a ověřit účinnost statických a dynamických metod popsaných v
%předchozím textu.
%
%\subsection{Četnost výskytu počtu uzlů}%
%Pro tři vybrané logické funkce\footnote{funkce byly zadány jako PLA soubory} s
%různým počtem neurčených vstupních proměnných byly opakovaně načítány do MBD s
%náhodně vygenerovaným pořadím. Výsledkem tohoto testu je pro každou funkci
%histogram pro každou udávající četnost výskytu počtu uzlů MBD, který je silně
%závislý na pořadí proměnných. Do těchto grafů byly také vyneseny výsledky
%statických metod FORCE\footnote{průměrná} a STAT.\\
%\indent Byly použity tři pla soubory, které měly všechny shodný počet vstupních
%proměnných - 20 a stejný počet termů - 200. Lišily se počtem neurčených vstupních
%proměnných kdy první soubor neměl žádné neurčené vstupní proměnné, druhý jich měl 20\%
%a třetí 30\%, a všechny tři funkce byly plně určeny.\\
%
%\noindent Testování probíhalo tak, že pro každou funkci bylo vygenerováno
%10.000 náhodných pořadí a ty byly použity k načtení MBD. Pro každou funkci bylo
%rovněž použito statických řadících heuristik FORCE a STAT. STAT dává pro
%stejnou funkci vždy stejný výsledek, tak stačilo načíst funkci pouze jednou.
%FORCE vychází z náhodného pořadí a tak bylo nutné provést rovněž 10.000 načtení
%každé funkce s touto technikou řazení. Do grafů jsou vyneseny pouze průměrn0
%hodnoty získaných řazením FORCE. Získané charakteristiky jsou na obrázcích
%\ref{mbd0dcexp}, \ref{mbd20dcexp} a \ref{mbd30dcexp}. Obrázek \ref{mbdalldcexp}
%nabízí srovnání všech charakteristik
%najednou.\\
%
%\noindent Ze čtyř jmenovaných obrázku vyplývají dvě velmi zajímavé skutečnosti.
%Četnost výskytů počtů uzlů má přibližné průběh gaussovy křivky, přičemž její
%nejvyšší bod (maximum) leží v průměrné hodnotě. Mnohem zajímavější však je, že
%s počtem neurčených vstupních hodnot se tato křivka nejen roztahuje a snižuje,
%ale také rapidně narůstá průměrný počet uzlů v MBD a sním ruku v ruce stoupá i
%čas potřebný na načtení MBD. Důležitým zjištěním je i výkonnost statické řadící
%techniky STAT. U všech tří funkcí se její výsledek zobrazí do \emph{levé paty}
%grafu, což znamená, že jde o velmi dobrý výsledek. Pro zajímavost je dobré
%dodat, že u jedné z funkcí dosáhl algoritmus STAT absolutně nejlepšího výsledku
%z celkových 20.001 vyzkoušených pořadí\footnote{10.000 x Random, 10.000 x
%FORCE, 1 x STAT}.
%
%
%\bfig
%    \includegraphics[width=12.5cm]{img/mbd-0dc.png}
%    \caption[Četnost výskytu počtů uzlů - soubor 20i-1o-200t-0dc.pla]{%\footnotesize
%    \textbf{Četnost výskytu počtů uzlů - soubor 20i-1o-200t-0dc.pla.}
%    Funkce má 0\% neurčených vstupních hodnot. \uv{S} označuje hodnotu dosaženou algoritmem
%    STAT a \uv{F} metodou FORCE.}
%    \label{mbd0dcexp}
%\efig
%
%\bfig
%    \includegraphics[width=12.5cm]{img/mbd-20dc.png}
%    \caption[Četnost výskytu počtů uzlů - soubor 20i-1o-200t-20dc.pla]{%\footnotesize
%    \textbf{Četnost výskytu počtů uzlů - soubor 20i-1o-200t-20dc.pla.}
%    Funkce má 20\% neurčených vstupních hodnot. \uv{S} označuje hodnotu
%    dosaženou algoritmem STAT a \uv{F} metodou FORCE.}
%    \label{mbd20dcexp}
%\efig
%
%\bfig
%    \includegraphics[width=12.5cm]{img/mbd-30dc.png}
%    \caption[Četnost výskytu počtů uzlů - soubor 20i-1o-200t-30dc.pla]{%\footnotesize
%    \textbf{Četnost výskytu počtů uzlů - soubor 20i-1o-200t-30dc.pla.}
%     Funkce má 30\% neurčených vstupních hodnot. \uv{S} označuje hodnotu dosaženou
%     algoritmem STAT a \uv{F} metodou FORCE.}
%    \label{mbd30dcexp}
%\efig
%
%\bfig
%    \includegraphics[width=12.5cm]{img/mbd-alldc.png}
%    \caption[Porovnání četností výskytů počtů uzlů pro všechny funkce]{
%    \textbf{Porovnání četností výskytů počtů uzlů pro všechny funkce.}}
%    \label{mbdalldcexp}
%\efig
%
%\pagebreak
%\subsection{Účinnost řadících technik}%
%V tomto experimentu šlo o to porovnat jednotlivé techniky řazení - statické
%i dynamické. Účinnost je měřena počtem uzlů, které MBD obsahuje.\\
%\indent Experiment byl proveden pro deset různých funkcí, které měly
%různý počet vstupních proměnných, různým počet termů i různý počet
%neurčených vstupních hodnot. Byly testována jak náhodná volba pořadí, tak
%statické metody FORCE a STAT. U náhodných pořadí a FORCE byla funkce načtena
%padesátkrát a výsledkem byla její průměrná hodnota. Na funkci načtenou jednou
%ze statických technik MBD byla ještě použita dynamická prohazovací metoda.
%Výsledek experimentu znázorňuje tabulka \ref{uc_raz_exp}.\\
%
%\noindent Z výsledku je dostatečně patrné, jak velký účinek má dynamické
%prohazování proměnných na snížení počtu uzlu v MBD. Ruku v ruce se statickou
%technikou STAT, bylo dosaženo absolutně nejlepšího celkové výsledku, kdy se
%podařilo snížit velikost MBD téměř o 10\%. Propadákem byla metoda FORCE, jež
%dosáhla dokonce horších výsledků než při generovaném náhodném pořadí.
%
%
%\btab
%\caption[Účinnost řadících technik]{%\footnotesize
%\textbf{Účinnost řadících technik.}
%Sloupec \emph{Random} ukazuje počet uzlů v MBD, jestliže nebyly použity
%žádné řadící techniky (pořadí bylo náhodně vybráno). Sloupec \emph{FORCE} zobrazuje
%počet uzlů dosažených použitím statické heuristiky FORCE. Poslední sloupec \emph{STAT}
%nabízí výsledky dosažené, pokud byl použit algoritmus STAT. Podsloupec \emph{Normal} pro
%každou statickou metodu řazení zobrazuje počet uzlů v MBD, nebylo-li použito následného
%dynamického řazení. Pod sloupec \emph{Swap} naopak ukazuje výsledky dosažené s
%dodatečným přehazování proměnných. Tučně vytištěné hodnoty označují nejlepší dosažené
%výsledky pro jednotlivé funkce.
%}
%\label{uc_raz_exp}
%\vskip 20pt
%\begin{tabular}{crrrrrr}
%\toprule
%\multirow{2}{*}{Soubor} & \multicolumn{2}{c}{Random} & \multicolumn{2}{c}{FORCE} & \multicolumn{2}{c}{STAT}\\
%\cmidrule{2-7}
%    & Normal & Swap & Normal & Swap & Normal & Swap\\
%\midrule
%\ttr{10i-1o-100t-0dc.pla} & 132 & 128 & 132 & \textbf{127} & 136 & 131\\
%\ttr{10i-1o-100t-20dc.pla} & 189 & 183 & 190 & 187 & 186 & \textbf{172}\\
%\ttr{10i-1o-100t-30dc.pla} & 167 & 162 & 166 & \textbf{159} & 166 & 161\\
%\ttr{20i-1o-200t-0dc.pla} & 1220 & 1184 & 1220 & 1182 & 1193 & \textbf{1145}\\
%\ttr{20i-1o-200t-20dc.pla} & 2724 & 2510 & 2723 & 2470 & 2359 & \textbf{2280}\\
%\ttr{20i-1o-200t-30dc.pla} & 4884 & 4401 & 4858 & 4382 & 4269 & \textbf{4159}\\
%\ttr{30i-1o-300t-0dc.pla} & 4420 & 4337 & 4415 & 4329 & 4433 & \textbf{4291}\\
%\ttr{30i-1o-300t-20dc.pla} & 6815 & 6451 & 6784 & 6438 & 6242 & \textbf{6143}\\
%\ttr{30i-1o-300t-30dc.pla} & 11897 & 10665 & 11850 & 10769 & 10550 & \textbf{9969}\\
%\ttr{50i-1o-300t-5dc.pla} & 10451 & 10342 & 10457 & 10348 & 10402 & \textbf{10318}\\
%\midrule
%\ttl{~~~~~~~~~Celkem} & 42899 &  40363 &  42795 &  40391 &  39936 &  \textbf{38769}\\
%\ttl{~~~~~~~~~Celkem (\%)} & \ttc{100} & \ttc{94,1} & \ttc{99,8} & \ttc{94,2} & \ttc{93,1} & \ttc{\textbf{90,4}}\\
%\bottomrule
%\end{tabular}
%\etab
%
%\subsection{Zhodnocení}%
%Výsledky dosažené v této kapitole jsou velmi zajímavé. Už předem bylo víceméně
%jasné, že pořadí vstupních proměnných hodně záleží a zde provedené testy to jen
%dokazují. Jako vhodná volba řadících technik se zdá kombinace snadno
%implementovatelné a časové méně složité statické a vyspělejší metody dynamické
%metody. Ačkoliv zde představená dynamická technika měla své rezervy (uvíznutí v
%lokálním minimu), přesto ukázala svou nespornou sílu a potenciál. Statická
%metoda STAT, která vznikla při práci na tomto projektu je velmi milým
%překvapením a alternativou ke všem ostatním, převážně mnohem složitějším
%metodám. Problémem metody FORCE je, že používá velmi problematickou veličinu -
%\emph{span} - na určení kvality\footnote{ponecháno bez přímého důkazu -
%jednoduše výsledky této metody hovoří za vše.}.\\
%\indent Ze čtyř grafů plyne jeden zásadní a dříve ne tak patrný závěr: Velikost
%MBD je nekompromisně přímo závislá na počtu neurčených vstupních hodnot. Čím je
%neurčených vstupních hodnot více, tím MBD celkově větší a rozpětí jeho možných
%velikostí širší. U řídce definovaných funkcí\footnote{s vyšším počtem
%neurčených vstupních hodnot.} narůstá důležitost statických metod, jelikož
%rychlost dynamických technik je závislá na velikosti MBD - zde se každý předem
%ušetřený uzel velmi hodí.
