source: liacs/SCA2010/BDD/report.tex@ 136

%
% $Id: report.tex 571 2008-04-20 17:31:04Z rick $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage{graphicx}
\usepackage{url}
\usepackage{multicol}
\usepackage{fancybox}
\usepackage{amssymb,amsmath}

\author{Rick van der Zwet, Universiteit Leiden}
\title{BDD synthese}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}}
\date{\today}

\begin{document}

\maketitle

\section{Inleiding}
De hierin besproken inhoud is een samenvatting gemaakt van pagina 86--88 en de
daarin genoemde opgave 60 en 63 uit het college boek~\cite{DK2009} na
aanleiding van het vak Seminar Combinatorial Algorithms 2010~\cite{SCA2010}. 


\section{Introductie BDD}
Synthese van een Binary Decision Diagram \emph{BDD} is het belangrijke
\emph{BDD} algoritme~\cite[pp 86]{DK2009}. Welke in essentie een \emph{BDD}
functie,$f$, pakt en deze combineert met een andere \emph{BDD} functie,$g$,
zodanig dat er een nieuwe \emph{BDD} ontstaat voor de nieuwe functie.
Bijvoorbeeld $f \wedge g$ of $f \oplus g$.
De reden dat dit zo belangrijk is komt met het feit dat het combineren van
\emph{BDD}s aan de basis staat aan het uitdrukken van complexe systemen dmv van
gecombineerde simpele functies. In sectie~\ref{werking} zal deze techniek
uitgelegd worden, het zogenoemde \emph{smelten} (\emph{melding}) welke in
sectie~\ref{voorbeeld} dit toegepast zal worden in een concreet voorbeelden.

\section{Samenvoegen van \emph{BDD}}
\label{werking}
De term voor het samenvoegen \emph{BDD} structuren zullen we smelten
(\emph{melding}) noemen. Er werkt volgens de volgende principies.  Men neme
$\alpha = (v,l,h)"$ en $\alpha' = (v',l',h')$. De $\alpha \diamond \alpha'$, de
"\emph{emulsie}" (\emph{meld}) van $\alpha$ en $\alpha'$, is dan als volgt
gedefineerd als $\alpha$ ad $\alpha'$ niet beiden bladeren (\emph{sinks}) zijn:
\begin{equation}
\alpha \diamond \alpha' = \left\{
\begin{array}{l l}
(v, l \diamond l'), h \diamond h'), & \mathrm{if~} v = v'; \\
(v, l \diamond \alpha'), h \diamond \alpha'), & \mathrm{if~} v < v'; \\
(v, \alpha \diamond l'), \alpha \diamond h'), & \mathrm{if~} v > v'. \\
\end{array} \right.
\end{equation}

De oplettende lezer (voor de rest, voorbeeld figuur~\ref{voorbeeldSamenvoegen}) zal
zien dat je door het samenvoegen van de bladeren er in plaats van de twee bladeren
$\top$ en $\bot$, er nu vier bladeren mogelijk zijn:
\begin{equation}
\label{bladeren}
\begin{array}{l l l l}
\bot \diamond \bot, & \bot \diamond \top, & \top \diamond \bot, & \top \diamond \top\\
\end{array}
\end{equation}
Om er weer een 'valide' \emph{BDD} van te maken zullen deze bladeren vervangen
worden door het uitgerekende blad. Als bijvoorbeeld de $\diamond$ operatie een
$EN$ operatie was, wordt de bladrij in~\ref{bladeren} vervangen door de rij
$\bot, \bot, \bot, \top$. Nu is het zaak de \emph{BDD} te vereenvoudigen, om zo
duplicaat bladeren te snoeien (\emph{pruning}).

De kracht van deze aanpak zit hem in de zogenoemde generieke $\diamond$
operatie. Het maakt niet uit welke booleaanse operatie er gebruikt wordt aan
het eind van de rit. De gegeneerde gesmolten \emph{BDD} is geldig voor allen.

Kijkend naar de limieten moet geoordeeld worden kan hetzelfde altijd bereikt
worden door in het slechte geval de \emph{BDD}s achter elkaar te plakken welke
dan in dit geval $B(f)B(g)$ knopen oplevert. Voorbeeld~\ref{voorbeeldPlakken}
is hier een geval van. In het meer algemene geval geldt meestal $B(f) + B(g)$.
Deze grenzen worden in voorbeeld~\ref{voorbeeldSamenvoegen} aangescherpt.

