% options:
% thesis=B bachelor's thesis
% thesis=M master's thesis
% czech thesis in Czech language
% slovak thesis in Slovak language
% english thesis in English language
% hidelinks remove colour boxes around hyperlinks

\documentclass[thesis=B,czech]{FITthesis}[2012/06/26]

\usepackage[utf8]{inputenc} % LaTeX source encoded as UTF-8

\usepackage{listings}
\usepackage{color}
\usepackage{transparent}

\usepackage{graphicx} %graphics files inclusion
% \usepackage{amsmath} %advanced maths
% \usepackage{amssymb} %additional math symbols

\usepackage{dirtree} %directory tree visualisation

% % list of acronyms
% \usepackage[acronym,nonumberlist,toc,numberedsection=autolabel]{glossaries}
% \iflanguage{czech}{\renewcommand*{\acronymname}{Seznam pou{\v z}it{\' y}ch zkratek}}{}
% \makeglossaries

\newcommand{\tg}{\mathop{\mathrm{tg}}} %cesky tangens
\newcommand{\cotg}{\mathop{\mathrm{cotg}}} %cesky cotangens

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}

\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  breaklines=true,                 % sets automatic line breaking
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{mygreen},    % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
  extendedchars=true,              % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible)
  keywordstyle=\color{blue},       % keyword style
  lineskip={-1.6pt},
  language=C,                 % the language of the code
  otherkeywords={*,...},            % if you want to add more keywords to the set
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showspaces=false,                % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
  showstringspaces=false,          % underline spaces within strings only
  showtabs=false,                  % show tabs within strings adding particular underscores
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
  stringstyle=\color{mymauve},     % string literal style
  tabsize=2,                       % sets default tabsize to 2 spaces
  title=\lstname,                  % show the filename of files included with \lstinputlisting; also try caption instead of title
  literate={ě}{{\v e}}1 {á}{{\'a}}1 {š}{{\v s}}1 {ř}{{\v r}}1 {ž}{{\v ž}}1 {ý}{{\'y}}1 {á}{{\'a}}1 {í}{{\'i}}1 {é}{{\'e}}1 {ú}{{\'u}}1 {ů}{{\r u}}1 {ť}{{\' t}}1  {č}{{\v c}}1 
}

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% ODTUD DAL VSE ZMENTE
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 

\department{Katedra softwarového inženýrství}
\title{Randomizace algoritmů v~systému ABC}
\authorGN{Jakub} %(křestní) jméno (jména) autora
\authorFN{Lerl} %příjmení autora
\authorWithDegrees{Jakub Lerl} %jméno autora včetně současných akademických titulů
\supervisor{doc.Ing. Petr Fišer, Ph.D.}
\acknowledgements{Chtěl bych upřímně poděkovat svému vedoucímu práce za trpělivost, ochotu spolupracovat a hlavně pevné nervy, které jsem často pokoušel. Dále bych chtěl poděkovat svému kamarádovi Tomášovi, kterého považuji za nejlepšího programátora co zná.}
\abstractCS{Logická syntéza je důležitým prvkem v~oboru Číslicových obvodů. Nástroj ABC pro logickou syntézu využívá plně deterministických algoritmů. Během procesu není prováděn žádný náhodný výběr. Algoritmy při stejném vstupu tedy vrátí pokaždé stejný výstup. Algoritmy jsou ovšem velmi citlivé (mimo jiné) na~změnu např. pořadí vstupů. Randomizování ekvivalentních voleb v~těchto algoritmech tak vede k~nalezení různých řešení, která mohou být kvalitnější než u deterministického algoritmu. 

V této práci jsem úspěšně randomizoval algoritmy \textit{balance} a \textit{rewrite}. Testování algoritmu \textit{rewrite} dopadlo podle očekávání a jeho používání v~syntézním procesu může přinést pozitivní výsledky. Randomizovaný \textit{balance} ovšem generoval horší výsledky než deterministický, byl proto několikrát upravován do~formy, která je konkurenceschopná deterministickému. Podařilo se mi dosáhnout průměrného zhoršení pouze 0.09\% oproti referenčnímu \textit{balance}, což už už se dá považovat za statistickou chybu.}
\abstractEN{Logic synthesis is an important topic in circuit domain. The ABC tool uses fully deterministic algorithms for logic synthesis. No random decisions are made in the process and for any input it returns the same output. Nonetheless algorithms are very sensitive to changes of variable ordering. Randomization of equal choices in the process may lead to find better results.

In this thesis I successfully implemented randomization of \textit{balance} and \textit{rewrite}. Testing randomized \textit{rewrite} ended as expected and its use in synthesis process may bring positive results. Nonetheless testing randomized \textit{balance} generated worse results than deterministic one. So I reworked it many times to achieve algorithm which is able to compete that. I implemented semi-randomized \textit{balance}. It generates better results on average than fully-randomized algorithm and it is worse than deterministic \textit{balance} entirely by 0.09\%. This difference can be looked at just as statistical margin for error.}
\placeForDeclarationOfAuthenticity{V~Praze}
\declarationOfAuthenticityOption{4} %volba Prohlášení (číslo 1-6)
\keywordsCS{Obvody, Randomizace algoritmu, Minimalizace, Logická syntéza,  Balance, Rewriting, ABC.}
\keywordsEN{Circuits, Randomized algorithm, Minimalization, Logic synthesis, Balance, Rewriting, ABC.}

\begin{document}

% \newacronym{CVUT}{{\v C}VUT}{{\v C}esk{\' e} vysok{\' e} u{\v c}en{\' i} technick{\' e} v~Praze}
% \newacronym{FIT}{FIT}{Fakulta informa{\v c}n{\' i}ch technologi{\' i}}

\begin{introduction}
Logická syntéza je proces, který požadované chování obvodu v~abstraktní formě převede do~designové implementace v~rámci logických hradel.  Logická optimalizace je pak část logické syntézy, která se snaží, aby výsledný obvod podléhal specifickým omezením. V~praxi se nejčastěji klade důraz na~minimální počet hradel a hloubku obvodu.

Základy logické syntézy se objevují v~roce 1939, kdy Claude Shannon poukázal na~fakt, že lze dvojhodnotovou logikou popsat operace obvodů \cite{ClaudeShannon}. Zprvu se k~minimalizaci přistupovalo například s~pomocí Karnaughových map \cite{KMAP}. Ovšem s~rostoucím počtem vstupů tento způsob přístupu ztrácí na~efektivitě. Později tento způsob vystřídaly sofistikovanější algoritmy (Quine - McCluskey algorithm \cite{McCluskey}), které mohl provádět počítač. 
Nástup nových technologií (PLA, FPGA) \cite{PLA} zvýšil potřebu po efektivnějších algoritmech. Logická optimalizace je NP-těžkým \cite{NPH1} problémem \cite{NPCoptimization}. V~takovém případě je vhodné s~rostoucím počtem vstupů zvolit jinou metodiku k~nalezení řešení.

%\cite{NPH2}
%@ARTICLE{NPH2,
%    author  = "{A. Mishchenko, S. Chatterjee, and R. Brayton}",
%    title   = "{Computers and Intractability, A Guide to the Theory of NP-Completeness}",
%    year    = "1990",
%    journal = "{W. H. Freeman & Co. New York}"
%}

V současných nástrojích \cite{web:ABCOfficial} se v~syntézním procesu používá kombinace více deterministických algoritmů a heuristik \cite{Heuristics}. V~průběhu těchto algoritmů dochází k~výskytu více ekvivalentních voleb, jejichž výběr na~funkcionalitu daného algoritmu nemá vliv. Zato na~výsledné řešení vliv má. To znamená, že se během syntézního procesu neprovádí žádné náhodné volby, a při stejných vstupech budeme dostávat pokaždé stejný výstup. Na~jednu stranu je velmi snadné se k~danému řešení znovu dostat například opakovaným spouštěním. Na~druhou stranu potenciálně lepšího řešení z~důvodu determinizmu nemusí být nikdy dosaženo.

\end{introduction}

\chapter{Cíl Práce}
Cílem práce je do~nástroje ABC (open-source nástroj pro~logickou syntézu) zavést prvky náhodnosti. V~ABC je implementována řada syntézních algoritmů, které jsou plně deterministické, tj. při opakovaném spouštění produkují stejné výsledky. Na~druhou stranu jsou však citlivé např. na~pořadí vstupů syntetizovaného obvodu, což svědčí o~přítomnosti algoritmů, do~kterých by mohlo být možné vložit prvek náhodného výběru, bez narušení funkčnosti. Mým úkolem tedy bude náhodnost do~algoritmu vložit. Dále mám za úkol provést měření a porovnat randomizované řešení s~deterministickým.

\chapter{Seznam pojmů}

\textbf{\textit{Boolovská síť}} (Boolean network) je orientovaný acyklický graf, jehož uzly reprezentují logická hradla a hrany reprezentují propojení mezi nimi. Boolovskou síť můžeme nazývat také třeba síť nebo obvod.

\textbf{\textit{Primární Vstup}} (PO - Primary Input) je uzel, ke~kterému nevede žádná hrana. 

\textbf{\textit{Primární Výstup}} (PO - Primary Output) pak nazýváme uzel, ze~kterého žádná hrana nevede.

\textbf{\textit{And Inverted Graph}} (AIG) je boolovská síť, jež se skládá pouze z~dvou-vstupých AND uzlů, a invertorů. 

\textbf{\textit{Hloubka}} (depth/delay) AIG je pak největší počet uzlů od~PI k~PO. 

\textbf{\textit{Velikost}} (area/size) sítě je pak počet všech uzlů v~síti.

\textbf{\textit{Řez}} (cut) uzlu \textit{n} je množina uzlů sítě, pro kterou platí, že všechny cesty od~primárního vstupu k~\textit{n} prochází uzly z~této množiny. Tento řez je fanout-free pakliže uzly, patřící do~řezu nemají žádné další výstupy mimo daný řez.

\textbf{\textit{Lokální funkce}} (local function) AIG uzlu \textit{n} je boolovská funkce AIG podgrafu s~kořenem v~uzlu \textit{n} vyjádřena listy řezu uzlu \textit{n}.

\textbf{\textit{Strukturní Hashování}} AIG je způsob ukládání uzlů. Strukturní hashování přináší několik výhod jako např. sloučení uzlů se stejnými vstupy. Při vytváření uzlů se jeho vstupy \uv{zahashují} a přidají do~AIG manageru \cite{ABCprogramming} \cite{ABCTutorial} viz. dále.

\textbf{\textit{Hloubka uzlu}} Hloubka uzlu \textit{n} je počet uzlů mezi Primárním vstupem a \textit{n} včetně uzlu samotného. Primární vstup má hloubku 0.

\textbf{\textit{Topologické pořadí}} Topologické uspořádání je taková posloupnost uzlů grafu, že pro každou jeho hranu (\textit{u}, \textit{v}) platí, že uzel \textit{u} má nižší hloubku než uzel \textit{v}. Topologicky lze proto uspořádat pouze acyklické grafy.

\textbf{\textit{Binární rozhodovací diagram}} (BDD - Binary Decision Diagram) je způsob reprezentace logické funkce \cite{BDD}.

\textbf{\textit{SuperAND}} je vektor, který reprezentuje vícevstupý AND v~AIG. Používá se při tree balancing kroku v~algoritmu \textit{balance}. Více \ref{sec:balance}.

\textbf{\textit{Faktorizace}} neboli sestrojení Faktorované formy z~logické funkce ve~formátu SOP. Podrobnosti \ref{sec:refactor}.

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% ANALÝZA ABC
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
\chapter{Úvod do~ABC}
\section{ABC}
ABC je konzolový nástroj pro syntézu a minimalizaci číslicových obvodů \cite{web:ABCOfficial} \cite{ABCTutorial} \cite{ABCprogramming}. Je v~něm implementováno několik algoritmů pro optimalizaci sítě využívajících vlastností AIG. Umí načítat a ukládat soubory ve~formátu PLA, BLIF, SLIF, Verilog a dalších. Dále dokáže ověřovat ekvivalenci dvou obvodů.
ABC je napsaný v~jazyce C. Autor zde používá \uv{Maďarskou notaci} \cite{HunNotation}. ABC je open-source a zdrojový kód je tedy volně přístupný např. na~online repozitáři \cite{web:ABCGit}. V~ABC je připravené inovativní programovatelné prostředí, přizpůsobené pro práci s~obvody \cite{ABCprogramming} \cite{ABCTutorial}. Je zde implementována řada elementárních metod jako například: 

\begin{itemize}
  \item Vytvoření nové sítě (\textit{Abc\_NtkAlloc})
  \item Označení primárních vstupů a výstupů(\textit{Abc\_NtkPi})
  \item Vytvoření uzlu (\textit{Abc\_AigAnd})
  \item Nastavení konstant (\textit{Abc\_AigReplace})
  \item Provádět elementární logické funkce (\textit{Abc\_AigOr, Abc\_AigXor atd...})
\end{itemize}

\section{AIG}
AIG je primární reprezentace sítí v~ABC. Je to orientovaný acyklický graf, jehož uzly reprezentují dvouvstupové AND hradla a hrany propojení. Každá hrana v~AIG může mít doplňkový atribut, který reprezentuje invertor viz. \ref{fig:AIG}. Tento způsob přístupu má mnoho výhod:
\begin{itemize}
  \item Každá síť může být velmi snadno převedena na~AIG
  \item Používá se zde jen jeden typ uzlu
  \item Nedochází k~prudkému vzrůstu velikosti s~velikostí sítě a počtem PI (na rozdíl od~BDD \cite{BDD})
  \item Snadno se mapuje na~technologie
  \item Části AIG se snadno upravují
  \item Snadné operace
\end{itemize}
AIG je vždy ukládán ve~formě strukturního hashe. Většina algoritmů (\textit{balance}, \textit{collapse}, \textit{renode}, \textit{rewrite}, \textit{refactor}, \textit{retime}) v~ABC pracuje s~AIG a využívá výhod strukturního hashování: 
\begin{itemize}
\item Každé 2 ANDy se stejnými vstupy jsou spojeny do~jednoho.
\item Nikde v~grafu se nevyskytuje jednovstupý uzel.
\item Propagování konstant
\end{itemize}

\begin{figure}
  \centering
  \label{fig:AIG}
    \includegraphics[width=0.6\textwidth]{AIG}
  \caption{Ukázka AIG. Uzly jsou ANDy, hrany spojení a černé puntíky na~hranách invertory.}
\end{figure}

Převod obvodu na~AIG se z~konzole provede příkazem \textit{strash}. Vizualizace malého AIG (do~100 uzlů) může být provedena příkazem \textit{show}. Hashování probíhá za běhu při každém volání nějaké elementární AIG operace. Mimo jiné díky strukturnímu hashování je dosaženo následujících vlastností, které urychlují práci s~AIG:
\begin{itemize}
\item Žádné volné uzly (tj. bez výstupního uzlu)
\item AND uzly jsou uloženy v~topologickém pořadí v~poli objektů \textit{pBins} viz. \ref{AigMan}
\item Konstantní uzel má vždy Identifikační číslo 0 v~poli objektů (uzly, vstupy, výstupy, propojení)
\item Hloubka každého uzlu je reflektována hloubkou jeho vstupů
\end{itemize}
Manažer pro strukturní hashování si uchovává informace o dané síti. V~ukázce \ref{AigAndCreate} můžeme vidět jak k~samotnému hashování dochází při vytváření ANDu. Nejprve se otestuje, zda je hashovací tabulka dostatečně velká. Dále uspořádá uzly tak, aby levý předek měl menší Id než pravý předek a přidají se na~vstup novému ANDu. Díky tomu máme zachovanou komutativitu vstupů. Mějme uzel \textit{F} se vstupy \textit{a} a \textit{b}, pak funkce \textit{F = ab} \textit{F = ba} budou mít stejnou pozici v~hashovací tabulce, protože se vždy uspořádají podle Id. Dále nám Hashovací funkce viz. \ref{HashKey} vrátí index, na~který uložíme uzel. V~případě, že již existuje uzel se stejnými vstupy,  se na~daný index nic neuloží, protože daná pozice už je obsazená, tudíž takový uzel už v~grafu je.

\begin{lstlisting}[caption={Definice AIG manageru.},label=AigMan]
struct Abc_Aig_t_
{
    // Aig síť
    Abc_Ntk_t *       pNtkAig;
    // Konstantní uzel
    Abc_Obj_t *       pConst1;
    // pole zahashovaných uzlu
    Abc_Obj_t **      pBins;
    // velikost hashovací tabulky
    int               nBins;
    // počet uzlů
    int               nEntries;
    // pole nezahashovaných uzlů
    Vec_Ptr_t *       vNodes;
    Vec_Ptr_t *       vStackReplaceOld;
    Vec_Ptr_t *       vStackReplaceNew;
    Vec_Vec_t *       vLevels;
    Vec_Vec_t *       vLevelsR;
    Vec_Ptr_t *       vAddedCells;
    Vec_Ptr_t *       vUpdatedNets;
};

\end{lstlisting}
\begin{lstlisting}[caption={Ukázka hashování při vytváření AND uzlu.},label=AigAndCreate]
Abc_Obj_t * Abc_AigAndCreate( Abc_Aig_t * pMan, Abc_Obj_t * p0, Abc_Obj_t * p1 )
{
    Abc_Obj_t * pAnd;
    unsigned Key;
    // check if it is a good time for table resizing
    if ( pMan->nEntries > 2 * pMan->nBins )
        Abc_AigResize( pMan );
    // order the arguments
    if ( Abc_ObjRegular(p0)->Id > Abc_ObjRegular(p1)->Id )
        pAnd = p0, p0 = p1, p1 = pAnd;
    // create the new node
    pAnd = Abc_NtkCreateNode( pMan->pNtkAig );
    Abc_ObjAddFanin( pAnd, p0 );
    Abc_ObjAddFanin( pAnd, p1 );
    // set the level of the new node
    pAnd->Level  = 1 + Abc_MaxInt( Abc_ObjRegular(p0)->Level, Abc_ObjRegular(p1)->Level ); 
    pAnd->fExor  = Abc_NodeIsExorType(pAnd);
    pAnd->fPhase = (Abc_ObjIsComplement(p0) ^ Abc_ObjRegular(p0)->fPhase) & (Abc_ObjIsComplement(p1) ^ Abc_ObjRegular(p1)->fPhase);
    // add the node to the corresponding linked list in the table
    Key = Abc_HashKey2( p0, p1, pMan->nBins );
    pAnd->pNext      = pMan->pBins[Key];
    pMan->pBins[Key] = pAnd;
    pMan->nEntries++;
    pAnd->pCopy = NULL;
    // add the node to the list of updated nodes
    if ( pMan->vAddedCells )
        Vec_PtrPush( pMan->vAddedCells, pAnd );
    return pAnd;
}
\end{lstlisting}
\begin{lstlisting}[caption={Ukázka hashovací funkce.},label=HashKey]
static unsigned Abc_HashKey2( Abc_Obj_t * p0, Abc_Obj_t * p1, int TableSize ) 
{
    unsigned Key = 0;
    Key ^= Abc_ObjRegular(p0)->Id * 7937;
    Key ^= Abc_ObjRegular(p1)->Id * 2971;
    Key ^= Abc_ObjIsComplement(p0) * 911;
    Key ^= Abc_ObjIsComplement(p1) * 353;
    return Key % TableSize;
}
\end{lstlisting}
\section{Uzly}
Všechny komponenty v~ABC jsou mimo jiné typu objekt (definice v~souboru \uv{src/base/abc/abc.h}), který si o sobě uchovává informace například jakého typu je (uzel, hrana, síť), má svoje unikátní ID - \textit{int Id;} 32 bitové číslo, které je přidělování při vytváření obvodu. 

Hodnota ID není v~ABC skoro nikde využívána (kromě elementárních operací). Jediné Id, které nesmí být uzlům přiděleno je 0. Ta je rezervována pro konstantní uzel. 

Objekt má dále mnoho dalších atributů viz. \ref{defAbcObj}. Uzly mohou mít žádný nebo více výstupů, které mohou být dalšími uzly nebo propojení. Konstantní uzly nemají žádný vstupní uzel a Invertor má vždy jeden výstup. Každý uzel má svojí logickou funkci uloženou v~proměnné \textit{pNode->pData}, která je složená z~vstupních uzlů. Funkce může nabývat více různých formátů jako jsou SOP \cite{ABCTutorial} \cite{Balance}, BDD \cite{BDD1} \cite{BDD2} nebo hradla (AND). V~AIG se ovšem logická funkce uchovávat nemusí díky vlastnostem strukturního hashování. Namísto toho je logická funkce uzlu definována oběma jeho syny, kteří jsou také ANDy.
\section{Hrany}
Hrana v~AIG je objekt, který obsahuje nepovinný doplňkový atribut, který reprezentuje invertor. Hrany se vytvářejí za běhu při připojování uzlů funkcí \textit{Abc\_NtkCreateLatch( pAig );}.
\begin{lstlisting}[caption={Definice třídy \textit{Abc\_Obj\_t\_}},label=defAbcObj]
struct Abc_Obj_t_     // 48/72 bytes (32-bits/64-bits)
{
    Abc_Ntk_t *       pNtk;          
    Abc_Obj_t *       pNext;         
    int               Id;            
    unsigned          Type    :  4;  
    unsigned          fMarkA  :  1;  
    unsigned          fMarkB  :  1;  
    unsigned          fMarkC  :  1;  
    unsigned          fPhase  :  1; 
    unsigned          fExor   :  1;  
    unsigned          fPersist:  1; 
    unsigned          fCompl0 :  1
    unsigned          fCompl1 :  1;  
    unsigned          Level   : 20;  
    Vec_Int_t         vFanins;      
    Vec_Int_t         vFanouts;      
    union { void *    pData;     
      int             iData; };    
    union { void *    pTemp;   
      Abc_Obj_t *     pCopy;         
      int             iTemp;
      float           dTemp; };
}; 
\end{lstlisting}

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% ANALÝZA ALGORITMŮ
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
\chapter{Analýza Algoritmů}
Syntézní proces napomáhá převést obvod z~návrhu v~abstraktní formě (např. RTL \cite{RTL}) na~technologický design. Na~výsledný obvod jsou kladena různá specifika, která by měl splňovat. V~současnosti se nejčastěji klade důraz na~minimální počet hradel a minimální hloubku. Tato specifika ovšem z~nalezení takového obvodu činí NP-těžký problém. 

Pro syntézu se tak používají různě algoritmy, které napomáhají těchto specifik dosáhnout různými metodami. Algoritmus \textit{balance} se snaží snížit hloubku obvodu, zatímco \textit{rewriting} nebo \textit{refactor} zase snižují počet AND hradel. Kombinace více algoritmů pak může najít uspokojivé řešení. V~praxi se používají syntézní skripty, které obsahují sekvenci těchto algoritmů. V~souboru \uv{abc.rc} jsou tyto skripty definovány jako sekvence příkazů ve~formě aliasů (\textit{st - strash, b - balance, rw - rwrite, rf - refactor, rs -resub}...).
Jako ukázku zde uvedu několik syntézních skriptů, na~které bude mít moje práce vliv:
\begin{itemize}
  \item \textbf{resyn} - \uv{b; rw; rwz; b; rwz; b}
  \item \textbf{resyn2} - \uv{b; rw; rf; b; rw; rwz; b; rfz; rwz; b}
  \item \textbf{resyn2a} - \uv{b; rw; b; rw; rwz; b; rwz; b}
  \item \textbf{resyn3} - \uv{b; rs; rs -K 6; b; rsz; rsz -K 6; b; rsz -K 5; b}
  \item \textbf{compress} - \uv{b -l; rw -l; rwz -l; b -l; rwz -l; b -l}
  \item \textbf{rwsat} - \uv{st; rw -l; b -l; rw -l; rf -l}
  \item \textbf{choice} - \uv{fraig\_store; resyn; fraig\_store; resyn2; fraig\_store; fraig\_restore}
\end{itemize}
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% ANALÝZA BALANCE
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
\section{Balance}
\label{sec:balance}
Algoritmus \textit{balance} dokáže snížit v~mnoha případech hloubku AIG \cite{Balance}. Vedlejším produktem může být i snížení počtu uzlů. Dosahuje toho pomocí dvou kroků:
\begin{enumerate}
\item \textbf{Covering} - Algoritmus v~prvním kroku nejprve identifikuje množiny sousedících (tj. takových, mezi kterými vede hrana) uzlů, které mezi sebou nemají žádný doplňkový atribut (tj. invertor) a spojí je do~sebe, čímž vytvoří jeden mnohavstupý AND (dále superAND) \ref{fig:Covering}. Vstupy superANDu seřadí podle hloubky sestupně. Pro třídění se v~ABC používá funkce qsort \cite{qsort}.

\item \textbf{Tree Balancing} - V~následujícím kroku, pro~každý takto vytvořený AND odebírá vstupy tak, že odebere dva s~nejnižší hloubkou a spojí je do~nového ANDu, který pak zpět připojí do~mnohavstupého ANDu. Spojování opakujeme dokud v~rebalancovaném mnohavstupého ANDu nezůstanou jen dva vstupy viz. \ref{fig:TreeBalancing}. Při tomto procesu nemůže být navýšen počet hradel, ovšem může dojít k~vytvoření uzlu, který sdílí lokální funkci s~jiným již existujícím uzlem. Díky vlastnostem AIG (konkrétně \uv{logic sharing} \cite{Balance}) můžeme tedy jeden takovýto uzel vynechat, čímž snížíme počet uzlů v~AIG. K~tomuto jevu dochází díky strukturnímu hashování, které zabraňuje jakékoliv duplikaci uzlů se stejnými vstupy. 
\end{enumerate}

Při \uv{Tree balancing} kroku se vybírají dva libovolné uzly s~nejnižší hloubkou, které se připojí na vstup ANDu. Kvůli faktu, že algoritmus je plně deterministický, k~tomuto chování ovšem nedochází. Pokud algoritmus nenajde uzly, které sdílí logickou funkci s~jiným uzlem, vybere dva poslední uzly v~pořadí. Toto chování ignoruje potenciální lepší výsledky při zvolení skutečně dvou náhodných takových uzlů.

\begin{figure}
  \centering
  \label{fig:Covering}
    \includegraphics[width=1\textwidth]{covering}
  \caption{Ilustrace \uv{Covering} kroku. \cite{Balance}}
\end{figure}

\begin{figure}
  \centering
  \label{fig:TreeBalancing}
    \includegraphics[width=0.8\textwidth]{treeBalancing}
  \caption{Ilustrace \uv{Tree-Balancing} kroku. \cite{Balance}}
\end{figure}

\begin{figure}
  \centering
  \label{fig:CoverTreeBalance}
    \includegraphics[width=1\textwidth]{Covering_treeBalancing}
  \caption{Ilustrace kompletního \textit{balance}. \cite{Balance}}
\end{figure}

Funkce \textit{Abc\_NodeBalance\_rec} \ref{NodeBalance}, \textit{Abc\_NodeBalanceCone\_rec} \ref{NodeBalanceCone} a\\ \textit{Abc\_NodeBalancePermute} \ref{NodeBalancePermute} jsou hlavním pilířem implementace algoritmu \textit{balance}. Všechny funkce s~předponou \uv{Abc\_NodeBalance} jsou implementovány v~souboru \uv{src/base/abci/abcBalance.c}. Algoritmus začíná zadáním příkazu do~příkazové řádky, kde se příkaz přeloží a zavolá se funkce\\ \textit{Abc\_NtkBalance()}. Tato funkce pro  každý primární vstup zavolá rekurzivní funkci\\ \textit{Abc\_NodeBalance\_rec} s~následujícími parametry:
\begin{itemize}
  \item \textbf{pNtkNew} - ukazatel na~síť, ve~které se vyskytuje
  \item \textbf{pNodeOld} - ukazatel na~kořenový uzel, který je zrovna balancován.
  \item \textbf{vStorage} - ukazatel na~vektor obsahující množinu superANDů. Přistupuje se k~němu jako k~zásobníku.
  \item \textbf{Level} - úroveň zanoření rekurze. Při prvním volání je nastaveno na~0
\end{itemize}
Zbylé parametry jsou případné parametry zadané z~příkazové řádky. Ihned po zavolání se identifikují uzly, které jsou na~vstupu superANDu. Funkce \textit{Abc\_NodeBalanceCone}() \ref{NodeBalanceCone} prohledává graf do~hloubky a ukládá takové uzly do~vektoru \textit{vSuper}, které nemají invertor nebo nejsou PI. Po prohledání grafu máme ve~vektoru vSuper uložené uzly, které jsou vstupy superANDu s~kořenem \textit{pNodeOld}. Na~všechny uzly z~vektoru vSuper se pak zavolá opětovně \textit{Abc\_NodeBalance\_rec}() s~hloubkou zanoření o jedna větší a daným uzlem jako kořenem. Funkce se přestane rekurzivně volat v~případě že jsme prohledali celý graf. 

Jako první se vyhodnotí ten uzel, který byl v~rekurzi volán jako poslední. Díky tomu se bude AIG \textit{balancovat} odspodu a každý uzel, který je právě \textit{balancován} má všechny listy již \textit{vybalancované}. Uzly v~superANDu \textit{vSuper} se setřídí podle úrovně zanoření. Autor zde používá nestabilní třídící algoritmus qsort \cite{qsort}. 

Uzly superANDu jsou setříděné podle hloubky sestupně. Nyní se zavolá funkce \textit{NodeBalancePermute}, která v~cyklu ověří, zda v~superANDu není uzel, který s~posledním uzlem po přidání do~ANDu nevytvořil nový uzel, který už v~grafu je. Pokud ano, prohodí nalezený uzel s~uzlem na~indexu \textit{PočetuzlůVsuperANDu - 2}. 

Pro lepší pochopení, předpokládejme následující superAND:
\newline
\newline
\begin{tabular}{ | l |c | c | c | c | c | c | c | c | }
  \hline
  Index uzlu & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7  \\ \hline
  Hloubka uzlu & 5 & 4 & 2 & 0 & 0 & 0 & 0 & 0 \\ 
  \hline
\end{tabular}
\newline
\newline
Funkce \textit{NodeBalancePermute} \ref{NodeBalancePermute} pak otestuje zda uzel na~indexu 7 a jiný uzel na~indexu v~rozmezí 3 - 6 po spojení nevytvoří uzel, který už v~grafu je. Pokud takový uzel najde, prohodí ho s~uzlem na~indexu 6. Pokud se žádný takový uzel nenajde, \uv{Popnou}(Pop je obecný termín pro odebrání posledního prvku ze~zásobníku) se dva uzly (tj. 6 a 7) a ty se dají na~vstup nově vytvořenému uzlu a ten je zařazen zpět do~superANDu na~příslušnou pozici, abychom zachovali sestupnou hloubku uzlů. V~případě, že se takový uzel najde, dojde k~prohození. \uv{Popnutím} posledních dvou uzlů vytvoříme nový uzel, který v~grafu už je. Díky strukturnímu hashování ušetříme minimálně jeden AND uzel, protože strukturní hashování zabrání duplikaci uzlů. Tento proces se opakuje tak dlouho odkud v~superANDu nezbude poslední uzel, který se stane novým kořenem. Poté co jsou spojeny všechny uzly v~superANDu se vrátí kořenový uzel a ten je zařazen na~vstup rodičovského superANDu, kde se celý proces opakuje pro rodičovský superAND.

Dá se předpokládat, že náhodnou permutací uzlů stejné úrovně budeme dostávat více různých řešení, z~nichž mohou být některá lepší, než deterministická.
Balance je v~ABC implementován jako příkaz \textit{balance}.


\begin{lstlisting}[caption={Ukázka Balance v~ABC.},label=NodeBalance]
Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, Vec_Vec_t * vStorage, int Level, int fDuplicate, int fSelective, int fUpdateLevel )
{
    Abc_Aig_t * pMan = (Abc_Aig_t *)pNtkNew->pManFunc;
    Abc_Obj_t * pNodeNew, * pNode1, * pNode2;
    Vec_Ptr_t * vSuper;
    int i, LeftBound;
    // return if the result if known
    if ( pNodeOld->pCopy ) return pNodeOld->pCopy;
    // get the implication supergate
    vSuper = Abc_NodeBalanceCone( pNodeOld, vStorage, Level, fDuplicate, fSelective );
    if ( vSuper->nSize == 0 ){ 
    // it means that the supergate contains two nodes in the opposite polarity
        pNodeOld->pCopy = Abc_ObjNot(Abc_AigConst1(pNtkNew));
        return pNodeOld->pCopy;
    }
    // for each old node, derive the new well-balanced node
    for ( i = 0; i < vSuper->nSize; i++ ) {
        pNodeNew = Abc_NodeBalance_rec( pNtkNew, Abc_ObjRegular((Abc_Obj_t *)vSuper->pArray[i]), vStorage, Level + 1, fDuplicate, fSelective, fUpdateLevel );
        vSuper->pArray[i] = Abc_ObjNotCond( pNodeNew, Abc_ObjIsComplement((Abc_Obj_t *)vSuper->pArray[i]) );
    }
    if ( vSuper->nSize < 2 ) printf( "BUG!\n" );
    // sort the new nodes by level in the decreasing order
    Vec_PtrSort( vSuper, (int (*)(void))Abc_NodeCompareLevelsDecrease );
    // balance the nodes
    while ( vSuper->nSize > 1 ) {
        // find the left bound on the node to be paired
        LeftBound = (!fUpdateLevel)? 0 : Abc_NodeBalanceFindLeft( vSuper );
        // find the node that can be shared (if no such node, randomize choice)
        Abc_NodeBalancePermute( pNtkNew, vSuper, LeftBound );
        // pull out the last two nodes
        pNode1 = (Abc_Obj_t *)Vec_PtrPop(vSuper);
        pNode2 = (Abc_Obj_t *)Vec_PtrPop(vSuper);
        Abc_VecObjPushUniqueOrderByLevel( vSuper, Abc_AigAnd(pMan, pNode1, pNode2) );
    }
    // mark the old node with the new node
    pNodeOld->pCopy = (Abc_Obj_t *)vSuper->pArray[0];
    vSuper->nSize = 0;

    return pNodeOld->pCopy;
}
\end{lstlisting}
\begin{lstlisting}[caption={Ukázka funkce \textit{Abc\_NodeBalanceCone\_rec}().},label=NodeBalanceCone]
int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, int fFirst, int fDuplicate, int fSelective )
{
    int RetValue1, RetValue2, i;
    // check if the node is visited
    if ( Abc_ObjRegular(pNode)->fMarkB )
    {
        // check if the node occurs in the same polarity
        for ( i = 0; i < vSuper->nSize; i++ )
            if ( vSuper->pArray[i] == pNode )
                return 1;
        // check if the node is present in the opposite polarity
        for ( i = 0; i < vSuper->nSize; i++ )
            if ( vSuper->pArray[i] == Abc_ObjNot(pNode) )
                return -1;
        assert( 0 );
        return 0;
    }
    // if the new node is complemented or a PI, another gate begins
    if ( !fFirst && (Abc_ObjIsComplement(pNode) || !Abc_ObjIsNode(pNode) || (!fDuplicate && !fSelective && (Abc_ObjFanoutNum(pNode) > 1)) || Vec_PtrSize(vSuper) > 10000) )
    {
        Vec_PtrPush( vSuper, pNode );
        Abc_ObjRegular(pNode)->fMarkB = 1;
        return 0;
    }
    assert( !Abc_ObjIsComplement(pNode) );
    assert( Abc_ObjIsNode(pNode) );
    // go through the branches
    RetValue1 = Abc_NodeBalanceCone_rec( Abc_ObjChild0(pNode), vSuper, 0, fDuplicate, fSelective );
    RetValue2 = Abc_NodeBalanceCone_rec( Abc_ObjChild1(pNode), vSuper, 0, fDuplicate, fSelective );
    if ( RetValue1 == -1 || RetValue2 == -1 )
        return -1;
    // return 1 if at least one branch has a duplicate
    return RetValue1 || RetValue2;
}
\end{lstlisting}
\begin{lstlisting}[caption={Ukázka funkce \textit{Abc\_NodeBalancePermute}().},label=NodeBalancePermute]
void Abc_NodeBalancePermute(Abc_Ntk_t * pNtkNew, Vec_Ptr_t * vSuper, int LeftBound)
{
  Abc_Obj_t * pNode1, *pNode2, *pNode3;
  int RightBound, i;
  // get the right bound
  RightBound = Vec_PtrSize(vSuper) - 2;
  assert(LeftBound <= RightBound);
  if (LeftBound == RightBound)
    return;
  // get the two last nodes
  pNode1 = (Abc_Obj_t *)Vec_PtrEntry(vSuper, RightBound + 1);
  pNode2 = (Abc_Obj_t *)Vec_PtrEntry(vSuper, RightBound);
  // find the first node that can be shared
  for (i = RightBound; i >= LeftBound; i--)
  {
    pNode3 = (Abc_Obj_t *)Vec_PtrEntry(vSuper, i);
    if (Abc_AigAndLookup((Abc_Aig_t *)pNtkNew->pManFunc, pNode1, pNode3))
    {
      if (pNode3 == pNode2)
        return;
      Vec_PtrWriteEntry(vSuper, i, pNode2);
      Vec_PtrWriteEntry(vSuper, RightBound, pNode3);
      return;
    }
  }
}
\end{lstlisting}

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% ANALÝZA REWRITING
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
\section{Rewriting}
Algoritmus \textit{Rewriting} dokáže snížit počet AND uzlů v~AIG \cite{Rewriting}. Dosahuje toho v~následujících krocích:
\begin{enumerate}
  \item Najde 4-vstupý fanout-free řez.
  \item z~něj sestrojí BDD \cite{BDD} (tj. kanonickou reprezentaci) a dále převede na~16-bitový integer, který reprezentuje logickou funkci v~daném bodě.
  \item Vyhledá ekvivalentní podgraf ekvivalentní třídy NPN (1 z~222 ekvivalentních) \cite{Rewriting}  viz. \ref{fig:rwr1}. Tyto podgrafy se předpočítávají při alokaci manažera.
  \item Nahradí starý podgraf novým, pokud bude výsledek lepší. Přepínač -z povolí nahrazování i v~případě, že bude podgraf stejně velký.
\end{enumerate}

Dvě logické funkce jsou NPN ekvivalentní pokud mají permutované vstupy, negované vstupy nebo negovaný výstup. 

\textit{Příklad}: funkce \textit{F = ab + c} a \textit{G = ac + b} jsou NPN ekvivalentní, protože prohozením vstupů \textit{b} a \textit{c} dostáváme identickou funkci. Funkce \textit{F = ab + c} a \textit{G = ab} nejsou NPN ekvivalentní, protože libovolným počtem permutací a negací nedokážeme z~funkce o třech proměnných udělat funkci o dvou proměnných \cite{Rewriting}.

Pro čtyř vstupý graf dostáváme 222 NPN ekvivalentních možností \cite{Rewriting}. Výběr jednoho z~takových podgrafů je ovšem plně deterministický - vybere se první nalezený nejlepší podgraf. 

\begin{figure}
  \centering
  \label{fig:rwr1}
    \includegraphics[width=0.8\textwidth]{rwr1}
  \caption{Různé AIG struktury funkce F=abc. \cite{Rewriting}}
\end{figure}

\begin{figure}
  \centering
  \label{fig:rwr2}
    \includegraphics[width=0.8\textwidth]{rwr2}
  \caption{Dva různé případy jak může dopadnout nahrazení novým podgrafem. \cite{Rewriting}}
\end{figure}

Takové chování algoritmu přehlíží možnost výběru různých (potenciálně lepších) řešení. Je vhodné tedy množinu řešení v~průběhu procesu náhodně permutovat, aby i při výběru prvního nalezeného grafu byl vybrán jeden ze~všech \uv{kvalitních} kandidátů na~řešení.

Algoritmus \textit{rewriting} je v~ABC implementovaný v~souborech \\ \uv{src/base/abci/abcRewrite.c}, \uv{src/opt/rwr/*}, \uv{src/opt/cut/*} (pro práci s~řezem), \uv{src/misc/vec/vecPtr.h} (pro práci s~vektorem). Rewriting můžeme evokovat příkazem \uv{rewrite}.

Po zavolání příkazu \textit{rewrite} nebo jeho aliasu definovaném v~souboru \uv{abc.rc} \textit{rw} se příkaz přeloží, nastaví přepínače (např. \textit{-z} nastaví \textit{fUseZeros} \ref{NodeRwr} na~1) a zavolá funkce \textit{Ntk\_Rewrite}(). Ta sama o sobě není příliš zajímavá. Důležitá je ovšem část, kdy iterátor \textit{Abc\_NtkForEachNode}() začne procházet uzly v~grafu v~topologickém pořadí a na~každý takový uzel zavolá \textit{Rwr\_NodeRewrite}() \ref{NtkRwr}. Ta vrátí nový počet uzlů, které jsme ušetřili při nahrazení. V~tomto bodě už je starý graf nahrazen novým (nebo není, pokud nebyla nalezena menší struktura). Parametry:
\begin{itemize}
  \item \textbf{pManRwr} a \textbf{pManCut} - manažerské funkce pro správu rewritingu a řezu
  \item \textbf{pNode} - kořenový uzel podgrafu, který bude nahrazený menším v~případě že bude nalezen. 
  \item další paramtery představují přepínače
\end{itemize}

\begin{lstlisting}[caption={Tělo funkce \textit{Abc\_NtkRewrite}},label=NtkRwr]
Abc_NtkForEachNode( pNtk, pNode, i )
    {
        if ( i >= nNodes ) break; 
        if ( Abc_NodeIsPersistant(pNode) ) continue;
        if ( Abc_ObjFanoutNum(pNode) > 1000 ) continue;

        // for each cut, try to resynthesize it
        nGain = Rwr_NodeRewrite( pManRwr, pManCut, pNode, fUpdateLevel, fUseZeros, fPlaceEnable );
        if ( !(nGain > 0 || (nGain == 0 && fUseZeros)) )
            continue;
        // if we end up here, a rewriting step is accepted

        pGraph = (Dec_Graph_t *)Rwr_ManReadDecs(pManRwr);
        fCompl = Rwr_ManReadCompl(pManRwr);

        if ( fPlaceEnable ) Abc_AigUpdateReset( (Abc_Aig_t *)pNtk->pManFunc );

        if ( fCompl ) Dec_GraphComplement( pGraph );
        Dec_GraphUpdateNetwork( pNode, pGraph, fUpdateLevel, nGain );
        if ( fCompl ) Dec_GraphComplement( pGraph );
    }
\end{lstlisting}

Funkce \textit{Rwr\_NodeRewrite} \ref{NodeRwr} na~vstup dostane zadaný uzel a začne procházet všechny jeho řezy se čtyřmi listy. Pro každý takovýto řez si spočítá logickou funkci a uloží současný graf, aby se mohl, v~případě že se nenajde žádný lepší podgraf, vrácen do~původního stavu. \textit{Rwr\_CutEvaluate} \ref{CutEval} pak prohledá les podgrafů, které už má připravé v~rewrite manažeru \textit{p} a z~něj vybere jeden z~nejvhodnějších. Výběr probíhá tak, že se porovnává, zda je nový podgraf menší než stávající uložený. V~případě zlepšení ho pak nahradí. Spočítá se počet ušetřených uzlů při nahrazení novým podgrafem a uloží do~\textit{nGain}. \textit{p->vFanins} obsahuje informaci o nejlepším řezu, který bude použit při nahrazení. Funkce vrátí -1 pokud graf nemůže být přepsán.

\begin{lstlisting} [caption={Definice funkce \textit{Rwr\_NodeRewrite}},label=NodeRwr]
int Rwr_NodeRewrite( Rwr_Man_t * p, Cut_Man_t * pManCut, Abc_Obj_t * pNode, int fUpdateLevel, int fUseZeros, int fPlaceEnable )
{
    int fVeryVerbose = 0;
    Dec_Graph_t * pGraph;
    Cut_Cut_t * pCut; //, * pTemp;
    Abc_Obj_t * pFanin;
    unsigned uPhase;
    unsigned uTruthBest = 0; // Suppress "might be used uninitialized"
    unsigned uTruth;
    char * pPerm;
    int Required, nNodesSaved;
    int nNodesSaveCur = -1; // Suppress "might be used uninitialized"
    int i, GainCur = -1, GainBest = -1;

    p->nNodesConsidered++;
    // get the required times
    Required = fUpdateLevel? Abc_ObjRequiredLevel(pNode) : ABC_INFINITY;

    // get the node's cuts
    pCut = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCut, pNode, 0, 0 );
    assert( pCut != NULL );
    // go through the cuts
    for ( pCut = pCut->pNext; pCut; pCut = pCut->pNext )
    {
        // consider only 4-input cuts
        if ( pCut->nLeaves < 4 )
            continue;

        // get the fanin permutation
        uTruth = 0xFFFF & *Cut_CutReadTruth(pCut);
        pPerm = p->pPerms4[ (int)p->pPerms[uTruth] ];
        uPhase = p->pPhases[uTruth];
        // collect fanins with the corresponding permutation/phase
        Vec_PtrClear( p->vFaninsCur );
        Vec_PtrFill( p->vFaninsCur, (int)pCut->nLeaves, 0 );
        for ( i = 0; i < (int)pCut->nLeaves; i++ )
        {
            pFanin = Abc_NtkObj( pNode->pNtk, pCut->pLeaves[(int)pPerm[i]] );
            if ( pFanin == NULL )
                break;
            pFanin = Abc_ObjNotCond(pFanin, ((uPhase & (1<<i)) > 0) );
            Vec_PtrWriteEntry( p->vFaninsCur, i, pFanin );
        }
        if ( i != (int)pCut->nLeaves )
        {
            p->nCutsBad++;
            continue;
        }
        p->nCutsGood++;
        int Counter = 0;
        Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninsCur, pFanin, i )
        if ( Abc_ObjFanoutNum(Abc_ObjRegular(pFanin)) == 1 )
            Counter++;
        if ( Counter > 2 )
             continue;

        // mark the fanin boundary 
        Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninsCur, pFanin, i )
            Abc_ObjRegular(pFanin)->vFanouts.nSize++;

        // label MFFC with current ID
        Abc_NtkIncrementTravId( pNode->pNtk );
        nNodesSaved = Abc_NodeMffcLabelAig( pNode );
        // unmark the fanin boundary
        Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninsCur, pFanin, i )
            Abc_ObjRegular(pFanin)->vFanouts.nSize--;

        // evaluate the cut
        pGraph = Rwr_CutEvaluate( p, pNode, pCut, p->vFaninsCur, nNodesSaved, Required, &GainCur, fPlaceEnable );

        // check if the cut is better than the current best one
        if ( pGraph != NULL && GainBest < GainCur )
        {
            // save this form
            nNodesSaveCur = nNodesSaved;
            GainBest  = GainCur;
            p->pGraph  = pGraph;
            p->fCompl = ((uPhase & (1<<4)) > 0);
            uTruthBest = 0xFFFF & *Cut_CutReadTruth(pCut);
            // collect fanins in the
            Vec_PtrClear( p->vFanins );
            Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninsCur, pFanin, i )
                Vec_PtrPush( p->vFanins, pFanin );
        }
    }

    if ( GainBest == -1 )
        return -1;
    // copy the leaves
    Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanins, pFanin, i )
        Dec_GraphNode((Dec_Graph_t *)p->pGraph, i)->pFunc = pFanin;

    p->nScores[p->pMap[uTruthBest]]++;
    p->nNodesGained += GainBest;
    if ( fUseZeros || GainBest > 0 )
    {
        p->nNodesRewritten++;
    }

    return GainBest;
}
\end{lstlisting}

Poslední a nejdůležitější funkci, kterou zde zmíním je \textit{Rwr\_CutEvaluate} \ref{CutEval}. Funkce se stará o vyhodnocování řezů. Na~vstup dostane:
\begin{itemize} 
  \item \textit{p} - rewrite manažer
  \item \textit{pRoot} - kořenový uzel řezu jeden 
  \item \textit{pCut} - jeden z~jeho řezů
  \item \textit{vFaninsCur} - informace o momentálně nejlepším podgrafu 
  \item \textit{nNodesSaved} - počet uložených uzlů 
\end{itemize}
Funkce jako první získá všechny grafy jejichž kořenový uzel má NPN ekvivalentní logickou funkci jako stávající a uloží je do~\textit{vSubgraphs}. Jedná se o vektor, který obsahuje ukazatele na~kořenové uzly podgrafů. Vektor pak iterátor \textit{Vec\_PtrForEachEntry}() prochází a testuje zda podgraf z~vektoru není lepší, než stávající. Pokud tomu tak je, uloží ho do~manažeru \textit{p} jako nový nejlepší podgraf. 

Vložením randomizace do~výběru z~vektoru \textit{vSubgraphs}, bychom mohli dosáhnout větší diverzity řešení. Nezáleží na~tom, v~jakém pořadí řešení z~třídy NPN ekvivalence vybíráme, vybere se vždy to nejlepší. Pokud je nejlepších řešení více, díky náhodné permutace dosáhneme toho, že všechny budou mít stejnou pravděpodobnost, že budou mít stejnou pravděpodobnost na~nahrazení.

\begin{lstlisting}[caption={Definice funkce \textit{Rwr\_CutEvaluate}},label=CutEval]
Dec_Graph_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int LevelMax, int * pGainBest, int fPlaceEnable ) {
  extern int            Dec_GraphToNetworkCount( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int NodeMax, int LevelMax );
  Vec_Ptr_t * vSubgraphs;
  Dec_Graph_t * pGraphBest = NULL; // Suppress "might be used uninitialized"
  Dec_Graph_t * pGraphCur;
  Rwr_Node_t * pNode, * pFanin;
  int nNodesAdded, GainBest, i, k;
  unsigned uTruth;
  float CostBest;//, CostCur;
  // find the matching class of subgraphs
  uTruth = 0xFFFF & *Cut_CutReadTruth(pCut);
  vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[uTruth] );
  p->nSubgraphs += vSubgraphs->nSize;
  // determine the best subgraph
  GainBest = -1;
  CostBest = ABC_INFINITY;
  Vec_PtrForEachEntry( Rwr_Node_t *, vSubgraphs, pNode, i ){
    // get the current graph
    pGraphCur = (Dec_Graph_t *)pNode->pNext;
    // copy the leaves
    Vec_PtrForEachEntry( Rwr_Node_t *, vFaninsCur, pFanin, k~)
      Dec_GraphNode(pGraphCur, k)->pFunc = pFanin;
    // detect how many unlabeled nodes will be reused
    nNodesAdded = Dec_GraphToNetworkCount( pRoot, pGraphCur, nNodesSaved, LevelMax );
    if ( nNodesAdded == -1 )
      continue;
    assert( nNodesSaved >= nNodesAdded );
    // count the gain at this node
      if ( GainBest < nNodesSaved - nNodesAdded ){
        GainBest   = nNodesSaved - nNodesAdded;
        pGraphBest = pGraphCur;

        // score the graph
        if ( nNodesSaved - nNodesAdded > 0 ){
          pNode->nScore++;
          pNode->nGain += GainBest;
          pNode->nAdded += nNodesAdded;
        }
      }
    }
  }
  if ( GainBest == -1 )
    return NULL;
  *pGainBest = GainBest;
  return pGraphBest;
}
 
\end{lstlisting}
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% ANALÝZA REFACTOR
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
\section{Refactor}
\label{sec:refactor}
Algoritmus \textit{refactoring} \cite{refactor} funguje jistým způsobem podobně jako rewriting. Jeho hlavním úkolem je snížení počtu uzlů v~AIG. Dosahuje toho pomocí dvou kroků.
\begin{enumerate}
\item Pro každý uzel spočítám řez (na rozdíl od~rewritingu, kde se braly v~úvahu jen 4-vstupé fanout-free řezy)
\item Převedu ho na faktorovanou formu. Pokud je faktorovaná forma menší než stávající podgraf, nahradí se jím. Přepínačem \textit{-z} můžeme nastavit že se faktorovaná forma má nahradit i v~případě že je faktorovaná forma stejně velká jako stávající podgraf.
\end{enumerate}
Faktorovaná forma je způsob zápisu logických funkcí v~boolovské algebře, kde se \uv{střídají} operátory AND a OR. Je definovaná rekurentně:
\begin{itemize}
\item písmeno je faktorovaná forma
\item součin faktorovaných forem je faktorovaná forma
\item součet faktorovaných forem je faktorovaná forma
\end{itemize}

Funkce ve~tvaru \textit{(ab + ac)} může být převedena na faktorovanou formu \textit{(a(b + c))}. Naopak \textit{(ad + b'c)'} není ve~faktorové formě, protože ze 4 písmen, které jsou ve~faktorové formě, postupným sčítáním a násobením nemůžeme danou funkci vytvořit. 

Algoritmus implementovaný v~ABC se vyhodnotí spuštěním příkazu \textit{refactor}. Po sytnaktickém rozboru přepínačů se zavolá funkce \textit{Abc\_NtkRefactor}, která samotná není příliš zajímavá. Důležitá je pasáž, kde iterátor začne procházet uzly v~grafu v~topologickém pořadí, pro každý takový najde řez a zavolá funkci \textit{Abc\_NodeRefactor} \ref{ntkrefactor} \ref{noderefactor} s~parametry:
\begin{enumerate}
\item \textit{pManRef} - refactor manažer
\item \textit{pNode} - ukazatel na uzel, který faktorizován
\item \textit{vFanins} - uzly řezu uložené ve~vektoru
\item \textit{fUpdateLevel}, \textit{fUseZeros}, \textit{fUseDcs} a \textit{fVerbose} jsou volitelné přepínače
\end{enumerate} 
Funkce \textit{Abc\_NodeRefactor} nejdříve spočítá logickou funkci daného řezu a uloží si jí ve~formátu BDD \cite{BDD1}, kterou vzápětí převede na SOP \cite{ABCTutorial} a uloží ji do~stringu \textit{pSop} ve~formátu \uv{A B C...  X\textbackslash n}. Každý řádek reprezentuje jeden součin, sloupce \textit{A B C..} mohou nabývat hodnot 1/0/-, podle toho zda jsou negované, nebo se v~součinu vůbec nevyskytují. Hodnota X může nabývat hodnot 0/1 a označuje negaci funkce.
\textbf{Příklad:} Logická funkce \textit{F = abc + cde + a'b'd} by pak v~pSop vypadala takto \uv{1 1 1 - -  1\textbackslash n- - 1 1 1  1\textbackslash n0 0 - 0  1\textbackslash n}. 

Tu pak předá funkci \textit{Dec\_Factor}, která ji faktorizuje a otestuje zda dojde ke~zmenšení celého grafu nebo ne. Jedna logická funkce může být ovšem vyjádřena více faktorovanými formami např.

\textit {ab + ac + bc = a(b+c) + bc}

\textit {ab + ac + bc = c(a+b) + ab}

Protože je Algoritmus plně deterministický, bude ignorováno mnoho  kandidátů na řešení, které by mohly být potenciálně lepší. Při opakovaném spuštění randomizace algoritmu \textit{refactor} by pak měla za důsledek větší pestrost řešení, z nichž některá by mohla být lepší než stávající deterministické.

\begin{lstlisting}[caption={Iterátor v~těle funkce \textit{Abc\_NtkRefactor}},label=ntkrefactor]
Abc_NtkForEachNode( pNtk, pNode, i ){
        // skip persistant nodes
        if ( Abc_NodeIsPersistant(pNode) ) continue;
        // skip the nodes with many fanouts
        if ( Abc_ObjFanoutNum(pNode) > 1000 ) continue;
        // stop if all nodes have been tried once
        if ( i >= nNodes ) break;
        // compute a reconvergence-driven cut
        vFanins = Abc_NodeFindCut( pManCut, pNode, fUseDcs );
        // evaluate this cut
        pFForm = Abc_NodeRefactor( pManRef, pNode, vFanins, fUpdateLevel, fUseZeros, fUseDcs, fVerbose );
        if ( pFForm == NULL ) continue;
        // acceptable replacement found, update the graph
        Dec_GraphUpdateNetwork( pNode, pFForm, fUpdateLevel, pManRef->nLastGain );
        Dec_GraphFree( pFForm );
    }
\end{lstlisting}
\begin{lstlisting}[caption={Ukázka funkce \textit{Abc\_NodeRefactor}},label=noderefactor]
Dec_Graph_t * Abc_NodeRefactor( Abc_ManRef_t * p, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, int fUpdateLevel, int fUseZeros, int fUseDcs, int fVerbose ){

    Required = fUpdateLevel? Abc_ObjRequiredLevel(pNode) : ABC_INFINITY;
    p->nNodesConsidered++;
    // get the function of the cut
    bNodeFunc = Abc_NodeConeBdd( p->dd, p->dd->vars, pNode, vFanins, p->vVisited );  Cudd_Ref( bNodeFunc );
    // get the SOP of the cut
    pSop = Abc_ConvertBddToSop( NULL, p->dd, bNodeFunc, bNodeFunc, vFanins->nSize, 0, p->vCube, -1 );
    // get the factored form
    pFForm = Dec_Factor( pSop );
    ABC_FREE( pSop );
    // mark the fanin boundary 
    Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pFanin, i )
        pFanin->vFanouts.nSize++;
    // label MFFC with current traversal ID
    Abc_NtkIncrementTravId( pNode->pNtk );
    nNodesSaved = Abc_NodeMffcLabelAig( pNode );
    // unmark the fanin boundary and set the fanins as leaves in the form
    Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pFanin, i ){
        pFanin->vFanouts.nSize--;
        Dec_GraphNode(pFForm, i)->pFunc = pFanin;
    }
    // detect how many new nodes will be added (while taking into account reused nodes)
    nNodesAdded = Dec_GraphToNetworkCount( pNode, pFForm, nNodesSaved, Required );
    // quit if there is no improvement
    if ( nNodesAdded == -1 || (nNodesAdded == nNodesSaved && !fUseZeros) )
    {
        Cudd_RecursiveDeref( p->dd, bNodeFunc );
        Dec_GraphFree( pFForm );
        return NULL;
    }
    // compute the total gain in the number of nodes
    p->nLastGain = nNodesSaved - nNodesAdded;
    p->nNodesGained += p->nLastGain;
    p->nNodesRefactored++;

    Cudd_RecursiveDeref( p->dd, bNodeFunc );
    return pFForm;
}

\end{lstlisting}



% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% REALIZACE
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
\chapter{Realizace}
Cílem randomizace je snaha zvětšit prohledávaný prostor řešení. Pokud randomizovaný algoritmus po opakovaném spuštění vygeneruje různé struktury, z~nichž budou některé lepší než referenční, můžeme to považovat za úspěch. V~průměru by ovšem nemělo dojít ke~zlepšení ani ke~zhoršení. Nicméně funkcionalita algoritmu by měla být zachována. Vložení náhodného výběru do~místa, kde má dojít k~výběru jednoho z~ekvivalentních variant, by mohlo odpovídat požadovaným podmínkám. Dalším přínosem randomizace je možnost uniknutí z~lokálního minima při dlouhodobé iteraci.
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% BALANCE
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
\section{Balance}
V~tree-balancing kroku dochází k~odebírání uzlů stejné úrovně ze superANDu. Uzly v~superANDu (\textit{vSuper}) jsou setříděné sestupně podle hloubky uzlů.

První návrh byl \uv{Plná randomizace} tj. permutace vstupů superANDu tak, aby uzly zůstaly setříděné podle úrovně. Bylo by pak náhodné nejen pořadí zpracovávaných vstupů, ale i nacházení vhodných vhodných kandidátů ke~sdílení. Implementoval jsem proto funkci \textit{Abc\_NodeBalanceShuffle} \ref{balShuffle}. Ta na vstup dostane množinu vstupů superANDu a každou množinu uzlů každé úrovně zpermutuje. Při psaní funkce \textit{Vec\_PtrRandomShuffle} \ref{VecRndShuffle} jsem se inspiroval  \cite{rndshuffle}. Ta se bude volat pokaždé před voláním funkce \textit{Abc\_NodeBalancePermute}.

\begin{lstlisting}[caption={Definice funkce \textit{Abc\_NodeBalanceShuffle}},label=balShuffle]
void Abc_NodeBalanceShuffle( Vec_Ptr_t * vSuper ){
    int RightBound, LeftBound;
    RightBound = Vec_PtrSize( vSuper ) - 1;
    LeftBound = Abc_NodeBalanceFindLeftFrom( vSuper, RightBound );
    while ( 1 ){
        LeftBound = Abc_NodeBalanceFindLeftFrom( vSuper, RightBound );
        Vec_PtrRandomShuffle( vSuper, LeftBound, RightBound );    
    return;
}
\end{lstlisting}
\begin{lstlisting}[caption={Definice funkce \textit{Vec\_PtrRandomShuffle}},label=VecRndShuffle]
static inline void Vec_PtrRandomShuffle(Vec_Ptr_t * vSuper, int begin, int end ){
  int i, rnd;
  void * tmp;

  for ( i = end ; i > begin; --i) {
    rnd = rand() % ( i - begin + 1 );
    tmp = Vec_PtrEntry(vSuper, i);
    Vec_PtrWriteEntry(vSuper, i, Vec_PtrEntry(vSuper, begin + rnd));
    Vec_PtrWriteEntry(vSuper, begin + rnd, tmp);
  }
}
\end{lstlisting}

Testoval jsem randomizovaný \textit{balance} 2000 krát pro 222 obvodů různé velikosti a počtu PI/PO. Testy ovšem vykázaly průměrné zhoršení oproti referenčnímu řešení více než 1\% v~počtu AND hradel. Navíc pro některé obvody (xparc.blif, mainpla.blif, spla.blif...viz. \ref{fig:balTesty} - modrá hodnota označuje deterministický běh) ani nejlepší nalezené řešení nebylo lepší než referenční při 50 000 opakování. 

Dále jsem testoval, jak se bude měnit zhoršení v~závislosti na míře randomizace (k náhodné permutaci docházelo jen v~50\%, 20\%, 10\%, 1\% případů). Zhoršení klesalo s~klesající randomizací. Proč se tak děje jsem ovšem neodhalil. Podle mně je tomu tak kvůli tomu, že specifický tvar AIG zvýhodňuje deterministický balance oproti plně randomizovanému. Jde ovšem pouze o mou domněnku, své tvrzení nemám čím podložit. Jedná se totiž o uzly s~mnoha uzly a vstupy, je tedy poměrně obtížné z~grafů získat nějaké informace.

\begin{figure}
  \centering
  \label{fig:balTesty}
    \includegraphics[width=0.49\textwidth]{xparc}
    \includegraphics[width=0.49\textwidth]{mainpla-0001}
  \caption{Histogram xparc.blif a mainpla.blif při úplné randomizaci.}
\end{figure}

%\begin{figure}
%  \centering
%  \label{fig:mainpla}
%  \caption{Histogram mainpla.blif při úplné randomizaci}
%\end{figure}

Po dohodě s~vedoucím práce jsem testoval případ, jak se zlepší průměrné řešení randomizovaného algoritmu v~případě, že se bude hledat vhodný kandidát ke~sdílení v~celém superANDu, nikoli pouze v~rámci stejné úrovně. Tato metoda má průměrné zhoršení o 0.4\% méně než plná randomizace. Tato metoda ovšem testuje více prvků, tudíž se časová složitost algoritmu zvýší o konstantu. I přes to jsem se rozhodl tuto změnu v~algoritmu ponechat.

Další návrh byl \uv{Částečná randomizace}. V~případě, že se nenajde vhodný kandidát ke~sdílení, vybere se jiný uzel s~nejnižší dostupnou úrovní. Pokud je takových uzlů víc, vybere se náhodně \ref{permuteExt}. Na rozdíl od~stávajícího modelu, kde se vybíraly uzly na indexech \textit{početUzlů - 1} a \textit{početUzlů - 2}. 

Tento model byl v~ABC již navržený v~komentáři ve~funkci \\ \textit{Abc\_NodeBalancePermute}. Měření ukázalo viditelné zlepšení oproti plné randomizaci navíc bylo konkurenceschopné deterministické variantě. Nejen, že došlo k~průměrnému zhoršení od~průměru pouze o 0,09\%, ale zároveň nacházel řešení, které nalezl deterministický algoritmus. 
\begin{figure}
  \centering
  \label{fig:balTesty}
    \includegraphics[width=0.49\textwidth]{xparc-hist}
    \includegraphics[width=0.49\textwidth]{mainpla-hist}
    \includegraphics[width=0.49\textwidth]{s38417-hist}
    \includegraphics[width=0.49\textwidth]{apex2-hist}
  \caption{Histogramy při částečné randomizaci.}
\end{figure}
V ABC jsem randomizaci balance nastavil na volitelný přepínač \textit{-r} ve~funkci \textit{Abc\_CommandBalance} v~souboru \uv{abc.c}.

Porovnával jsem chování příkazu \textit{permute} (náhodná permutace vstupů a výstupů) oproti deterministickému řešení. Zhoršení oproti deterministickému řešení činilo 0,05\%. Z~toho by se dalo usuzovat, že permutace vstupů je robustnější než randomizace ekvivalentních voleb. 
\begin{lstlisting}[caption={Rozšíření funkce \textit{Abc\_NodeBalancePermute}},label=permuteExt]
if( fRandomize ){ 
  int Choice = rand() % (RightBound - LeftBound + 1);
  pNode3 = Vec_PtrEntry( vSuper, LeftBound + Choice );
  if ( pNode3 == pNode2 )
    return;
  Vec_PtrWriteEntry( vSuper, LeftBound + Choice, pNode2 );
  Vec_PtrWriteEntry( vSuper, RightBound,         pNode3 );
}
\end{lstlisting} 
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% REWRITING
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
\section{Rewriting}
Při výběru z~množiny NPN ekvivalentních podgrafů se vybírá ten, který je nejvhodnější. Pokud je nejvhodnějších více, zachová se první nalezený. V~případě nastavení přepínače \textit{-z} popř. aliasu \textit{rwz} bude nahrazování probíhat i v~případě, že počet uzlů zůstane stejný. 

Množina podgrafů daného řezu je uložená ve~vektoru \textit{vSubgraphs}. Ten je lineárně procházen a testována každá možnost přepisu. Implementoval jsem tedy vektorovou funkci \textit{Vec\_PtrShuffle}, která náhodně permutuje prvky ve~vektoru \ref{ptrShuffle}. Tuto funkci zavolám před tím než se začne vektor procházet.

\begin{lstlisting}[caption={Rozšíření funkce \textit{Vec\_PtrShuffle}},label=ptrShuffle]
static inline void Vec_PtrShuffle(Vec_Ptr_t * pVec){
  int i, rnd;
  void * tmp;
  for (i = pVec->nSize - 1; i > 0; --i) {
    rnd = rand() % (i + 1);
    tmp = Vec_PtrEntry(pVec, i);
    Vec_PtrWriteEntry(pVec, i, Vec_PtrEntry(pVec, rnd));
    Vec_PtrWriteEntry(pVec, rnd, tmp);
  }
}
\end{lstlisting}

Testoval jsem randomizovaný \textit{rewriting} 5000 krát pro 222 obvodů různé velikosti a počtu PI/PO. Testy ukázaly zlepšení v~počtu uzlů o 0,18\% a zlepšení v~počtu úrovní o 1,09\%. Dá se tedy předpokládat, že se randomizovaný \textit{rewriting} chová podle očekávání.

\begin{figure}
  \centering
  \label{fig:rwrTesty}
    \includegraphics[width=0.49\textwidth]{pdc-0001}
    \includegraphics[width=0.49\textwidth]{prom1-0001}
    \includegraphics[width=0.49\textwidth]{mainpla-0002}
    \includegraphics[width=0.49\textwidth]{ex1010-0001}
  \caption{Histogramy randomizovaného rewritingu.}
\end{figure}

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% SOUBORY
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
\section{Seznam upravených souborů}
\begin{tabular}{ l l }
\textbf{Vector} \\
src/misc/vec/vecPtr.h      & řádek: 1114\\

\textbf{Rewrite} \\
src/base/abc/abc.h         & řádek: 860\\
src/base/abci/abc.c        & řádek: 3801, 3812, 3836, 3869, 388\\
src/base/abci/abcRewrite.c & řádek: 129, 61\\
src/base/abci/abcIvy.c     & řádek: 551, 554 \\
src/base/abci/abcProve.c   & řádek: 146, 335, 337  \\
src/base/abci/abcQuant.c   & řádek: 53, 60\\
src/opt/rwr/rwrEva.c       & řádek: 32, 59, 152, 253, 268\\

\textbf{Balance} \\
src/base/abc/abc.h         & řádek: 586\\
src/base/abci/abc.c        & řádek: 3154, 3165, 3186, 3207, 3220, 3242\\
src/base/abci/abcBalance.c & řádek: 30, 31, 53, 74,107, 131, 139, 201, 230, 322, 345, 366\\
src/base/abci/abcIvy.c     & řádek: 549, 552\\
src/base/abci/abcProve.c   & řádek: 156, 336\\
src/base/abci/abcQuant.c   & řádek: 56, 62\\
\end{tabular}
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% MĚŘENÍ
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
\section{Výsledky měření}
Algoritmy jsem testoval spouštěním sekvence příkazů \uv{\textit{read file.blif; st; command; ps}}, který jsem opakoval minimálně 1000krát pro každý obvod. Z~výpisu jsem pak zachoval vždy nejlepší výsledek (AndMin), nejhorší výsledek (AndMax) a průměrný výsledek (AndAvg) jak pro velikost, tak pro hloubku (Lev). Testoval jsem 222 obvodů, které jsou stejně jako všechna naměřená data na přiloženém CD. Zhoršení/zlepšení (\textit{AndAvg/AndRef * 100 - 100}) se pak odvíjí podle referenčního řešení, které v~tabulkách \ref{tab:randBalance} a \ref{tab:randRewrite} uvádím jako \uv{AndRef}. Záporné hodnoty značí pokles počtu Uzlů, kladné nárůst.
V tabulce \ref{tab:summary} Je viditelné, že Úplná randomizace z~nějakého důvodu stabilně vykazuje hroší výsledky než částečná. Ostatní algoritmy se chovají podle očekávání. Syntézní skript jsem po dohodě s~vedoucím práce zvolil \textit{choice}.

\textbf{Choice} -\textit{ fraig\_store; resyn; fraig\_store; resyn2; fraig\_store; fraig\_restore}

\textbf{alias resyn} - \textit{b; rw; rf; b; rw; rwz; b; rfz; rwz; b}

\textbf{alias resyn2} - \textit{b; rw; rwz; b; rwz; b}

Z důvodu velké zátěže byl na testování využit stroj vedoucího práce. Skript byl iterován 20x a vzorek 1000 spuštění. Hodnoty byly porovnávány nativně jako u \textit{balance} a \textit{rewrite}. Počet AND uzlů se snížil v~průměru o 1,15\% a úroveň o 5,5\%. Z~toho se dá usuzovat, že randomizace má pozitivní vliv na iterativní optimalizaci obvodu.
\begin{table}
\begin{tabular}{ | l | r |  r | r |  }
\hline
Process & AndMax & AndAvg & LevAvg \\ \hline
Částečná randomizace \textit{balance}  & -8,17\% & 0,09\% & 0,00\% \\ \hline
Úplná randomizace \textit{balance}  & -7,40\% & 1,12\% & 0,00\% \\ \hline
\textit{permute; balance}   & -10,52\% & 0,05\% & 0,00\% \\ \hline
\textit{rewrite}  & -5,58\% & -0,18\% & -14,28\% \\ \hline
\textit{permute; rewrite} & -8,33\% & -0,06\% & -12,50\% \\ \hline
\textit{choice} & -40,00\% & -1,15\%  & -5,52\% \\ \hline
\end{tabular}
\caption{shrnutí výsledků}
\label{tab:summary}
\end{table}

\begin{table}
\resizebox{14cm}{!} {
\begin{tabular}{ | l | r | r | r | r | r | r |  r | r | r | }
\hline
 & AndMin & AndMax & AndAvg & AndRef & Odchylka & LevMin & LevMax & LevAvg & LevRef \\ \hline
alu2 & 370 & 372 & 371 & 372 & -0,26\% & 39 & 39 & 39 & 39 \\ \hline
amd & 496 & 509 & 502 & 506 & -0,79\% & 15 & 16 & 15 & 16 \\ \hline
apex1 & 2156 & 2178 & 2167 & 2159 & 0,37\% & 23 & 25 & 24 & 24 \\ \hline
apex2 & 325 & 347 & 334 & 345 & -3,18\% & 26 & 27 & 26 & 27  \\ \hline
apex3 & 1905 & 1924 & 1916 & 1912 & 0,20\% & 19 & 19 & 19 & 19 \\ \hline
apex4 & 2879 & 2897 & 2887 & 2886 & 0,03\% & 20 & 20 & 20 & 20 \\ \hline
apex5 & 1001 & 999 & 982 & 1010 & -2,77\% & 13 & 14 & 13 & 14  \\ \hline
apex6 & 639 & 640 & 639 & 640 & -0,15\% & 15 & 15 & 15 & 15 \\ \hline
apla & 215 & 225 & 219 & 221 & -0,90\% & 13 & 13 & 13 & 13 \\ \hline
bca & 2656 & 2695 & 2675 & 2672 & 0,11\% & 26 & 26 & 26 & 26 \\ \hline
bcb & 2408 & 2454 & 2431 & 2428 & 0,12\% & 25 & 26 & 25 & 25 \\ \hline
bcc & 2347 & 2386 & 2366 & 2361 & 0,21\% & 23 & 25 & 24 & 25 \\ \hline
bcd & 1706 & 1738 & 1722 & 1721 & 0,05\% & 25 & 25 & 25 & 25 \\ \hline
bc0 & 1210 & 1240 & 1227 & 1211 & 1,32\% & 24 & 28 & 25 & 25 \\ \hline
br1 & 172 & 174 & 173 & 174 & -0,57\% & 17 & 17 & 17 & 17 \\ \hline
br2 & 117 & 131 & 124 & 125 & -0,80\% & 13 & 14 & 13 & 13 \\ \hline
bw & 154 & 160 & 157 & 160 & -1,87\%5 & 7 & 8 & 7 & 8\\ \hline
jbp & 414 & 433 & 421 & 424 & -0,70\% & 16 & 16 & 16 & 16 \\ \hline
k2 & 1421 & 1478 & 1444 & 1474 & -2,03\% & 22 & 22 & 22 & 22 \\ \hline
lal & 85 & 94 & 90 & 86 & 4,65\% & 7 & 8 & 7 & 8 \\ \hline
lin & 1148 & 1166 & 1156 & 1157 & -0,08\% & 17 & 17 & 17 & 17 \\ \hline
luc & 234 & 237 & 235 & 236 & -0,42\% & 10 & 10 & 10 & 10 \\ \hline
mainpla & 4156 & 4198 & 4176 & 4168 & 0,19\% & 31 & 34 & 32 & 31 \\ \hline
mark1 & 279 & 308 & 296 & 301 & -1,66\% & 26 & 27 & 26 & 27 \\ \hline
max1024 & 913 & 927 & 919 & 917 & 0,21\% & 20 & 20 & 20 & 20 \\ \hline
max128 & 430 & 442 & 436 & 433 & 0,69\% & 12 & 12 & 12 & 12 \\ \hline
max46 & 167 & 168 & 167 & 168 & -0,59\% & 17 & 17 & 17 & 17 \\ \hline
max512 & 612 & 625 & 619 & 613 & 0,97\% & 19 & 19 & 19 & 19 \\ \hline
misex3 & 1277 & 1291 & 1284 & 1278 & 0,46\% & 21 & 21 & 21 & 21 \\ \hline
misex3c & 613 & 618 & 615 & 616 & -0,16\% & 20 & 21 & 20 & 21  \\ \hline
pdc & 1269 & 1293 & 1279 & 1278 & 0,07\% & 23 & 23 & 23 & 23 \\ \hline
pm1 & 35 & 44 & 40 & 40 & 0,00\% & 5 & 5 & 5 & 5 \\ \hline
pope & 675 & 675 & 675 & 675 & 0,00\% & 11 & 11 & 11 & 11 \\ \hline
prom1 & 7073 & 7078 & 7075 & 7075 & 0,00\% & 17 & 17 & 17 & 17 \\ \hline
prom2 & 3194 & 3201 & 3197 & 3198 & -0,03\% & 16 & 16 & 16 & 16 \\ \hline
p82 & 114 & 116 & 114 & 114 & 0,00\% & 8 & 8 & 8 & 8 \\ \hline
rd53 & 54 & 54 & 54 & 54 & 0,00\% & 7 & 7 & 7 & 7 \\ \hline
rd73 & 151 & 151 & 151 & 151 & 0,00\% & 12 & 12 & 12 & 12 \\ \hline
rd84 & 218 & 220 & 219 & 217 & 0,92\% & 12 & 12 & 12 & 12 \\ \hline
risc & 100 & 99 & 99 & 99 & 0,00\% & 7 & 7 & 7 & 7 \\ \hline
root & 246 & 252 & 248 & 249 & -0,40\% & 13 & 13 & 13 & 13 \\ \hline
rot & 526 & 535 & 530 & 531 & -0,18\% & 21 & 21 & 21 & 21 \\ \hline
ryy6 & 16 & 16 & 16 & 16 & 0,00\% & 6 & 6 & 6 & 6 \\ \hline
sao2 & 147 & 157 & 151 & 152 & -0,65\% & 10 & 10 & 10 & 10 \\ \hline
sct & 72 & 75 & 73 & 71 & 2,80\% & 6 & 6 & 6 & 6 \\ \hline
seq & 2022 & 2044 & 2032 & 2032 & 0,00\% & 22 & 22 & 22 & 22 \\ \hline
sex & 44 & 46 & 44 & 44 & 0,00\% & 6 & 6 & 6 & 6 \\ \hline
shift & 146 & 146 & 146 & 146 & 0,00\% & 6 & 6 & 6 & 6 \\ \hline
\end{tabular}
}
\label{tab:randBalance}
\caption{Ukázka naměřených dat částečně randomizovaného \textit{balance}.}
\end{table}
\begin{table}
\resizebox{14cm}{!} {
\begin{tabular}{ | l | r | r | r | r | r | r |  r | r | r | }
\hline 
 & AndMin & AndMax & AndAvg & AndRef & Odchylka: & LevMin & LevMax & LevAvg & LevRef \\ \hline
alcom & 78 & 78 & 78 & 78 & 0,00\% & 4 & 5 & 4 & 4 \\ \hline
alu1 & 30 & 30 & 30 & 30 & 0,00\% & 3 & 3 & 3 & 3 \\ \hline
alu2 & 370 & 372 & 371 & 372 & -0,26\% & 39 & 39 & 39 & 39 \\ \hline
alu3 & 71 & 71 & 71 & 71 & 0,00\% & 10 & 10 & 10 & 10 \\ \hline
alu4 & 680 & 681 & 680 & 680 & 0,00\% & 41 & 41 & 41 & 41 \\ \hline
al2 & 106 & 107 & 106 & 106 & 0,00\% & 6 & 6 & 6 & 6 \\ \hline
amd & 496 & 509 & 502 & 506 & -0,79\% & 15 & 16 & 15 & 16 \\ \hline
apex1 & 2156 & 2178 & 2167 & 2159 & 0,37\% & 23 & 25 & 24 & 24 \\ \hline
apex2 & 325 & 347 & 334 & 345 & -3,18\% & 26 & 27 & 26 & 27\\ \hline
apex3 & 1905 & 1924 & 1916 & 1912 & 0,20\% & 19 & 19 & 19 & 19 \\ \hline
apex4 & 2879 & 2897 & 2887 & 2886 & 0,03\% & 20 & 20 & 20 & 20 \\ \hline
apex5 & 1001 & 999 & 982 & 1010 & -2,77\% & 13 & 14 & 13 & 14 \\ \hline
apex6 & 639 & 640 & 639 & 640 & -0,15\% & 15 & 15 & 15 & 15 \\ \hline
apex7 & 201 & 202 & 201 & 201 & 0,00\% & 14 & 14 & 14 & 14 \\ \hline
apla & 215 & 225 & 219 & 221 & -0,90\% & 13 & 13 & 13 & 13 \\ \hline
bca & 2656 & 2695 & 2675 & 2672 & 0,11\% & 26 & 26 & 26 & 26 \\ \hline
bcb & 2408 & 2454 & 2431 & 2428 & 0,12\% & 25 & 26 & 25 & 25 \\ \hline
bcc & 2347 & 2386 & 2366 & 2361 & 0,21\% & 23 & 25 & 24 & 25\\ \hline
bcd & 1706 & 1738 & 1722 & 1721 & 0,05\% & 25 & 25 & 25 & 25 \\ \hline
bc0 & 1210 & 1240 & 1227 & 1211 & 1,32\% & 24 & 28 & 25 & 25 \\ \hline
br1 & 172 & 174 & 173 & 174 & -0,57\% & 17 & 17 & 17 & 17 \\ \hline
br2 & 117 & 131 & 124 & 125 & -0,8 \% & 13 & 14 & 13 & 13 \\ \hline
bw & 154 & 160 & 157 & 160 & -1,87\% & 7 & 8 & 7 & 8 \\ \hline
b1 & 10 & 10 & 10 & 10 & 0,00\% & 4 & 4 & 4 & 4 \\ \hline
b10 & 516 & 523 & 519 & 520 & -0,19\% & 22 & 24 & 23 & 23 \\ \hline
b11 & 82 & 83 & 82 & 82 & 0,00\% & 6 & 6 & 6 & 6 \\ \hline
b12 & 68 & 68 & 68 & 68 & 0,00\% & 7 & 7 & 7 & 7 \\ \hline
b2 & 1449 & 1479 & 1465 & 1466 & -0,06\% & 20 & 20 & 20 & 20 \\ \hline
b3 & 395 & 411 & 404 & 410 & -1,46\% & 25 & 27 & 26 & 27 \\ \hline
b4 & 290 & 298 & 294 & 292 & 0,68\% & 15 & 17 & 16 & 16 \\ \hline
b7 & 82 & 83 & 82 & 82 & 0,00\% & 6 & 6 & 6 & 6 \\ \hline
b9 & 87 & 87 & 87 & 87 & 0,00\% & 9 & 9 & 9 & 9 \\ \hline
cc & 54 & 54 & 54 & 54 & 0,00\% & 4 & 4 & 4 & 4 \\ \hline
clip & 141 & 141 & 141 & 141 & 0,00\% & 10 & 11 & 10 & 10 \\ \hline
clpl & 10 & 10 & 10 & 10 & 0,00\% & 10 & 10 & 10 & 10 \\ \hline
cmb & 43 & 43 & 43 & 43 & 0,00\% & 8 & 8 & 8 & 8 \\ \hline
cm138a & 16 & 16 & 16 & 16 & 0,00\% & 4 & 4 & 4 & 4 \\ \hline
cm150a & 50 & 51 & 50 & 50 & 0,00\% & 10 & 11 & 10 & 10 \\ \hline
cm151a & 24 & 24 & 24 & 24 & 0,00\% & 8 & 8 & 8 & 8 \\ \hline
cm152a & 21 & 21 & 21 & 21 & 0,00\% & 6 & 6 & 6 & 6 \\ \hline
cm162a & 34 & 34 & 34 & 34 & 0,00\% & 9 & 9 & 9 & 9 \\ \hline
cm163a & 32 & 32 & 32 & 32 & 0,00\% & 8 & 8 & 8 & 8 \\ \hline
cm42a & 18 & 18 & 18 & 18 & 0,00\% & 3 & 3 & 3 & 3 \\ \hline
cm82a & 20 & 20 & 20 & 20 & 0,00\% & 5 & 5 & 5 & 5 \\ \hline
cm85a & 36 & 36 & 36 & 36 & 0,00\% & 7 & 7 & 7 & 7 \\ \hline
comp & 98 & 98 & 98 & 98 & 0,00\% & 16 & 18 & 17 & 17 \\ \hline
con1 & 17 & 17 & 17 & 17 & 0,00\% & 5 & 5 & 5 & 5 \\ \hline
\end{tabular}
}
\label{tab:randRewrite}
\caption{Ukázka naměřených dat randomizovaného \textit{rewrite}.}
\end{table}

\begin{table}
\resizebox{14cm}{!} {
\begin{tabular}{ | l | r | r | r | r | r | r |  r | r | r | }

\hline
 & AndMin & AndMax & AndAvg & AndRef & Odchylka & LevMin & LevMax & LevAvg & LevRef \\ \hline
5xp1 & 37 & 69 & 55 & 54 & 1,85\% & 5 & 8 & 6 & 6  \\ \hline
9sym & 136 & 157 & 146 & 138 & 5,79\% & 8 & 9 & 8 & 9  \\ \hline
9symml & 119 & 142 & 130 & 127 & 2,36\% & 7 & 9 & 7 & 8  \\ \hline
C1355 & 167 & 294 & 196 & 189 & 3,70\% & 10 & 9 & 10 & 11  \\ \hline
C17 & 6 & 6 & 6 & 6 & 0,00\% & 3 & 3 & 3 & 3 \\ \hline
C1908 & 220 & 312 & 263 & 284 & -7,39\% & 14 & 19 & 16 & 16 \\ \hline
C2670 & 362 & 469 & 414 & 431 & -3,94\% & 10 & 13 & 11 & 12  \\ \hline
C3540 & 589 & 681 & 629 & 624 & 0,80\% & 20 & 25 & 21 & 21 \\ \hline
C432 & 100 & 99 & 97 & 99 & -2,02\% & 13 & 18 & 15 & 15 \\ \hline
C499 & 170 & 299 & 193 & 202 & -4,45\% & 10 & 9 & 10 & 12  \\ \hline
C5315 & 824 & 946 & 888 & 855 & 3,85\% & 17 & 21 & 18 & 19  \\ \hline
C6288 & 1946 & 2275 & 2093 & 2080 & 0,62\% & 49 & 60 & 53 & 53 \\ \hline
C7552 & 1000 & 999 & 1026 & 1066 & -3,75\% & 14 & 17 & 15 & 14 \\ \hline
C880 & 184 & 216 & 199 & 194 & 2,57\% & 11 & 17 & 13 & 13 \\ \hline
Z5xp1 & 57 & 89 & 71 & 76 & -6,57\% & 4 & 9 & 5 & 5 \\ \hline
Z9sym & 100 & 99 & 92 & 103 & -10,67\% & 7 & 9 & 7 & 8  \\ \hline
al2 & 71 & 88 & 78 & 80 & -2,50\% & 3 & 5 & 3 & 3 \\ \hline
alcom & 54 & 64 & 57 & 57 & 0,00\% & 3 & 3 & 3 & 3 \\ \hline
alu1 & 22 & 22 & 22 & 22 & 0,00\% & 2 & 2 & 2 & 2 \\ \hline
alu2 & 191 & 236 & 212 & 208 & 1,92\% & 13 & 19 & 15 & 15 \\ \hline
alu3 & 38 & 50 & 42 & 44 & -4,54\% & 6 & 8 & 6 & 6 \\ \hline
alu4 & 400 & 478 & 436 & 436 & 0,00\% & 16 & 21 & 18 & 20  \\ \hline
amd & 162 & 219 & 192 & 165 & 16,36\% & 10 & 9 & 8 & 9  \\ \hline
apex1 & 1149 & 1227 & 1188 & 1176 & 1,02\% & 10 & 13 & 10 & 11  \\ \hline
apex2 & 133 & 174 & 158 & 143 & 10,48\% & 10 & 13 & 11 & 12  \\ \hline
apex3 & 1000 & 999 & 1008 & 998 & 1,00\% & 10 & 12 & 10 & 11  \\ \hline
apex4 & 1590 & 1710 & 1648 & 1687 & -2,31\% & 10 & 12 & 11 & 11 \\ \hline
apex5 & 439 & 525 & 483 & 507 & -4,73\% & 10 & 9 & 8 & 8 \\ \hline
apex6 & 312 & 355 & 330 & 323 & 2,16\% & 10 & 9 & 8 & 9  \\ \hline
apex7 & 101 & 133 & 116 & 119 & -2,52\% & 10 & 9 & 8 & 10  \\ \hline
apla & 100 & 99 & 108 & 97 & 11,34\% & 5 & 9 & 6 & 7  \\ \hline
b1 & 6 & 6 & 6 & 6 & 0,00\% & 2 & 2 & 2 & 2 \\ \hline
b10 & 209 & 248 & 228 & 230 & -0,86\% & 10 & 9 & 9 & 10  \\ \hline
b11 & 52 & 62 & 56 & 59 & -5,08\% & 3 & 4 & 3 & 4  \\ \hline
b12 & 33 & 40 & 35 & 36 & -2,77\% & 4 & 5 & 4 & 4 \\ \hline
b2 & 638 & 730 & 684 & 695 & -1,58\% & 10 & 13 & 11 & 12  \\ \hline
b3 & 171 & 215 & 193 & 192 & 0,52\% & 10 & 9 & 8 & 9  \\ \hline
b4 & 141 & 171 & 154 & 154 & 0,00\% & 6 & 8 & 6 & 8  \\ \hline
b7 & 53 & 63 & 56 & 58 & -3,44\% & 3 & 4 & 3 & 4  \\ \hline
b9 & 54 & 60 & 56 & 57 & -1,75\% & 5 & 6 & 5 & 4  \\ \hline
bc0 & 442 & 531 & 492 & 517 & -4,83\% & 10 & 12 & 11 & 11 \\ \hline
bca & 1292 & 1403 & 1342 & 1369 & -1,97\% & 11 & 14 & 12 & 13  \\ \hline
bcb & 1146 & 1241 & 1198 & 1224 & -2,12\% & 11 & 15 & 12 & 12 \\ \hline
bcc & 1080 & 1191 & 1135 & 1129 & 0,53\% & 10 & 14 & 11 & 13  \\ \hline
bcd & 793 & 881 & 835 & 833 & 0,24\% & 10 & 14 & 12 & 12 \\ \hline
br1 & 62 & 91 & 75 & 65 & 15,38\% & 10 & 9 & 7 & 8  \\ \hline
br2 & 48 & 69 & 56 & 50 & 12,00\% & 6 & 8 & 6 & 6 \\ \hline
bw & 100 & 99 & 95 & 95 & 0,00\% & 4 & 7 & 5 & 6  \\ \hline
c8 & 57 & 72 & 64 & 66 & -3,03\% & 4 & 6 & 5 & 6  \\ \hline
\end{tabular}
}
\caption{Ukázka naměřených dat syntézního skriptu \textit{choice}.}
\end{table}

\begin{conclusion}
  Cílem mé práce byla randomizace algoritmů v~systému ABC, aniž by byla funkcionalita algoritmů narušena. Randomizované algoritmy by měly v~průměru dosahovat stejných, výsledků jako deterministické. Randomizoval jsem příkazy \textit{balance} a \textit{rewrite}. Randomizace rewrite dopadla podle očekávání a její využití může být prospěšné v~syntézním procesu. Testy ukázaly průměrné zlepšení ve~velikosti 0,18\%  a hloubky o 1,09\%. Plně randomizovaný \textit{balance} se nechoval podle očekávání a přinášel stabilně horší výsledky. Velikost obvodu je v~průměru o 1,12\% větší. Byl proto upraven na částečně randomizovanou formu, která přináší stabilně lepší výsledky, než úplná. Zhoršení v~takovém případě činí pouze 0,09\%, což se dá považovat za statistickou chybu.
  
Téma randomizace algoritmů v~ABC je stále otevřené, protože se nejedná pouze o tyto dva, které jsem v~této práci implementoval. V~budoucnu je možná randomizace i dalších algoritmů jako jsou např. \textit{resub}, \textit{refactor} a další.
\end{conclusion}

\bibliographystyle{csn690}
\bibliography{mybibliographyfile}

\appendix

\chapter{Seznam použitých zkratek}
% \printglossaries
\begin{description}
  \item[AIG] And Inverted Graph
  \item[BDD] Binary Decision Diagram
  \item[CI] Primary Input and Latch Output
  \item[CO] Primary Output and Latch Input
  \item[DAG] Directed Acyclic Graph
  \item[FPGA] Field Programmable Gate Array
  \item[GUI] Graphical user interface
  \item[LUT] Look up Table 
  \item[PI] Primary Input
  \item[PO] Primary Output
  \item[PLA] Programmable logic array
  \item[SOP] Sum Of Products
  \item[XML] Extensible markup language
\end{description}


\chapter{Obsah přiloženého CD}

%upravte podle skutecnosti

\begin{figure}
  \dirtree{%
    .1 readme.txt\DTcomment{stručný popis obsahu CD}.
    .1 abc\_Randomized\DTcomment{adresář se spustitelnou formou implementace}.
    .2 readme.md \DTcomment{manuál ke~kompilaci a používání}.
    .2 src\DTcomment{adresář se zdrojovými soubory}.
    .2 lib\DTcomment{adresář externích knihoven}.
    .2 circs \DTcomment{adresář s~testovanými obvody}.
    .1 tests\DTcomment{adresář s~histogramy a naměřenými daty}.
    .1 text \DTcomment{adresář s~potřebnými soubory k~vysázení BP}.
    .2 thesis.pdf\DTcomment{text práce ve~formátu PDF}.
    .2 thesis.tex\DTcomment{text práce ve~formátu \LaTeX{}}.
  }
\end{figure}

\end{document}
