\documentclass[11pt,german,a4paper]{report}
\usepackage{a4wide,graphicx,textcomp,amssymb, amsmath, nameref, acronym, color, epsf, listings, float} %here
\usepackage[utf8]{inputenc}
\usepackage[hidelinks]{hyperref}
\usepackage[ngerman]{babel}
\selectlanguage{ngerman}
\usepackage[margin=2.6cm]{geometry}
\usepackage[export]{adjustbox}[2011/08/13]
\pagestyle{headings} %Kopfzeilen
\setcounter{secnumdepth}{3}
\lstset{language=VHDL,frame=single,numbers=left}
\begin{document}

\title{\LARGE{Bachelorarbeit} \vspace{1cm}\\ 
  {\Huge \textbf {Parallele Berechnung der Mandelbrotmenge mit grafischer Ausgabe auf einem FPGA}}\\ \vspace{0.6cm}
  von\\
  {\huge \textbf {Meister Rados}
  	  \vfill
   \begin{center}
	\includegraphics[width=0.18\textwidth]{irilogoblue.png}
   \end{center}
  Betreuer:\\
  Dr. Jano Gebelein \\
  Lehrstuhl für Infrastruktur und Rechnersysteme in der Informationsverarbeitung \\ \vspace{0.3cm}
  Institut für Informatik\\
  Johann Wolfgang Goethe-Universität \\
  Frankfurt am Main\\
}}
\maketitle
\tableofcontents     %Inhaltsverzeichnis
\clearpage
\thispagestyle{plain}	
\noindent\Huge{\textbf{Abkürzungsverzeichnis}}\\
{\normalsize \begin{acronym}[Bash]
		\acro{ALU}{Arithmetic Logic Unit}\\
		Ein Hardwarebaustein, der ausschließlich zur logischen Berechnung von arithmetischen Ausdrücken dient.
		\acro{ASCII}{American Standard Code for Information Interchange}\\
		Eine rechnerinterne binär-Kodierung für Zeichen, die zum Beispiel von der Tastatur eingegeben werden können.
		\acro{BRAM}{Block \ac{RAM}}\\
		Eine konfigurierbare Unterklasse des \ac{RAM}s, die mit verschiedenen Wortbreiten genutzt werden kann.
		\acro{CPU}{Central Processing Unit}\\
		Ein Hardwarebaustein, der Programmcode ausführt. Er beherbergt alle primäre Recheneinheiten und koordiniert diese.
		\acro{DSP}{Digital Signal Processor}
		\acro{EPROM}{Erasable Programmable Read-Only Memory}\\
		Siehe \ac{PROM}, allerdings besteht die Möglichkeit, den beschriebenen Speicher wieder freizugeben.
		\acro{FPGA}{Field Programmable Gate Array} \\Ein Chip, in den logische Schaltungen geladen werden können. Somit ist er als konfigurierbare Hardware zu verstehen.
		\acro{GAL}{Generic Array Logic}\\
		Ein Halbleiterbaustein, der über komplett konfigurierbare Verknüpfungen zwischen seinen Ein- und Ausgängen verfügt.
		\acro{HDL}{Hardware Description Language}\\
		Eine hardwarebeschreibende, so genannte \glqq low-level\grqq~Beschreibungssprache, mit der integrierte Schaltungen beschrieben werden können. Sie kann genutzt werden, um ein \ac{FPGA} zu konfigurieren.
		\acro{ID}{Identifikationsnummer}\\
		Eine Zahl, die eindeutig mit einem Objekt oder einer Entität korrespondiert.
		\acro{IDE}{Integrated Development Environment}\\
		Ein Programm, das Programmierern ermöglicht, Quellcode zu kompilieren und zu testen. Darüber hinaus werden hilfreiche Werkzeuge für diesen Vorgang bereitgestellt.
		\acro{IP-Core}{Intellectual Property-Core}\\
		Ein Funktionsblock, der vom Hersteller angeboten wird, um Funktionalitäten in ein eigenes Design einzubringen.
		\acro{LED}{Light Emitting Diode}\\
		Ein Halbleiter-Bauelement, das bei Stromfluss in Durchlassrichtung ein Licht ausstrahlt.
		\acro{LUT}{Look-Up Table}\\
		\acro{MHz}{Megahertz}\\
		1 Megahertz $\hat{=}$ 1.000.000 Hertz. Ein Megahertz entspricht somit dem Ablauf einer Million Zyklen pro Sekunde.
		\acro{PCB}{Printed Circuit Board}\\
		Eine Leiterplatte, auf der integrierte Schaltungen physikalisch realisiert werden.
		\acro{Pmod}{Peripheral Module}\\
		Ein Schnittstellen-Standard. Er dient in dieser Bachelorarbeit als Schnittstelle zwischen dem \ac{FPGA} und dem Joystick oder  dem \ac{LED} Display.
		\acro{PROM}{Programmable Read-Only Memory}\\
		Ein Festwertspeicher, in den einmalig Daten geschrieben werden können. Diese Daten bleiben auch ohne Versorgungsspannung erhalten.
		\acro{RAID}{Redundant Array of Independent Disks}\\
		Bezeichnet ein Verfahren, bei dem Massenspeicher in einen Verbund geschaltet werden. Dies kann, je nach Umsetzung, zu einer höheren Datensicherheit oder Schreib- oder Lesegeschwindigkeit führen.
		\acro{RAM}{Random Access Memory}\\
		Bezeichnet einen Speicher, der über eine Speicheradresse direkt angesprochen werden kann. Er dient meist als Hauptspeicher für Recheneinheiten.
		\acro{SPI}{Serial Peripheral Interface}\\
		Ein Bus-System, das dazu dient, mit Peripherie zu kommunizieren.
		\acro{UART}{Universal Asynchronous Reciever Transmitter}\\
		Schnittstelle, die zum seriellen Senden und Empfangen von Daten dient. In dieser Bachelorarbeit wird sie zur Kommunikation zwischen dem Computer und dem FPGA genutzt.
		\acro{VHDL}{Very High Speed HDL}\\
		Eine Hardwarebeschreibungssprache. Sie wird in dieser Bachelorarbeit zum Konfigurieren des FPGAs genutzt.
		
		
\end{acronym}}
\normalsize
\listoffigures
\listoftables
\clearpage
\noindent\Huge{\textbf{Zusammenfassung}}\\
\normalsize

\thispagestyle{plain}
\vspace{20px}
In dieser Bachelorarbeit wird ein VHDL-Entwurf vorgestellt, der parallel eine grafische Ausgabe der Mandelbrotmenge berechnet. Es wird auf das Rechnen mit komplexen Zahlen, sowie die Definition der Mandelbrotmenge, Automaten in VHDL-Syntax und die Möglichkeit durch Modularisierung eine einfache, theoretisch beliebig-fache Parallelisierung zu erzielen, eingegangen. Zudem wird die Problematik der praktisch begrenzten Anzahl der konfigurierbaren Logikzellen auf dem FPGA aufgezeigt. Abschließend werden Simulationsergebnisse genutzt, um die Effizienz der Parallelisierung des Entwurfs einschätzen zu können.\\

\vspace*{5cm}


\noindent\Huge{\textbf{Abstract}} \normalsize(English)\\

\vspace*{20px}

A VHDL implementation to parallely compute an visual image of the Mandelbrot set is being presented in the following bachelor thesis. The definition of the aforementioned set, the laws of complex numbers, as well as the implementation of finite state machines in VHDL syntax and lastly the advantages of modularized programming regarding parallelization is being concerned. Furthermore, a problem regarding the limited amount of configurable cells inside the FPGA is shown up in this thesis. Finally, the data resulting from the simulation is evaluated in order to estimate the efficiency provided by parallelizing the design.

\clearpage
\chapter{Einleitung}
\section{Motivation}
\label{motivation}
In dem Modul \glqq Mathe für die Informatik 1: Analysis und lineare Algebra\grqq, das Teil der Basismodule des Bachelors an der Goethe Universität Frankfurt am Main ist, wird das Rechnen mit komplexen Zahlen vorgestellt. Eine praktische Anwendung zur Ergänzung der Lehrveranstaltung 
\cite{BO} kann durch die hier geleistete Vorarbeit dargestellt werden.\\
Einer der bekanntesten Anwendungsfälle der komplexen Zahlen findet sich in Verbindung mit der Mandelbrotmenge. Die Darstellung ist, verglichen mit anderen mathematischen oder geometrischen Konstrukten, aufgrund der unendlichen Vielfalt einzigartig.\\
In einem anderen Basismodul des Bachelor Studienganges, dem \glqq Grundlagen von Hardwaresystemen - Praktikum\grqq, werden \ac{FPGA}s  vorgestellt. Es wird dort die konfigurierbare Hardware eingeführt, die es möglich macht, jegliche digitale Berechnungen zu implementieren. Dazu wird eine sogenannte \ac{HDL} verwendet. In diesem Praktikum wird die Hardwarebeschreibungssprache \ac{VHDL} gelehrt \cite{BO}.\\
Um das aus diesen beiden Veranstaltungen gelehrte Wissen praktisch zusammenzuführen, liegt es nahe, die Berechnung der Mandelbrotmenge auf einem solchen \ac{FPGA} zu implementieren und sie in ihrer einzigartigen Vielfalt auszugeben. Darüber hinaus besteht ein Forschungsaspekt darin, herauszufinden, inwiefern sich diese Berechnung parallelisieren lässt.

\section{Arbeitsumgebung}

\subsection{Software}
Der \ac{VHDL}-Code wurde in der Xilinx Vivado 2016.4 Umgebung, installiert auf einem Windows 7 Laptop, entwickelt. Die genutzte Hardwarebeschreibungssprache ist \ac{VHDL}. Vivado allein übernimmt hierbei alle wichtigen Rollen wie das Aufzeigen von Syntaxfehlern als \ac{IDE}, das Synthetisieren des Codes zu einer Neztliste, das Routen des \ac{VHDL} Entwurfs, sowie das Erzeugen eines Schaltkreislayouts. Ebenfalls wird das Generieren des Bitstreams und das Konfigurieren der Zielplattform, des \ac{FPGA}s, von Vivado übernommen.
\clearpage
\subsection{Hardware}
\subsubsection{FPGA}
\label{fpga}
Als Zielplattform dient das von Digilent entwickelte Nexys 4 DDR Board. Das Nexys 4 basiert auf dem Xilinx Artix-7 \ac{FPGA} Chip und bietet weitreichende Peripherie, mit der es möglich wird, die entwickelten Anwendungen sehr vielseitig zu implementieren. Wesentlich sind die konfigurierbaren Zellen auf dem Artix-7 Chip, die es ermöglichen das Board mit einem Entwurf zu laden. Dazu verfügt der Chip über FlipFlops, \ac{BRAM}, \ac{DSP}s, und \ac{LUT}s \cite{Dig0}. \\

In dieser Bachelorarbeit sind die relevanten Schnittstellen:
\begin{itemize}
	\item \ac{UART} Schnittstelle
	\item 16 \ac{LED}s
	\item 16 Schalter
	\item 5 Taster
	\item 2 \ac{Pmod} Schnittstellen
\end{itemize}

\begin{figure}[h]
\begin{center}
	\includegraphics[width=0.6\textwidth]{nexys-4-ddr-2.png}
