\chapter{Testování}

\section{Vstupní zdroje pro naimplementovaný  program}
\indent \indent Textové popisy signálově přechodového grafu, dle specifikací na text a
na samotný graf, lze nalézt na stránkách \cite{od1}. Konkrétně se jedná o soubory označené 
\hbox{g/název\_souboru.g}. Ne však všechny tyto soubory jsou použitelné, použitelné soubory musí splňovat podmínky viz. Příloha. 
 
\section{Výstup ATACS}
\indent \indent Na výstup přijdou jak informace o čase provádění jednotlivých úloh, tak rovnice
popisující obvod.
Pro příklad jsem nastavil generátor tak, aby zohledňoval C-element.
Výstup pro ATACS může mít následující podobu:
\newline
\newline [+Rx: ($\neg$ Ax \& Ao)]
\newline [-Rx: (Ax \& $\neg$Ao)]
\newline [+Ax: (A1i \& A2i)]
\newline [-Ax: ($\neg$A1i \& $\neg$A2i)]
\newline [+Ao: (Ri \& $\neg$Rx)]
\newline [-Ao: ($\neg$Ri \& Rx)]
\newline [ R1o: (Rx)] Combinational
\newline [ R2o: (Rx)] Combinational
\newline 
\newline Kde  vstupní signály programu jsou \textit { Ri, A1i, A2i } a výstupy nebo interní 
signály jsou \textit { Rx Ax Ao R1o R2o }. Rovnice se generují pro výstupy a interní signály. 
Pokud je na konci řádku napsáno Combinational znamená to, že signál pro vstupy Reset a 
Set \hbox{C-elementu} je stejný, jen pro Reset je tento daný signál invertovaný. Výsledkem je vypuštění \hbox{C-elementu}. Pokud bych \hbox{C-element} nechal, vypadalo by to pro R1o následovně.
\newline 
\newline [ +R1o: (Rx)] 
\newline [ -R1o: ($\neg$Rx)] 
\newline 
\newline 
Znak $\neg$ znamená negaci signálu, amprsand \& představuje logický AND. Textový řetězec, který je na levé straně od dvojtečky představuje jméno výstupu nebo interního signálu. Na pravé straně od dvojtečky jsou rovnice charakterizující výstup nebo interní signál Pokud je před výstupem plus nebo mínus jedná se o vstup pro Set, označeno + resp. pro Reset, označeno -. Pokud se ve výpisu vyskytuje více rovnic pro identický výstup nebo interní signál, pak mezi těmito rovnicemi je logický OR.

\section{Vybrané grafy}
\indent \indent Pro testování jsem zvolil grafy, které odpovídají specifikaci signálově přechodového grafu. Konkrétně se jedná o soubory g/roberto.g a g/vmeP.g. Příklady představují syntézu asynchronních
kontrolérů. Grafy jsou specifikovány tak, že nedojde k redundantnímu zakódování při transformaci nebo k porušení výše zmíněných podmínek pro vstupní soubor.  ATACS redundanci dokáže odstranit, například algoritmem vkládáním signálu a podat odpovídající výsledek. Podobný algoritmus však není součástí mého programu, proto pokud by došlo ke vložení takového  grafu, pak by došlo k hlášení o redundantním zakódování.
\section{Průběh syntézy na ATACS}
\indent \indent Vybral jsem nejprve soubor  g/roberto.g a poté jsme zvolil g/vmeP.g  .
ATACS jsem nastavil tak, aby jeho vstupem byly soubory s příponou .g. Nastavení zahrnuje parametr udávající, že program bude syntetizovat obvod s ohledem na \hbox{C-elementy}.

\section{Výstup z ATACS}
\indent \indent Pro vstupní soubor g/roberto.g jsem dostal následující funkce, které popisují
chování obvodu. 
\newline 
\newline [+done: ($\neg$pc)]
\newline [-done: (ev)]
\newline [ ev: ($\neg$ done\_in\_1 \& $\neg$ done\_in\_2 \& done\_out\_1 \& done\_out\_2 \& done \& pc)] Combinational
\newline [$\neg$ pc: (done\_in\_1 \& done\_in\_2 \& $\neg$ done\_out\_1 \& $\neg$ done\_out\_2 \& $\neg$ done \& $\neg$ ev)] Combinational
\newline 
\newline Výstup pro vstupní soubor g/vmeP.g.
\newline 
\newline [ lds: (csc0)] Combinational
\newline [ d: (ldtack \& csc0)] Combinational
\newline [+csc0: (dsr \& $\neg$ ldtack)]
\newline [-csc0: ($\neg$ dsr)]

