\documentclass[a4paper]{article}

%\usepackage{ucs}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[czech]{babel}

%\newif\ifpdf
%\if\pdfoutput\undefined
%  \pdffalse
%\else
%  \pdftrue
%\fi

%\ifpdf
%  \pdfpagewidth=\paperwidth
%  \pdfpageheight=\paperheight
%  \pdfcompresslevel=9
%\fi

\title{Použití genetických algoritmů pro syntézu celulárních automatů
na testování logických obvodů}

\author{Petr Hašlar\\Vedoucí práce: Ing. Petr Fišer}

\begin{document}

\maketitle

\section{Záměr práce}

Cílem této práce je prozkoumat různé implementace genetických algoritmů
z hlediska chování jimi syntetizovaných celulárních automatů na testování
logických obvodů. Chování každého takového automatu je posuzováno podle
jeho vhodnosti pro testování zvoleného logického obvodu. Vhodností se zde
rozumí celkový počet chyb tohoto obvodu, které jsou detekovatelné
testovacími vektory produkovanými uvažovaným automatem.

\section{Úvod do problematiky}

\subsection{Přístupy k návrhu obvodů}

Se stále rostoucí složitostí integrovaných obvodů nabývá na důležitosti
začlenění vlastností umožňujících automatizované testování obvodů
do designu obvodů samotných. Tento způsob designu se nazývá
,,Design for Testing`` (DFT). Použití tohoto přístupu k designu obvodů
v praxi výrazně usnadňuje testování takto navržených obvodů během
výrobního procesu a v některých případech představuje jediný možný
způsob, jak výrobek otestovat v přijatelném čase.

\subsection{Způsoby testování obvodů}

\subsubsection{Základní paradigmata testování}

Co se samotného testování týče, v průběhu druhé poloviny dvacátého
století se paralelně rozvíjela dvě paradigmata: strukturální a
funkcionální.

Strukturální paradigma předpokládá, že pokud je výrobek správně
sestaven z konečného počtu otestovaných součástí podle dobře
navrženého plánu, tzv. netlistu, je finální výrobek bezchybný.

Funkcionální paradigma oproti tomu předpokládá, že finální vyrobek
neobsahuje chyby v tom případě, že jeho chování odpovídá funkční
specifikaci v návrhu výrobku.

Je nasnadě, že strukturální paradigma umožňuje oproti paradigmatu
funkcionálnímu konstruovat podstatně jednodušší testy--stačí pouze
ověřit funkčnost použitých součástek a jejich správné propojení.
Není zde třeba ověřovat odezvy obvodu na exponenciální počet ohodnocení
jeho vstupů. Tento problém ovšem v praxi často naráží na úskalí stále
větší složitosti vyráběných obvodů. Abychom mohli obvody tímto způsobem
testovat, musíme mít možnost sledovat a manipulovat elementární prvky
obvodu často až na té nejnižší úrovni. Pokud máme navíc v signální
cestě od testovacího vstupu k testovanému prvku jakékoliv paměťové
elementy, které mohou nabývat konečného počtu diskrétních stavů,
roste nám složitost testování tohoto prvku exponenciálně. To při
návrhu testů působí značné obtíže a může často vyústit až v neřešitelný
problém. Z tohoto důvodu je velice důležité, aby se na tyto možné
problémy pamatovalo už při návrhu samotného obvodu.

Pokud se rozhodneme testovat z pohledu funkcionálního paradigmatu,
stačí nám předpokládat, že obvod je správně sestavený podle netlistu
a jako takový jej budeme ověřovat podle jeho funkční specifikace.
Nepotřebujeme tedy pro jeho úspěšné otestování blíže znát jeho vnitřní
strukturu.

\subsubsection{Zabudované testy}

Finální výrobky často obsahují zabudované vnitřní auto-testy,
,,Built in Self Test`` (BIST). Tyto testy jsou nezávisle na jakémkoliv
vnějším testovacím zařízení schopny otestovat úplnou nebo alespoň
částečnou funkcionalitu výrobku. To má kromě snížených nároků
na složitost vnějšího testovacího a diagnostického zařízení,
,,Automated Test Equipment`` (ATE), za následek i možnost provádět
testy po skončení výrobního procesu a dokonce i přímo v uživatelském
prostředí.

V průběhu automatizovaného testování logických obvodů jsou zpravidla
na primární a testovací vstupy testovaných obvodů aplikovány testovací
vektory nebo jejich posloupnosti konečné délky. Při návrhu testů je
cílem najít takové vektory nebo jejich posloupnosti, které umožní
odlišit správné chování testovaného obvodu od chování nespravného,
způsobeného konkrétní chybou v obvodu.