\end{center}
\caption[Das FPGA]{Digilent Nexys4 Board mit Artix-7 Chip}
\label{nexys4}
\end{figure}

\subsubsection{Joystick}
Zur Eingabe wird ein \ac{Pmod} Joystick von Digilent verwendet. Dieser verfügt für die Eingabe über 3 Taster, sowie einen 2 Achsen Joystick. Außerdem werden 2 \ac{LED}s zur Ausgabe genutzt. Der Joystick wird über ein \ac{SPI} betrieben.\\
Der Stick dient zur primären Navigation durch die Mandelbrotmenge. Wird er bis zum Anschlag in eine der vier zum \ac{PCB} senkrechten Richtungen bewegt, ändert sich die Position des sichtbaren Ausschnitts der Mandelbrotmenge. Durch Herunterdrücken des Joysticks wird gezoomt.

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.4\textwidth]{Pmod_JSTK__42787.png}
	\end{center}
	\caption[Der Joystick]{Digilent \ac{Pmod} Joystick \cite{Dig1}}
	\label{pmod_jstk}
\end{figure}

\subsubsection{LED Display}
Zur grafischen Ausgabe der berechneten Mandelbrotmenge wird ein \ac{Pmod} \ac{LED} Display von Digilent verwendet. Das Display verfügt über 6144 Pixel, 94 Pixel in der Breite und 64 Pixel in der Höhe. Jeder Pixel hat eine 16 Bit Farbauflösung, das heißt, jeder Pixel kann bis zu 65.536 verschiedene Farben darstellen.

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.4\textwidth]{pmodoledrgb-0.png}
	\end{center}
	\caption[Das Display]{Digilent \ac{Pmod} LED Display, das Zielgerät der grafischen Ausgabe.\cite{Dig2}}
	\label{pmod_led}
\end{figure}

\section{Ziele}
\label{ziele}
Ziele dieser Bachelorarbeit bestehen darin,
\begin{itemize}
	\item einen Hardwareentwurf für \ac{FPGA}s zu entwickeln, der darauf spezialisiert ist, die Mandelbrotmenge zu erkunden
	\item einen Joystick zur Eingabe einzubinden, um durch die Mandelbrotmenge navigieren zu können und diese auf einem Display auszugeben
	\item zu einer Beurteilung über Effizienz der Parallelisierbarkeit der Berechnung zu kommen

\end{itemize}
\chapter{Stand der Technik}

\section{FPGAs}

Das erste Field Programmable Gate Array wurde 1985 von Ross Freeman entwickelt \cite{CB07}. Davor allerdings stand eine lange Entwicklungszeit, angefangen 1960 mit dem ersten Feldeffekttransistor über den ersten konfigurierbaren Speicher, dem 1970 entwickelten \ac{PROM} und einem Jahr später, 1971, dem wiederbeschreibbaren \ac{EPROM} bis hin zum \ac{GAL} im Jahre 1983 \cite{KF15}.\\
Seitdem wird an immer leistungsstärkeren \ac{FPGA}s geforscht, um immer vielseitigere und anspruchsvollere Entwürfe realisieren zu können. Aktuelle \ac{FPGA}s sind soweit konfigurierbar, dass sie zu einer eigenständigen \ac{CPU} konfiguriert werden können. Dem Programmierer sind hierbei keine konventionellen Auflagen gegeben. Er darf frei nach Belieben seine \ac{CPU} entwerfen und sie ganz präzise für einen bestimmten Anwendungsfall zuschneiden.\\
Dadurch ergibt sich ein grundlegender Vorteil: wird zum Beispiel in einem Anwendungsfall ausschließlich dividiert, so besteht die Möglichkeit, alle auf dem \ac{FPGA} verfügbaren Logikgatter auf das Dividieren zu optimieren. Eine \ac{CPU}, die in Desktop-Rechnern verbaut ist, verfügt nur über universelle, statische logische Einheiten. Diese allerdings in großer Zahl, sodass sie beliebige Anwendungen in schnellem Kontextwechsel ausführen kann. Das macht sie zwar vielseitig einsetzbar, aber die gesamte Rechenkraft kann nicht ausschließlich dem Dividieren zugeordnet werden, sodass in diesem beispielhaften Anwendungsfall der Einsatz eines \ac{FPGA} sinnvoller ist.\\
Somit lässt sich prinzipiell schließen: Der Anwendungsfall entscheidet, ob eine \ac{CPU} oder ein \ac{FPGA} Verwendung findet. Kann eine digitale Schaltung eine gegebene Aufgabe lösen, eignet sich ein \ac{FPGA} mit entsprechender Konfiguration. Steht allerdings bei Inbetriebnahme des Gerätes der Anwendungsfall nicht fest, so eignet sich eine \glqq Alleskönner\grqq- \ac{CPU}, die über diverse Recheneinheiten verfügt.\\
Eine konkrete Anwendung für \ac{FPGA}s findet sich in der Forschung an \ac{RAID}-Controllern, die ohne Batterie auskommen sollen \cite{WP}. Neue Technologie, die diese Ansprüche erfüllen soll, kann flexibel mit einem \ac{FPGA} getestet und eingesetzt werden. Die Möglichkeit, \ac{FPGA}s neu zu konfigurieren, erspart dabei kostspieliges Austauschen der Hardware.
\\
In dieser Bachelorarbeit wird daher das \ac{FPGA} so konfiguriert, dass es parallel die Mandelbrotmenge (siehe Kapitel \ref{mm}) berechnet. \\
Für nähere Informationen zu dem in dieser Bachelorarbeit verwendeten \ac{FPGA}, siehe Kapitel \ref{fpga} (\nameref{fpga}).

\section{Komplexe Zahlen}
Die Menge der komplexen Zahlen $\mathbb{C}$ ist eine Erweiterung der Menge der reellen Zahlen $\mathbb{R}$ um eine imaginäre Einheit $i$, die folgende elementare Eigenschaft aufweist: $$i^2 = -1$$Dadurch erhält zum Beispiel die Gleichung $x^2 + 1 = 0$, die im reellen Zahlenraum $\mathbb{R}$ keine Lösung hat,  eine Lösungsmenge $\mathbb{L} = \{i\}$. Damit hat jede algebraische Gleichung positiven Grades über die komplexen Zahlen $\mathbb{C}$ eine Lösung.\\
Auch in der Physik oder  der Elektrotechnik finden die komplexen Zahlen $\mathbb{C}$ Anwendung. Darauf wird aber in dieser Arbeit nicht näher eingegangen.\\
Alle komplexen Zahlen c $\in \mathbb{C}$ sind von der Form: $c = a + b \cdot i$, wobei $a,b \in \mathbb{R}$ und $i$ die komplexe Einheit darstellt. $a$ ist als Realteil einer komplexen Zahl $c$, und $b \cdot i$ als Imaginärteil von $c$ zu verstehen.\\
Die komplexen Zahlen lassen sich in einem zweidimensionalen Graphen darstellen, indem die horizontale Achse den Realteil, und die vertikale Achse den Imaginärteil der komplexen Zahl beschreibt. Dieser Graph nennt sich auch die \glqq Komplexe Ebene\grqq.
\begin{figure}[h]
	\label{complexplane}
	\begin{center}
		\includegraphics[width=0.2\textwidth]{complex-plane.png}
	\end{center}
	\caption[Die komplexe Ebene]{Die komplexe Ebene und eine komplexe Zahl $a + b \cdot i$ \cite{cp}}
\end{figure}

\subsection{Rechnen mit komplexen Zahlen}
Es werden die folgenden arithmetischen Operationen auf komplexen Zahlen betrachtet:
\begin{itemize}
	\item \nameref{addition}
	\item \nameref{subtraction}
	\item\nameref{multiplication}
	\item \nameref{absoluteValue}
\end{itemize}
\subsubsection{Addition}
\label{addition}
Seien $c_0 := a + b \cdot i$ und $c_1 := c + d \cdot i$ zwei komplexe Zahlen, so ist ihre Summe $$c_0 + c_1 = (a + b \cdot i) + (c + d \cdot i) = (a + c) + (b + d) \cdot i$$
Vereinfacht lässt sich sagen, dass sich jeweils die Realteile, sowie die Imaginärteile der beiden komplexen Zahlen addieren.
\subsubsection{Subtraktion}
Die Subtraktion verläuft analog zur Addition. Seien weiterhin  $c_0 := a + b \cdot i$ und $c_1 := c + d \cdot i$ zwei komplexe Zahlen, so ist ihre Differenz  $$c_0 - c_1 = (a + b \cdot i) - (c + d \cdot i) = (a - c) + (b - d) \cdot i$$
Auch hier ist zu beobachten, dass sich jeweils die Realteile, sowie die Imaginärteile voneinander subtrahieren.
\label{subtraction}
\subsubsection{Multiplikation}
\label{multiplication}
Seien weiterhin  $c_0 := a + b \cdot i$ und $c_1 := c + d \cdot i$ zwei komplexe Zahlen, so ist ihr Produkt $$c_0 \cdot c_1 = (a + b \cdot i) \cdot (c + d \cdot i) = (a \cdot c - b \cdot d) + (a \cdot
 d + b \cdot c) \cdot i$$
Das Quadrat einer komplexen Zahl $c_0 := a + b \cdot i$ lässt sich vereinfacht wie folgt darstellen:
$$ c_0^2 = (a + b \cdot i) \cdot (a + b \cdot i) = a^2 + 2 \cdot a \cdot b \cdot i + (b \cdot i)^2 =  a^2 + 2 \cdot a \cdot b \cdot i - b^2 = a^2 - b^2 + 2 \cdot a \cdot b \cdot i$$
\subsubsection{Betragsrechung}
Sei  $c_0 := a + b \cdot i$ eine komplexe Zahl, so lässt sich ihr Betrag, also die Distanz von $c_0$ zum Ursprung der komplexen Ebene wie folgt berechnen:
$$|a + b \cdot i| = \sqrt{a^2 + b^2}$$
\label{absoluteValue}

\section{Mandelbrotmenge}
\label{mm}
\subsection{Definition}
Die Mandelbrotmenge $\mathbb{M}$ ist eine Menge von komplexen Zahlen in der komplexen Ebene. Eine komplexe Zahl $c$ ist genau dann in der Mandelbrotmenge, wenn sie unter unendlich langer Iteration der \hyperref[mf]{Mandelbrotschen Formel} zu einem bestimmten Wert konvergiert. Existiert kein Konvergenzwert, so divergiert $c$ unter Iteration der \hyperref[mf]{Mandelbrotschen Formel} und liegt nicht in der Mandelbrotmenge.
Die Formel, die auf einer komplexen Zahl iteriert wird, ist wie folgt definiert:\\

