From 4b692f7adc5436638a922691bd953557937e7824 Mon Sep 17 00:00:00 2001 From: Emile Date: Sat, 23 Feb 2019 02:12:08 +0100 Subject: :memo: updated stuff making it easier for new readers to grasp the main concepts --- .main.tex.swp | Bin 12288 -> 12288 bytes docs/.container.tex.swp | Bin 36864 -> 40960 bytes docs/.ergebnisse.tex.swp | Bin 12288 -> 36864 bytes docs/.generieren.tex.swp | Bin 0 -> 28672 bytes docs/.netzwerk.tex.swp | Bin 12288 -> 12288 bytes docs/.simulieren.tex.swp | Bin 16384 -> 40960 bytes docs/100tree.pdf | Bin 0 -> 44503 bytes docs/container.tex | 34 +++++++++---- docs/danksagung.tex | 1 - docs/ergebnisse.tex | 17 ++++--- docs/generieren.tex | 126 +++++++++++++++++++++++++---------------------- docs/netzwerk.tex | 4 +- docs/quellen.tex | 18 +++++++ docs/simulieren.tex | 88 +++++++++++++++++---------------- docs/tree5.pdf | Bin 0 -> 330745 bytes docs/vorgehensweise.tex | 7 ++- main.pdf | Bin 265313 -> 284958 bytes main.tex | 2 +- 18 files changed, 175 insertions(+), 122 deletions(-) create mode 100644 docs/.generieren.tex.swp create mode 100644 docs/100tree.pdf delete mode 100644 docs/danksagung.tex create mode 100644 docs/tree5.pdf diff --git a/.main.tex.swp b/.main.tex.swp index 9c876be..eff3c11 100644 Binary files a/.main.tex.swp and b/.main.tex.swp differ diff --git a/docs/.container.tex.swp b/docs/.container.tex.swp index 824f43c..5a322ab 100644 Binary files a/docs/.container.tex.swp and b/docs/.container.tex.swp differ diff --git a/docs/.ergebnisse.tex.swp b/docs/.ergebnisse.tex.swp index bb8e21c..bb476e4 100644 Binary files a/docs/.ergebnisse.tex.swp and b/docs/.ergebnisse.tex.swp differ diff --git a/docs/.generieren.tex.swp b/docs/.generieren.tex.swp new file mode 100644 index 0000000..4091eb4 Binary files /dev/null and b/docs/.generieren.tex.swp differ diff --git a/docs/.netzwerk.tex.swp b/docs/.netzwerk.tex.swp index 422f672..53a00cb 100644 Binary files a/docs/.netzwerk.tex.swp and b/docs/.netzwerk.tex.swp differ diff --git a/docs/.simulieren.tex.swp b/docs/.simulieren.tex.swp index 000780c..8f496aa 100644 Binary files a/docs/.simulieren.tex.swp and b/docs/.simulieren.tex.swp differ diff --git a/docs/100tree.pdf b/docs/100tree.pdf new file mode 100644 index 0000000..fcd7c6b Binary files /dev/null and b/docs/100tree.pdf differ diff --git a/docs/container.tex b/docs/container.tex index 86da058..e8673ae 100644 --- a/docs/container.tex +++ b/docs/container.tex @@ -3,7 +3,11 @@ Um eine optimale Skalierbarkeit zu erreichen wird die Anwendung in einzelne Module aufgeteilt und in einzelne Container verpackt. Dadurch ist es einfach möglich die Anwendung auf mehreren Rechnern gleichzeitig laufen zu lassen und -entsprechende Interaktionen zwischen den Container zu definieren. +entsprechende Interaktionen zwischen den Container zu definieren. Durch die +containerisierung mithilfe von Docker\footnote{\url{https://www.docker.com/}} +ist es ebenfalls möglich die Container auf einem beliebegem Betriebssystem zu +starten ohne von bestimmten bibliotheksveriosnen abhängig zu sein da diese in +den Container bereits integriert sind. \subsection{Modularisierung des Generators} Um den Generator zu modularisieren muss erst definiert werden was für @@ -36,9 +40,10 @@ Modul welches die Daten in die Datenbank schreibt. \subsubsection{Generator Modul} Das Generator Modul generiert zufällige Koordinaten in einem definiertem Intervall und sendet diese an einen NFW Container. Damit nicht ein Container -unter der last der ein kommenden Antworten leidet wird der reverse-Proxy +unter der last der ein kommenden Antworten leidet wird der +Reverse-Proxy\footnote{\url{https://de.wikipedia.org/wiki/Reverse_Proxy}} Traefik\footnote{\url{https://traefik.io/}} verwendet. Dieser routet die -Anfragen an weitere Container weiter wodurch optimale Lastverteilung und +Anfragen an weitere Container weiter wodurch einer optimale Lastverteilung und Skalierbarkeit gegeben ist. \subsubsection{NFW Modul} @@ -48,6 +53,10 @@ Anfragen zu hoch wird einfach ein identische Container gestartet werden. Traefik erkennt diesen Container automatisch und kann diesen beim Routen der Anfragen entsprechend nutzen. +\subsubsection{DB Modul} +Um die Daten zurück in die Datenbank zu schrieben wird das DB-Modul welches +unter \ref{subsubsec:db_modul} genau beschrieben wird verwendet. + \subsection{Modularisierung des Simulators} Der Simulator simuliert die Sterne aus der Datenbank indem er Stern für Stern die Kraft die auf einen Stern wirkt berechnet, die neue Position des Sternes @@ -87,12 +96,15 @@ gespeicherten Baum in Kombination des Barnes-Hut Algorithmus nutzt. Nachdem die Kraft berechnet wurde kann die Neue Position des Sternes berechnet werden und wieder in die Datenbank eingefügt werden. -\subsubsection{DB Modul} +\subsubsection{DB Modul} \label{subsubsec:db_modul} Der Datenbank Container interagiert mit der Datenbank und stellt verschiedene Methoden zur Verfügung um z.B. Sterne in die Datenbank einzufügen, Daten aus der Datenbank zu erhalten und den Massen Mittelpunkt aller inneren Knoten zu berechnen. +\par Das Modul stellt ebenfalls funktionen zur verfügung welche sterne die in +die Funktion gegeben werden in die Datenbank einfügen und lesen können. + \subsection{Sonstige Container} \subsubsection{Viewer} @@ -127,7 +139,8 @@ sammelt die Daten alle paar Sekunden ein und speichert diese um anschließend einen Verlauf in der Form eines Graphen o.ä. darzustellen. Um alle Server zu monitoren kann Grafana auf mehrere Prometheus Instanzen zugreifen und entsprechende Graphen generieren. Somit ist es möglich mit geringem Aufwand -alle laufenden Dienste auf einen Blick zu überwachen. +alle laufenden Dienste auf einen Blick zu überwachen. Der Gesamte Prozess ist +in Abbilding \ref{fig:monitoring_setup} dargestellt. \begin{figure}[ht!] \centering @@ -206,16 +219,19 @@ desto höher wird die Auslastung der Datenbank. Um dieses Problem zu lösen bietet es sich an die Datenbank in mehrere teile aufzuspalten. Ein weiters essenzielles Problem das bei der Verteilung der Simulations rechen Knoten in verschiedene Rechenzentren entsteht ist, dass die Bandbreite zur Datenbank -sinkt und die Latenz steigt. +sinkt und die Latenz steigt. Dieses Problem wird durch sogennantes +``Sharding'' (vertikale bzw. horizontalte +Fragmentierung\footnote{\url{https://de.wikipedia.org/wiki/Denormalisierung\#Fragmentierung}}) +gelöst. -\subsubsection{Sharding} +\subsubsection{Sharding (Vertikale bzw. Horizontale Fragmentierung)} Ab einer gewissen Größe kann eine Galaxie nicht mehr in einer Datenbank gespeichert werden. Diese muss demnach auf mehrere Rechner aufgeteilt werden. Da die Datenbank einerseits die einzelnen Sterne Speicher und Bäume welche die Sterne referenziert bietet es sich hier an diese beiden Bestandteile der Datenbank in einzelne Datenbanken auszulagern. -\paragraph{Sterne} ~\\ +\paragraph{Sterne (Horizontale Fragmentierung)} ~\\ Möchte man eine Liste an Sternen auf mehrere Datenbanken aufspalten wird die Liste entsprechend aufgeteilt und auf die Datenbanken verteilt. Wird nun ein bestimmter Stern gesucht wird die Anfrage über einen reverse-proxy geleitet @@ -224,7 +240,7 @@ welcher die Anfrage an die entsprechende Datenbank weiterleitet. \par Es ist somit möglich die Liste an Sternen auf mehrere Datenbanken aufzuteilen und somit die Last von einem System auf mehrere zu verteilen. -\paragraph{Bäume} ~\\ +\paragraph{Bäume (Vertikale Fragmentierung)} ~\\ Die Aufteilung der Datenbank in der die Bäume gespeichert werden gestaltet sich ähnlich. Statt alle Bäume in einer Datenbank zu speichern, werden die entsprechenden Teilbäume ab einer bestimmten Tiefe in verschiedene Datenbanken diff --git a/docs/danksagung.tex b/docs/danksagung.tex deleted file mode 100644 index 6862b5c..0000000 --- a/docs/danksagung.tex +++ /dev/null @@ -1 +0,0 @@ -\section{Danksagung} diff --git a/docs/ergebnisse.tex b/docs/ergebnisse.tex index cea3c8e..dc6bd82 100644 --- a/docs/ergebnisse.tex +++ b/docs/ergebnisse.tex @@ -1,9 +1,12 @@ \section{Ergebnisse} -Die ``ursprüngliche`` Laufzeit in \( O(n^2) \) ist auf \( O(n \cdot log_4(n)) \) -reduziert was es (in der Theorie) ermöglicht eine ``echte`` Galaxie mit -200.000.000 Sternen in \textbf{45 Minuten} statt \textbf{1267 Jahren} zu -simulieren. Es wird dabei davon ausgegangen, dass pro Sekunde die Kraft die auf -1.000.000 Sterne wirkt berechnet werden kann. Dies ist auf einen einzlnem -Rechner nicht durchführbar, durch die Aufteilung auf mehrere Rechner ist es -jedoch möglich. +Die Generierung der Punktwolken ist komplett skaliert, es ist nun möglich +mehrere Generator-Instanzen hochzufen welche die Sterne generieren und in eine +Datenbank schreiben. Die Sterne in der Datenbank können nun auch simuliert +werden, die ``ursprüngliche`` Laufzeit in \( O(n^2) \) ist auf \( O(n \cdot +log_4(n)) \) reduziert was es (in der Theorie) ermöglicht eine ``echte`` +Galaxie mit 200.000.000 Sternen in \textbf{45 Minuten} statt \textbf{1267 +Jahren} zu simulieren (Faktor 14.808.695). Es wird dabei davon ausgegangen, +dass pro Sekunde die Kraft die auf 1.000.000 Sterne wirkt berechnet werden +kann. Dies ist auf einen einzlnem Rechner nicht durchführbar, durch die +Aufteilung auf mehrere Rechner ist es jedoch möglich. diff --git a/docs/generieren.tex b/docs/generieren.tex index 778940f..cf9b7ce 100644 --- a/docs/generieren.tex +++ b/docs/generieren.tex @@ -2,14 +2,16 @@ Das Generieren der Statischen Punkt Wolke aus der die Galaxie abstrahiert wird ist ein wichtiger Bestandteil des Gesamtprojektes, denn alles baut auf ihr auf. -Kurz: um Kräfte zwischen Sternen zu berechnen braucht man erstmal Sterne! +Kurz: um Kräfte zwischen Sternen zu berechnen braucht man erstmal Sterne! Dazu +wird das Navarro-Frenk-White Profil verwendet um eine Statische Punktwolke zu +generieren. \subsection{Das Navarro-Frenk-White Profil} -Das Navarro-Frenk-White Profil (NFW-Profil) ist ein Profil das genutzt wird, um +Das Navarro-Frenk-White Profil (NFW-Profile) \cite{navarrofrenkwhite95} ist ein Profil das genutzt wird, um die Räumilche Massen Verteilung von Sternen zu definieren. Es generiert für einen Stern mit dem Abstand \( r \) zum Mittelpunkt der Galaxie eine Warscheinlichkeit \( \rho \) welche definiert wie Warscheinlich es ist das der -Stern mit dem Abstand \( r \) generiert wird: +Stern mit dem Abstand \( r \) existiert: \begin{equation} \label{eq:NFW_profile} \rho_{NFW}(r) = \frac{ 1 }{ \sqrt{ 2 \pi } \cdot \sigma } \cdot @@ -48,21 +50,22 @@ Die Galaxie sieht aus der Ferne jetzt jedoch aus wie ein Würfel, da die aus \( indem statt \( \rho_{NFW_{1}}(r) \) folgendes gerechnet wird: \( \rho_{NFW_{1}}(r) - \rho_{NFW_{1}}(r_{max}) = \rho_{NFW_{2}}(r)\) -\paragraph{Veranschaulichung:}~\\ - -\begin{center} - \begin{tikzpicture} - \draw[very thin, color=lightgray, step=5mm] (-0.9, -0.9) grid (3.9, 2.4); - \draw[->] (-1,0) -- (4,0) node[right] {$x$}; - \draw[->] (0,-1) -- (0,2.5) node[above] {$y$}; - \draw[scale=0.5, domain=0.25:6.5, smooth, variable=\x, black] plot ({\x},{(1/\x) + 1}) node[above] {$\rho_{NFW_{1}}(x)$}; - \draw[scale=0.5, domain=0.25:6.5, smooth, variable=\x, black] plot ({\x},{1/\x}) node[below] {$\rho_{NFW_{2}}(x)$}; - \end{tikzpicture} -\end{center} +\begin{figure} +\centering +\begin{tikzpicture} + \draw[very thin, color=lightgray, step=5mm] (-0.9, -0.9) grid (3.9, 2.4); + \draw[->] (-1,0) -- (4,0) node[right] {$x$}; + \draw[->] (0,-1) -- (0,2.5) node[above] {$y$}; + \draw[scale=0.5, domain=0.25:6.5, smooth, variable=\x, black] plot ({\x},{(1/\x) + 1}) node[above] {$\rho_{NFW_{1}}(x)$}; + \draw[scale=0.5, domain=0.25:6.5, smooth, variable=\x, black] plot ({\x},{1/\x}) node[below] {$\rho_{NFW_{2}}(x)$}; +\end{tikzpicture} +\caption{Durch Verschiebung des NFW-Profils wird } +\end{figure} Problematisch ist hierbei die Tatsache, dass aufgrund der Verschiebung die Anzahl der Sterne die in Relation zu dem Bereich in dem sie generiert werden -sehr stark sinkt. +sehr stark sinkt und die Zeit um eine bestimmte Anzahl an Sternen zu generieren +sehr stark steigt. \subsection{Random Sampling} \label{subsec:random_sampling} @@ -80,42 +83,42 @@ einen zufälligen Wert \( r \) im Intervall \( \psi \), kann überprüft werden, > r \lor s < r \) gilt. Ist \( r > s \), wird der Stern verworfen, ist \( r < s \) wird der Stern behalten. -\paragraph{Veranschaulichung:}~\\ +\begin{figure} +\centering +\begin{tikzpicture} + % draw the background grid + \draw[very thin, color=lightgray, step=5mm] (-0.9, -0.9) grid (3.9, 2.4); -\begin{center} - \begin{tikzpicture} - % draw the background grid - \draw[very thin, color=lightgray, step=5mm] (-0.9, -0.9) grid (3.9, 2.4); - - % draw the x-ticks - \draw[xshift=0cm](0.5cm, 1pt) -- (0.5cm, -3pt) node[anchor=north] {$r_{1}$}; - \draw[xshift=0cm](1.5cm, 1pt) -- (1.5cm, -3pt) node[anchor=north] {$r_{2}$}; - - % draw the y-ticks - \draw[yshift=0cm](1pt, 0.5cm) -- (-3pt, 0.5cm) node[anchor=east] {$p(r_{1})$}; - \draw[yshift=0cm](1pt, 1.0cm) -- (-3pt, 1.0cm) node[anchor=east] {$p(r_{2})$}; - - % draw the dotted lines connecting the point s_1 - \draw[thick, dotted] (0.5, 0) -- (0.5, 0.5); - \draw[thick, dotted] (0, 0.5) -- (0.5, 0.5); - - % draw the dotted lines connecting the point s_2 - \draw[thick, dotted] (0, 1.0) -- (1.5, 1.0); - \draw[thick, dotted] (1.5, 0) -- (1.5, 1.0); - - % draw the axes - \draw[->] (-1,0) -- (4,0) node[right] {$r$}; - \draw[->] (0,-1) -- (0,2.5) node[above] {$\psi$}; - - % draw the plot - \draw[scale=0.5, domain=0.25:6.5, smooth, variable=\x, black] - plot ({\x},{(1/\x) + 1}) node[above] {$\rho_{NFW_{1}}(x)$}; - - % draw the points - \fill (0.5, 0.5) circle (0.05) node[above] {$s_1$}; - \fill (1.5, 1) circle (0.05) node[above] {$s_2$}; - \end{tikzpicture} -\end{center} + % draw the x-ticks + \draw[xshift=0cm](0.5cm, 1pt) -- (0.5cm, -3pt) node[anchor=north] {$r_{1}$}; + \draw[xshift=0cm](1.5cm, 1pt) -- (1.5cm, -3pt) node[anchor=north] {$r_{2}$}; + + % draw the y-ticks + \draw[yshift=0cm](1pt, 0.5cm) -- (-3pt, 0.5cm) node[anchor=east] {$p(r_{1})$}; + \draw[yshift=0cm](1pt, 1.0cm) -- (-3pt, 1.0cm) node[anchor=east] {$p(r_{2})$}; + + % draw the dotted lines connecting the point s_1 + \draw[thick, dotted] (0.5, 0) -- (0.5, 0.5); + \draw[thick, dotted] (0, 0.5) -- (0.5, 0.5); + + % draw the dotted lines connecting the point s_2 + \draw[thick, dotted] (0, 1.0) -- (1.5, 1.0); + \draw[thick, dotted] (1.5, 0) -- (1.5, 1.0); + + % draw the axes + \draw[->] (-1,0) -- (4,0) node[right] {$r$}; + \draw[->] (0,-1) -- (0,2.5) node[above] {$\psi$}; + + % draw the plot + \draw[scale=0.5, domain=0.25:6.5, smooth, variable=\x, black] + plot ({\x},{(1/\x) + 1}) node[above] {$\rho_{NFW_{1}}(x)$}; + + % draw the points + \fill (0.5, 0.5) circle (0.05) node[above] {$s_1$}; + \fill (1.5, 1) circle (0.05) node[above] {$s_2$}; +\end{tikzpicture} +\caption{Veranschauliching des Konzeptes welches beim Random-Sampling verwendet wird.} +\end{figure} In der obigen Abbildung ist zu sehen wir zwei zufällige Punkte \( s_1 \) und \( s_2 \) generiert wurden. @@ -136,6 +139,9 @@ s_1 > NFW(r_1) & \rightarrow \text{Stern wird verworfen} \end{cases} \end{equation} +Es kann somit für einen gegebenen Stern geprüft werden ob dieser existiert oder +nicht und anhand dessen beschlossen werden ob der Stern beibehalten wird oder +nicht. \subsection{Lookup Tabellen} Statt nun für jeden Stern die Distanz des jeweiligen Sternes \( r \) in das @@ -157,17 +163,21 @@ zugeordnet wird: Die Tabelle kann jedoch nicht so genaue Ergebnisse liefern wie das NFW-Profil, sie kann jedoch so angepasst werden, dass sie in den Arbeitsspeicher passt und somit das NFW-Profil so genau wie möglich widerspiegelt und das Generieren -stark verbessert. Mit genügend Arbeitsspeicher ist der Fehler dann auch -vernachlässigbar. Ein Kritischer Faktor, der beachtet werden muss wenn -Lookuptabellen genutzt werden, ist die Geschwindigkeit des jeweiligen -Speichermediums. Nutzt man z.B. Eine sehr langsame Festplatte kann es mehr -Sinne machen die jeweiligen Werte direkt zu berechnen. Dagegen ist eine -schnelle SSD (Solid-State-Drive) um einiges schneller. +stark verbessert. Dadurch das sie in den Arbeitsspeicher passt ist der Tatsache +das sie nicht direk berechnet wird auch zu vernachlässigen, denn das Lesen von +Daten aus dem Arbeitsspeicher funktioniert sehr schnell. Mit genügend +Arbeitsspeicher ist der Fehler demnach auch vernachlässigbar. Ein Kritischer +Faktor, der beachtet werden muss wenn Lookuptabellen genutzt werden, ist die +Geschwindigkeit des jeweiligen Speichermediums. Nutzt man z.B. Eine sehr +langsame Festplatte kann es mehr Sinne machen die jeweiligen Werte direkt zu +berechnen. Dagegen ist eine schnelle SSD (Solid-State-Drive) um einiges +schneller, kommt jedoch nicht gegen den Arbeitsspeicher an weshalb es sich +nicht lohnt ein anders Medium zu nutzen. \subsection{Beschleunigung der Generierung} Es existieren mehrere Möglichkeiten die Generierung der Punkte zu verbessern. -Eine gute Möglichkeit ist die Nutzung von mehr Rechenleistung. Bei der Nutzung +Eine gute Möglichkeit ist die Nutzung von mehr Rechenleistung. Bei der Nutzung von \( n \) mal sovielen Rechen kernen ist das Generieren von Sternen \( n \) mal schneller. Die Server des Server-Hosters Hetzner können dabei gut verwendet werden: Es wird stündlich abgerechnet und 32 Kerne mit 128 GB RAM @@ -177,4 +187,4 @@ Günstigen Preis, sehr viele Koordinaten zu generieren. Die Ausgabe von jeder Potentiellen Koordinate in die Kommandozeile verlangsamt die Generierung unglaublich stark, da der Rechner darauf wartet das die Ausgabe fertig ist bevor er mit der nächsten Rechnung beginnt was zu einer relativ -starken Verlangsamung der Generierung führt. +starken Verlangsamung der Generierung führt. Dies sollte also verhindert werden. diff --git a/docs/netzwerk.tex b/docs/netzwerk.tex index a885633..e619b73 100644 --- a/docs/netzwerk.tex +++ b/docs/netzwerk.tex @@ -1,5 +1,5 @@ \section{Netzwerk} Damit die Container untereinander interagieren können kommunizieren sie über -verschiedene APIs. Die NFW-container exponieren eine HTTP API welche einen wert \( r \) -annehmen und den jeweiligen NFW Wert ausrechnen. +verschiedene APIs. Die NFW-container exponieren eine HTTP API welche einen Wert +\( r \) annehmen und den jeweiligen NFW Wert ausrechnen. diff --git a/docs/quellen.tex b/docs/quellen.tex index cc4a9a3..bad56b0 100644 --- a/docs/quellen.tex +++ b/docs/quellen.tex @@ -1 +1,19 @@ \section{Quellen} + +\begin{thebibliography}{99} + +\bibitem{navarrofrenkwhite95} + Julio F. Navarro, Carlos S. Frenk and Simon D.M. White, + \textit{The Structure of Cold Dark Matter Halos}, + 1986. + +\bibitem{barneshut86} + Josh Barnes and Piet Hut, + \textit{A Hierarchical \(O ( N log N )\) Force calculation Algorithm}, + Nature, + vol. 324, pp.446, + 1986. + + +\end{thebibliography} + diff --git a/docs/simulieren.tex b/docs/simulieren.tex index d3c128b..245c78f 100644 --- a/docs/simulieren.tex +++ b/docs/simulieren.tex @@ -36,29 +36,8 @@ Massen Mittelpunkt zieht aus. Rotiert man die Galaxie jedoch zu schnell, explodiert sie förmlich, da die Sterne nicht mehr zusammengehalten werden und die Fliehkraft sie einfach auseinanderzieht. -\subsubsection{Die Kraft als Vektor} -Um die Kraft als Vektor zu berechnen, welcher ein Stern B auf einen Stern A -ausübt, wird die folgende Formel verwendet: - -\begin{equation} - \vec{F}_{AB} = \underbrace{-G \frac{m_A m_B}{|r_{AB}|^2}}_{Scalar} - \cdot \underbrace{\frac{r_B - r_A}{|r_B - r_A|}}_{Vector} -\end{equation} - -Die Summe der Kräfte die auf einen Stern wirken ist somit die Summe aller -Kräfte die zwischen dem jeweiligen Stern \( a \) und allen anderen Sternen -wirken: - -\begin{equation} - F_{a} = \sum_{\substack{i=0 \\ i\neq a}}^{n-1} F_{ai} -\end{equation} - \subsection{Konzepte} -%Die Software ist komplett in Golang geschrieben was die Nutzung von mehreren -%Threads mithilfe von Go-Methoden stark vereinfacht. Um den Barnes-Hut -%Algorithmus anzuwenden muss die Galaxie in einen Octree unterteilt werden. -%Dabei wird eine Zelle definiert die alle Sterne beinhaltet welche anschließen -%solange unterteilt, bis eine der drei end- Bedingungen eintrifft. + \subsubsection{Zu lösende Probleme} Wie bereits beschrieben ist eines der Probleme das Auftritt die Anzahl der @@ -78,7 +57,7 @@ kleine Cluster an Sternen welche weit genug vom Stern auf den die Kräfte berechnet werden sollen weg sind und klein genug sind zu einem Pseudo- Stern zusammengefasst werden welcher durch den Masse Mittelpunkt der Sterne die er repräsentiert definiert ist. Das Konzept wurde 1986 von Josch Barnes und Piet Hut -veröffentlicht und erlaubt es die Anzahl an Kräften die berechnet werden müssen +veröffentlicht \cite{barneshut86} und erlaubt es die Anzahl an Kräften die berechnet werden müssen von \( O(n^2) \) auf \( O(n log(n)) \) zu reduzieren. \subsubsection{Generierung von Quadtrees und entsprechende Bäume} @@ -196,6 +175,24 @@ Pseudostern zusammengefasst werden. \subsection{Kraft-Berechnungen} + +\subsubsection{Die Kraft als Vektor} +Um die Kraft als Vektor zu berechnen, welcher ein Stern B auf einen Stern A +ausübt, wird die folgende Formel verwendet: + +\begin{equation} + \vec{F}_{AB} = \underbrace{-G \frac{m_A m_B}{|r_{AB}|^2}}_{Scalar} + \cdot \underbrace{\frac{r_B - r_A}{|r_B - r_A|}}_{Vector} +\end{equation} + +Die Summe der Kräfte die auf einen Stern wirken ist somit die Summe aller +Kräfte die zwischen dem jeweiligen Stern \( a \) und allen anderen Sternen +wirken: + +\begin{equation} + F_{a} = \sum_{\substack{i=0 \\ i\neq a}}^{n-1} F_{ai} +\end{equation} + \subsubsection{Berechnung der auf einen Stern wirkenden Kraft} \par Um die Kraft, welche auf einen bestimmten Stern wirkt, zu berechnen, wird der @@ -310,7 +307,7 @@ dargestellt} ] \end{forest} } -\; +\, \subfloat[Stern B kann nicht eingefügt werden, da der Slot durch A belegt ist, also wird A weiter in den Baum versickert.]{ \begin{forest} for tree={circle,draw, s sep+=0.25em} @@ -325,7 +322,7 @@ dargestellt} ] \end{forest} } -\; +\, \subfloat[B wird nun eingefügt, da sich B jedoch nicht in einem Blatt befinden, muss B weiter versickert werden.]{ \begin{forest} for tree={circle,draw, s sep+=0.25em} @@ -339,7 +336,7 @@ dargestellt} ] \end{forest}\quad\\[2ex] } -\; +\, \subfloat[Damit B versickert werden kann, wird der Platz der durch A besetzt wird freigemacht, indem A weiter versickert wird.]{ \begin{forest} for tree={circle,draw, s sep+=0.25em} @@ -356,7 +353,7 @@ dargestellt} ] \end{forest}\quad } -\; +\, \subfloat[B kann jetzt in den Baum versickert werden und ist nun ein Blatt.]{ \begin{forest} for tree={circle,draw, s sep+=0.25em} @@ -383,7 +380,7 @@ dargestellt} \subsubsection{Speichern der Sterne} Die Sterne werden in einer Tabelle in Datenbank \mbox{PostgreSQL} gespeichert. -Die Tabelle ist folgendermaßen aufgebaut: +Die Tabelle ist wie in Abbildung \ref{fig:stars_table} zu sehen aufgebaut. \begin{figure}[h!] \centering @@ -397,6 +394,7 @@ n & \(x_n\) & \(y_n\) & \(vx_n\)& \(vy_n\) & \(m_n\) \\ \hline \caption{Darstellung der Tabelle in der die Sterne gespeichert werden. Die star\_id spalte beinhaltet eine global einmalige ID wodurch jeder Stern identifiziert werden kann.} +\label{fig:stars_table} \end{figure} Dadurch das jeder Stern eine einmalige ID besitzt kann diese verwendet werden @@ -404,22 +402,26 @@ um einfach auf Sterne zu verweisen. Dies ist im Kontext des Einfügens sehr hilfreich da die Verschiebung eines Sternes durch ändern der Stern-ID vollzogen werden kann. -\subsubsection{Speichern von Bäumen} - -Um die Bäume in einer Datenbank zu speichern muss eine einheitliche Struktur -definiert werden um Probleme in der Zukunft zu verhindern. Die Nutzung von -speziellen Graphen Datenbanken bietet sich natürlich an, jedoch wird diese -starke Spezialisierung schnell zu einem Hindernis. Um nach dem KISS -Prinzip\footnote{"Das KISS-Prinzip (englisch Keep it simple, stupid) fordert, -zu einem Problem eine möglichst einfache Lösung anzustreben." -\url{https://de.wikipedia.org/wiki/KISS-Prinzip}} eine möglichst einfache -Lösung zu nutzen werden die Bäume in einer Relationalen Datenbank gespeichert. -Jeder Knoten wird dabei in einer Zeile der Datenbank gespeichert und erhält -eine global einzigartige ID. Die Kinder in andrem Knoten hängen werden anhand -ihrer ID in der Zeile gespeichert sodass es einfach möglich ist einfach auf -diese zuzugreifen und beim rekursiven durchsuchen des Baumes auf diese -zuzugreifen. +\par Jeder Stern besitzt eine Position, einer Geschwindingkeit und eine Masse. +Dadurch kann man einen Stern definieren, jedoch auch berechnen was für eine +Kraft der Stern auf andere Sterne auswirkt. +\subsubsection{Speichern von Bäumen} +Um die Bäume in denen die galaxien giepeichert werden in einer Datenbank zu +speichern, muss eine einheitliche Struktur definiert werden um Probleme in der +Zukunft zu verhindern. Die Nutzung von speziellen Graphen Datenbanken bietet +sich natürlich an, jedoch wird diese starke Spezialisierung schnell zu einem +Hindernis. Um nach dem KISS Prinzip\footnote{"Das KISS-Prinzip (englisch Keep +it simple, stupid) fordert, zu einem Problem eine möglichst einfache Lösung +anzustreben." \url{https://de.wikipedia.org/wiki/KISS-Prinzip}} eine möglichst +einfache Lösung zu nutzen werden die Bäume in einer Relationalen Datenbank +gespeichert. Jeder Knoten wird dabei in einer Zeile der Datenbank gespeichert +und erhält eine global einzigartige ID. Die Kinder in andrem Knoten hängen +werden anhand ihrer ID in der Zeile gespeichert sodass es einfach möglich ist +einfach auf diese zuzugreifen und beim rekursiven durchsuchen des Baumes auf +diese zuzugreifen. Möchte man einen Teilbaum unterteilen können einfach vier +neue Knoten erzuegt werden welche vom Knoten an dem sie hängen referneziert +werden. \begin{figure*}[ht] \begin{tabular} {l | l | l | l | l | l | l | l | l | l} diff --git a/docs/tree5.pdf b/docs/tree5.pdf new file mode 100644 index 0000000..0967b96 Binary files /dev/null and b/docs/tree5.pdf differ diff --git a/docs/vorgehensweise.tex b/docs/vorgehensweise.tex index dc47957..197dfbf 100644 --- a/docs/vorgehensweise.tex +++ b/docs/vorgehensweise.tex @@ -1,7 +1,12 @@ \section{Vorgehensweise} -Wir schon in der Einleitung beschrien habe ich mehrere Techniken kombiniert um +Wie schon in der Einleitung beschrien habe ich mehrere Techniken kombiniert um mein Ziel zu erreichen. Das komplette Projekt lässt sich in mehrere Abschnitte unterteilen: Die Generierung der Punkt Wolke welche als Galaxie abstrahiert wird und als Basis für weitere Berechnungen genutzt wird, das Einfügen der einzelnen Sterne in einen k-nären Baum und die anschließende Simulation welche durch nutzen des Barnes-Hut Algorithmus sehr stark beschleunigt wird. + +\par Um einer optimale Skallierbarkeit zu erreichen wird die Datenbank in +mehrere Teile unterteilt. Die Simulation wird ebenfalls auf mehrere Servern +durchgeführt wodurch es möglich ist die skallierung auf (theoretisch) unendlich +vielen systemen laufen zu lassen. diff --git a/main.pdf b/main.pdf index b6b51be..df6cfe5 100644 Binary files a/main.pdf and b/main.pdf differ diff --git a/main.tex b/main.tex index b7ed18c..ae1e8fa 100644 --- a/main.tex +++ b/main.tex @@ -21,6 +21,7 @@ % code listings \usepackage{listings} \usepackage{listings-golang} +\usepackage{pdfpages} \lstset{ frame=single, @@ -49,7 +50,6 @@ \input{docs/netzwerk} \input{docs/ergebnisse} \input{docs/quellen} -\input{docs/danksagung} \end{document} -- cgit 1.4.1