Pokud se při našem uvažování omezíme pouze na kombinační obvody, je
zřejmé, že počet možných testovacích vektorů roste exponenciálně
s počtem vstupů uvažovaných obvodů. Z toho můžeme usuzovat na vysokou
časovou náročnost samotného testu, pokud bychom při něm chtěli použít
všechny vektory, nemluvě o všech jejich možných posloupnostech. Pro
sekvenční obvody je velikost prostoru testovacích vektorů ještě výrazně
větší.

V praxi se proto často snažíme omezit se pouze na určitou část prostoru
všech možných posloupností testovacích vektorů. Toho se dá dosáhnout
generováním posloupnosti pseudo-náhodným generátorem. Pokud se nám
podaří najít optimální počáteční konfiguraci generátoru (tzv. seed),
dá se s vysokou pravděpodobností předpokládat, že jím generovaná
posloupnost pokryje většinu lehce detekovatelných poruch, které tvoří
zhruba 90\% všech poruch. Zbývající, těžko detekovatelné poruchy lze
detekovat předem danou sadou testovacích vektorů nebo upravenými vektory
z generátoru.

\subsubsection{Generátory testovacích vektorů}

Nejčastěji se používají dva typy pseudo-náhodných generátorů: lineární
zpětnovazební posuvné registry (LFSR) a celulární automaty (CA).

Lineární zpětnovazební posuvné registry jsou sekvenční logické obvody
sestavené z klopných obvodů typu D a XOR hradel. Vstup každého D obvodu
je napojen na výstup jemu přiřazeného XOR hradla, které zprostředkovává
samotnou zpětnou vazbu. Tvar LFSR, tj. nastavení jeho zpětných vazeb
lze popsat tzv. generujícím polynomem. Na základě znalosti tohoto polynomu
a seedu lze předpovědět, jak bude posloupnost vektorů generovaná takto
definovaným LFSR vypadat.

Celulární automaty jsou sekvenční obvody do značné míry podobné LFSR.
Od nich se liší především lokálností zpětných vazeb a ovlivnitelnou
četností jedniček a nul ve výstupním vektoru. V řadě případů vykazují
při generování pseudo-náhodných vektorů lepší vlastnosti než LFSR.
Díky lokalitě vazeb jsou také méně náročné na místo během návrhu
topologie obvodu.

\section{Nástin řešení}

\subsection{Základní schéma algoritmu}

Všechny implementované genetické algoritmy se drží následujícího
základního schématu:

\begin{itemize}
  \item{Vytvoř počáteční populaci jedinců}
  \item{Proveď selekci jedinců vhodných k páření}
  \item{Vytvoř novou populaci aplikací genetických operátorů
    na skupinu jedinců z předchozího kroku}
  \item{Nahraď původní populaci nově vytvořenou populací}
  \item{Pokud není splněna zadaná podmínka (tj. vyčerpán povolený čas,
    dosažena určitá průměrná kvalita populace atd.), přejdi ke kroku 2,
    jinak ukonči simulaci}
\end{itemize}

\subsection{Vytváření počáteční populace}

Každý jedinec v populaci obsahuje chromosom, ze kterého se odvozují
veškeré jeho vlastnosti a kvality. V našem případě se omezíme na řetězce
pevné délky nad binární abecedou \{0,1\}. V takto definovaném chromosomu
je zakódována informace o tvaru celulárního automatu a jeho počáteční
konfiguraci (tzv. seedu). Tvar automatu je popsán jeho charakteristickou
maticí, která je do chromosomu převedena po řádcích. Zbývající část
chromosomu reprezentuje seed automatu. Délka chromosomu bude tedy stanovena
jako součet počtu členů matice a délky seedu. Z výše uvedené struktury
chromosomu vyplývá, že můžeme v dalších úvahách za platný chromosom
považovat v podstatě jakýkoliv binární řetězec odpovídající délky.

Počáteční populace jedinců je generována náhodně s nastavitelnou četností
jedniček a nul v chromozomu. Volbou této četnosti tak de facto umístíme
počáteční populaci do určité oblasti prostoru všech možných jedinců.
Touto volbou můžeme výrazně ovlivnit výsledky algoritmu zejména v případě,
že je stavový prostor algoritmu výrazně větší, než celkový počet všech
prohledaných stavů v průběhu provádění algoritmu. Přesně tato situace
nastane v případě genetických algoritmů. Stavový prostor algoritmu zde
tvoří přímo množina všech možných jedinců spolu s genetickými operátory,
které vlastně umožňují přechod mezi jedinci.

\subsection{Selekce jedinců}