Definition 1: \emph{\hyperref[mf]{Mandelbrotsche Formel}}\\
\label{mf}
$$z_0 = 0 + 0 \cdot i$$
$$z_{n+1} = z_n^2 + c$$
\\Sei für eine beliebige Zahl $c \in \mathbb{C}$ festzustellen, ob sie divergiert oder konvergiert, so wird diese Formel auf $c$ so lange iteriert, bis der Betrag von $c$ einen bestimmten Wert $absValueMax$ überschreitet. Dieser Wert ist frei aus $\mathbb{R}_{>0}$ zu wählen. 
\subsubsection{Iterieren}
\begin{itemize}
	\item $z_0$: 
	Gemäß der Mandelbrotschen Formel ist der Wert jeder komplexen Zahl $c$ in der ersten Iteration stets 0.\\
	$\implies z_0 = 0 + 0 \cdot i$
	\item $z_1$:
	 In der zweiten Iteration wird der Wert von $z_0$ quadriert. Anschließend wird der Wert von der Zahl $c$ addiert.\\
	 $\implies z_1 = 0^2 + c = c$
	 \item In der zweiten Iteration wird $z_1$, also $c$ selbst, quadriert. Danach wird wieder die Konstante $c$ addiert.\\
	 $\implies z_2 = c^2 + c$
	 \item In der dritten, und jeder folgenden Iteration, wird ebenso weiter verfahren.\\
	 $\implies z_3 = (c^2 + c)^2 + c$\\
	 $\implies z_4 = ((c^2 + c)^2 + c)^2 + c$\\
	 $\implies z_5 = (((c^2 + c)^2 + c)^2 + c)^2 + c$\\
	 $\implies z_6 = ...$
\end{itemize}
  \subsubsection{Abbruchkriterien: Konvergenz und Divergenz}
  Mit der Iteration wird so lange verfahren, bis der Betrag von $c$ die gewählte obere Schranke $absValueMax$ überschreitet. Sollte allerdings der Wert von $c$ unter Iteration zu einem bestimmten Wert kleiner als $absValueMax$ konvergieren, so kann $absValueMax$ nie erreicht werden. Es liegt der erste Fall von Konvergenz vor. Die Zahl $c$ kann aber auch unter Iteration zwischen zwei Werten, die beide jeweils kleiner als $absValueMax$ sind, alternieren, oder sich unendlich lange chaotisch um eine komplexe Zahl kleiner als $absValueMax$ bewegen. Auch in diesen Fällen nimmt man an, das $c$ konvergiert. Um in den Fällen der Konvergenz nicht unendlich lange zu iterieren, wird eine Obergrenze der Iterationsanzahl, ein Wert $iterationMax$ benötigt. Wird dieser erreicht ohne Divergenz festzustellen, so stellt das das hinreichende Kriterium für Konvergenz dar und das Iterieren auf $c$ wird beendet. Sollte dies für eine komplexe Zahl $c$ gelten, so liegt sie in der Mandelbrotmenge.

\subsection{Geschichtliches}
Die Mandelbrotmenge wurde nach Benoît Mandelbrot, einem französisch-US-amerikanischen Mathematiker benannt  \cite{mm0}. Eine erste Veröffentlichung, in der eine farbige und detailreiche grafische Darstellung der Mandelbrotmenge zu sehen ist, und bei der auf die Selbstähnlichkeit und auf das Wiederkehren der Julia-Mengen \cite{JU} eingegangen wird, stammt bereits aus dem Jahre 1981/82 \cite{mm1}.\\
Erste Forschungen bezüglich dem Verhalten von Zahlen in der komplexen Ebene unter Iteration von polynomiellen Funktionen wurden schon viel früher, im Jahre 1906 von Pierre Fatou veröffentlicht \cite{PF06}. Zu dieser Zeit war es noch nicht möglich, das Erforschte mit elektronischen Hilfsmitteln zu berechnen und in irgendeiner Form grafisch auszugeben. Was Pierre Fatou erforschte, steht in unmittelbaren Zusammenhang mit den heutzutage so genannten Julia-Mengen \cite{PFwiki}.\\
Die erste visuelle Darstellung der Mandelbrotmenge wurde 1978/1979 von Robert W. Brooks und Peter Matelski veröffentlicht \cite{RBPM78}. Diese Darstellung bedient sich noch keinen Farben, bloß dem \ac{ASCII} Zeichen \grqq*\glqq, das einer konvergierenden komplexen Zahl entspricht. Divergierende komplexe Zahlen erhalten in dieser Darstellung kein Symbol und bilden somit die weiße Fläche in der Darstellung.
\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.4\textwidth]{fatou1906.jpg}
	\end{center}
	\caption[Visualisierung der Julia-Mengen]{Visualisierung einer Julia-Menge, die bereits 1906 von Fatou untersucht wurde.}
\end{figure}
\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.7\textwidth]{firstman.png}
	\end{center}
	\caption[Erste Visualisierung der Mandelbrotmenge]{Die erste veröffentlichte Visualisierung der Mandelbrotmenge \cite{RBPM78}}
\end{figure}
\subsection{Erzeugen der Bilder}
Um die farbkodierte Darstellung der Mandelbrotmenge umzusetzen, wird ein Ausschnitt der komplexen Ebene auf die anzeigende Bildfläche gelegt. Nun erhält jeder Pixel eine komplexe Zahl $c$, die an der Stelle des Pixels zur komplexen Ebene korrespondiert. Anschließend wird auf  $c$ gemäß der \hyperref[mf]{Mandelbrotschen Formel} iteriert. Es werden die Iterationen gezählt, die es gebraucht hat, um Divergenz festzustellen, also bis der Betrag von $c$ die Obergrenze $absValuaMax$ überschritten hat. Die Anzahl der benötigten Iterationen wird im Folgenden als \emph{\hyperref[itval]{Iterationswert}} bezeichnet. Jedem \hyperref[itval]{Iterationswert} wird eine Farbe zugewiesen, die dann an dem Pixel angezeigt wird. Diese Farben werden in einer Farbpalette hinterlegt. Da diese unabhängig von den Berechnungen ist, besteht hier die freie Wahl über die Farben, die angezeigt werden. Daraus resultieren beliebig viele verschiedene farbliche Repräsentationen der Mandelbrotmenge.\\
Wird unter Iteration die obere Iterationsgrenze $iterationMax$ erreicht, so stellt dies das hinreichende Kriterium dar, um Konvergenz anzunehmen. Für jede Zahl $c$ wird dann angenommen, dass sie in der Mandelbrotmenge liegt. Es wird konventionell die Farbe schwarz an dieser Stelle angezeigt.\\


Definition 2: \emph{\hyperref[itval]{Iterationswert}}\\
\label{itval}
 Der \hyperref[itval]{Iterationswert} beschreibt die Anzahl an Iterationen, die benötigt wurden, bis der Betrag einer komplexen Zahl den Wert $absValueMax$ überschritten hat.\\
 

\begin{figure}[h]
	\label{man}
	\begin{center}
		\includegraphics[width=0.8\textwidth]{man.png}

	\caption[Die Mandelbrotmenge]{

			 Die grafische Darstellung der Mandelbrotmenge mit zugehöriger Farbpalette darunter. Im äußeren Bereich  des Bildes sind die Grenzen zwischen den \hyperref[itval]{Iterationswerten} gut zu erkennen.}
	\end{center}
\end{figure}

\chapter{Ansatz}

\section{Modularisierung}

Das modulare Programmieren ist ein Programmierparadigma, das sich dadurch charakterisiert, dass ein größeres Programm aus kleineren Untereinheiten, so genannten Modulen, besteht. Es bietet sich die Möglichkeit, die einzelnen Module gezielt zu testen und sie im Bedarfsfall zu erweitern, ändern oder auszutauschen. Wichtig dabei ist, dass die Schnittstelle zu den anderen Modulen nicht geändert wird. Sollte eine Änderung der Schnittstelle aufgrund größeren Umstrukturierungen an einem Modul nötig sein, so muss ebenfalls die Schnittstelle auf der korrespondierenden Seite so angepasst werden, sodass beide Schnittstellen wieder übereinstimmen.\\
Sollte im Vorhinein Funktionalität und Schnittstelle der einzelnen Module bekannt sein, so können die Module parallel entwickelt werden.\\
Durch mehrfache Instantiierung eines Moduls besteht die Möglichkeit, die gleiche Rechnung parallel auszuführen. Dazu muss dieses Modul nur ein einziges Mal geschrieben werden und es bedarf eines hierarchisch übergeordnetem Modul, das genügend Schnittstellen bereitstellt und alle Module koordinieren kann. Eine Obergrenze für die Anzahl der instantiierten Module besteht dabei theoretisch nicht.\\
Somit bietet die modulare Programmierung zwei wesentliche Vorteile: einfache Parallelisierung, in Anwendung und Entwicklung, sowie flexible Designs aufgrund der einfachen Austauschbarkeit der Module.\\
Wie in diesem Kontext die Modularisierung umgesetzt wurde, siehe Kapitel \glqq\nameref{implementierung}\grqq (Kapitel \ref{implementierung}).

\subsection{Modularisierung in VHDL}

In \ac{VHDL} werden Hardwarebausteine (also die Module) in strikter Trennung zwischen Schnittstelle (\glqq Entity\grqq) und Verhalten (\glqq Architecture\grqq) beschrieben. In der \glqq Entity\grqq~-Umgebung werden die Ein- und Ausgänge des Bausteins definiert. In der \glqq Architecture\grqq-Umgebung besteht die Möglichkeit, mit Hilfe der \texttt{component} Anweisung andere Bausteine zu instantiieren. Versorgt man die Ein- und Ausgänge des instantiierten Moduls mit Signalen aus der übergeordneten \glqq Architecture\grqq, lässt sich eine Hierarchie unter den Hardwarebausteinen erzeugen. Daraus resultiert implizit eine modulare Programmierung. 

\section{Automaten}

Um die Funktionalität der Module strukturiert und übersichtlich zu implementieren, werden endliche Automaten genutzt. In \ac{VHDL} eignet sich eine Implementierung eines Moore-Automaten. Ein Moore-Automat ist ein endlicher, deterministischer Automat, dessen Ausgabe nur von seinem aktuellen Zustand abhängt. Er besteht aus 
\begin{itemize}
	\item einem Eingabealphabet $\Sigma$, eine Menge von Zeichen, die gelesen werden können. Da Eingabe auch aus Zeichenfolgen bestehen dürfen, gilt für alle Eingabeworte $w$ : $w \in \Sigma^*$
	\item einer nicht-leeren Menge von Zuständen $Q$
	\item einer Transitionsfunktion $\delta : Q \times \Sigma \to Q$, die einem aktuellen Zustand $q \in Q$ gepaart mit einer Eingabe $w \in \Sigma$ einen Folgezustand $q^+ \in Q$ zuweist.
	\item einem Startzustand $q_0 \in Q$, der zu Beginn vom Automaten angenommen wird
	\item einer Menge $F \subseteq Q$ von akzeptierenden Zuständen. Befindet sich nach Verarbeiten der Eingabe der Automat in einem Zustand $q \in F$, so wird die Eingabe als akzeptiert angesehen. Terminiert der Automat in einem Zustand $q \notin F$, so ist die Eingabe als verworfen anzusehen. Im Rahmen der Implementierung spielt das Akzeptieren von Eingaben keine Rolle, daher wird $F$ stets die leere Menge $\emptyset$ sein.
\end{itemize}
Um einen Moore-Automaten eindeutig zu beschreiben, bedarf es der Definition dieser 5 Eigenschaften. Konventionell wird demnach ein Moore-Automat $M$ als Quintupel $M = (Q, \Sigma, \delta, q_0, F)$ angegeben.