\section{Průběh generování VHDL kódu v naimplementovaném programu}
\indent \indent Jako vstup jsem použil stejné soubory jako pro ATACS, tedy  roberto.g a vmeP.g. Po předložení prvního souboru vmeP.g naimplementovanému programu,  jsem získal následující VHDL kód.
\newline 
Hlavička kódu je, vždy stejná.
\textit {
\newline library IEEE;
\newline use IEEE.STD\_LOGIC\_1164.ALL;
\newline use IEEE.STD\_LOGIC\_ARITH.ALL;
\newline use IEEE.STD\_LOGIC\_UNSIGNED.ALL;
}
\newline
\newline  Vstupům  resp. výstupům se přidá před jméno signálu  'in' resp. 'out' .
\textit {
\newline entity vme is
 \newline Port ( indsr: in STD\_LOGIC;
\newline inldtack: in STD\_LOGIC;
\newline outlds: out STD\_LOGIC;
\newline outd: out STD\_LOGIC 
 \newline );
 \newline end vme;
}
\newline 
\newline Začátek popisu chování obvodu ve VHDL se skrývá v architektuře.
\newline \textit {architecture Behavioral of vme is }
Komponenta charakterizující C-element.
\textit {
\newline component cm
\newline Port ( S : in  STD\_LOGIC;
\newline R : in  STD\_LOGIC;
\newline out'\_c : out  STD\_LOGIC);
\newline end component;
\newline }
\newline Interní signály a ostatní pomocné signály jsou nadefinovány níže.
\textit {
\newline signal dsr : STD\_LOGIC;
\newline signal ldtack : STD\_LOGIC;
\newline signal lds : STD\_LOGIC;
\newline signal d : STD\_LOGIC;
\newline signal csc0 : STD\_LOGIC;
\newline signal csc0S : STD\_LOGIC;
\newline signal csc0R : STD\_LOGIC;
\newline }
\newline 
Začátek od něhož dochází k vykonání chování obvodu.
\newline \textit {begin}
\newline Přiřazení vstupních, výstupních signálů a pomocných signálů. Pomocné signály odpovídají jménům 
signálů ve vstupním souboru.
\newline 
\textit {dsr <= indsr;
\newline ldtack <= inldtack;
\newline outlds <= lds;
\newline outd <= d;
\newline }
\newline Samotné funkce vygenerovány naimplementovaným programem. Pokud je použit C-element,
 je k signálu přidáno písmeno S resp. R znázorňující Set a Reset.
\textit {
\newline lds<= csc0 ;
\newline d<= ldtack and csc0 ;
\newline csc0CM : cm
\newline port map ( csc0S , csc0R , csc0 );
\newline csc0S <= dsr and (not ldtack) ;
\newline csc0R <= (not dsr) ;
}
\newline Konec architektury
\newline \textit {end Behavioral;}
Pro mě jsou nejdůležitější výstupní rovnice ty mohu porovnat s ATACS výstupními rovnicemi.
\newline  \newline V našem případě se jedná o tyto řádky:
\textit {
\newline d<= ldtack and csc0 ;
\newline csc0CM : cm
\newline port map ( csc0S , csc0R , csc0 );
\newline csc0S <= dsr and (not ldtack) ;
\newline csc0R <= (not dsr) ;
}
\newline 
\newline Pro předložení druhého vstupního souboru  roberto.g, získávám následující rovnice, přičemž
 vynechávám zbytek VHDL kódu, který není potřeba pro srovnání.
\textit {
\newline doneCM : cm
\newline port map ( doneS , doneR , done );
\newline doneS <= (not pc) ;
\newline doneR <= ev ;
\newline ev<= (not done\_in\_1) and (not done\_in\_2) and done\_out\_1 and done\_out\_2 and done and pc ;
\newline pcCM : cm
\newline port map ( pcS , pcR , pc );
\newline pcS <= done ;
\newline pcR <= done\_in\_1 and done\_in\_2 and (not done\_out\_1) and (not done\_out\_2) and (not done) and (not ev) ;
\newline }

\section{Výsledné srovnání}
\indent \indent Pro soubor vmeP.g mohu přiřadit  funkce  VHDL kódu k jednotlivým rovnicím z ATACS. Vycházím z předpokladu, že na levé straně od  '<='  ve VHDL kódu jsou
 výstupy a na pravé straně jsou odpovídající rovnice. Jména signálů jsou generovány naimplementovaným  programem tak, aby bylo možné porovnat shodu. V hranatých závorkách jsou výsledky z ATACS.
\newline \textit {	lds<= csc0 ; }			
\newline [ lds: (csc0)] Combinational
\newline 	\textit { d<= ldtack and csc0 ; }			
\newline [ d: (ldtack \& csc0)] Combinational		
\newline
\textit {
\newline csc0CM : cm
\newline port map ( csc0S , csc0R , csc0 );
\newline csc0S <= dsr and (not ldtack) ; }	
\newline [+csc0: (dsr \& $\neg$ ldtack)]
\newline \textit { csc0R <= (not dsr) ; }			
\newline [-csc0: ($\neg$ dsr)]
 \newline 
\newline Pro první vstupní soubor mohu konstatovat, že výsledky se shodují.
\newline 
\newline 
Srovnání pro druhý vstupní soubor :
\newline \textit { doneCM : cm
\newline port map ( doneS , doneR , done );
\newline doneS <= (not pc) ; }
\newline [+done: ($\neg$ pc)]
\newline \textit { doneR <= ev ; }
\newline [-done: (ev)]
\newline
\newline \textit { ev<= (not done\_in\_1) and (not done\_in\_2) and done\_out\_1 and done\_out\_2 and done and pc ; }
\newline [ ev: ($\neg$ done\_in\_1 \& $\neg$ done\_in\_2 \& done\_out\_1 \& done\_out\_2 \& done \& pc)]
Combinational
\newline
\newline \textit { pcCM : cm
\newline port map ( pcS , pcR , pc );
\newline pcS <= done ; }
\newline ???
\newline \textit { pcR <= done\_in\_1 and done\_in\_2 and (not done\_out\_1) and (not done\_out\_2) and (not done) and (not ev) ; }
\newline [$\neg$ pc: (done\_in\_1 \& done\_in\_2 \& $\neg$ done\_out\_1 \& $\neg$ done\_out\_2 \& $\neg$ done \& $\neg$ ev)]   Combinational
\newline 

V druhém případě mohu konstatovat, že pro všechny rovnice ve VHDL se našly odpovídající rovnice z ATACS, kromě jedné označené \textit {???}. Ovšem vzápětí podotknu, že se nejedná o chybu v logice. Problém je způsoben tím, že naimplementovaný program nedokáže rozeznat, že pro signál v Setu, existuje invertovaný signál v Resetu a tudíž schopnost vypuštění. Program dokáže odstranit pouze prví výskyt, pokud v Resetu a Setu je jeden stejný signál, přičemž v Resetu je signál invertovaný. Proč to není z pohledu logiky chyba? Protože signálem vždy dojde zároveň k nastavení Setu a Resetu, tudíž \hbox{C-element} ztrácí váhu, jelikož se dá nahradit vodičem na kterém bude jistě menší zpoždění, než na hradlech tvořící \hbox{C-element} a obvod pak může běžet rychleji.
\newline 

\section{Časová složitost }
\indent \indent Pro vytvoření představy o době výpočtů jednotlivých částí programu jsem vytvořil dva grafy s 50 vstupními proměnnými, na kterých by testováni mělo proběhnout. Hodnota 50 je zvolena záměrně, jelikož se jedná o mezní hodnotou počtů vstupních proměnných programu. Mezní hodnota odpovídá více jak dvojnásobku největší hodnoty u příkladů z ATACSu. Vstupní proměnné zahrnují jak vstupní signály, tak i výstupní a interní signály. Počet míst v STG je omezen na 200 a počet stavů grafu SG na 2000. Pro stanovení hodnoty míst pro STG jsem vycházel ze skutečnosti, že grafy uvedené na stránkách ATACS, málokdy překročí počet míst o dva a půl násobek vstupních proměnných. Hodnoty pro vybrané grafy z ATACS jsou v tabulce \ref{tab:tab5}, grafy jsou součástí obsahu CD. Hodnota stanovená pro SG je záměrně naddimenzována, jelikož stanovení hodnoty pro počet stavů je předem velice obtížné.

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\bf{Graf} & \bf{Vstupní signály} & \bf{Výstupní signály} & \bf{Interní signály}  \\
\hline
$G1.g$ & $5$ & $7$ & $0$  \\
\hline
$G2.g$ & $3$ & $3$ & $0$  \\
\hline
$G3.g$ & $2$ & $2$ & $1$  \\
\hline
$G4.g$ & $3$ & $2$ & $0$  \\
\hline
$G5.g$ & $4$ & $3$ & $0$  \\
\hline
\bf{Graf} & \bf{Počet přechodů v STG} & \bf{Počet větveni v STG} & \bf{Počet míst v STG} \\
\hline
$G1.g$ & $24$ & $2$ & $29$  \\
\hline 
$G2.g$ & $12$ & $3$ & $15$  \\
\hline
$G3.g$ & $10$ & $1$ & $11$  \\
\hline
$G4.g$ & $10$ & $2$ & $12$  \\
\hline
$G5.g$ & $14$ & $2$ & $22$  \\
\hline
\bf{Graf} & \bf{Počet stavů v SG}  & \bf{Čas výpočtu} & \bf{} \\
\hline
$G1.g$ & $64$ & $0.563s$ & $$  \\
\hline 
$G2.g$ & $24$ & $0.531s$ & $$  \\
\hline
$G3.g$ & $14$ & $0.453s$ & $$  \\
\hline
$G4.g$ & $17$ & $0.485s$ & $$  \\
\hline
$G5.g$ & $66$ & $0.562s$ & $$   \\
\hline
\end{tabular}
\end{center}
\caption{Vybrané grafy z ATACS}
\label{tab:tab5}
\end{table}

Grafy, které jsem připravil splňují stanovené podmínky pro STG. Správnost a průchodnost grafů byla prověřena na ATACS. Názvy souboru s popisem grafů jsou test1.g a test2.g, parametry grafů jsou uvedeny v tabulce \ref{tab:tab6}. U grafu test2.g  je druhé rozvětvení v STG vnořené v prvním rozvětvení. Soubory popisující grafy jsou součástí obsahu CD.

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\bf{Název} &  $test1.g$ & $test2.g$ \\
\hline
\bf{Vstupní signály} & $17$ & $20$ \\
\hline
\bf{Výstupní signály} & $18$ & $17$ \\
\hline
 \bf{Interní signály}  & $15$ & $13$  \\
\hline
\bf{Počet přechodů v STG} & $100$  & $100$\\
\hline
\bf{Počet větveni v STG} &  $1$  &  $2$ \\
\hline 
\bf{Počet míst v STG} & $101$   & $102$ \\
\hline
\end{tabular}
\end{center}
\caption{Parametry grafů popsané v souborech test1.g a test2.g.}
\label{tab:tab6}
\end{table}

V tabulce \ref{tab:tab7} jsou uvedeny časy výpočtu pro vybrané úseky programu. Úseky se zaměřují na převedení vstupního souboru do struktury reprezentující STG, na transformaci STG na SG a na vytvoření regionů a minimalizaci. Dále je v tabulce parametr udávající počet vygenerovaných stavů v SG. Časy uvedené v tabulce jsou získány za pomocí programu Cygwin a  příkazu \textit{time}. 

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\bf{Název} &  $test1.g$ & $test2.g$ \\
\hline
\bf{Počet stavů v SG}  & $700$ & $1888$ \\
\hline
\bf{Převod vstupního souboru [s]} & $0.453$  & $0.485$\\
\hline
\bf{Transformace [s]}  & $0.234$ & $1.437$ \\
\hline
\bf{Tvorba regionů [s]}  &  $1.568$ & $13.162$\\
\hline 
  \bf{Minimalizace[s]} &  $1.737$ & $35,023$ \\
\hline
\bf{Celkový čas výpočtu[s]} & $4.383$ & $50.530$\\
\hline
 \end{tabular}
\end{center}
\caption{Časové údaje pro úseky výpočtu pro test1.g a test2.g. a počet stavů v signálově přechodovém grafu}
\label{tab:tab7}
\end{table}

Z hodnot, které jsem získal pro grafy popsané v souborech test1.g a test2.g, mohu konstatovat, že použitý algoritmus pro transformaci grafů je poměrně rychlý, ikdyž jeho asymptotická složitost je $O(xn^2)$. Kde $n$ je počet míst obsahující tokeny a $x$ je aktuální počet stavů v SG. 
Největší časové kvantum, pak zabírají úseky pro vytvoření regionů a minimalizaci. Asymptotická složitost pro vytvoření regionů je $\Theta (abc)$, kde $a$ je počet vstupních proměnných, $b$ je počet stavů SG a $c$  počet přechodů mezi stavy SG.  Pro úsek minimalizace je asymptotická složitost $O(defg)$, kde samotný algoritmus minimalizace má $O(fg)$. Proměnná $d$ je počet výstupních a interních signálů, $e$ je počet stavů v ER+ a ER-, $f$  je počet vstupních proměnných a $g$ je počet termů v ER+ $\cup$ QR+ resp. ER- $\cup$ QR-.Urychlit minimalizaci by možná mohl externí minimalizátor za cenu narušení kompaktnosti programu. Pro úplnost asymptotická  složitost úseku pro převod vstupního souboru je $O(h)$, kde $h$ je počet argumentů ve vstupním souboru.

 
\section{Testování vstupu }
\indent \indent Zde musím konstatovat, že nebylo v mých silách otestovat všechny možné varianty 
nesmyslných vstupů. Program samozřejmě funguje pro správně zadané vstupní soubory. Obsah souboru tedy musí dodržovat stanovené podmínky pro textové vyjádření STG.

\section{Závěr testování}
\indent \indent Pro správné vstupní soubory, které dodržují pravidla specifikace signálově přechodového grafu a vymezenou množinu popisného textu, je program schopen vygenerovat správný VHDL kód, který odpovídá skutečnosti.