Pokud už máme vytvořenou populaci, potřebujeme najít způsob, jakým převést
informaci o kvalitě jedince na počet potomků, které může tento jedinec
zplodit. V řadě případů je tento problém řešen vytvořením zvláštní skupiny
jedinců určených k páření. Mohutnost této skupiny zpravidla odpovídá
velikosti populace a při volbě dvojic jedinců určených k páření budeme
uvažovat pouze a jedině jedince z této skupiny. Každý jedinec z populace
může být v této skupině zastoupen několikrát a nebo v ní může zcela chybět.
Četnost výskytu jedinců ve skupině je přímo uměrná jejich kvalitě a
v podstatě odpovídá počtu rozmnožovacích aktů, do kterých může ten který
jedinec vstoupit.

Zbývá už jen rozhodnout, jak tuto skupinu naplnit selekcí jedinců
z uvažované populace. Z mnoha možných přístupů jsem si vybral selekci
jedinců pomocí vícekolového turnaje. V rámci každého kola turnaje
se vždy uskuteční určitý počet klání, do kterých vstupují n-tice
jedinců. Vítězný jedinec má zajištěno místo ve skupině. Každý jedinec
v populaci se může v rámci jednoho kola turnaje účastnit pouze jediného
klání a počet klání je stanoven tak, aby každý jedinec tuto šanci
skutečně dostal. Celkový počet kol turnaje je stanoven podle aktuální
potřeby algoritmu vždy tak, aby ve skupině nezůstalo po skončení turnaje
žádné místo volné.

Často bývá vhodné do mechanizmu selekce implementovat vlastnost, která
umožní nejsilnějším jedincům beze změny přejít do nové populace.
Touto vlastností je tzv. elitismus. Jejím prostřednictvím je možné
simulovat větší životnost kvalitních jedinců v populaci. V našem
zjednodušeném modelu populace platí, že ti nejkvalitnější jedinci mají
šanci přežít po dobu alespoň dvou generací, zatímco ti méně kvalitní
uhynou při výměně generací. Je dobré si také připomenout fakt, že
i jedinci, kteří jsou součástí elity, se mohou rozmnožovat.

\subsection{Genetické operátory}

Samotný proces rozmnožování v podstatě spočívá v rekombinaci chromosomů
rodičů a případné mutaci chromosomů potomků. Tlak na páření kvalitních
jedinců vyjadřuje naději, že potomci kvalitních rodičů budou alespoň
tak kvalitní, jako jejich rodiče a jejich šance na přežití v simulovaném
prostředí tak bude vyšší, než v případě rodičů.

Z předchozího textu je zřejmé, že budeme dále uvažovat pouze dvě operace
na chromosomech: křížení a mutaci. Mezi základní typy křížení patří
křížení bodové a křížení uniformní. Mutace bývá nejčastěji jednobodová,
zřídkakdy pak vícebodová.

V bodovém křížení se každý z rodičovských chromosomů rozřízne na několika
místech a vznikne tak určitý počet zpravidla různě dlouhých segmentů
které ze kterých se pak sestaví chromosomy potomků. Při sestavování
chromosomu prvního potomka se s předem definovanou pravděpodobností
použije segment z prvního rodiče a s doplňkovou pravděpodobností segment
z druhého rodiče. Druhý potomek je pak zrcadlovým obrazem prvního potomka.
V našem případě použijeme křížení jednobodové, které se dá zjednodušeně
popsat tak, že se z obou rodičovských chromosomů odřízne stejně velká
koncová část, jejímž prohozením získáme dva potomky.

Zatímco od křížení si slibujeme posílení výhodných vlastností rodičů
v potomcích, mutace pak do celého procesu vnáší určitý náhodný prvek.
Ten je užitečný především jako určitá kompenzace ztráty informace
v důsledku selekce. Mutace, ať už jedno- či vícebodová, spočívá ve změně
ohodnocení náhodně vybraných genů v chromosomu. Nové ohodnocení může být
jak náhodně vybraný prvek z domény genu, tak soused aktuálně použitého
prvku.

\section{Použitá literatura a zdroje}

\begin{itemize}
  \item{Fišer P.-Kubátová H.: \emph{Improvement of the Fault Coverage
    of the Pseudo-Random PhaseColumn-Matching BIST}}
  \item{Fišer P.-Kubátová H.: \emph{Pseudorandom Testing – A Study of
    the Effect of the Generator Type}}
  \item{Galaktionov P.: \emph{Syntéza generátoru testovacích vektorů
    pomocí genetických algoritmů}, CTU FEE, 2006}
  \item{Dwoskin J.: \emph{Cellular Automata as BIST Pattern Generators},
    2002}
  \item{Wikipedia: \emph{Design for Test}\\
    "http://en.wikipedia.org/wiki/Design\_For\_Test"}
  \item{Wikipedia: \emph{Automatic Test Pattern Generation}\\
    "http://en.wikipedia.org/wiki/Automatic\_test\_pattern\_generation"}
\end{itemize}

\end{document}