\subsection{Moore-Automaten in VHDL-Syntax}
In \ac{VHDL} lassen sich Moore-Automaten mit Hilfe der Aufzählungstypen (\texttt{type}-Anweisung), der Prozessumgebung (\texttt{process}-Anweisung) und des \texttt{case-when}-Statements realisieren. Die Aufzählungstypen erlauben es, Zustände mit einem lesbaren Bezeichner zu versehen. Auf der Hardware allerdings werden Zustände weiterhin binär kodiert. Die Prozessumgebung ermöglicht es, mit High-Level-Programmieranweisungen wie \texttt{if-then-else}, oder \texttt{case-when} Statements übersichtlich in allen möglichen Zuständen Eingaben zu verarbeiten und daraufhin einen Folgezustand zu ermitteln. Hier wird dem Programmierer das mühsame Dekodieren von Zuständen abgenommen.\\
Moore-Automaten lassen sich mit verschieden vielen Prozessen implementieren. In dieser Implementierung wurde entschieden, 3 Prozesse zu nutzen:
\begin{itemize}
	\item Der erste Prozess dient dazu, synchron zum Taktsignal in einen ermittelten Folgezustand zu wechseln. Auch das Verarbeiten eines Reset-Signals wird hier realisiert.
	\item Der zweite Prozess bestimmt die Ausgabe für den aktuellen Zustand.
	\item Der dritte Prozess ist der einzige asynchrone Prozess. Er bestimmt den Folgezustand und kann auf Eingaben reagieren.
\end{itemize}
Es ist auch möglich einen Moore-Automaten mit einem einzigen asynchronen Prozess zu realisieren. Dabei ergeben sich andere Ergebnisse nach der Synthese. Dies kann eventuell zu Vor- und Nachteile in der Optimierung der Schaltung und dem daraus resultierendem Timing führen.\\


\begin{minipage}{\textwidth}
\lstinputlisting[caption={Beispielhafte Deklaration der Zustandsmenge $Q = \{start, c\_calc7\}$ und des Startzustandes $q_0 = start$ in \ac{VHDL}}]{types.vhd}
\end{minipage}

\begin{minipage}{\textwidth}
	\lstinputlisting[caption={Beispielhafte Implementierung des ersten Prozesses}]{nextstate.vhd}
	
\end{minipage}

\section{IP-Cores}
\ac{IP-Core}s sind bereits fertig geschriebene Code-Blöcke, die Dritte zur lizenzierten Nutzung bereitstellen. In dieser Implementierung kommen folgende \ac{IP-Core}s zum Einsatz:
\begin{itemize}
	\item Floating-Point\\
	Zum Rechnen mit Gleitkommazahlen. Arithmetische Operationen wie die Addition, Subtraktion und Multiplikation werden von Floating-Point übernommen.
	Floating Point nimmt zwei Operanden als Bitvektor entgegen und gibt einen Bitvektor als Ergebnis zurück. Die genaue Kommunikation erfolgt über einzelne Pins, die über die Gültigkeit der Daten auf den Vektoren Auskunft gibt. Die korrekte Ansteuerung von Floating-Point muss implementiert werden.
	\item Clocking Wizard\\
	Zum Erzeugen sauberer Clock-Signale.
	Clocking-Wizard nimmt ein Clock-Signal entgegen und kann daraus verschiedene Clock-Signale, auch anderer Frequenz erzeugen.
	Auch hier muss die korrekte Ansteuerung implementiert werden.
\end{itemize} 

\section{Systemeigenschaften}

Um die Aufgabenstellung aus \ref{ziele} zu erfüllen, müssen folgende Systemeigenschaften implementiert werden:

\begin{enumerate}
	\item \label{hci}Um die Mensch-Computer-Interaktion sicher zu stellen, müssen der Joystick und das LED-Display korrekt angesprochen werden
	\item \label{complex2disp}die komplexe Ebene muss auf dem \ac{LED} Display ausgegeben werden
	\item \label{values}Es müssen sinnvolle Werte für die Variablen $absValueMax$ und $iterationMax$ gefunden werden
	\item \label{makemath} Es müssen beliebig viele komplexe \ac{ALU}s (im Folgenden z.T. auch nur \glqq ALU\grqq) mit einer komplexen Zahl des sichtbaren Bildbereichs versorgt werden
	\item \label{makealu}Es muss eine parallelisierbare \ac{ALU} entwickelt werden, die die \hyperref[mf]{Mandelbrotsche Formel} auf einer komplexen Zahl iterieren kann
	\item \label{makecolor} Die errechneten \hyperref[itval]{Iterationswerte} für jeden Pixel müssen einer Farbe zugeordnet werden, die dann auf dem Display an der korrekten Stelle angezeigt werden
\end{enumerate}

\noindent \textbf{Ansätze, um die kleineren Ziele zu erreichen:}\\

\noindent (\ref{hci}.) Die Mensch Computer-Interaktion wird von den Modulen \nameref{jstk} und \nameref{led} übernommen. Genaueres wird in Abschnitt \ref{jstk} (\nameref{jstk}), und \ref{led} (\nameref{led}) erläutert.\\
(\ref{complex2disp}.) Um die komplexe Ebene auf dem \ac{LED} Display auszugeben, wird lediglich der Wert der komplexen Zahl in der unteren linken Ecke des Displays gespeichert. Von dort aus wird auf den Realwert dieser Zahl ein Zoomfaktor addiert. Ist der rechte Rand des Displays erreicht (nach 96 Pixeln, 95 Additionen), wird der ursprüngliche Realwert wiederhergestellt und der Zoomfaktor wird auf den Imaginärteil addiert. Nach diesem Schema wird weiter verfahren, bis der obere rechte Pixel erreicht wird. So wird lediglich unter der Verwendung einer Addiereinheit das ganze Display nach und nach abgearbeitet.\\
(\ref{values}.) Der Wert für $absValueMax$ muss aus $\mathbb{R}_{>0}$ stammen. Um unnötige komplizierte Rechnungen zu vermeiden, wurde entschieden, den Wertebereich, aus dem $absValueMax$ stammen darf, auf $\mathbb{N}_{>0}$ zu begrenzen. Da die Mandelbrotmenge etwa um den Ursprung der komplexen Ebene zentriert ist, und der betragsmäßig davon am weitesten entfernte Punkt bei $2 + 0 \cdot i$ liegt, eignet sich 2 als Wert für $absValueMax$. In dieser Implementierung wurde entschieden, eben 2 als Wert zu benutzen. Andere Implementierungen, die 100 (oder ähnlich große Zahlen) als Wert für $absValueMax$ gewählt haben, kommen zur scheinbar gleichen visuellen Darstellung, allerdings sind die \hyperref[itval]{Iterationswerte} höher, da das Abbruchkriterium für die Iteration später erreicht wird. Dies führt zu längeren Berechnungszeiten, ohne sichtbar anderem Ergebnis.\\
Der Wert für $iterationMax$ stammt aus $\mathbb{N}_{>0}$. Je höher dieser Wert gewählt wird, desto länger dauern die Berechnungen für die Bildpunkte, vor allem jene, an denen der Wert der komplexen Zahl konvergiert. Dafür können bei hoher Zoomstufe schärfere Bilder der Mandelbrotmenge erzeugt werden. Als Kompromiss zwischen Rechenzeit und Qualität wurde $iterationMax$ auf 1.000 gesetzt.
\\
(\ref{makemath}.) Die korrekte Ansteuerung der \ac{ALU}s übernimmt das Hardwaremodul \glqq\nameref{math}\grqq. Genaueres ist Abschnitt \ref{math} (\nameref{math}) zu entnehmen.
\\
(\ref{makealu}.) Das Iterieren der \hyperref[mf]{Mandelbrotschen Formel} auf einer gegebenen komplexen Zahl $c$ übernimmt das Hardwaremodul \grqq\nameref{complex}\glqq. Näheres ist Abschnitt \ref{complex} (\nameref{complex}) zu entnehmen.
\\
(\ref{makecolor}.) Die Bits für den Farbwert eines Pixels können direkt aus den Bits des \hyperref[itval]{Iterationswerts} bestimmt werden.
\\

\chapter{Implementierung}
\label{implementierung}

Im Folgenden wird die genaue Implementierung dargestellt. Es folgt eine stichpunktartige Übersicht über die Funktionalität jedes Moduls, das zugehörige Schaltbild, die grafische Automatendarstellung und eine Prosa-Erklärung für das Verhalten des Automaten. Zur grafischen Darstellung ist anzumerken, dass die impliziten Eigenkanten in jedem Zustand zur Lesbarkeit  ausgespart wurden. Die Eigenkanten sorgen dafür, dass der aktuelle Zustand nicht gewechselt wird, sollte keines der dargestellten Übergangskriterien erfüllt sein. Ebenfalls ausgespart wurden alle Kanten, die von jedem Zustand in einen \glqq Resetzustand\grqq~ führen.\\ Die gezeigten Automaten wurden in \ac{VHDL} geschrieben, der zugehörige Code befindet sich im Anhang.

\section{Top-Modul}
\label{top}
Das Hardwaremodul \nameref{top} stellt das Herzstück der Implementierung dar. Unter seine Aufgaben fällt das
\begin{itemize}
	\item Verarbeiten der Ausgabe des \nameref{jstk}s
	\item Anpassen des aktuell sichtbaren Bildausschnitts
	\item Versorgen des \nameref{led}s mit gültigen Farb- und Koordinatenwerten
	\item Starten des \nameref{math}s
	\item Auswerten der Ergebnisse des \nameref{math}s 
\end{itemize}

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.66\textwidth]{topbb.pdf}
	\end{center}
	\caption{Das Schaltbild des \nameref{top}s}
\end{figure}

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.96\textwidth]{fsm1.pdf}
	\end{center}
	\caption{Der Automat des \nameref{top}s}
\end{figure}

\noindent \textbf{Verarbeiten der Ausgabe des \nameref{jstk}s}\\
Wenn sich der Automat des \nameref{top}s im Zustand \glqq idle\grqq~befindet, kann auf Signale des \nameref{jstk}s reagiert werden. Signalisiert der \nameref{jstk}, dass der Joystick in eine zum \ac{PCB} senkrechte Richtung bewegt wurde, so wird über die Zustände $move\_dir_i$ mit $dir \in \{up, down, left, right\}, i \in \{0, ..., 5\}$ der Wert der komplexen Zahl in der linken unteren Ecke des Displays angepasst.\\

