aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/multiplikation
diff options
context:
space:
mode:
Diffstat (limited to 'buch/papers/multiplikation')
-rw-r--r--buch/papers/multiplikation/images/meas_python.pdfbin26004 -> 22384 bytes
-rw-r--r--buch/papers/multiplikation/images/meas_python.tex44
-rw-r--r--buch/papers/multiplikation/images/x.pdfbin23603 -> 0 bytes
-rwxr-xr-xbuch/papers/multiplikation/loesungsmethoden.tex30
4 files changed, 39 insertions, 35 deletions
diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf
index cea4f4b..ab3b14b 100644
--- a/buch/papers/multiplikation/images/meas_python.pdf
+++ b/buch/papers/multiplikation/images/meas_python.pdf
Binary files differ
diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex
index c8892be..d942f46 100644
--- a/buch/papers/multiplikation/images/meas_python.tex
+++ b/buch/papers/multiplikation/images/meas_python.tex
@@ -43,8 +43,8 @@
\begin{tikzpicture}
\begin{axis}[
xmode=log, ymode=log,
-xmin=30, xmax=4100,
-ymin=0.00001, ymax=60000,
+xmin=30, xmax=4200,
+ymin=0.01, ymax=70000,
grid=both,
major grid style={black!50},
xlabel = data input ($n$),
@@ -121,29 +121,23 @@ width=12cm, height=8cm,
(2046,6154.18)
(4096,46813.3)
};
- \addlegendentry{NumPy}
- \addplot[ color=blue,
- ] coordinates {
-% (2,1.83582e-05 )
-% (4,7.86781e-06)
-% (8,1.00136e-05)
-% (16,5.4121e-05 )
- (32,4.26769e-05)
- (64,0.000118494)
- (128,0.000244141 )
- (256,0.000695705 )
- (512,0.00221705 )
- (1024,0.0188088 )
-(2046,0.215739)
-(4096,1.49159)
- };
- \addplot [
- domain= 1:5000,
- samples=100,
- color=yellow,
- ]
- {(x-1000)^3};
- \addlegendentry{$\mathcal{O}\left(n^3\right)$}
+% \addlegendentry{NumPy}
+% \addplot[ color=blue,
+% ] coordinates {
+% % (2,1.83582e-05 )
+% % (4,7.86781e-06)
+% % (8,1.00136e-05)
+% % (16,5.4121e-05 )
+% (32,4.26769e-05)
+% (64,0.000118494)
+% (128,0.000244141 )
+% (256,0.000695705 )
+% (512,0.00221705 )
+% (1024,0.0188088 )
+% (2046,0.215739)
+% (4096,1.49159)
+% };
+
\end{axis}
\end{tikzpicture}
diff --git a/buch/papers/multiplikation/images/x.pdf b/buch/papers/multiplikation/images/x.pdf
deleted file mode 100644
index da4956f..0000000
--- a/buch/papers/multiplikation/images/x.pdf
+++ /dev/null
Binary files differ
diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex
index 464085d..be8c2d4 100755
--- a/buch/papers/multiplikation/loesungsmethoden.tex
+++ b/buch/papers/multiplikation/loesungsmethoden.tex
@@ -389,6 +389,14 @@ Folgende Algorithmen wurden jeweils in \texttt{C} und \texttt{Python} implementi
Der Code kann im zum Buch gehörigem \textit{GitHub} \footnote{\url{https://github.com/AndreasFMueller/SeminarMatrizen.git}} Repository gefunden werden.
Anzumerken ist, dass die Matrizenmultiplikation von \texttt{NumPy} als einzige Implementation Multiprocessing und Multithreading verwendet, dies f\"uhrt zu den tiefen Messzeiten.
In Abbildung \ref{multiplikation:fig:python} und Abbildung \ref{multiplikation:fig:c_meas_4096} sind de Messresultate grafisch dargestellt. Die selben Messresultate sind tabellarisch in Tabelle \ref{multiplikation:tab:messung_Python} und Tabelle \ref{multiplikation:tab:messung_C} ersichtlich.
+
+In der Messung mit der Programmiersprache \texttt{C}, kann ein typischer Cache-Effekt beobachtet wer-
+den. Bei den Algorithmen von Winograd und der Standardmethode hat bei einer Gr\"osse von
+n = 2048 wohl eine Zeile der Matrix nicht an einer Cache Speicherstelle platzt. Diese beiden Al-
+Algorithmen sind die Einzigen, welche \texttt{for}-Schleifen über die ganze Breite der Matrizen verwenden.
+Dies führt dazu, dass ganze Zeilen zwischengespeichert werden müssen. Bei den anderen Algorith-
+men ist dies nicht der Fall.
+
Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{multiplikation:tab:pc_config} aufgelistet.
@@ -400,14 +408,15 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul
\textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{BLAS (\textit{s})} \\
\hline
\multicolumn{6}{c}{} \\
- \textbf{32} & 0.000081 &0.000594 & 0.00047& 0.00010 & 0.000022 \\
- \textbf{64} & 0.00065 & 0.0042& 0.0033& 0.00065& 0.00017 \\
- \textbf{128} & 0.0055 & 0.036& 0.024& 0.0052 & 0.0012 \\
- \textbf{256} & 0.054 & 0.32 & 0.17 & 0.057& 0.010 \\
- \textbf{512} & 0.48 & 2.61 & 1.20 & 0.51 & 0.074\\
- \textbf{1024} & 4.16 & 19.92& 8.45 & 4.53 & 0.704 \\
- \textbf{2048} & 125.90 & 159.33& 59.26 & 130.62 & 6.84 \\
- \textbf{4096} & 1111.31 & 1147.10& 414.64 & 1179.26 & 55.84\\
+ \textbf{32} & 0.000089 & 0.000594 & 0.0005 & 0.00008 & 0.000021 \\
+ \textbf{64} & 0.00069 & 0.0044 & 0.0036 & 0.00064 & 0.00018 \\
+ \textbf{128} & 0.0057 & 0.035 & 0.025 & 0.0052 & 0.0012 \\
+ \textbf{256} & 0.052 & 0.29 & 0.178 & 0.053 & 0.0096 \\
+ \textbf{512} & 0.51 & 2.22 & 1.25 & 0.55 & 0.077 \\
+ \textbf{1024} & 4.50 & 17.65 & 8.83 & 4.67 & 0.764 \\
+ \textbf{2048} & 129.28 & 141.61 & 61.901 & 136.67 & 7.63 \\
+ \textbf{4096} & 1111.31 & 1147.10 & 414.64 & 1179.26 & 55.84 \\
+ \textbf{8192} & 9376.17 & 9606.40 & 3014.23 & 10071.51& 478.42 \\
\multicolumn{6}{c}{} \\
\hline
\hline
@@ -427,13 +436,14 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul
\textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{\texttt{NumPy}(\textit{s})} \\
\hline
\multicolumn{6}{c}{} \\
- \textbf{32} & 0.0240 &0.0271 & 0.04852& 0.01871 & 4.26e-05 \\
+ \textbf{32} & 0.0240 &0.0271 & 0.04852& 0.01871 & 0.0000426 \\
\textbf{64} & 0.186 & 0.265& 0.2204& 0.1530& 0.000118 \\
\textbf{128} & 1.563 & 1.777& 1.447& 1.1947 & 0.000244 \\
\textbf{256} & 11.006 & 13.27 & 9.938 & 8.298& 0.000695 \\
\textbf{512} & 85.476 & 105.397 & 63.961 & 68.36 & 0.00221\\
\textbf{1024} & 750.757 & 847.321& 461.494 & 537.374 & 0.0188 \\
- \textbf{4096} & - & - & - & - & 1.633 \\
+ \textbf{2048} & 6154.18 & 7375.93& 3860.57 & 4884.61 & 0.215 \\
+ \textbf{4096} & 46813.3 & 58466 & 22904.3 & 43597.1 & 1.49 \\
\multicolumn{6}{c}{} \\
\hline
\hline