% % $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{}} \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}