\noindent \textbf{Anpassen des aktuell sichtbaren Bildausschnitts}\\
Da das Display eine Breite von 96 Pixeln hat, realisiert die Addition des 48-Fachen des Zoomfaktors (der jeweils einem Schritt von $\frac{1}{96}$ auf dem Display entspricht) auf den Realteil der komplexen Zahl in der unteren linken Ecke eine Verschiebung um 50\% nach rechts. Eine Verschiebung gleicher Größe nach links wird realisiert, indem das 48-Fache des Zoomfaktors von dem Realteil der komplexen Zahl in der unteren linken Ecke subtrahiert wird.\\
Da das Display eine Höhe von 64 Pixeln hat, genügt es, das 32-Fache des Zoomfaktors auf den Imaginärteil der komplexen Zahl in der unteren linken Ecke zu addieren oder von ihm zu subtrahieren, um den Bildausschnitt um 50\% nach oben oder unten zu bewegen.\\
Das Errechnen des 32-Fachen, beziehungsweise 48-Fachen, des Zoomfaktors übernimmt das Modul \glqq floating\_point\_multiply\grqq. Die darauffolgende Addition oder Subtraktion übernimmt das Modul \glqq floating\_point\_adder\grqq~beziehungsweise \glqq floating\_point\_subtractor\grqq. Aufgrund der Datenabhängigkeit ist eine Parallelisierung hier nicht möglich.\\
Der Zoomvorgang wird durch die Zustände $zoom_i$ mit $i \in \{0, ..., 8\}$ realisiert. Ein einfacher Zoom kann durch das Senken des Zoomfaktors umgesetzt werden. Dies entspricht einer kleineren Schrittweite zwischen den komplexen Zahlen für die der \hyperref[itval]{Iterationswert} berechnet wird. Um einen mittigen Zoom umzusetzen, muss auch der Wert der komplexen Zahl in der unteren linken Ecke des Displays angepasst werden. Diese Anpassung muss relativ zum aktuellen Zoomfaktor errechnet werden. Es wurde entschieden, den Zoomfaktor mit jedem Zoom zu halbieren. Der Realteil der komplexen Zahl in der unteren linken Ecke wird dabei um das 24-Fache des aktuellen Zoomfaktors erhöht, der Imaginärteil um das 16-Fache des aktuellen Zoomfaktors. Dies sorgt dafür, dass in die Mitte des Bildausschnitts gezoomt wird, also nach dem Zoom keine ungewollte Verschiebung entsteht.\\

\noindent \textbf{Versorgen des \nameref{led} mit gültigen Farb- und Koordinatenwerten}\\
Das \nameref{top} stellt insgesamt 5 Datenbusse für den \nameref{led} zur Verfügung. Die Farbwerte des aktuell errechneten Pixels werden über die jeweils 3 Bit breiten Datenbusse \glqq r\grqq, \glqq g\grqq~und \glqq b\grqq~übermittelt. Der 7 Bit breite Datenbus \glqq x\grqq~übermittelt Informationen über die aktuelle X-Koordinate. Der 6 Bit breite Datenbus \glqq y\grqq~über die Y-Koordinate.\\

\noindent \textbf{Starten des \nameref{math}s}\\
Startzustand des \nameref{top}s ist \glqq send\_re\grqq. Auf diesen folgen \glqq send\_im\grqq~und \glqq send\_zf\grqq. Diese 3 Zustände versorgen das \nameref{math} mit aktuellen Daten über den Wert der komplexen Zahl in der unteren linken Ecke des Displays. Um Leitungen zu sparen, werden die 3 Werte \glqq re\grqq, \glqq im\grqq~und \glqq zf\grqq~seriell über den Datenbus \glqq data\grqq~übertragen. Die Steuerleitungen \glqq re\_ready\grqq, \glqq re\_received\grqq, \glqq im\_ready\grqq, \glqq im\_received\grqq, \glqq zf\_ready\grqq~ und \glqq zf\_received\grqq~dienen dazu, die Daten kontrolliert zu übertragen. Anschließend wird dem \nameref{math} befohlen, ein neues Bild zu berechnen. Dazu dient die Steuerleitung \glqq run\grqq, auf die das \nameref{math} mit Starten der Berechnungen reagiert.\\
Sobald eine Eingabe über den Joystick gemacht wird, werden neue Werte für die komplexe Zahl in der linken unteren Ecke des Displays berechnet. Im Falle eines Zooms, wird auch der Zoomfaktor angepasst. Diese Vorgänge enden immer in dem Zustand \glqq send\_re\grqq, sodass nach Eingabe über den Joystick stets ein neues Bild berechnet wird.\\

\noindent \textbf{Auswerten der Ergebnisse des \nameref{math}s}\\
Das \nameref{math} reicht die Ergebnisse der komplexen \ac{ALU}s an das \nameref{top} weiter. Dies erfolgt über einen 23 Bit breiten Bus, dessen untere 10 Bits den \hyperref[itval]{Iterationswert} eines Pixels speichert. Die Nummer des Pixels wird in den oberen 13 Bit gespeichert. Die untersten 3 Bits des \hyperref[itval]{Iterationswertes} werden genutzt, um den Rotanteil des Bildpunktes zu bestimmen. Die 3 nächsten Bits bestimmen den Grünanteil und die nächsten 3 Bits den Blauanteil.

\section{Math-Modul}
\label{math}
Das Hardwaremodul \nameref{math} stellt die Verbindung zwischen dem \nameref{top} und den beliebig vielen komplexen \ac{ALU}s dar. Ihre konkreten Aufgaben sind das
\begin{itemize}
	\item Erhalten von dem Wert der komplexen Zahl in der aktuell unteren linken Ecke des Displays
	\item Berechnen der 6144 komplexen Zahlen im sichtbaren Ausschnitt der komplexen Ebene
	\item Aufteilen der 6144 zu berechnenden komplexen Zahlen auf beliebig viele \ac{ALU}s
	\item Versehen der Ergebnisse der \ac{ALU}s mit einer \ac{ID}
\end{itemize}

\vspace{2cm}
\begin{figure}[H]
	\begin{center}
		\includegraphics[width=\textwidth]{mathbb.pdf}
	\end{center}
	\caption{Das Schaltbild des \nameref{math}s}
\end{figure}

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=1.15\textwidth, center]{fsm2.pdf}
	\end{center}
	\caption{Der Automat des \nameref{math}s}
\end{figure}
\clearpage
\noindent \textbf{Erhalten von dem Wert der komplexen Zahl in der aktuell unteren linken Ecke des Displays}\\
Die Zustände \glqq receive\_re\grqq, \glqq fetch\_re\grqq, \glqq receive\_im\grqq, \glqq fetch\_im\grqq\, \glqq receive\_zf\grqq~und \glqq fetch\_zf\grqq~ dienen zum kontrollierten Empfangen der Information über den aktuellen Wert der komplexen Zahl in der unteren linken Ecke des Displays, sowie die Schrittweite zwischen jedem Pixel, dem Zoomfaktor.\\

\noindent \textbf{Berechnen der 6144 komplexen Zahlen im sichtbaren Ausschnitt der komplexen Ebene}\\
Da das Display 6144 Pixel hat, müssen 6144 korrespondierende komplexe Zahlen errechnet werden. Die erste komplexe Zahl befindet sich in der unteren linken Ecke. Die vom \nameref{top} übermittelten Daten sind für den ersten Pixel bereits gültig. Die nächsten 95 komplexen Zahlen werden durch Addition des Zoomfaktors auf den Realteil der jeweils aktuellen komplexen Zahl errechnet. Somit wird die unterste Zeile des Displays bearbeitet. Diese Berechnungen werden von den Zuständen \glqq calc\_next\_pixel\grqq, \glqq calc\_next\_pixel\_re\grqq, \glqq wait\_for\_re\_value\_ready\grqq~und \glqq fetch\_re\grqq~realisiert. Der nächste Pixel befindet sich in der vorletzten Zeile des Displays, in der Spalte ganz links. Um die komplexe Zahl für diesen Pixel zu errechnen, wird der ursprüngliche Realteil wiederhergestellt und der Zoomfaktor auf den Imaginärteil addiert. Somit wird ein \glqq line-break\grqq~umgesetzt. Dies übernehmen die Zustände \glqq calc\_next\_pixel\grqq, \glqq calc\_next\_pixel\_im\grqq, \glqq wait\_for\_im\_value\_ready\grqq~und \glqq fetch\_im\grqq.\\

\noindent \textbf{Aufteilen der 6144 zu berechnenden komplexen Zahlen auf beliebig viele \ac{ALU}s}\\
Die Zustände \glqq pixel\_ready\grqq~und \glqq run\_alu$_i$\grqq~sorgen dafür, dass untätige \ac{ALU}s mit Aufgaben versorgt werden, sobald eine komplexe Zahl zur Berechnung verfügbar ist. Ist eine \ac{ALU} fertig, so wird dies über die Steuerleitung \glqq done\_alu$_i$\grqq~signalisiert. Der Automat des \nameref{math}s wechselt dann in einen Zustand \glqq fetch\_alu$_i$\grqq, der das Ergebnis der \ac{ALU} holt und sichert. Der Zustand \glqq wait\_for\_alus\grqq~wird am Ende der Berechnung eines Bildes eingenommen. Er stellt die Ausnahme dar, dass nach dem Sichern des Ergebnisses der \ac{ALU} keine weiteren Aufträge erzeugt werden müssen. Von ihm aus gelangt das \nameref{math} wieder in den Ausgangszustand \glqq idle\grqq, in dem es auf neue Werte für die komplexe Zahl in der unteren linken Ecke des Displays wartet, um anschließend mit der Neuberechnung eines Bildes beginnen zu können.\\

\noindent \textbf{Versehen der Ergebnisse der \ac{ALU}s mit einer \ac{ID}}\\
Jeder Pixel, der berechnet wird, wird mit einer \ac{ID} versehen. Die \ac{ID} ist in diesem Fall die Nummer des berechneten Pixels. Dies dient später dazu, einem errechneten \hyperref[itval]{Iterationswert} einem Pixel zuzuordnen, sollten die \ac{ALU}s in unterschiedlicher Reihenfolge ihre Berechnung beenden und ihr Ergebnis ausgeben.\\
\clearpage
\section{Komplexe-\ac{ALU}}
\label{complex}
Die komplexe \ac{ALU} (im Folgenden z.T. auch nur \glqq \ac{ALU}\grqq) iteriert die \hyperref[mf]{Mandelbrotsche Formel} auf einer gegebenen komplexen Zahl $c$. Sie gibt einen \hyperref[itval]{Iterationswert} für $c$ zurück. Die \hyperref[itval]{Iterationswerte} liegen im Intervall [0, 999] wobei die 0 einen konvergierenden Pixel beschreibt.\\

Unter ihre genauen Aufgaben fällt das
\begin{itemize}
	\item Erhalten einer komplexen Zahl
	\item Iterieren, bis entweder Konvergenz oder Divergenz festgestellt wird
	\item Zurückgeben eines \hyperref[itval]{Iterationswertes}
\end{itemize}

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=\textwidth]{complexbb.pdf}
	\end{center}
	\caption{Das Schaltbild der komplexen \ac{ALU}}
\end{figure}

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=1.2\textwidth, center]{fsm3.pdf}
	\end{center}
	\caption{Der Automat der komplexen \ac{ALU}}
\end{figure}
\clearpage

\noindent \textbf{Erhalten einer komplexen Zahl}\\
Im Gegensatz zum \nameref{math} erhält die \nameref{complex} die Werte der komplexen Zahl parallel. Es werden 2 64-Bit Leitungen genutzt, um die Daten zu übertragen. Daher reicht es aus, einen einzigen Zustand \glqq init\grqq~zur kontrollierten Übertragung zu nutzen. Die erhaltenen Werte werden in Registern \glqq z0\_re\grqq~und \glqq z0\_im\grqq~gespeichert.\\

\noindent \textbf{Iterieren}\\
Das Itertieren auf einer komplexen Zahl $c$ wird von den Zuständen \glqq c\_iterate\grqq, \glqq c\_calc$_i$\grqq~mit $i \in \{0, ..., 12\}$ durchgeführt. Zu den nötigen Berechnungen gehören das Quadrieren von $c$, das anschließende Addieren der Konstanten $c$ auf sein Quadrat, das Ermitteln des Betrages von $c$ und das Prüfen, ob $\left|c\right|$ der Wert  $absValueMax$ überschritten wurde.