Het smelten ligt aan de basis van de daarwerkelijke synthese. Een simpele
variant kan gemaakt worden met algoritme $R$. Maak eerst een reeks van
alle knopen $\alpha$ in $B(f)$ en $\alpha'$ in $B(g)$ met knoop $\alpha
\diamond \alpha'$ in rij $\alpha$ en column $\alpha'$. Vervang de bladeren
(\ref{bladeren}) door $\bot$ en $\top$. En voor algoritme $R$ uit op $f \diamond
g$. Op het eerste gezicht lijkt algoritme $R$ er ongeveer $B(f)B(g)$ over te
doen, maar doordat je onbereikbare knopen niet hoeft te evalueren zal je
uitkomen op $B(f \diamond g)$.

Deze 'truc' zorgt ervoor dat de tijd binnen de perken blijft, maar er is dan
nog niets gezegt over de hoeveelheid geheugen er nodig is. Omdat er nu
$B(f)B(g)$ knopen in geheugen gehouden moet wordt zal dit problemen opleveren
bij kleine en grotere algoritmen. Om deze ineffientie aan te pakken is
algoritme $S$ \footnote{Algoritme $S$ wordt niet in deze samenvatting gehandeld
de vakwebsite~\cite{SCA2010} heeft een verwijzing van de samenvatting van dit
algoritme} ontworpen.


\section{Voorbeelden}
\label{voorbeeld}
\subsection{Product groei in synthese van \emph{BDD}}
\label{voorbeeldSamenvoegen}
Het volgende voorbeeld is een uitwerking van opgave 60~\cite[pg. 130]{DK2009}
de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009}

Neem aan dat $f(x_{1},...,x_{n})$ en $g(x_{1},...,x_{n})$ de respectieve
\emph{profielen} (\emph{profiles})~\cite[pg 101]{DK2009} $(b_{0},...,b_{n})$ en
$(b'_{0},...,b_{n})$ hebben. En de respectieve \emph{quasi-profielen}
(\emph{quasi-profiles})~\cite[pg 103]{DK2009} $(q_{0},...,q_{n})$ en
$(q'_{0},...,q'_{n})$.  Om te laten zijn dat de gesmolten $f \diamond g$ het
aantal knopen van $B(f \diamond g) \leq
\sum^{n}_{j=0}(q_{j}b'_{j}+b_{j}q'_{j}-b_{j}b'_{j})$ bevat moet gekeken worden aan het aantal \emph{beads}~\cite[pg 72]{DK2009} dat mogelijkerwijs gemaakt kunnen worden van de functies $f$ en $g$.  

Elke bead van de orde $n - j$ van het geoordende paar $(f,g)$ zal binnen de standaard combinatie vallen de $b_{j}b_{j}'$ geordende beats van $(f,g)$. vallen of is er eentje uit een meer speciaal gegenereerde reeks van een (bead,geen-bead) of (geen-bead, bead) $b_{j}(q_{j}' - b_{j}') + (q_{j} - b{j})b_{j}'$. Zie hierbij dat van een functie het $B(quasi-profiel) \geq B(profiel)$. En dat alle in het profiel altijd in het quasi-profiel zit. Er dus de geen-bead kan beschrijven als de rest van de quasi-profiel minus profiel.

Dit bij elkaar optellen levert op $b_{j}b_{j}' + b_{j}(q_{j}' - b_{j}') + (q_{j} - b{j})b_{j}'$. Vereenvoudigen en de sommering is oefening voor de lezer.

\subsection{Som groei in synthese van \emph{BDD}}
\label{voorbeeldPlakken}
Het volgende voorbeeld is een uitwerking van opgave 63~\cite[pg. 131]{DK2009}
de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009}

Laat $f(x_{1},...,x_{n}) = M_{m}(x_{1} \oplus x_{2},x_{3} \oplus
x_{4},...,x_{2m-1} \oplus x_{2m};x_{2m+1},...,x_{n})$ en $g(x_{1},...,x_{n}) =
M_{m}(x_{2} \oplus x_{3},...,x_{2m-2} \oplus x_{2m-1},x_{2m};\overline
x_{2m+1},...,\overline x_{n})$ waar $n = 2m + 2^{m}$. 

Dan is $B(f) = 2^{m+2}-1 \approx 4n$, $B(g) = 2^{m+1}-2^{m} \approx 3n$ en $B(g
\hat f) = 2^{m+1}+2^{m-1}-1 \approx 2n^{2}$. Om aan deze 'magische' reeksen te
komen is het belangrijk eerst naar de profielen te kijken.





\begin{thebibliography}{}
\bibitem[DK2009]{DK2009} D.E. Knuth. Fascicle 1. \texttt{Bitwise Tricks \&
Techniques; Binary Decision Diagrams}, volume 4 of \texttt{The Art of Computer
Programming}. Pearson Education, first edition, March 2009.
\bibitem[SCA2010]{SCA2010} Lecture Seminar Combinatorial Algorithms, 
\url{http://www.liacs.nl/~kosters/semcom/}, dr. W.A. (Walter) Kosters, LIACS,
Spring 2010

\end{thebibliography}
\end{document}