In den Zuständen \glqq c\_calc0\grqq, \glqq c\_calc1\grqq~und \glqq c\_calc2\grqq~wird das Quadrat des Real- und Imaginärteils mit den beiden Multiplizierern parallel berechnet. Die Ergebnisse $re^2$ und $im^2$ werden in Signalen $z\_re\_s$ und $z\_im\_s$ gespeichert.

Die Zustände \glqq c\_calc3\grqq, \glqq c\_calc4\grqq~und \glqq c\_calc5\grqq~ berechnen parallel $re^2 + im^2$, $re^2 - im^2$ und $2 \cdot re$ mit Hilfe des Addierers, des Subtraktors und des Multiplizierers. Die Summe $re^2 + im^2$ ist das Quadrat des Betrages. Es gilt $re^2 + im^2 = \left| c \right|^2$. Dieses Ergebnis wird in einem Signal $z\_absolute$ gespeichert. Die Differenz $re^2 - im^2$ ist der Realteil von $c^+$, allerdings muss noch der Realteil von $c$ addiert werden. Die Differenz wird in einem Signal $zp\_re$ zwischengespeichert. Die Multiplikation $2 \cdot re$ ist das erste Produkt der Rechnung $2 \cdot re \cdot im$, was die erste Rechnung für den Imaginärteil von $c^+$ darstellt. Dieses Ergebnis wird in einem Signal $zp\_im$ zwischengespeichert.

Die Zustände \glqq c\_calc6\grqq, \glqq c\_calc7\grqq~und \glqq c\_calc8\grqq~berechnen parallel $(2 \cdot re) \cdot im$, $z\_absolute - 4$ und $re + zp\_re$. Das Produkt $(2 \cdot re) \cdot im$ entspricht dem Imaginärteil von $c^+$, allerdings muss auch hier noch der Imaginärteil von $c$ addiert werden. Das Ergebnis wird in $zp\_im$ zwischengespeichert und überschreibt dort den alten Wert $2 \cdot re$. Um zu prüfen, ob $absValueMax$ überschritten wurde, wird $z\_absolute - absValueMax^2$ gerechnet und überprüft, ob das Ergebnis positiv ist. Um einen weiteren \ac{IP-Core} für die Berechnung einer Wurzel einer Gleitkommazahl zu sparen, wurde entschieden, nicht $\sqrt{z\_absolute}$ auszurechnen und mit $absValueMax$ zu vergleichen, sondern $z\_absolute = \left| c\right|^2$ mit $absValueMax^2$ zu vergleichen. So kommt die Subtraktion von $absValueMax^2 = 2^2 = 4$ zustande. Um einen Kompatarator-\ac{IP-Core} zu sparen, wird das Vorzeichen der Differenz als ausschlaggebend betrachtet. Gilt $\left|c\right|^2 - absValueMax^2 > 0$, so liegt $c$ nicht in der Mandelbrotmenge. Der Automat wechselt dann in einen Zustand \glqq c\_diverge\grqq. Die Summe $re + zp\_re$ stellt den fertig berechneten Realteil der komplexen Zahl $c^+$ dar.

Die Zustände \glqq c\_calc9\grqq, \glqq c\_calc10\grqq~und \glqq c\_calc11\grqq~berechnen den Imaginärteil von $c^+$. Der fertig berechnete Imaginärteil wird im Register $zp\_im$ abgelegt.

Zustand \glqq c\_calc12 \grqq~implementiert die Erkennung von Konvergenz. Die genaue Realisierung ist im nächsten Punkt erläutert. Folgezustand ist \glqq c\_converge\grqq. Lag kein hinreichendes Kriterium für Konvergenz vor, so wird der \hyperref[itval]{Iterationswert} erhöht, die inaktuellen Werte für $z\_re$ und $z\_im$ werden mit $z^+\_re$ und $z^+\_im$ überschrieben und Folgezustand ist \glqq c\_iterate\grqq. In \glqq c\_iterate \grqq~wird der aktuelle \hyperref[itval]{Iterationswert} mit $iterationMax$ verglichen. Sollte die Obergrenze $iterationMax$ erreicht worden sein, so wechselt der Automat in Zustand \glqq c\_converge \grqq. Andernfalls wird der komplette Zyklus erneut durchlaufen.\\

\noindent \textbf{Erkennen von Konvergenz}\\
Das Erkennen von Konvergenz gestaltet sich komplizierter als das Erkennen von Divergenz. Hierzu reicht nicht eine einfache Subtraktion, es müssen 3 verschiedene Fälle abgedeckt werden:
\begin{itemize}
	\item Die komplexe Zahl hat unter Iteration ihren Konvergenzwert erreicht
	\item Die komplexe Zahl gerät unter Iteration in einen Zyklus
	\item Der \hyperref[itval]{Iterationswert} $iterationMax$ wurde überschritten.
\end{itemize}

Tritt der erste Fall ein, so ist $c^+ = c$. Im Zustand \glqq c\_calc\_12\grqq~wird überprüft, ob die Werte für $re$ und $im$ mit den Ergebnissen der Iteration $zp\_re$ und $zp\_im$ übereinstimmen. Ist dies der Fall, so ist Konvergenz garantiert. Beispiele, wie der Ursprung der komplexen Ebene (0+0 $\cdot\ i$) werden somit in nur einer Iteration als konvergierend gezeigt. In diesem Fall werden also 999 Iterationen gespart.\\
Den zweiten Fall zu prüfen stellt sich schwieriger dar. Um garantiert zu erkennen, ob eine komplexe Zahl $c$ unter Iteration der \hyperref[mf]{Mandelbrotschen Formel} in einen Zyklus gerät, müsste man jede komplexe Zahl $c_{i-1}$ bis zur aktuellen Iteration $i$ abspeichern und überprüfen, ob in den $i-1$ Iterationen zuvor dieser Wert für $c$ bereits errechnet wurde. In Programmiersprachen wie Java wäre dies mit Hilfe der Datenstruktur \glqq Sets\grqq \cite{J9} schnell implementiert. Eine solche Umsetzung ist in \ac{VHDL} nicht ohne Weiteres möglich. Daher werden bloß die Realteile der letzten 10 errechneten komplexen Zahlen gespeichert, um Zyklen bis zur Größe von 10 zu erkennen. Dazu dienen die Signale $l_i$ mit $i \in \{0, ..., 9\}$. Im Zustand \glqq c\_calc\_0\grqq~wird der Wert von l9 mit dem Wert von l8 überschrieben. In den Folgezuständen \glqq c\_calc\_1\grqq~bis \glqq c\_calc\_9\grqq~passiert diese Verschiebung mit den restlichen Signalen. Somit steht in jeder Iteration im Zustand \glqq c\_calc\_12\grqq~der Realteil der letzten 10 komplexen Zahlen zum Vergleichen zu Verfügung. Sollte der neu errechnete Realteil mit einem der Werte von $l_i$ mit $i \in \{0, ..., 9\}$ übereinstimmen, so ist der Folgezustand \glqq c\_converge\grqq.
\\

\noindent \textbf{Zurückgeben eines \hyperref[itval]{Iterationswertes}}\\
Der \hyperref[itval]{Iterationswert} wird über das Signal \glqq iteration\_out\grqq~an das \nameref{math} ausgegeben. Dieser Bus hat eine Breite von 10 Bit. Diese Breite ergibt sich nach folgender Gleichung durch Einsetzen des Wertes 1.000 für $iterationMax$: $$Datenbusbreite = \lceil log_2(iterationMax)\rceil = \lceil log_2(1000)\rceil = \lceil 9,965784...\rceil = 10$$
 Im Zustand \glqq c\_converge\grqq~wird ein 10-Bit Nullvektor auf den Bus gelegt. Dies zeigt an, dass die komplexe Zahl in der Mandelbrotmenge liegt und führt dazu, dass der Pixel an dieser Stelle schwarz bleibt.\\ Im Zustand \glqq c\_diverge\grqq~wird der aktuelle \hyperref[itval]{Iterationswert} in binär auf den Ausgabebus \glqq iteration\_out\grqq~gelegt. Die weitere Verarbeitung dieser Daten übernimmt dann das \nameref{math}.


\section{Joystick-Controller}
\label{jstk}
Das Hardwaremodul \nameref{jstk} implementiert den Treiber für den \ac{Pmod} Joystick. Das Drücken des Joysticks bis zum Anschlag in eine zum \ac{PCB} senkrechte Richtung signalisiert dem \nameref{top}, eine neue komplexe Zahl dem unteren linken Bildpunkt zuzuweisen. Somit kann durch die Mandelbrotmenge navigiert werden. Auch das Betätigen des Zoomes wird durch dieses Modul dem \nameref{top} signalisiert.
Der \nameref{jstk} wurde weitestgehend der Xilinx Demo File \cite{pmodjstk} entnommen und leicht angepasst, sodass der Joystick für diese Anwendung geeignet genutzt werden kann.\\

\section{LED-Controller}
\label{led}
Das Hardwaremodul \nameref{led} implementiert den Treiber für das \ac{Pmod} \ac{LED} Display. Es nimmt eine X-Koordinate aus dem Intervall [0,95] vom Datenbus \glqq x\grqq, sowie eine Y-Koordinate aus dem Intervall [0,63] vom Datenbus \glqq y\grqq~des \nameref{top}s entgegen. Die Farbwerte für die Pixel liegen auf den jeweils 3-Bit breiten Datenbussen \glqq r\grqq, \glqq g\grqq~und \glqq b\grqq~des \nameref{top}s.\\
Eine lauffähige Implementierung dieses Moduls war im Zeitrahmen der Bachelorarbeit leider nicht erfolgreich.

\section{Hierarchie}

Den Abbildungen ist die Hierarchie der Module zu entnehmen. Hierbei sind die grau gezeichneten Leitungen für die abgebildete Hierarchie irrelevant. Sie enden in der Logik der Automaten oder dienen zur Kommunikation und Datenübertragung zwischen den Modulen.

\begin{figure}[h]
	\begin{center}
	\includegraphics[width=0.8\textwidth]{top.pdf}
	\end{center}
	\caption{Die Hierarchie der Top-Level Ebene}
\end{figure}

Das \nameref{top} verbindet alle anderen Module miteinander und stellt damit die höchste Ebene dar. Ihre Ein- und Ausgänge werden direkt auf die Pins des Boards gelegt. Das Clock-Signal kommt vom Quarz des Boards und endet in einem \ac{IP-Core} \glqq Clocking-Wizard\grqq. Er erzeugt ein sauberes und kontrollierbares Clock-Signal, das alle weiteren Module versorgt. Die Frequenz von 100 \ac{MHz} bleibt erhalten. Der Joystick Controller erhält über die \ac{SPI} Schnittstelle \glqq miso\_jstk\grqq~ Informationen vom Joystick, der über den \ac{Pmod} Anschluss \glqq JA\grqq~ angeschlossen ist.\\Der \nameref{led} versorgt das \ac{LED} Display, das über den \ac{Pmod}-Port \glqq JC\grqq~angeschlossen wird.\\Die Module \glqq floating\_point\_adder\grqq, \glqq floating\_point\_subtractor\grqq~und \glqq floating\_point\_multiply\grqq~dienen dazu, den Wert der komplexen Zahl in der unteren linken Ecke des Displays, sowie den Zoomfaktor anzupassen. Je nach dem, ob nach rechts, links, oben oder unten navigiert wurde, oder ob gezoomt werden soll.

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.8\textwidth]{math.pdf}
	\end{center}
	\caption{Die Hierarchie des \nameref{math}s}
\end{figure}

Das \nameref{math} besitzt einen \glqq floating\_point\_adder\grqq, um den Zoomfaktor auf den Wert komplexer Zahlen zu addieren. Darüber hinaus steuert es beliebig viele \nameref{complex}s. Für jede \nameref{complex} werden Signale benötigt, die sie mit Informationen über die komplexe Zahl (aufgeteilt auf die beiden Datenbusse \glqq re\grqq~und \glqq im\grqq), auf der zu iterieren ist, versorgt. Die Leitungen \glqq received\grqq, \glqq idle\grqq~und \glqq done\grqq~dienen zur Kommunikation zwischen den \nameref{complex}s und dem \nameref{math}.

\chapter{Ergebnisse}

Im Folgenden werden die Ergebnisse der Implementierung präsentiert. Es wird einzeln auf die in \ref{ziele} definierten Ziele eingegangen.

\section{Der Hardwareentwurf}
Es wurde erfolgreich ein \ac{VHDL}-Entwurf für \ac{FPGA}s entwickelt, der ohne Fehler synthetisiert, implementiert und in das \ac{FPGA} geladen werden kann. Die Synthese entfernt bei der Optimierung einige Register, was zu ungewolltem Verhalten führen kann. Das Fortbestehen der Korrektheit des Entwurfs festzustellen, war zeitlich nicht möglich. Die Synthese, die Optimierung und die Implementierung, gefolgt vom Schreiben des Bitstreams eines Designs mit nur einer einzigen \ac{ALU}, dauern in der genutzten Version von Vivado insgesamt rund 13 Minuten. Für jede kleine Änderung am Code fällt dieser gesamte Prozess erneut an und benötigt für jede hinzukommende \ac{ALU} noch mehr Zeit.\\
Gemäß der Simulation kann der Hardwareentwurf auf einem Ausschnitt der komplexen Ebene die \hyperref[mf]{Mandelbrotsche Formel} iterieren und dazu ein farbiges Bild der Mandelbrotmenge ausrechnen. Das Anpassen des Bildausschnitts wurde erfolgreich implementiert und verläuft wie erwartet. Das stellt das Erkunden der Mandelbrotmenge sicher.

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.3\textwidth]{8alusimp.png}
	\end{center}
	\caption[8 ALUs auf dem Artix-7]{Der Hardwareentwurf mit 8 \ac{ALU}s auf dem Artix-7. Hellblau entspricht belegten Logikzellen, dunkelblau ist frei. 95\% der \ac{DSP}s werden genutzt.}
\end{figure}

\section{Joystick und Display}
Die Kommunikation mit dem Joystick wird erfolgreich vom \nameref{jstk} implementiert. Die Eingabe kann vom \nameref{top} verarbeitet werden und führt in der Simulation zu einem Anpassen des aktuell sichtbaren Ausschnitts der komplexen Ebene. Auf der Hardware werden die vier \ac{LED}s rechts genutzt, um korrekt verarbeitete Eingaben aufzuzeigen (Siehe Abbildung \ref{hwjstk} - Drücken nach rechts lässt die \ac{LED} ganz rechts aufleuchten).\\
Die Implementierung des \nameref{led}s war leider nicht erfolgreich. Das Einlesen in den über \ac{SPI} gesteuerten Solomon Systech SSD1331 Display Controller \cite{Dig3}, sowie das anschließend erfolgreiche Ansprechen des Displays war im Zeitrahmen der Bachelorarbeit nicht möglich. 

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=300px]{hw.png}
	\end{center}
	\caption[Display und Joystick am FPGA]{Der Joystick ließ sich erfolgreich als Eingabegerät einbinden. Das Display bleibt leider dunkel.}
	\label{hwjstk}
\end{figure}

\section{Beurteilung der Parallelisierungseffizienz}

Auf dem \ac{FPGA} ist es aufgrund der praktisch beschränkten Anzahl der konfigurierbaren Hardwarebausteine nicht möglich, mehr als 8 \nameref{complex}s unterzubringen (Siehe Anhang, \ref{16alusfail}). Das Fortbestehen der Korrektheit war im Zeitrahmen der Arbeit nicht möglich, weshalb eine Zeitmessung am Board nicht sinnvoll ist. Damit dennoch ein möglichst aussagekräftiges Urteil über Effizienz der Parallelisierung zustande kommt, werden die Simulationsergebnisse betrachtet. Dort besteht theoretisch keine Obergrenze für die Anzahl der parallel arbeitenden \ac{ALU}s, was gegenüber der Implementierung auf der Hardware ein großer Vorteil ist. Ebenfalls besteht die Möglichkeit, bis auf Nanosekunden genau die Zeit des theoretischen Ablaufes zu messen. Die Simulationsergebnisse stellen daher eine konstruktive Alternative da, um die Effizienz der Parallelisierung abschätzen zu können.\\

Spalte 1 der Tabelle \ref{erg_table} gibt Auskunft über die Anzahl der implementierten \ac{ALU}s in der jeweiligen Simulation.\\
Spalte 2 zeigt die in der Simulation vergangene Zeit, die es gedauert hat, bis alle 6144 Pixel des Bildes fertig berechnet wurden.\\
Der Speed-Up Faktor steht in Spalte 3. Die Zeit, die in der Simulation mit nur einer \ac{ALU} vergangen ist, wird als Referenzwert genommen. Damit steht jedes parallelisierte Ergebnis dem rein sequenziell berechnetem Ergebnis gegenüber.\\
In Spalte 4 steht die Größe der .wdb Datei. Dies ist die Datei, die das Simulationstool anlegt und dort Informationen über die laufende Simulation ablegt. Je länger eine Simulation läuft, desto größer wieder diese Datei.\\
Die letzte Spalte gibt Information über die in der Realität vergangene Zeit, die die Simulation lief. \\

\begin{table}[h]
	\begin{center}
		\begin{tabular}{|c||c|c|c|c|} \hline
			\textbf{\ac{ALU}s}& \textbf{Simulationszeit} & \textbf{Speed-Up Faktor}  & \textbf{Größe der .wdb Datei} & \textbf{Rechenzeit}\\ \hline
			1&2,980427328 s&100,0000\% & 925.129.378.000 Bytes& 87h 14m 59s\\ \hline
			2&1,499020169 s&198,8825\%&500.163.076.000 Bytes& 39h 33m 52s\\ \hline 
			4&0,749917795 s&397,9743\%&265.453.892.000 Bytes& 20h 19m 45s\\ \hline
			8&0,3789402895 s&786,8651\%&132.201.554.000 Bytes& 12h 42m 21s\\ \hline
			16&0,195372699 s&1525,5086\%&72.444.012.000 Bytes&7h 32m 02s\\ \hline
			32&0,992802226 s&3002,0353\%&51.261.537.000 Bytes&4h 01m 29s\\ \hline
			64&0,051410618 s&5797,2991\%&44.927.012.000 Bytes&3h 04m 51s\\ \hline
			128&0,027015148 s&11032,4301\%&41.329.587.000 Bytes&2h 44m 52s\\ \hline
		\end{tabular}
		\caption{Ergebnisse der Simulation}		
		\label{erg_table}
	\end{center}
\end{table}

Eine Exponenten-Regression über den Speed-Up Faktor ergibt folgende Funktion:
$$Speed Up Faktor \approx 102.1063968 \cdot AnzahlALUs^{0.9710699028}$$
Aus dem Exponenten der obigen Funktion lässt sich herauslesen, wie effizient die Hinzunahme einer weiteren komplexen \ac{ALU} ist. Ein Exponent von 1 bedeutet maximale Effizienz: jede weitere \nameref{complex}, addiert ihre komplette Rechenkraft zur bestehenden Gesamtrechenkraft hinzu. Der hier ermittelte Exponent lässt sich also als Effizienzfaktor bezeichnen und zeigt eine überraschend gute Effizienz bei Hinzunahme einer weiteren \ac{ALU}. Tabelle \ref{reg_table} zeigt, dass der Funktionswert der Regression bis 64 \ac{ALU}s leicht unterschätzend ist. Das heißt, dass der Effizienzfaktor bis dorthin noch größer als der obig ermittelte Wert ist. Bei 128 \ac{ALU}s ist der Regressionswert jedoch deutlich überschätzend, was vermuten lässt, dass ab dann die Effizienz jeder weiteren \ac{ALU} sinkt. Es ist zu erwarten, dass spätestens ab 6144 \ac{ALU}s der Effizienzfaktor sehr schnell gegen 0 geht, da jede weitere \nameref{complex} keine Bildpunkte zum Berechnen zugeteilt bekommen kann, demnach im Ruhezustand bleibt und schließlich die Berechnung nicht weiter beschleunigt.

\subsection{Bottleneck \nameref{math}}

Die Frage, ob die hier vorgestellte Implementierung \glqq embarrassingly parallel\grqq~ist, lässt sich im Hinblick auf das \nameref{math} leicht beantworten. Der Lösungsweg eines Problems wird als \glqq embarrassingly parallel\grqq~bezeichnet, wenn der Effizienzfaktor 1 ist. Durch jede weitere parallel ausgeführte Rechnung muss sich also die hinzukommende Rechenleistung zur bereits bestehenden Gesamtrechenleistung hinzu addieren. Der entstehende Aufwand, das Problem in ein weiteres Teilproblem aufzuteilen, das parallel gelöst werden kann, ist also gegenüber der hinzukommenden Rechenleistung zu vernachlässigen. Dies ist meist dann der Fall, wenn jede Rechnung, sowie jedes Ergebnis dieser Rechnungen in keine Abhängigkeit zueinander stehen und untereinander keine Kommunikation benötigen. Wie Tabelle \ref{reg_table} und der errechnete Effizienzfaktor zeigen, ist dies in dieser Implementierung nicht der Fall. Dies liegt am Design des \nameref{math}s, das die \ac{ALU}s steuert.\\
Das \nameref{math} ist so implementiert, dass das Holen und Sichern der Ergebnisse fertiger \ac{ALU}s höher priorisiert ist, als das Starten untätiger \ac{ALU}s. In den Simulationen ist gut zu sehen, dass höchstens 5 \ac{ALU}s gestartet werden, wenn alle laufenden \ac{ALU}s nach genau einer Iteration bereits Divergenz festgestellt haben. Dies passiert zum Beispiel in den untersten 3 Zeilen in Abbildung \ref{simpic}. Erst wenn ein Bereich der Mandelbrotmenge berechnet wird, in dem die komplexen Zahlen höhere \hyperref[itval]{Iterationswerte}, werden mehrere \ac{ALU}s gestartet. Eine solche Engstelle, die die Effektivität potentieller Rechenleistung hemmt, wird \glqq Bottleneck\grqq~genannt. Der hier vorliegende \glqq Bottleneck\grqq~kommt zustande, da das Starten einer \ac{ALU}, sowie das Holen und Sichern ihrer Ergebnisse nur sequenziell ausgeführt werden kann und eine Zeitspanne $t > 0s$ dauert.\\
Durch Änderungen am Code ist es möglich, das Starten einer untätigen \ac{ALU} höher zu priorisieren. Ob dies das Problem des \glqq Bottlenecks\grqq~lindern oder fördern würde, oder ob es den \glqq Bottleneck\grqq~bloß verschieben würde, wäre zu prüfen.

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=230px]{graph.png}
	\end{center}
	\caption{Graph der exponentiellen Regression}
\end{figure}


\begin{table}[H]
	\begin{center}
		\begin{tabular}{|c|c|c|c|c|} \hline
			\textbf{\ac{ALU}s}& \textbf{Speed-Up Faktor} & \textbf{Regressionswert}  &  \textbf{Fehler}&\textbf{Fehler im Durchschnitt}\\ \hline
			1&100\%&102,1063968&2,106396819&2,106396819\\ \hline
			2&198,8825\%&200,1585377&2,158537677&2,132467248\\ \hline
			4&397,9743\%&392,3695425&-4,630457512&-0,121841053\\ \hline
			8&786,8651\%&769,1595855&-16,84041451&-4,3014843815\\ \hline
			16&1525,5086\%&1507,778775&-17,22122543&-6,8854325912\\ \hline
			32&3002,0353\%&2955,689399&-46,31060091&-13,4562939776\\ \hline
			64&5797,2991\%&5794,0196348&-2,980365783&-11,959732807 \\ \hline
			128&11032,4301\%&11357,98083&325,9808257&30,282837006375\\ \hline
		\end{tabular}
		\caption{Exponenten-Regression über den Speed-Up Faktor}
		\label{reg_table}		
	\end{center}
\end{table}

Tabelle \ref{reg_table} stellt die tatsächlichen Werte des Speed-Up Faktors mit denen der Regression gegenüber. 
In Spalte 3 wird der Wert der Regressionsfunktion für die Anzahl der \ac{ALU}s aus jeder Zeile aufgelistet. Die Werte in Spalte 4 werden errechnet, indem der tatsächliche Speed-Up Faktor vom zugehörigen Regressionswert abgezogen wird. Dadurch wird ersichtlich, ob die Regressionsfunktion den tatsächlichen Speed-Up Faktor über- oder unterschätzt. Ein negativer Wert bedeutet, dass der tatsächliche Speed-Up Faktor besser ist, als die Regressionsfunktion angibt. Ein positiver Wert bedeutet, dass der tatsächliche Wert schlechter als der durch die Regressionsfunktion angegebene Wert ist. Die letzte Spalte zeigt die durchschnittliche Abweichung von dem Wert der Regression zum tatsächlichen Speed-Up Faktor. Je näher die durchschnittliche Abweichung an der 0 ist, desto höher ist die Güte der Regressionsfunktion anzusehen.\\
Hier ist gut zu erkennen, dass ab 128 komplexen \ac{ALU}s der Wert der Regressionsfunktion stark überschätzt (um rund 3\%). Dies lässt vermuten, dass ab dieser Anzahl von \ac{ALU}s die Effizienz jeder weiteren hinzuzunehmenden \ac{ALU} deutlich nachlässt.\\

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=96px]{pic.png}
	\end{center}
	\caption[Das in der Simulation berechnete Bild]{Das in der Simulation berechnete Bild (Originalgröße)}
	\label{simpic}
\end{figure}

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=96px]{man2.png}
		\includegraphics[width=96px]{man3.png}
		\includegraphics[width=96px]{man4.png}
		\caption[Weitere Bilder]{Beispielhafte Erkundung der Mandelbrotmenge. Das linke Bild wird erzeugt, wenn vom Startpunkt aus (siehe \ref{simpic}) 2 mal gezoomt wird. Das mittlere Bild ist zu sehen, wenn danach 2 mal nach links navigiert wird. Weiteres 3-maliges Zoomen und 2-maliges Navigieren nach links lässt das rechte Bild entstehen.}
	\end{center}
\end{figure}


\chapter{Zusammenfassung und Ausblick}

In diesem Kapitel wird zusammengefasst, welche der gesetzten Ziele im Rahmen der Bachelorarbeit erreicht wurden, zu welchen weiterführenden Projekten diese Arbeit dienen kann, wie sie erweitert und verbessert werden kann, sowie zu was sie genutzt werden kann.

\section{Was war erfolgreich?}

Die Brücke zwischen den in Kapitel \ref{motivation} (\nameref{motivation}) vorgestellten Modulen des Bachelorstudiengangs Informatik der Goethe Universität Frankfurt am Main konnte erfolgreich geschaffen werden.\\
Die gelehrte Theorie der komplexen Zahlen konnte mit der praktischen Anwendung der \ac{FPGA}s verbunden werden. Durch den Hardwareentwurf, der grundlegende arithmetische Berechnungen mit komplexen Zahlen, sowie das Iterieren der \hyperref[mf]{Mandelbrotschen Formel} auf einer komplexen Zahl beherrscht, wird der gelehrte Inhalt der Veranstaltung \glqq Mathe für die Informatik 1: Analysis und lineare Algebra\grqq~durch praktische Anwendung greifbarer.\\
Die Parallelisierung zeigte eine überraschend gute Skalierbarkeit mit bis zu 128 parallel arbeitenden komplexen \ac{ALU}s.\\
Der Joystick wurde erfolgreich in den Hardwareentwurf eingebunden, seine Funktionalität auf der Hardware konnte über die Ausgabe per \ac{LED}s gezeigt werden.

\section{Wie kann aufbauend verfahren werden?}

Um die Darstellung der Mandelbrotmenge visuell auszugeben, bedarf es noch der Implementierung des \nameref{led}s. Dies würde zugleich zeigen, ob die Korrektheit der Implementierung auf der Hardware weiterhin besteht.

\section{Mögliche Anwendungszwecke der Arbeit}

Der vorgestellte Entwurf kann in der Veranstaltung \glqq Mathe für die Informatik 1: Analysis und lineare Algebra\grqq~genutzt werden, um dem gelehrten theoretischen Wissen über komplexe Zahlen eine praktische Anwendung zu verleihen. Der von Studenten anfangs womöglich schwer aufzufassende Inhalt erhält dadurch eine grafische, leicht begreifbare Anwendung über den visuellen Lernkanal.\\
Das \nameref{math} kann jede Art von \ac{ALU} betreiben, die eine passende Schnittstelle hat. Daher besteht die Möglichkeit, auch andere mathematische grafisch darstellbare Objekte parallel zu berechnen. Auch die Umsetzung einer parallel rechnenden Grafik-Engine ist umsetzbar.\\
Durch Anpassung einiger Werte im \nameref{math} lässt sich auch die Bildfläche von größeren Displays berechnen.

\chapter{Anhang}

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=200px]{16alusfail.png}
	\end{center}
	\caption[Place-Design mit 16 ALUs nicht möglich]{16 \ac{ALU}s lassen sich nicht auf dem Artix-7 \ac{FPGA} unterbringen.}
	\label{16alusfail}
\end{figure}
Diese Fehlermeldung wird von Vivado erzeugt, wenn versucht wird den Entwurf mit 16 \ac{ALU}s auf dem Board unterzubringen. Die theoretisch unbegrenzte Anzahl der parallel rechnenden \ac{ALU}s ist durch die praktisch begrenzte Anzahl der konfigurierbaren Logikzellen im \ac{FPGA} in der Realität eingeschränkt. \\



\begin{figure}[H]
	\begin{center}
		\includegraphics[width=300px]{2alus.png}
	\end{center}
	\caption{Entwurf mit 2 \ac{ALU}s in der Simbox}
	\label{sim2}
\end{figure}

Abbildung \ref{sim2} zeigt die beendete Simulation eines Entwurfes mit 2 parallel rechnenden \ac{ALU}s. Gut zu sehen ist, dass die komplexen Zahlen, die unter Iteration der \hyperref[mf]{Mandelbrotschen Formel} konvergieren, besonders lange Berechnungszeiten haben. Die komplexen Zahlen in Zeile 32 haben einen Imaginärteil von 0. Für alle komplexen Zahlen mit diesem Imaginärteil, die einen Realteil zwischen -2 und 0,25 haben, konvergiert die komplexe Zahl. Daher konvergieren rund die Hälfte aller Bildpunkte in Zeile 32, was zu dem großen Anteil der Rechenzeit führt.\\

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=300px]{4alus.png}
	\end{center}
	\caption{Entwurf mit 4 \ac{ALU}s in der Simulation}
	\label{sim3}
\end{figure}

Abbildung \ref{sim3} zeigt die beendete Simulation eines Entwurfes mit 4 parallel rechnenden \ac{ALU}s.
Oben im gelben Kästchen steht die vergangene Simulationszeit an der Stelle des Cursors, der zeitlich dort befindet, wo der letzte Pixel des Bildes fertig berechnet wurde. Im nächsten Takt wechselt das \nameref{math} in den Zustand \glqq idle\grqq~und zieht das Signal \glqq picture\_done\grqq auf logisch 1.\\

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=300px]{8alussim.png}
	\end{center}
	\caption{Entwurf mit 8 \ac{ALU}s in der Simulation}
	\label{sim1}
\end{figure}


Abbildung \ref{sim1} zeigt die beendete Simulation eines Entwurfes mit 8 parallel rechnenden \ac{ALU}s. Gut zu sehen ist, dass die \ac{ALU}s ihre Bildpunkte zu unterschiedlichen Zeitpunkten fertig berechnet haben. Die Reihenfolge der fertigen Bildpunkte weist also mit steigender Anzahl der parallel rechnenden \ac{ALU}s eine abnehmende Ordnung auf. Das liegt daran, dass kurze Bildbereiche - angenommen 5 Pixel breit - komplexe Zahlen enthalten, die unter Iteration der \hyperref[mf]{Mandelbrotschen Formel} konvergieren. Diese 5 Pixel werden dann von den ersten 5 freien \ac{ALU}s übernommen, während die restlichen \ac{ALU}s die Zeile des Bildes zu Ende rechen und mit der nächsten Zeile fortsetzen. Dies führt dazu, dass die grünen Blöcke in der Simulationsdarstellung wachsen. Ein grüner Block wird vom Simulationsprogramm dann erzeugt, wenn bei aktueller Auflösung der Simulationszeit die Information eines Signales zu kurz stabil war, als dass sein Wert genügend Pixel zum Anzeigen bekäme.
\\


\begin{figure}[H]
	\begin{center}
		\includegraphics[width=300px]{1alusim.png}
	\end{center}
	\caption{Entwurf mit einer \nameref{complex} in der Simulation}
	\label{sim0}
\end{figure}

Abbildung \ref{sim0} zeigt einen Ausschnitt der Simulation eines Entwurfes mit nur einer einzigen \ac{ALU}. Das Bild wird rein sequenziell berechnet, weshalb der Wert des Signales \glqq y\grqq~ aufsteigend sortiert ist.

Die anderen Simulationen sehen den gezeigten Screenshots sehr ähnlich und werden daher nicht gezeigt.\\

\noindent Der Quellcode, die Vivado Projektdateien und ein Video zur Simulation sind auf der DVD hinterlegt. 

\bibliographystyle{IEEEtran}
\bibliography{references}

\end{document}