From ce9f4591847c6bd2dc6ebaa30fc5d72714e0280c Mon Sep 17 00:00:00 2001
From: Nunigan <michaelschmid13@hotmail.com>
Date: Tue, 10 Aug 2021 06:37:20 +0200
Subject: new measurements
---
buch/papers/multiplikation/code/MM | Bin 26848 -> 0 bytes
buch/papers/multiplikation/code/MM.c | 19 +-
buch/papers/multiplikation/code/MM.py | 77 ++++----
buch/papers/multiplikation/code/c_matrix.h | 204 ++++++++++++++-------
buch/papers/multiplikation/code/c_meas_4096.pdf | Bin 17448 -> 22360 bytes
buch/papers/multiplikation/code/ci.txt | 0
buch/papers/multiplikation/code/helper_class.py | 3 +-
buch/papers/multiplikation/code/meas/MM.txt | 118 +++++++++++-
buch/papers/multiplikation/code/meas/MM_dc.txt | 118 +++++++++++-
buch/papers/multiplikation/code/meas/blas.txt | 114 +++++++++++-
buch/papers/multiplikation/code/meas/ci/MM.txt | 11 ++
buch/papers/multiplikation/code/meas/ci/Wino.txt | 11 ++
buch/papers/multiplikation/code/meas/ci/blas.txt | 11 ++
buch/papers/multiplikation/code/meas/ci/dc.txt | 11 ++
.../multiplikation/code/meas/ci/strassen.txt | 11 ++
.../multiplikation/code/meas/old/8196/MM.txt | 1 +
.../multiplikation/code/meas/old/8196/MM_dc.txt | 1 +
.../multiplikation/code/meas/old/8196/blas.txt | 1 +
.../multiplikation/code/meas/old/8196/strassen.txt | 1 +
.../multiplikation/code/meas/old/8196/winograd.txt | 1 +
buch/papers/multiplikation/code/meas/old/MM.txt | 12 ++
buch/papers/multiplikation/code/meas/old/MM_dc.txt | 12 ++
buch/papers/multiplikation/code/meas/old/blas.txt | 12 ++
.../multiplikation/code/meas/old/strassen.txt | 12 ++
.../multiplikation/code/meas/old/winograd.txt | 12 ++
buch/papers/multiplikation/code/meas/strassen.txt | 122 ++++++++++--
buch/papers/multiplikation/code/meas/winograd.txt | 116 +++++++++++-
buch/papers/multiplikation/code/meas_4096.pdf | Bin 12952 -> 17369 bytes
buch/papers/multiplikation/code/meas_4096.txt | 6 +
buch/papers/multiplikation/images/algo_tab.pdf | Bin 0 -> 34251 bytes
buch/papers/multiplikation/images/algo_tab.tex | 122 ++++++++++++
buch/papers/multiplikation/images/meas_c.pdf | Bin 23161 -> 23552 bytes
buch/papers/multiplikation/images/meas_c.tex | 9 +-
buch/papers/multiplikation/loesungsmethoden.tex | 48 ++---
buch/papers/multiplikation/problemstellung.tex | 145 ++++++++-------
35 files changed, 1096 insertions(+), 245 deletions(-)
delete mode 100755 buch/papers/multiplikation/code/MM
create mode 100644 buch/papers/multiplikation/code/ci.txt
create mode 100644 buch/papers/multiplikation/code/meas/ci/MM.txt
create mode 100644 buch/papers/multiplikation/code/meas/ci/Wino.txt
create mode 100644 buch/papers/multiplikation/code/meas/ci/blas.txt
create mode 100644 buch/papers/multiplikation/code/meas/ci/dc.txt
create mode 100644 buch/papers/multiplikation/code/meas/ci/strassen.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/8196/MM.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/8196/MM_dc.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/8196/blas.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/8196/strassen.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/8196/winograd.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/MM.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/MM_dc.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/blas.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/strassen.txt
create mode 100644 buch/papers/multiplikation/code/meas/old/winograd.txt
create mode 100644 buch/papers/multiplikation/images/algo_tab.pdf
create mode 100644 buch/papers/multiplikation/images/algo_tab.tex
(limited to 'buch/papers/multiplikation')
diff --git a/buch/papers/multiplikation/code/MM b/buch/papers/multiplikation/code/MM
deleted file mode 100755
index d52dda4..0000000
Binary files a/buch/papers/multiplikation/code/MM and /dev/null differ
diff --git a/buch/papers/multiplikation/code/MM.c b/buch/papers/multiplikation/code/MM.c
index a897d4f..2588262 100755
--- a/buch/papers/multiplikation/code/MM.c
+++ b/buch/papers/multiplikation/code/MM.c
@@ -28,11 +28,12 @@ int main() {
// omp_set_num_threads(4);
// run_algo(openMP_MM, "openMP_MM",0);
run_algo(MM_dc, "MM_dc",0);
+
run_algo(strassen, "strassen",0);
run_algo(MM, "MM", 0);
- run_algo(winograd, "winograd", 0);
- run_algo_cblas(0);
+ run_algo(winograd, "winograd", 0);
+ run_algo_cblas(0);
return 0;
}
@@ -414,12 +415,12 @@ void run_algo(void (*algo)(), char alog_name[], int print)
for(int i=0; i<n_arrays; ++i)
{
- for(int j = 0; j<1; ++j)
+ for(int j = 0; j<10; ++j)
{
- int *C = (int*) malloc(n[i] * n[i] * sizeof(int));
- double dtime = omp_get_wtime();
- algo(Ap[i], Bp[i], (int*) C, n[i]);
- dtime = omp_get_wtime() - dtime;
+ int *C = (int*) malloc(n[i] * n[i] * sizeof(int));
+ double dtime = omp_get_wtime();
+ algo(Ap[i], Bp[i], (int*) C, n[i]);
+ dtime = omp_get_wtime() - dtime;
// printf("The %s program took %f seconds to execute \n", alog_name, dtime);
fprintf(fptr, "%f,%d\n", dtime, n[i]);
@@ -428,7 +429,7 @@ void run_algo(void (*algo)(), char alog_name[], int print)
printMatrix((int*)C, n[i]);
}
free(C);
- }
+ }
}
fclose(fptr);
@@ -442,7 +443,7 @@ void run_algo_cblas(int print)
fptr = fopen("meas/blas.txt", "w");
for(int i=0; i<n_arrays; ++i)
{
- for(int j = 0; j<1; ++j)
+ for(int j = 0; j<10; ++j)
{
double *dC = (double*) malloc(n[i] * n[i] * sizeof(double));
double dtime = omp_get_wtime();
diff --git a/buch/papers/multiplikation/code/MM.py b/buch/papers/multiplikation/code/MM.py
index 7220ae1..8a6824a 100644
--- a/buch/papers/multiplikation/code/MM.py
+++ b/buch/papers/multiplikation/code/MM.py
@@ -5,6 +5,7 @@ Created on Fri Mar 19 07:31:29 2021
@author: nunigan
"""
+import scipy.stats
import numpy as np
import time
import matplotlib.pyplot as plt
@@ -133,9 +134,6 @@ def winograd2(A, B):
def test_perfomance(n):
- import mkl
- mkl.set_num_threads(1)
-
t_mm = []
t_mm_dc = []
t_mm_strassen = []
@@ -148,21 +146,21 @@ def test_perfomance(n):
# A = np.random.randint(-100, 100,(i, i))
# B = np.random.randint(-100, 100,(i, i))
- # start = time.time()
- # C3 = strassen(A, B)
- # t_mm_strassen.append(time.time() - start)
+ start = time.time()
+ C3 = strassen(A, B)
+ t_mm_strassen.append(time.time() - start)
- # start = time.time()
- # C1 = MM(A, B)
- # t_mm.append(time.time() - start)
+ start = time.time()
+ C1 = MM(A, B)
+ t_mm.append(time.time() - start)
- # start = time.time()
- # C2 = MM_dc(A, B)
- # t_mm_dc.append(time.time() - start)
+ start = time.time()
+ C2 = MM_dc(A, B)
+ t_mm_dc.append(time.time() - start)
- # start = time.time()
- # C4 = winograd2(A, B)
- # t_wino.append(time.time() - start)
+ start = time.time()
+ C4 = winograd2(A, B)
+ t_wino.append(time.time() - start)
start = time.time()
C = A@B
@@ -173,10 +171,10 @@ def test_perfomance(n):
plt.rc('axes', labelsize=23)
plt.rc('xtick', labelsize=23)
plt.rc('ytick', labelsize=23)
- # plt.plot(n, t_mm, label='Standard', lw=5)
- # plt.plot(n, t_mm_dc, label='Divide and conquer', lw=5)
- # plt.plot(n, t_mm_strassen, label='Strassen', lw=5)
- # plt.plot(n, t_wino, label='Winograd', lw=5)
+ plt.plot(n, t_mm, label='Standard', lw=5)
+ plt.plot(n, t_mm_dc, label='Divide and conquer', lw=5)
+ plt.plot(n, t_mm_strassen, label='Strassen', lw=5)
+ plt.plot(n, t_wino, label='Winograd', lw=5)
plt.plot(n, t_np, label='NumPy A@B', lw=5)
# plt.xscale('log', base=2)
plt.legend()
@@ -186,9 +184,9 @@ def test_perfomance(n):
plt.tight_layout()
# plt.yscale('log')
plt.legend(fontsize=19)
- # plt.savefig('meas_' + str(max(n))+ '.pdf')
- # arr = np.array([n, t_mm, t_mm_dc, t_mm_strassen, t_wino, t_np])
- # np.savetxt('meas_' + str(max(n))+ '.txt',arr)
+ plt.savefig('meas_' + str(max(n))+ '.pdf')
+ arr = np.array([n, t_mm, t_mm_dc, t_mm_strassen, t_wino, t_np])
+ np.savetxt('meas_' + str(max(n))+ '.txt',arr)
return t_np
@@ -249,6 +247,8 @@ def plot_c_res(ave, num):
# blas_t = np.mean(blas_t.reshape(-1,ave),axis=1)
# blas_n = np.mean(blas_n.reshape(-1,ave),axis=1)
+
+
def func(x, a,b):
return b*x**a
@@ -261,11 +261,11 @@ def plot_c_res(ave, num):
plt.rc('axes', labelsize=23)
plt.rc('xtick', labelsize=23)
plt.rc('ytick', labelsize=23)
- plt.loglog(MM_n, MM_t, label='3 For Loops', lw=5)
- plt.loglog(winograd_n, winograd_t, label='Winograd MM', lw=5)
- plt.loglog(blas_n, blas_t, label='Blas', lw=5)
- plt.loglog(strassen_n, strassen_t, label='Strassen', lw=5)
- plt.loglog(MM_dc_n, MM_dc_t, label='Divide and Conquer', lw=5)
+ plt.loglog(MM_n, MM_t, '.', label='3 For Loops', lw=5)
+ plt.loglog(winograd_n, winograd_t, '.', label='Winograd MM', lw=5)
+ plt.loglog(blas_n, blas_t, '.', label='Blas', lw=5)
+ plt.loglog(strassen_n, strassen_t, '.', label='Strassen', lw=5)
+ plt.loglog(MM_dc_n, MM_dc_t, '.', label='Divide and Conquer', lw=5)
plt.xlabel("n")
# plt.yscale('log', base=10)
# plt.xscale('log', base=2)
@@ -281,16 +281,31 @@ def plot_c_res(ave, num):
plt.legend()
# return [MM_n,winograd_n,blas_n,strassen_n,MM_dc_n]
+
+
return [MM_t,winograd_t,blas_t,strassen_t,MM_dc_t]
+def mean_confidence_interval(data, confidence=0.95):
+ a = 1.0 * np.array(data)
+ n = len(a)
+ m, se = np.mean(a), scipy.stats.sem(a)
+ h = se * scipy.stats.t.ppf((1 + confidence) / 2., n-1)
+ return m, m-h, m+h
+
# test%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if __name__ == '__main__':
- # A = plot_c_res(1, 4096)
-
-
- arr = plot(1024)
+ A = plot_c_res(10, 4096)
+ name = ['MM', 'Wino', 'blas', 'strassen', 'dc']
+ for i in range(5):
+ ci_inner = []
+ for j in range(11):
+ ci_inner.append(mean_confidence_interval(A[i][j*10:(j+1)*10]))
+ np.savetxt('meas/ci/' + name[i]+'.txt',ci_inner)
+
+ # arr = plot(1024)
# n = np.logspace(1,12,12,base=2,dtype=(np.int))
+ # n=[2048,4096]
# n = np.arange(1,50,2)
# A = np.random.randint(-10, 6, (5,3))
# B = np.random.randint(-10, 6, (3,5))
diff --git a/buch/papers/multiplikation/code/c_matrix.h b/buch/papers/multiplikation/code/c_matrix.h
index 14389fc..63d5390 100644
--- a/buch/papers/multiplikation/code/c_matrix.h
+++ b/buch/papers/multiplikation/code/c_matrix.h
@@ -1,101 +1,177 @@
-/* Seminar Matrizen, autogenerated File, Michael Schmid, 02/08/2021, 22:48:43 */
+/* Seminar Matrizen, autogenerated File, Michael Schmid, 10/08/2021, 05:46:32 */
#include <stdint.h>
const int A0[][2] =
{
- {75,47},
- {-41,-24}
+ {60,-84},
+ {-66,-1}
};
const int B0[][2] =
{
- {-53,-95},
- {-93,30}
+ {-45,87},
+ {-38,-73}
};
const double dB0[][2] =
{
- {-53,-95},
- {-93,30}
+ {-45,87},
+ {-38,-73}
};
const double dA0[][2] =
{
- {75,47},
- {-41,-24}
+ {60,-84},
+ {-66,-1}
};
const int A1[][4] =
{
- {47,11,-66,8},
- {36,98,39,82},
- {-32,12,40,-79},
- {61,-20,-85,-98}
+ {-72,-19,-91,62},
+ {-36,-74,-44,-47},
+ {-39,-31,50,-93},
+ {-81,2,-17,-86}
};
const int B1[][4] =
{
- {37,75,-53,9},
- {37,-33,-67,38},
- {70,39,-93,43},
- {43,41,23,-4}
+ {-66,39,-23,52},
+ {-88,-13,13,-13},
+ {-45,-70,28,-20},
+ {96,5,88,96}
};
const double dB1[][4] =
{
- {37,75,-53,9},
- {37,-33,-67,38},
- {70,39,-93,43},
- {43,41,23,-4}
+ {-66,39,-23,52},
+ {-88,-13,13,-13},
+ {-45,-70,28,-20},
+ {96,5,88,96}
};
const double dA1[][4] =
{
- {47,11,-66,8},
- {36,98,39,82},
- {-32,12,40,-79},
- {61,-20,-85,-98}
+ {-72,-19,-91,62},
+ {-36,-74,-44,-47},
+ {-39,-31,50,-93},
+ {-81,2,-17,-86}
};
const int A2[][8] =
{
- {-54,-87,87,69,52,-21,-86,55},
- {19,-75,-61,-50,-55,-23,66,-92},
- {-73,-67,-36,19,84,-11,24,46},
- {-98,62,-76,57,-100,6,-23,-51},
- {62,46,1,-64,42,-9,85,-12},
- {35,-59,-17,-47,78,86,-50,74},
- {-15,45,33,-59,-9,-81,49,96},
- {-57,22,-43,7,-30,-45,-5,13}
+ {-36,-2,-58,-32,34,-89,49,-55},
+ {-68,-73,52,-3,-51,-37,-31,70},
+ {73,-90,-21,-79,-15,96,-99,12},
+ {68,-25,38,-73,-60,35,-99,72},
+ {-43,-87,48,-84,-100,37,80,53},
+ {-27,88,-5,-82,-57,-27,20,10},
+ {-91,-47,54,-90,-99,-76,50,-18},
+ {69,-36,76,5,-67,-38,-95,91}
};
const int B2[][8] =
{
- {-71,-82,-80,-78,83,-97,48,-24},
- {15,75,15,-60,-63,-53,1,-50},
- {-84,63,67,-2,78,93,-13,95},
- {61,-26,-88,56,56,27,26,1},
- {2,54,21,36,9,-41,53,53},
- {85,-11,42,-51,-6,3,27,97},
- {10,-2,90,-76,-75,0,8,-37},
- {10,-64,47,-69,66,-50,89,-66}
+ {-84,22,-13,-66,-42,51,66,0},
+ {37,-65,66,-85,-10,-23,77,5},
+ {1,41,-79,0,63,-37,-10,29},
+ {72,66,-99,92,-28,65,25,-40},
+ {69,-49,65,-18,64,-97,-47,30},
+ {36,86,66,-12,-17,89,1,-37},
+ {-100,11,27,23,-75,-23,96,-9},
+ {68,90,-87,-99,-70,-28,98,-76}
};
const double dB2[][8] =
{
- {-71,-82,-80,-78,83,-97,48,-24},
- {15,75,15,-60,-63,-53,1,-50},
- {-84,63,67,-2,78,93,-13,95},
- {61,-26,-88,56,56,27,26,1},
- {2,54,21,36,9,-41,53,53},
- {85,-11,42,-51,-6,3,27,97},
- {10,-2,90,-76,-75,0,8,-37},
- {10,-64,47,-69,66,-50,89,-66}
+ {-84,22,-13,-66,-42,51,66,0},
+ {37,-65,66,-85,-10,-23,77,5},
+ {1,41,-79,0,63,-37,-10,29},
+ {72,66,-99,92,-28,65,25,-40},
+ {69,-49,65,-18,64,-97,-47,30},
+ {36,86,66,-12,-17,89,1,-37},
+ {-100,11,27,23,-75,-23,96,-9},
+ {68,90,-87,-99,-70,-28,98,-76}
};
const double dA2[][8] =
{
- {-54,-87,87,69,52,-21,-86,55},
- {19,-75,-61,-50,-55,-23,66,-92},
- {-73,-67,-36,19,84,-11,24,46},
- {-98,62,-76,57,-100,6,-23,-51},
- {62,46,1,-64,42,-9,85,-12},
- {35,-59,-17,-47,78,86,-50,74},
- {-15,45,33,-59,-9,-81,49,96},
- {-57,22,-43,7,-30,-45,-5,13}
- };
-const int *Ap[3] = {(int*) A0,(int*) A1,(int*) A2};
-const int *Bp[3] = {(int*) B0,(int*) B1,(int*) B2};
-const double *dAp[3] = {(double*) dA0,(double*) dA1,(double*) dA2};
-const double *dBp[3] = {(double*) dB0,(double*) dB1,(double*) dB2};
-int n[3] = {2,4,8};
-int n_arrays = 3;
+ {-36,-2,-58,-32,34,-89,49,-55},
+ {-68,-73,52,-3,-51,-37,-31,70},
+ {73,-90,-21,-79,-15,96,-99,12},
+ {68,-25,38,-73,-60,35,-99,72},
+ {-43,-87,48,-84,-100,37,80,53},
+ {-27,88,-5,-82,-57,-27,20,10},
+ {-91,-47,54,-90,-99,-76,50,-18},
+ {69,-36,76,5,-67,-38,-95,91}
+ };
+const int A3[][16] =
+ {
+ {-24,65,21,19,94,70,-90,-81,53,-41,-23,-1,58,-80,-54,59},
+ {-42,76,-19,98,29,-56,92,14,45,11,82,83,48,-13,81,66},
+ {43,-57,-67,95,5,72,11,0,-47,55,-24,36,84,54,-31,-54},
+ {-39,-40,19,97,-82,-56,27,95,81,-21,-50,-74,-35,-87,-28,-26},
+ {-74,-98,79,92,-24,-48,99,94,55,-83,70,98,-24,18,-67,14},
+ {20,76,11,-23,-56,21,0,42,64,86,-74,44,93,-76,-30,97},
+ {13,20,-73,-11,-30,80,53,-8,60,21,17,-42,82,-72,-6,-80},
+ {36,-93,-64,-21,20,-85,15,24,99,81,-52,64,71,-56,52,63},
+ {32,9,-2,-85,17,62,-98,-35,75,-58,-44,-20,-47,89,-95,52},
+ {93,-43,86,68,-6,-25,90,57,60,-10,65,-97,43,46,-60,-41},
+ {43,-33,0,50,-100,26,-60,95,39,-70,-61,-81,9,-23,-99,-4},
+ {20,61,15,43,-96,93,-55,38,-29,-1,-10,26,-87,18,64,6},
+ {-98,-84,51,16,-14,86,52,59,44,-39,-2,10,82,-66,54,19},
+ {89,-49,-37,-6,-53,40,-11,46,-51,-56,86,34,11,13,-20,-49},
+ {-90,14,28,-45,-25,-56,-51,-61,28,-8,51,91,95,-10,-85,58},
+ {8,-44,88,-71,-27,11,89,37,86,-78,-44,-56,-87,0,-42,-61}
+ };
+const int B3[][16] =
+ {
+ {62,-30,62,92,29,-93,-95,44,-33,-88,-29,9,-88,-42,-90,-70},
+ {60,37,-44,-93,-87,6,-53,2,-29,53,-49,59,6,83,-15,50},
+ {-19,85,-49,-14,84,-4,12,88,-83,-81,-24,-16,-12,-42,-63,-71},
+ {-42,-78,-58,-61,-29,67,-28,-46,64,7,6,-13,88,-42,95,-24},
+ {-90,-56,8,-30,-89,70,37,-29,24,-8,-10,-2,-25,-63,-95,-91},
+ {10,-81,42,-28,-13,-68,-72,-20,-22,5,-79,-50,-88,62,57,69},
+ {-67,24,-71,-43,11,48,33,-93,-82,-65,-4,5,-15,25,-54,-45},
+ {-49,19,-29,90,-97,-87,78,-39,-75,-85,-79,-35,54,3,-73,7},
+ {-7,39,70,-42,32,-100,56,4,-24,-57,38,-49,-50,-44,79,-42},
+ {37,-65,-55,22,-97,-42,-76,95,97,-27,38,11,0,-81,-23,35},
+ {26,-70,10,-29,47,-70,-52,29,-13,-18,5,34,18,32,87,91},
+ {-84,41,-19,96,-51,-19,81,75,81,92,2,-40,-42,-69,-10,-61},
+ {-30,98,71,-51,91,-59,58,86,86,-22,-84,7,66,-55,-52,23},
+ {-71,-44,-9,90,26,18,26,-10,-85,64,-47,3,72,81,74,-8},
+ {52,-59,-91,22,8,-63,84,9,-11,-54,-78,-71,-98,42,96,57},
+ {18,-39,34,-50,-62,-96,-2,-78,52,94,-33,2,-19,-9,-86,-75}
+ };
+const double dB3[][16] =
+ {
+ {62,-30,62,92,29,-93,-95,44,-33,-88,-29,9,-88,-42,-90,-70},
+ {60,37,-44,-93,-87,6,-53,2,-29,53,-49,59,6,83,-15,50},
+ {-19,85,-49,-14,84,-4,12,88,-83,-81,-24,-16,-12,-42,-63,-71},
+ {-42,-78,-58,-61,-29,67,-28,-46,64,7,6,-13,88,-42,95,-24},
+ {-90,-56,8,-30,-89,70,37,-29,24,-8,-10,-2,-25,-63,-95,-91},
+ {10,-81,42,-28,-13,-68,-72,-20,-22,5,-79,-50,-88,62,57,69},
+ {-67,24,-71,-43,11,48,33,-93,-82,-65,-4,5,-15,25,-54,-45},
+ {-49,19,-29,90,-97,-87,78,-39,-75,-85,-79,-35,54,3,-73,7},
+ {-7,39,70,-42,32,-100,56,4,-24,-57,38,-49,-50,-44,79,-42},
+ {37,-65,-55,22,-97,-42,-76,95,97,-27,38,11,0,-81,-23,35},
+ {26,-70,10,-29,47,-70,-52,29,-13,-18,5,34,18,32,87,91},
+ {-84,41,-19,96,-51,-19,81,75,81,92,2,-40,-42,-69,-10,-61},
+ {-30,98,71,-51,91,-59,58,86,86,-22,-84,7,66,-55,-52,23},
+ {-71,-44,-9,90,26,18,26,-10,-85,64,-47,3,72,81,74,-8},
+ {52,-59,-91,22,8,-63,84,9,-11,-54,-78,-71,-98,42,96,57},
+ {18,-39,34,-50,-62,-96,-2,-78,52,94,-33,2,-19,-9,-86,-75}
+ };
+const double dA3[][16] =
+ {
+ {-24,65,21,19,94,70,-90,-81,53,-41,-23,-1,58,-80,-54,59},
+ {-42,76,-19,98,29,-56,92,14,45,11,82,83,48,-13,81,66},
+ {43,-57,-67,95,5,72,11,0,-47,55,-24,36,84,54,-31,-54},
+ {-39,-40,19,97,-82,-56,27,95,81,-21,-50,-74,-35,-87,-28,-26},
+ {-74,-98,79,92,-24,-48,99,94,55,-83,70,98,-24,18,-67,14},
+ {20,76,11,-23,-56,21,0,42,64,86,-74,44,93,-76,-30,97},
+ {13,20,-73,-11,-30,80,53,-8,60,21,17,-42,82,-72,-6,-80},
+ {36,-93,-64,-21,20,-85,15,24,99,81,-52,64,71,-56,52,63},
+ {32,9,-2,-85,17,62,-98,-35,75,-58,-44,-20,-47,89,-95,52},
+ {93,-43,86,68,-6,-25,90,57,60,-10,65,-97,43,46,-60,-41},
+ {43,-33,0,50,-100,26,-60,95,39,-70,-61,-81,9,-23,-99,-4},
+ {20,61,15,43,-96,93,-55,38,-29,-1,-10,26,-87,18,64,6},
+ {-98,-84,51,16,-14,86,52,59,44,-39,-2,10,82,-66,54,19},
+ {89,-49,-37,-6,-53,40,-11,46,-51,-56,86,34,11,13,-20,-49},
+ {-90,14,28,-45,-25,-56,-51,-61,28,-8,51,91,95,-10,-85,58},
+ {8,-44,88,-71,-27,11,89,37,86,-78,-44,-56,-87,0,-42,-61}
+ };
+const int *Ap[4] = {(int*) A0,(int*) A1,(int*) A2,(int*) A3};
+const int *Bp[4] = {(int*) B0,(int*) B1,(int*) B2,(int*) B3};
+const double *dAp[4] = {(double*) dA0,(double*) dA1,(double*) dA2,(double*) dA3};
+const double *dBp[4] = {(double*) dB0,(double*) dB1,(double*) dB2,(double*) dB3};
+int n[4] = {2,4,8,16};
+int n_arrays = 4;
diff --git a/buch/papers/multiplikation/code/c_meas_4096.pdf b/buch/papers/multiplikation/code/c_meas_4096.pdf
index 5236afb..b42082f 100644
Binary files a/buch/papers/multiplikation/code/c_meas_4096.pdf and b/buch/papers/multiplikation/code/c_meas_4096.pdf differ
diff --git a/buch/papers/multiplikation/code/ci.txt b/buch/papers/multiplikation/code/ci.txt
new file mode 100644
index 0000000..e69de29
diff --git a/buch/papers/multiplikation/code/helper_class.py b/buch/papers/multiplikation/code/helper_class.py
index 485fa76..ad67909 100755
--- a/buch/papers/multiplikation/code/helper_class.py
+++ b/buch/papers/multiplikation/code/helper_class.py
@@ -101,5 +101,6 @@ if __name__ == '__main__':
helper = Helper()
# n = np.arange(2,10)
- n = np.logspace(1,3,3,base=2,dtype=(np.int))
+ n = np.logspace(1,4,4,base=2,dtype=(np.int))
+ # n=[8192]
C = helper.write_c_matrix(n)
diff --git a/buch/papers/multiplikation/code/meas/MM.txt b/buch/papers/multiplikation/code/meas/MM.txt
index e296dd7..7bffb6e 100644
--- a/buch/papers/multiplikation/code/meas/MM.txt
+++ b/buch/papers/multiplikation/code/meas/MM.txt
@@ -1,12 +1,110 @@
-0.000001,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
0.000001,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000001,4
+0.000001,4
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000001,8
0.000001,8
-0.000010,16
-0.000081,32
-0.000654,64
-0.005556,128
-0.054253,256
-0.487317,512
-4.162845,1024
-125.909034,2048
-1111.312696,4096
+0.000011,16
+0.000011,16
+0.000011,16
+0.000011,16
+0.000011,16
+0.000021,16
+0.000011,16
+0.000011,16
+0.000011,16
+0.000011,16
+0.000090,32
+0.000093,32
+0.000083,32
+0.000082,32
+0.000090,32
+0.000080,32
+0.000080,32
+0.000080,32
+0.000089,32
+0.000126,32
+0.000771,64
+0.000651,64
+0.000651,64
+0.000651,64
+0.000731,64
+0.000673,64
+0.000745,64
+0.000672,64
+0.000671,64
+0.000707,64
+0.005642,128
+0.005579,128
+0.005768,128
+0.005745,128
+0.005518,128
+0.005877,128
+0.005513,128
+0.005850,128
+0.005769,128
+0.005581,128
+0.052188,256
+0.051988,256
+0.051888,256
+0.051518,256
+0.051709,256
+0.051543,256
+0.051707,256
+0.051845,256
+0.051495,256
+0.051834,256
+0.507020,512
+0.504111,512
+0.502049,512
+0.529743,512
+0.501028,512
+0.502097,512
+0.503490,512
+0.502079,512
+0.506688,512
+0.504163,512
+4.538722,1024
+4.291473,1024
+4.516302,1024
+4.374630,1024
+4.719557,1024
+4.438999,1024
+4.641680,1024
+4.407959,1024
+4.441451,1024
+4.677313,1024
+129.433279,2048
+129.277802,2048
+129.284817,2048
+129.086884,2048
+129.197444,2048
+129.350999,2048
+129.264250,2048
+129.295723,2048
+129.402601,2048
+129.300820,2048
diff --git a/buch/papers/multiplikation/code/meas/MM_dc.txt b/buch/papers/multiplikation/code/meas/MM_dc.txt
index f6be928..b78b925 100644
--- a/buch/papers/multiplikation/code/meas/MM_dc.txt
+++ b/buch/papers/multiplikation/code/meas/MM_dc.txt
@@ -1,12 +1,110 @@
0.000003,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
0.000002,4
-0.000010,8
-0.000068,16
-0.000594,32
-0.004264,64
-0.036289,128
-0.324645,256
-2.612010,512
-19.928951,1024
-159.333884,2048
-1147.106865,4096
+0.000001,4
+0.000001,4
+0.000001,4
+0.000001,4
+0.000001,4
+0.000001,4
+0.000001,4
+0.000001,4
+0.000001,4
+0.000008,8
+0.000008,8
+0.000008,8
+0.000008,8
+0.000007,8
+0.000007,8
+0.000007,8
+0.000007,8
+0.000018,8
+0.000008,8
+0.000075,16
+0.000063,16
+0.000088,16
+0.000062,16
+0.000086,16
+0.000092,16
+0.000081,16
+0.000080,16
+0.000070,16
+0.000085,16
+0.000581,32
+0.000659,32
+0.000584,32
+0.000714,32
+0.000666,32
+0.000574,32
+0.000616,32
+0.000534,32
+0.000506,32
+0.000506,32
+0.004567,64
+0.004502,64
+0.004332,64
+0.004578,64
+0.004543,64
+0.004426,64
+0.004497,64
+0.004329,64
+0.004288,64
+0.004277,64
+0.036456,128
+0.034901,128
+0.034545,128
+0.034283,128
+0.035150,128
+0.034663,128
+0.034901,128
+0.034022,128
+0.034368,128
+0.035154,128
+0.296292,256
+0.297592,256
+0.302464,256
+0.299557,256
+0.299367,256
+0.306394,256
+0.287616,256
+0.292630,256
+0.289542,256
+0.277019,256
+2.331956,512
+2.224501,512
+2.203910,512
+2.198937,512
+2.206083,512
+2.199477,512
+2.199847,512
+2.225379,512
+2.202491,512
+2.235926,512
+17.649432,1024
+17.636769,1024
+17.639024,1024
+17.625402,1024
+17.722286,1024
+17.611777,1024
+17.653120,1024
+17.748270,1024
+17.691817,1024
+17.614448,1024
+141.943689,2048
+141.580812,2048
+141.882050,2048
+141.516253,2048
+141.351237,2048
+141.641167,2048
+141.596407,2048
+141.607048,2048
+141.469723,2048
+141.515550,2048
diff --git a/buch/papers/multiplikation/code/meas/blas.txt b/buch/papers/multiplikation/code/meas/blas.txt
index 92a61b9..9414d8f 100644
--- a/buch/papers/multiplikation/code/meas/blas.txt
+++ b/buch/papers/multiplikation/code/meas/blas.txt
@@ -1,12 +1,110 @@
0.000001,2
-0.000001,4
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
0.000001,8
+0.000000,8
+0.000000,8
+0.000000,8
+0.000000,8
+0.000000,8
+0.000000,8
+0.000000,8
+0.000000,8
+0.000000,8
0.000003,16
-0.000022,32
-0.000179,64
+0.000003,16
+0.000003,16
+0.000003,16
+0.000003,16
+0.000003,16
+0.000012,16
+0.000003,16
+0.000003,16
+0.000003,16
+0.000021,32
+0.000019,32
+0.000030,32
+0.000020,32
+0.000020,32
+0.000020,32
+0.000020,32
+0.000020,32
+0.000020,32
+0.000020,32
+0.000180,64
+0.000192,64
+0.000163,64
+0.000153,64
+0.000153,64
+0.000197,64
+0.000163,64
+0.000267,64
+0.000226,64
+0.000164,64
+0.001216,128
+0.001233,128
+0.001364,128
0.001278,128
-0.010165,256
-0.074739,512
-0.704748,1024
-6.845095,2048
-55.845038,4096
+0.001211,128
+0.001295,128
+0.001206,128
+0.001371,128
+0.001225,128
+0.001250,128
+0.009733,256
+0.009497,256
+0.009586,256
+0.009600,256
+0.009768,256
+0.009566,256
+0.009731,256
+0.009550,256
+0.009664,256
+0.009794,256
+0.077453,512
+0.076616,512
+0.088812,512
+0.075990,512
+0.076925,512
+0.076303,512
+0.075915,512
+0.075600,512
+0.075122,512
+0.075029,512
+0.769186,1024
+0.775780,1024
+0.753906,1024
+0.757834,1024
+0.772001,1024
+0.770950,1024
+0.791317,1024
+0.753319,1024
+0.747228,1024
+0.752347,1024
+7.625205,2048
+7.652278,2048
+7.640682,2048
+7.649428,2048
+7.632806,2048
+7.579347,2048
+7.612317,2048
+7.676742,2048
+7.632979,2048
+7.619210,2048
diff --git a/buch/papers/multiplikation/code/meas/ci/MM.txt b/buch/papers/multiplikation/code/meas/ci/MM.txt
new file mode 100644
index 0000000..e4ad1ba
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/ci/MM.txt
@@ -0,0 +1,11 @@
+0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00
+2.999999999999999864e-07 -4.555021440490437016e-08 6.455502144049043430e-07
+1.800000000000000130e-06 1.498379044967867836e-06 2.101620955032132425e-06
+1.199999999999999861e-05 9.737842837259007037e-06 1.426215716274099018e-05
+8.930000000000000221e-05 7.942767152586658090e-05 9.917232847413342352e-05
+6.922999999999999684e-04 6.611729768299406300e-04 7.234270231700593067e-04
+5.684200000000000363e-03 5.587928563282692010e-03 5.780471436717308717e-03
+5.177150000000000502e-02 5.161257221154376407e-02 5.193042778845624596e-02
+5.062468000000001078e-01 5.001729723042721565e-01 5.123206276957280592e-01
+4.504808599999999608e+00 4.404751183933223402e+00 4.604866016066775813e+00
+1.292894618999999921e+02 1.292188312556721144e+02 1.293600925443278697e+02
diff --git a/buch/papers/multiplikation/code/meas/ci/Wino.txt b/buch/papers/multiplikation/code/meas/ci/Wino.txt
new file mode 100644
index 0000000..4ec0106
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/ci/Wino.txt
@@ -0,0 +1,11 @@
+9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07
+0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00
+2.000000000000000333e-06 1.999999999999999909e-06 2.000000000000000757e-06
+1.199999999999999861e-05 9.737842837259007037e-06 1.426215716274099018e-05
+8.329999999999999189e-05 7.952898408510092581e-05 8.707101591489905797e-05
+6.478999999999999733e-04 6.173195729945008762e-04 6.784804270054990705e-04
+5.287299999999999986e-03 5.226513788941518357e-03 5.348086211058481615e-03
+5.267459999999999504e-02 5.240389179019239174e-02 5.294530820980759833e-02
+5.249752000000000862e-01 5.233835466989910090e-01 5.265668533010091634e-01
+4.671160999999999675e+00 4.572509907501117965e+00 4.769812092498881384e+00
+1.366769777000000090e+02 1.363957928284978891e+02 1.369581625715021289e+02
diff --git a/buch/papers/multiplikation/code/meas/ci/blas.txt b/buch/papers/multiplikation/code/meas/ci/blas.txt
new file mode 100644
index 0000000..5d7ff7b
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/ci/blas.txt
@@ -0,0 +1,11 @@
+9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07
+0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00
+9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07
+3.899999999999999929e-06 1.864058553533107683e-06 5.935941446466892176e-06
+2.100000000000000223e-05 1.871284586667546976e-05 2.328715413332453469e-05
+1.858000000000000168e-04 1.595988766828141249e-04 2.120011233171859087e-04
+1.264900000000000009e-03 1.221091632895032926e-03 1.308708367104967091e-03
+9.648900000000000185e-03 9.575266909835235610e-03 9.722533090164764760e-03
+7.737650000000000083e-02 7.445101996220353235e-02 8.030198003779646931e-02
+7.643868000000000329e-01 7.545731380187049586e-01 7.742004619812951072e-01
+7.632099399999999534e+00 7.613379481172315444e+00 7.650819318827683624e+00
diff --git a/buch/papers/multiplikation/code/meas/ci/dc.txt b/buch/papers/multiplikation/code/meas/ci/dc.txt
new file mode 100644
index 0000000..df268a9
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/ci/dc.txt
@@ -0,0 +1,11 @@
+2.999999999999999864e-07 -3.786471488222973584e-07 9.786471488222972253e-07
+1.100000000000000056e-06 8.737842837259009412e-07 1.326215716274099171e-06
+8.600000000000000670e-06 6.210712693650135778e-06 1.098928730634986641e-05
+7.819999999999998990e-05 7.075203863371232107e-05 8.564796136628765873e-05
+5.940000000000001269e-04 5.439534118129448707e-04 6.440465881870553830e-04
+4.433900000000000167e-03 4.349138038034851966e-03 4.518661961965148369e-03
+3.484430000000000166e-02 3.435947773230259988e-02 3.532912226769740344e-02
+2.948473000000000344e-01 2.887830472415335303e-01 3.009115527584665384e-01
+2.222850699999999957e+00 2.193855611791002858e+00 2.251845788208997057e+00
+1.765923450000000372e+01 1.762601016688562439e+01 1.769245883311438305e+01
+1.416103936000000090e+02 1.414816028568733657e+02 1.417391843431266523e+02
diff --git a/buch/papers/multiplikation/code/meas/ci/strassen.txt b/buch/papers/multiplikation/code/meas/ci/strassen.txt
new file mode 100644
index 0000000..983fed9
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/ci/strassen.txt
@@ -0,0 +1,11 @@
+0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00
+2.099999999999999799e-06 1.572163328693768390e-06 2.627836671306231420e-06
+1.130000000000000023e-05 7.484018077564905836e-06 1.511598192243509547e-05
+7.069999999999999733e-05 6.500652995675561090e-05 7.639347004324438376e-05
+5.040999999999999474e-04 4.766428619697257881e-04 5.315571380302741610e-04
+3.595999999999999804e-03 3.528938496002300557e-03 3.663061503997699052e-03
+2.544810000000000128e-02 2.513634544137222787e-02 2.575985455862777468e-02
+1.781816999999999984e-01 1.773043765864557864e-01 1.790590234135442105e-01
+1.255500000000000060e+00 1.247847949398645628e+00 1.263152050601354492e+00
+8.830237099999999728e+00 8.790366960647805428e+00 8.870107239352194028e+00
+6.190186909999999898e+01 6.183048085945843297e+01 6.197325734054156499e+01
diff --git a/buch/papers/multiplikation/code/meas/old/8196/MM.txt b/buch/papers/multiplikation/code/meas/old/8196/MM.txt
new file mode 100644
index 0000000..0edf9f6
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/8196/MM.txt
@@ -0,0 +1 @@
+9376.173434,8192
diff --git a/buch/papers/multiplikation/code/meas/old/8196/MM_dc.txt b/buch/papers/multiplikation/code/meas/old/8196/MM_dc.txt
new file mode 100644
index 0000000..36f6ff0
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/8196/MM_dc.txt
@@ -0,0 +1 @@
+9606.402522,8192
diff --git a/buch/papers/multiplikation/code/meas/old/8196/blas.txt b/buch/papers/multiplikation/code/meas/old/8196/blas.txt
new file mode 100644
index 0000000..b5989fb
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/8196/blas.txt
@@ -0,0 +1 @@
+478.429957,8192
diff --git a/buch/papers/multiplikation/code/meas/old/8196/strassen.txt b/buch/papers/multiplikation/code/meas/old/8196/strassen.txt
new file mode 100644
index 0000000..ca06e97
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/8196/strassen.txt
@@ -0,0 +1 @@
+3014.235467,8192
diff --git a/buch/papers/multiplikation/code/meas/old/8196/winograd.txt b/buch/papers/multiplikation/code/meas/old/8196/winograd.txt
new file mode 100644
index 0000000..2a529c4
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/8196/winograd.txt
@@ -0,0 +1 @@
+10071.512655,8192
diff --git a/buch/papers/multiplikation/code/meas/old/MM.txt b/buch/papers/multiplikation/code/meas/old/MM.txt
new file mode 100644
index 0000000..e296dd7
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/MM.txt
@@ -0,0 +1,12 @@
+0.000001,2
+0.000001,4
+0.000001,8
+0.000010,16
+0.000081,32
+0.000654,64
+0.005556,128
+0.054253,256
+0.487317,512
+4.162845,1024
+125.909034,2048
+1111.312696,4096
diff --git a/buch/papers/multiplikation/code/meas/old/MM_dc.txt b/buch/papers/multiplikation/code/meas/old/MM_dc.txt
new file mode 100644
index 0000000..f6be928
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/MM_dc.txt
@@ -0,0 +1,12 @@
+0.000003,2
+0.000002,4
+0.000010,8
+0.000068,16
+0.000594,32
+0.004264,64
+0.036289,128
+0.324645,256
+2.612010,512
+19.928951,1024
+159.333884,2048
+1147.106865,4096
diff --git a/buch/papers/multiplikation/code/meas/old/blas.txt b/buch/papers/multiplikation/code/meas/old/blas.txt
new file mode 100644
index 0000000..92a61b9
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/blas.txt
@@ -0,0 +1,12 @@
+0.000001,2
+0.000001,4
+0.000001,8
+0.000003,16
+0.000022,32
+0.000179,64
+0.001278,128
+0.010165,256
+0.074739,512
+0.704748,1024
+6.845095,2048
+55.845038,4096
diff --git a/buch/papers/multiplikation/code/meas/old/strassen.txt b/buch/papers/multiplikation/code/meas/old/strassen.txt
new file mode 100644
index 0000000..fdfbf2b
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/strassen.txt
@@ -0,0 +1,12 @@
+0.000001,2
+0.000003,4
+0.000010,8
+0.000066,16
+0.000470,32
+0.003368,64
+0.024232,128
+0.172000,256
+1.209262,512
+8.457472,1024
+59.267256,2048
+414.648901,4096
diff --git a/buch/papers/multiplikation/code/meas/old/winograd.txt b/buch/papers/multiplikation/code/meas/old/winograd.txt
new file mode 100644
index 0000000..d185906
--- /dev/null
+++ b/buch/papers/multiplikation/code/meas/old/winograd.txt
@@ -0,0 +1,12 @@
+0.000001,2
+0.000001,4
+0.000002,8
+0.000011,16
+0.000100,32
+0.000654,64
+0.005229,128
+0.057440,256
+0.517850,512
+4.539413,1024
+130.627663,2048
+1179.261048,4096
diff --git a/buch/papers/multiplikation/code/meas/strassen.txt b/buch/papers/multiplikation/code/meas/strassen.txt
index fdfbf2b..d6e040e 100644
--- a/buch/papers/multiplikation/code/meas/strassen.txt
+++ b/buch/papers/multiplikation/code/meas/strassen.txt
@@ -1,12 +1,110 @@
-0.000001,2
-0.000003,4
-0.000010,8
-0.000066,16
-0.000470,32
-0.003368,64
-0.024232,128
-0.172000,256
-1.209262,512
-8.457472,1024
-59.267256,2048
-414.648901,4096
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000004,4
+0.000002,4
+0.000002,4
+0.000002,4
+0.000002,4
+0.000002,4
+0.000002,4
+0.000002,4
+0.000002,4
+0.000001,4
+0.000020,8
+0.000018,8
+0.000008,8
+0.000008,8
+0.000008,8
+0.000008,8
+0.000008,8
+0.000008,8
+0.000008,8
+0.000019,8
+0.000080,16
+0.000075,16
+0.000078,16
+0.000085,16
+0.000065,16
+0.000065,16
+0.000065,16
+0.000064,16
+0.000065,16
+0.000065,16
+0.000546,32
+0.000480,32
+0.000563,32
+0.000551,32
+0.000502,32
+0.000504,32
+0.000463,32
+0.000462,32
+0.000508,32
+0.000462,32
+0.003675,64
+0.003665,64
+0.003493,64
+0.003708,64
+0.003465,64
+0.003502,64
+0.003710,64
+0.003537,64
+0.003637,64
+0.003568,64
+0.025342,128
+0.025179,128
+0.026475,128
+0.025758,128
+0.025333,128
+0.024988,128
+0.025727,128
+0.025298,128
+0.025283,128
+0.025098,128
+0.181311,256
+0.178432,256
+0.177075,256
+0.177474,256
+0.177025,256
+0.177805,256
+0.177944,256
+0.178151,256
+0.177858,256
+0.178742,256
+1.283374,512
+1.246682,512
+1.245898,512
+1.251547,512
+1.250288,512
+1.250495,512
+1.257037,512
+1.255247,512
+1.255382,512
+1.259050,512
+8.784102,1024
+8.845725,1024
+8.771100,1024
+8.770184,1024
+8.955977,1024
+8.849161,1024
+8.806902,1024
+8.808937,1024
+8.848900,1024
+8.861383,1024
+61.787123,2048
+61.972599,2048
+61.822434,2048
+62.051331,2048
+61.946171,2048
+61.911404,2048
+61.872671,2048
+61.791260,2048
+61.818110,2048
+62.045588,2048
diff --git a/buch/papers/multiplikation/code/meas/winograd.txt b/buch/papers/multiplikation/code/meas/winograd.txt
index d185906..970a3f4 100644
--- a/buch/papers/multiplikation/code/meas/winograd.txt
+++ b/buch/papers/multiplikation/code/meas/winograd.txt
@@ -1,12 +1,110 @@
0.000001,2
-0.000001,4
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,2
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
+0.000000,4
0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000002,8
+0.000011,16
+0.000011,16
+0.000011,16
+0.000011,16
+0.000011,16
+0.000011,16
+0.000011,16
+0.000021,16
+0.000011,16
0.000011,16
-0.000100,32
-0.000654,64
-0.005229,128
-0.057440,256
-0.517850,512
-4.539413,1024
-130.627663,2048
-1179.261048,4096
+0.000092,32
+0.000092,32
+0.000081,32
+0.000081,32
+0.000081,32
+0.000081,32
+0.000088,32
+0.000079,32
+0.000079,32
+0.000079,32
+0.000670,64
+0.000739,64
+0.000609,64
+0.000609,64
+0.000700,64
+0.000648,64
+0.000626,64
+0.000626,64
+0.000626,64
+0.000626,64
+0.005321,128
+0.005286,128
+0.005180,128
+0.005223,128
+0.005249,128
+0.005299,128
+0.005205,128
+0.005268,128
+0.005464,128
+0.005378,128
+0.053123,256
+0.052325,256
+0.052729,256
+0.052930,256
+0.052207,256
+0.053178,256
+0.052122,256
+0.052681,256
+0.052965,256
+0.052486,256
+0.527028,512
+0.525201,512
+0.521822,512
+0.525147,512
+0.525241,512
+0.527725,512
+0.526321,512
+0.526479,512
+0.524020,512
+0.520768,512
+4.732299,1024
+4.617253,1024
+4.647425,1024
+4.519233,1024
+4.917471,1024
+4.564929,1024
+4.870771,1024
+4.555407,1024
+4.727473,1024
+4.559349,1024
+136.409028,2048
+136.390557,2048
+136.541672,2048
+136.598491,2048
+137.720790,2048
+136.825926,2048
+136.367686,2048
+136.650627,2048
+136.642195,2048
+136.622805,2048
diff --git a/buch/papers/multiplikation/code/meas_4096.pdf b/buch/papers/multiplikation/code/meas_4096.pdf
index e889d17..9e8fcea 100644
Binary files a/buch/papers/multiplikation/code/meas_4096.pdf and b/buch/papers/multiplikation/code/meas_4096.pdf differ
diff --git a/buch/papers/multiplikation/code/meas_4096.txt b/buch/papers/multiplikation/code/meas_4096.txt
index e69de29..cae1bc6 100644
--- a/buch/papers/multiplikation/code/meas_4096.txt
+++ b/buch/papers/multiplikation/code/meas_4096.txt
@@ -0,0 +1,6 @@
+2.048000000000000000e+03 4.096000000000000000e+03
+6.154183513402938843e+03 4.681333474493026733e+04
+7.375929301261901855e+03 5.846600176072120667e+04
+3.860573610544204712e+03 2.290433094644546509e+04
+4.884613198995590210e+03 4.359707747149467468e+04
+2.157390117645263672e-01 1.491588830947875977e+00
diff --git a/buch/papers/multiplikation/images/algo_tab.pdf b/buch/papers/multiplikation/images/algo_tab.pdf
new file mode 100644
index 0000000..7f2bb4f
Binary files /dev/null and b/buch/papers/multiplikation/images/algo_tab.pdf differ
diff --git a/buch/papers/multiplikation/images/algo_tab.tex b/buch/papers/multiplikation/images/algo_tab.tex
new file mode 100644
index 0000000..50ce392
--- /dev/null
+++ b/buch/papers/multiplikation/images/algo_tab.tex
@@ -0,0 +1,122 @@
+\documentclass{article}
+\usepackage[left=25mm,right=25mm,top=25mm,bottom=25mm]{geometry}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{times}
+\usepackage{geometry}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{algorithm}
+\usepackage{algpseudocode}
+\usepackage{mathrsfs}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{lipsum}
+\usepackage{amscd}
+\usepackage{graphicx}
+\usepackage{fancyhdr}
+\usepackage{textcomp}
+\usepackage{pgfplots}
+\usepackage{txfonts}
+\usepackage[all]{xy}
+\usepackage{paralist}
+\usepackage[colorlinks=true]{hyperref}
+\usepackage{array}
+\usepackage{tikz}
+\usepackage{slashed}
+\usepackage{pdfpages}
+\usepackage{multicol}
+\usepackage{cite}
+\usepackage{url}
+\usepackage{amsmath,amsfonts,amssymb}
+\usepackage{tikz}
+\usetikzlibrary{arrows,matrix,positioning}
+\usetikzlibrary{overlay-beamer-styles}
+\usetikzlibrary{matrix.skeleton}
+\usetikzlibrary{automata,positioning}
+\usetikzlibrary{decorations.text}
+\usepackage{listings}
+\usepackage{multirow}
+\usepackage{color}
+
+\begin{document}
+
+
+
+\begin{table}[t]
+ \begin{tabular}{ll}
+ \begin{minipage}{0.4\textwidth}
+ \begin{algorithm}[H]\footnotesize\caption{}
+ \label{multiplikation:alg:b1}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \Function{B1}{$a, b$}
+ \State \textbf{return} $a+b$
+ \EndFunction
+ \State
+ \State
+ \end{algorithmic}
+ \end{algorithm}
+ \end{minipage}
+ &
+ \begin{minipage}{0.4\textwidth}
+ \begin{algorithm}[H]\footnotesize\caption{}
+ \label{multiplikation:alg:b2}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \Function{B2}{$a, b$}
+ \State $ x \gets a+b $
+ \State $ y \gets a \cdot b $
+ \State \textbf{return} $x+y$
+ \EndFunction
+ \end{algorithmic}
+\end{algorithm}
+
+ \end{minipage}
+ \end{tabular}
+\end{table}
+
+\begin{table}
+ \begin{tabular}[t]{ll}
+ \begin{minipage}{0.4\textwidth}
+ \begin{algorithm}[H]\footnotesize\caption{}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \label{multiplikation:alg:linear}
+ \Function{L}{$\mathbf{a}, \mathbf{b}$,n}
+ \State $ sum \gets 0$
+ \For{$i = 0,1,2 \dots,n$}
+ \State $ sum \gets sum + A[i] \cdot B[i] $
+ \EndFor
+
+ \State \textbf{return} $sum$
+
+ \EndFunction
+ \State
+ \State
+ \end{algorithmic}
+ \end{algorithm}
+ \end{minipage}
+ &
+ \begin{minipage}{0.4\textwidth}
+ \begin{algorithm}[H]\footnotesize\caption{}
+ \label{multiplikation:alg:q1}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \Function{Q}{$\mathbf{A}, \mathbf{B}$,n}
+ \State $ sum \gets 0$
+ \For{$i = 0,1,2 \dots,n$}
+ \For{$j = 0,1,2 \dots,n$}
+ \State $ sum \gets sum + A[i] \cdot B[j] $
+ \EndFor
+ \EndFor
+ \State \textbf{return} $sum$
+ \EndFunction
+ \end{algorithmic}
+ \end{algorithm}
+ \end{minipage}
+ \end{tabular}
+\end{table}
+
+dhdfh
+\end{document}
diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf
index 3a4cfd8..e6af618 100644
Binary files a/buch/papers/multiplikation/images/meas_c.pdf and b/buch/papers/multiplikation/images/meas_c.pdf differ
diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex
index 818a7e6..647a322 100644
--- a/buch/papers/multiplikation/images/meas_c.tex
+++ b/buch/papers/multiplikation/images/meas_c.tex
@@ -43,8 +43,8 @@
\begin{tikzpicture}
\begin{axis}[
xmode=log, ymode=log,
-xmin=60, xmax=5000,
-ymin=1e-4, ymax=2e3,
+xmin=60, xmax=10000,
+ymin=1e-4, ymax=2e4,
grid=both,
major grid style={black!50},
xlabel = data Input ($n$),
@@ -70,6 +70,7 @@ width=12cm, height=8cm,
(1024,4.539413)
(2048,130.627663)
(4096,1179.261048)
+(8192,10071.512655)
};
\addlegendentry{Strassen}
\addplot [ color=black,
@@ -86,6 +87,7 @@ width=12cm, height=8cm,
(1024,8.457472 )
(2048,59.267256)
(4096,414.648901)
+(8192,3014.235467)
};
\addlegendentry{MM div and conq}
@@ -103,6 +105,7 @@ width=12cm, height=8cm,
(1024,19.928951 )
(2048,159.333884 )
(4096,1147.106865)
+(8192,9606.402522)
};
\addlegendentry{MM}
@@ -120,6 +123,7 @@ width=12cm, height=8cm,
(1024,4.162845 )
(2048,125.909034 )
(4096,1111.312696)
+(8192,9376.173434)
};
\addlegendentry{BLAS}
\addplot[ color=blue,
@@ -136,6 +140,7 @@ width=12cm, height=8cm,
(1024,0.704748 )
(2048,6.845095 )
(4096,55.845038)
+(8192,478.429957)
};
\end{axis}
\end{tikzpicture}
diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex
index a7612e1..464085d 100755
--- a/buch/papers/multiplikation/loesungsmethoden.tex
+++ b/buch/papers/multiplikation/loesungsmethoden.tex
@@ -39,13 +39,13 @@ Die \texttt{for i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix,
\end{algorithmic}
\end{algorithm}
-Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O}\left(n^3\right)$
+Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O} (n^3)$
\subsubsection{Divide and Conquer Methode}
F\"ur gewisse Algorithmen f\"uhren \textit{Divide and Conquer} Ans\"atze \cite{multiplikation:DAC} zu markant besseren Laufzeiten.
Die Grundidee ist, dass ein Problem in mehrere, meist simplere und kleinere Teilprobleme aufgeteilt wird.
-Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die Laufzeit von $\mathcal{O}\left(n^2\right)$ zu $\mathcal{O}(n \log n)$ verbessert werden kann.
+Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die Laufzeit von $\mathcal{O} (n^2)$ zu $\mathcal{O}(n \log n)$ verbessert werden kann.
Die Matrizenmultiplikation kann ebenfalls mit solch einem Ansatz berechnet werden.
Zur vereinfachten Veranschaulichung kann die Situation mit $\mathbf{A}$ und $\mathbf{B}$ der Gr\"osse $2^n \times 2^n$ verwendet werden.
@@ -68,7 +68,7 @@ Das Matrizen Produkt
\end{bmatrix},
\end{equation}
\begin{equation}
-\mathbf{C}_{ij} = \sum_{k=1}2n \mathbf{A}_{ik} \mathbf{B}_{kj}
+\mathbf{C}_{ij} = \sum_{k=1}^{2n} \mathbf{A}_{ik} \mathbf{B}_{kj}
\label{multiplikation:eq:MM_block}
\end{equation}
ist identisch zu der Gleichung \eqref{multiplikation:eq:MM}, f\"ur die Multiplikation der Untermatrize $\mathbf{A}_{ik}$ und $\mathbf{B}_{kj}$ wird die Matrizenmultiplikation verwendet.
@@ -109,7 +109,7 @@ Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} \ci
Ohne auf dieses vertieft einzugehen, bestimmt die Anzahl rekursiver Aufrufe $\mathcal{T} $ der Funktion die Laufzeit.
In diesem Fall wird die Funktion pro Durchlauf acht mal rekursiv aufgerufen, dies f\"uhrt
\begin{equation} \label{multiplikation:eq:laufzeitdac}
- \mathcal{T}(n) = 8 \cdot \mathcal{T}\left (\frac{n}{2}\right ) + n^2 = \mathcal{O}(n^{\log_2 8}) = \mathcal{O}\left (n^{3} \right )
+ \mathcal{T}(n) = 8 \cdot \mathcal{T} \left(\frac{n}{2}\right ) + n^2 = \mathcal{O}(n^{\log_2 8}) = \mathcal{O} (n^{3} )
\end{equation}
zu einer kubischen Laufzeit.
Die Addition zweier Matrizen $\mathbf{A} + \mathbf{B} = \mathbf{C}$ hat eine Laufzeit von $\mathcal{O}(n^{2})$ und kann neben dem dominierendem Anteil von $\mathcal{O}(n^{3})$ ignoriert werden.
@@ -202,7 +202,7 @@ Die Funktion wird sieben mal rekursiv aufgerufen.
Dies f\"uhrt nach dem \textit{Master Theorem} zu einer Laufzeit von
\begin{equation} \label{multiplikation:eq:laufzeitstrassen}
\mathcal{T}(n) =
-7 \cdot \mathcal{T}(\frac{n}{2}) + n^2 = \mathcal{O}\left(n^{\log_2 7}\right ) = \mathcal{O}\left(n^{2.8074} \right )
+7 \cdot \mathcal{T}\left(\frac{n}{2}\right) + n^2 = \mathcal{O}(n^{\log_2 7} ) = \mathcal{O}(n^{2.8074} )
\end{equation}
und ist somit schneller als die Standardmethode.
Man beachte, dass die Anzahl von Additionen und Subtraktionen gr\"osser und die Anzahl der Multiplikationen kleiner wurde.
@@ -267,7 +267,7 @@ sein, damit man etwas einspart.
Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden.
Falls $m=n=p$ werden $\frac{n^3}/{2}$ Multiplikationen benötigt.
Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \rightarrow \infty$ können Konstanten vernachlässigt werden und
- somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}\left(n^3 \right)$.
+ somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}(n^3 )$.
\begin{algorithm}\footnotesize\caption{Winograds Matrizenmultiplikation}
\setlength{\lineskip}{7pt}
\label{multiplikation:alg:winograd}
@@ -336,33 +336,33 @@ Die meisten Numerischen Bibliotheken von High-Level Skriptsprachen wie \texttt{M
\item Level 2
\begin{itemize}
\item Operationen der Art: $\mathbf{y} \leftarrow \alpha \mathbf{A}\mathbf{x}+\beta \mathbf{y}$
- \item Dieses Level hat $\mathcal{O}\left(n^2\right)$ Charakteristik
+ \item Dieses Level hat $\mathcal{O}(n^2)$ Charakteristik
\end{itemize}
\item Level 3
\begin{itemize}
\item Operationen der Art: $\mathbf{C} \leftarrow \alpha \mathbf{A}\mathbf{B}+\beta\mathbf{C}$
- \item Dieses Level hat $\mathcal{O}\left(n^3\right)$ Charakteristik
+ \item Dieses Level hat $\mathcal{O}(n^3)$ Charakteristik
\end{itemize}
\end{itemize}
Die \textit{BLAS} sind auf die modernen Computer Prozessoren optimiert und k\"onnen dank einer ausgeklügelter Verwendung der Speicherarchitektur zu erheblichen Leistungsoptimierungen f\"uhren.
-\subsubsection{General Matrix Multiplication (GEMM)}
-
-Die \textit{Double-GEMM} \cite{multiplikation:DGEMM} ist definiert als:
-
-\textit{DGEMM performs one of the matrix-matrix operations}
-$$
- C := \alpha \cdot op( A )\cdot op( B ) + \beta \cdot C,
- $$
- \textit{where op( X ) is one of}
-$$
-op( X ) = X \quad \text{ or } \quad op( X ) = X^T,
-$$
- \textit{alpha and beta are scalars, and A, B and C are matrices, with op( A )
- an m by k matrix, op( B ) a k by n matrix and C an m by n matrix.
- }
+%\subsubsection{General Matrix Multiplication (GEMM)}
+%
+%Die \textit{Double-GEMM} \cite{multiplikation:DGEMM} ist definiert als:
+%
+%\textit{DGEMM performs one of the matrix-matrix operations}
+%$$
+% C := \alpha \cdot op( A )\cdot op( B ) + \beta \cdot C,
+% $$
+% \textit{where op( X ) is one of}
+%$$
+%op( X ) = X \quad \text{ or } \quad op( X ) = X^T,
+%$$
+% \textit{alpha and beta are scalars, and A, B and C are matrices, with op( A )
+% an m by k matrix, op( B ) a k by n matrix and C an m by n matrix.
+% }
%Die Implementation von $\alpha\mathbf{A}\mathbf{B} + \beta \mathbf{C} = \mathbf{C}$, wobei $\alpha = 1.0$ und $\beta = 0.0$ in der \texttt{C}-Version von \textit{BLAS}, ist als
%\begin{lstlisting}[style=multiplikationC]
@@ -379,7 +379,7 @@ $$
Folgende Algorithmen wurden jeweils in \texttt{C} und \texttt{Python} implementiert.
\begin{itemize}
\item Standard Matrizenmultiplikation
- \item \textit{Devide and Conquer} Matrizenmultiplikation
+ \item \textit{Divide and Conquer} Matrizenmultiplikation
\item Strassens Matrizenmultiplikation
\item Winograds Matrizenmultiplikation
\item \texttt{BLAS} Matrizenmultiplikation in \texttt{C}
diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex
index e53b0de..c8ba274 100755
--- a/buch/papers/multiplikation/problemstellung.tex
+++ b/buch/papers/multiplikation/problemstellung.tex
@@ -14,87 +14,102 @@ Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der S
Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Abhängigkeit zur Inputgrösse \cite{multiplikation:bigo}.
$f(x) \in \mathcal{O}(g(x))$ besagt, dass die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$.
% Es gibt eine Konstante $K$ derart, dass $f(x) \le K g(x)$ für $x\to\infty$
-Als Beispiel: benötigt eine Funktion $g$ $\mathcal{O}\left(n^2 \right)$ Multiplikationen, so wächst $f$ mit $\mathcal{O}\left(n+ n^2 \right)$ nicht wesentlich schneller falls $x\to\infty$.
+Als Beispiel: benötigt eine Funktion $g$ $\mathcal{O} (n^2 )$ Multiplikationen, so wächst $f$ mit $\mathcal{O} (n+ n^2 )$ nicht wesentlich schneller falls $x\to\infty$.
Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet:
\begin{itemize}
\item $f \in \mathcal{O}(1) \rightarrow f$ ist beschr\"ankt
\item $f \in \mathcal{O}(n) \rightarrow f$ w\"achst linear
- \item $f \in \mathcal{O}\left (n^2 \right ) \rightarrow f$ w\"achst quadratisch
+ \item $f \in \mathcal{O} (n^2 ) \rightarrow f$ w\"achst quadratisch
\item $f \in \mathcal{O}(\log n) \rightarrow f$ w\"achst logarithmisch
\item $f \in \mathcal{O}(n \log n) \rightarrow f$ hat super-lineares Wachstum
- \item $f \in \mathcal{O}\left (e^n \right ) \rightarrow f$ w\"achst exponentiell
+ \item $f \in \mathcal{O} (e^n ) \rightarrow f$ w\"achst exponentiell
\item usw.
\end{itemize}
In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden.
Bei einer logarithmischen Darstellung werden Polynome der Form $f(x) = x^k$ als Gerade und Exponentialfunktionen der Form $f(x) = a^x$ als nach oben gekr\"ummte Kurven dargestellt.
-Sch\"on zu erkennen ist, dass Logarithmische Kurven beschr\"ankt sind.
+
\subsubsection{Beispiel Algorithmen}
Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen.
-\begin{minipage}{0.4\textwidth}
- \begin{algorithm}[H]\footnotesize\caption{}
- \label{multiplikation:alg:b1}
- \setlength{\lineskip}{7pt}
- \begin{algorithmic}
- \Function{B1}{$a, b$}
- \State \textbf{return} $a+b$
- \EndFunction
- \end{algorithmic}
- \end{algorithm}
-
- \begin{algorithm}[H]\footnotesize\caption{}
- \setlength{\lineskip}{7pt}
- \begin{algorithmic}
- \label{multiplikation:alg:linear}
- \Function{L}{$\mathbf{a}, \mathbf{b}$,n}
- \State $ sum \gets 0$
- \For{$i = 0,1,2 \dots,n$}
- \State $ sum \gets sum + A[i] \cdot B[i] $
- \EndFor
-
- \State \textbf{return} $sum$
-
- \EndFunction
- \end{algorithmic}
- \end{algorithm}
-\end{minipage}
-\hspace{2cm}
-\begin{minipage}{0.4\textwidth}
-
- \begin{algorithm}[H]\footnotesize\caption{}
- \label{multiplikation:alg:b2}
- \setlength{\lineskip}{7pt}
- \begin{algorithmic}
- \Function{B2}{$a, b$}
- \State $ x \gets a+b $
- \State $ y \gets a \cdot b $
- \State \textbf{return} $x+y$
- \EndFunction
- \end{algorithmic}
- \end{algorithm}
-
-
- \begin{algorithm}[H]\footnotesize\caption{}
- \label{multiplikation:alg:q1}
- \setlength{\lineskip}{7pt}
- \begin{algorithmic}
- \Function{Q}{$\mathbf{A}, \mathbf{B}$,n}
- \State $ sum \gets 0$
- \For{$i = 0,1,2 \dots,n$}
- \For{$j = 0,1,2 \dots,n$}
- \State $ sum \gets sum + A[i] \cdot B[j] $
- \EndFor
- \EndFor
- \State \textbf{return} $sum$
- \EndFunction
- \end{algorithmic}
- \end{algorithm}
-
-\end{minipage}
+
+\begin{table}[t]
+ \begin{tabular}{ll}
+ \begin{minipage}{0.48\textwidth}
+ \begin{algorithm}[H]\footnotesize\caption{}
+ \label{multiplikation:alg:b1}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \Function{B1}{$a, b$}
+ \State \textbf{return} $a+b$
+ \EndFunction
+ \State
+ \State
+ \end{algorithmic}
+ \end{algorithm}
+ \end{minipage}
+ &
+ \begin{minipage}{0.48\textwidth}
+ \begin{algorithm}[H]\footnotesize\caption{}
+ \label{multiplikation:alg:b2}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \Function{B2}{$a, b$}
+ \State $ x \gets a+b $
+ \State $ y \gets a \cdot b $
+ \State \textbf{return} $x+y$
+ \EndFunction
+ \end{algorithmic}
+ \end{algorithm}
+
+ \end{minipage}
+ \end{tabular}
+\end{table}
+
+\begin{table}
+ \begin{tabular}[t]{ll}
+ \begin{minipage}{0.48\textwidth}
+ \begin{algorithm}[H]\footnotesize\caption{}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \label{multiplikation:alg:linear}
+ \Function{L}{$\mathbf{a}, \mathbf{b}$,n}
+ \State $ sum \gets 0$
+ \For{$i = 0,1,2 \dots,n$}
+ \State $ sum \gets sum + A[i] \cdot B[i] $
+ \EndFor
+
+ \State \textbf{return} $sum$
+
+ \EndFunction
+ \State
+ \State
+ \end{algorithmic}
+ \end{algorithm}
+ \end{minipage}
+ &
+ \begin{minipage}{0.48\textwidth}
+ \begin{algorithm}[H]\footnotesize\caption{}
+ \label{multiplikation:alg:q1}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \Function{Q}{$\mathbf{A}, \mathbf{B}$,n}
+ \State $ sum \gets 0$
+ \For{$i = 0,1,2 \dots,n$}
+ \For{$j = 0,1,2 \dots,n$}
+ \State $ sum \gets sum + A[i] \cdot B[j] $
+ \EndFor
+ \EndFor
+ \State \textbf{return} $sum$
+ \EndFunction
+ \end{algorithmic}
+ \end{algorithm}
+ \end{minipage}
+ \end{tabular}
+\end{table}
\paragraph{Beschr\"ankter Algorithmus}
@@ -111,7 +126,7 @@ Die \texttt{for}-Schleife wird $n$-mal durchlaufen und f\"uhrt deshalb zu $\math
\paragraph{Quadratischer Algorithmus}
Der Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalten.
-Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$.
+Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O} (n^2 )$.
\begin{figure}
--
cgit v1.2.1
From 3c59b60807e1d1238bf591e238a42574327246ca Mon Sep 17 00:00:00 2001
From: Nunigan <michaelschmid13@hotmail.com>
Date: Tue, 10 Aug 2021 07:29:49 +0200
Subject: update plots
---
buch/papers/multiplikation/code/MM.py | 22 ++--
buch/papers/multiplikation/code/c_meas_4096.pdf | Bin 22360 -> 22207 bytes
buch/papers/multiplikation/code/helper_class.py | 4 +-
buch/papers/multiplikation/code/meas/ci/MM.txt | 11 --
buch/papers/multiplikation/code/meas/ci/Wino.txt | 11 --
buch/papers/multiplikation/code/meas/ci/blas.txt | 11 --
buch/papers/multiplikation/code/meas/ci/dc.txt | 11 --
.../multiplikation/code/meas/ci/strassen.txt | 11 --
buch/papers/multiplikation/code/meas_4096.pdf | Bin 17369 -> 18300 bytes
buch/papers/multiplikation/images/meas_c.pdf | Bin 23552 -> 24028 bytes
buch/papers/multiplikation/images/meas_c.tex | 115 +++++++++++----------
buch/papers/multiplikation/images/meas_python.pdf | Bin 21700 -> 26004 bytes
buch/papers/multiplikation/images/meas_python.tex | 53 ++++++----
buch/papers/multiplikation/images/x.pdf | Bin 0 -> 23603 bytes
14 files changed, 105 insertions(+), 144 deletions(-)
create mode 100644 buch/papers/multiplikation/images/x.pdf
(limited to 'buch/papers/multiplikation')
diff --git a/buch/papers/multiplikation/code/MM.py b/buch/papers/multiplikation/code/MM.py
index 8a6824a..8057850 100644
--- a/buch/papers/multiplikation/code/MM.py
+++ b/buch/papers/multiplikation/code/MM.py
@@ -291,19 +291,21 @@ def mean_confidence_interval(data, confidence=0.95):
n = len(a)
m, se = np.mean(a), scipy.stats.sem(a)
h = se * scipy.stats.t.ppf((1 + confidence) / 2., n-1)
- return m, m-h, m+h
+ return m, h
# test%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if __name__ == '__main__':
- A = plot_c_res(10, 4096)
- name = ['MM', 'Wino', 'blas', 'strassen', 'dc']
- for i in range(5):
- ci_inner = []
- for j in range(11):
- ci_inner.append(mean_confidence_interval(A[i][j*10:(j+1)*10]))
- np.savetxt('meas/ci/' + name[i]+'.txt',ci_inner)
-
- # arr = plot(1024)
+ # A = plot_c_res(10, 4096)
+ # name = ['MM', 'Wino', 'blas', 'strassen', 'dc']
+ # for i in range(5):
+ # ci_inner = []
+ # print(name[i])
+ # for j in range(11):
+ # m,h=mean_confidence_interval(A[i][j*10:(j+1)*10])
+ # print("({},{})".format(2**(j+1),m))
+ # np.savetxt('meas/ci/' + name[i]+'.txt',ci_inner)
+
+ arr = plot(4096)
# n = np.logspace(1,12,12,base=2,dtype=(np.int))
# n=[2048,4096]
# n = np.arange(1,50,2)
diff --git a/buch/papers/multiplikation/code/c_meas_4096.pdf b/buch/papers/multiplikation/code/c_meas_4096.pdf
index b42082f..f637ae4 100644
Binary files a/buch/papers/multiplikation/code/c_meas_4096.pdf and b/buch/papers/multiplikation/code/c_meas_4096.pdf differ
diff --git a/buch/papers/multiplikation/code/helper_class.py b/buch/papers/multiplikation/code/helper_class.py
index ad67909..3b74f67 100755
--- a/buch/papers/multiplikation/code/helper_class.py
+++ b/buch/papers/multiplikation/code/helper_class.py
@@ -101,6 +101,6 @@ if __name__ == '__main__':
helper = Helper()
# n = np.arange(2,10)
- n = np.logspace(1,4,4,base=2,dtype=(np.int))
+ n = np.logspace(1,11,11,base=2,dtype=(np.int))
# n=[8192]
- C = helper.write_c_matrix(n)
+ # C = helper.write_c_matrix(n)
diff --git a/buch/papers/multiplikation/code/meas/ci/MM.txt b/buch/papers/multiplikation/code/meas/ci/MM.txt
index e4ad1ba..e69de29 100644
--- a/buch/papers/multiplikation/code/meas/ci/MM.txt
+++ b/buch/papers/multiplikation/code/meas/ci/MM.txt
@@ -1,11 +0,0 @@
-0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00
-2.999999999999999864e-07 -4.555021440490437016e-08 6.455502144049043430e-07
-1.800000000000000130e-06 1.498379044967867836e-06 2.101620955032132425e-06
-1.199999999999999861e-05 9.737842837259007037e-06 1.426215716274099018e-05
-8.930000000000000221e-05 7.942767152586658090e-05 9.917232847413342352e-05
-6.922999999999999684e-04 6.611729768299406300e-04 7.234270231700593067e-04
-5.684200000000000363e-03 5.587928563282692010e-03 5.780471436717308717e-03
-5.177150000000000502e-02 5.161257221154376407e-02 5.193042778845624596e-02
-5.062468000000001078e-01 5.001729723042721565e-01 5.123206276957280592e-01
-4.504808599999999608e+00 4.404751183933223402e+00 4.604866016066775813e+00
-1.292894618999999921e+02 1.292188312556721144e+02 1.293600925443278697e+02
diff --git a/buch/papers/multiplikation/code/meas/ci/Wino.txt b/buch/papers/multiplikation/code/meas/ci/Wino.txt
index 4ec0106..e69de29 100644
--- a/buch/papers/multiplikation/code/meas/ci/Wino.txt
+++ b/buch/papers/multiplikation/code/meas/ci/Wino.txt
@@ -1,11 +0,0 @@
-9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07
-0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00
-2.000000000000000333e-06 1.999999999999999909e-06 2.000000000000000757e-06
-1.199999999999999861e-05 9.737842837259007037e-06 1.426215716274099018e-05
-8.329999999999999189e-05 7.952898408510092581e-05 8.707101591489905797e-05
-6.478999999999999733e-04 6.173195729945008762e-04 6.784804270054990705e-04
-5.287299999999999986e-03 5.226513788941518357e-03 5.348086211058481615e-03
-5.267459999999999504e-02 5.240389179019239174e-02 5.294530820980759833e-02
-5.249752000000000862e-01 5.233835466989910090e-01 5.265668533010091634e-01
-4.671160999999999675e+00 4.572509907501117965e+00 4.769812092498881384e+00
-1.366769777000000090e+02 1.363957928284978891e+02 1.369581625715021289e+02
diff --git a/buch/papers/multiplikation/code/meas/ci/blas.txt b/buch/papers/multiplikation/code/meas/ci/blas.txt
index 5d7ff7b..e69de29 100644
--- a/buch/papers/multiplikation/code/meas/ci/blas.txt
+++ b/buch/papers/multiplikation/code/meas/ci/blas.txt
@@ -1,11 +0,0 @@
-9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07
-0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00
-9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07
-3.899999999999999929e-06 1.864058553533107683e-06 5.935941446466892176e-06
-2.100000000000000223e-05 1.871284586667546976e-05 2.328715413332453469e-05
-1.858000000000000168e-04 1.595988766828141249e-04 2.120011233171859087e-04
-1.264900000000000009e-03 1.221091632895032926e-03 1.308708367104967091e-03
-9.648900000000000185e-03 9.575266909835235610e-03 9.722533090164764760e-03
-7.737650000000000083e-02 7.445101996220353235e-02 8.030198003779646931e-02
-7.643868000000000329e-01 7.545731380187049586e-01 7.742004619812951072e-01
-7.632099399999999534e+00 7.613379481172315444e+00 7.650819318827683624e+00
diff --git a/buch/papers/multiplikation/code/meas/ci/dc.txt b/buch/papers/multiplikation/code/meas/ci/dc.txt
index df268a9..e69de29 100644
--- a/buch/papers/multiplikation/code/meas/ci/dc.txt
+++ b/buch/papers/multiplikation/code/meas/ci/dc.txt
@@ -1,11 +0,0 @@
-2.999999999999999864e-07 -3.786471488222973584e-07 9.786471488222972253e-07
-1.100000000000000056e-06 8.737842837259009412e-07 1.326215716274099171e-06
-8.600000000000000670e-06 6.210712693650135778e-06 1.098928730634986641e-05
-7.819999999999998990e-05 7.075203863371232107e-05 8.564796136628765873e-05
-5.940000000000001269e-04 5.439534118129448707e-04 6.440465881870553830e-04
-4.433900000000000167e-03 4.349138038034851966e-03 4.518661961965148369e-03
-3.484430000000000166e-02 3.435947773230259988e-02 3.532912226769740344e-02
-2.948473000000000344e-01 2.887830472415335303e-01 3.009115527584665384e-01
-2.222850699999999957e+00 2.193855611791002858e+00 2.251845788208997057e+00
-1.765923450000000372e+01 1.762601016688562439e+01 1.769245883311438305e+01
-1.416103936000000090e+02 1.414816028568733657e+02 1.417391843431266523e+02
diff --git a/buch/papers/multiplikation/code/meas/ci/strassen.txt b/buch/papers/multiplikation/code/meas/ci/strassen.txt
index 983fed9..e69de29 100644
--- a/buch/papers/multiplikation/code/meas/ci/strassen.txt
+++ b/buch/papers/multiplikation/code/meas/ci/strassen.txt
@@ -1,11 +0,0 @@
-0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00
-2.099999999999999799e-06 1.572163328693768390e-06 2.627836671306231420e-06
-1.130000000000000023e-05 7.484018077564905836e-06 1.511598192243509547e-05
-7.069999999999999733e-05 6.500652995675561090e-05 7.639347004324438376e-05
-5.040999999999999474e-04 4.766428619697257881e-04 5.315571380302741610e-04
-3.595999999999999804e-03 3.528938496002300557e-03 3.663061503997699052e-03
-2.544810000000000128e-02 2.513634544137222787e-02 2.575985455862777468e-02
-1.781816999999999984e-01 1.773043765864557864e-01 1.790590234135442105e-01
-1.255500000000000060e+00 1.247847949398645628e+00 1.263152050601354492e+00
-8.830237099999999728e+00 8.790366960647805428e+00 8.870107239352194028e+00
-6.190186909999999898e+01 6.183048085945843297e+01 6.197325734054156499e+01
diff --git a/buch/papers/multiplikation/code/meas_4096.pdf b/buch/papers/multiplikation/code/meas_4096.pdf
index 9e8fcea..ecf2cff 100644
Binary files a/buch/papers/multiplikation/code/meas_4096.pdf and b/buch/papers/multiplikation/code/meas_4096.pdf differ
diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf
index e6af618..faf347e 100644
Binary files a/buch/papers/multiplikation/images/meas_c.pdf and b/buch/papers/multiplikation/images/meas_c.pdf differ
diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex
index 647a322..fe2bd2f 100644
--- a/buch/papers/multiplikation/images/meas_c.tex
+++ b/buch/papers/multiplikation/images/meas_c.tex
@@ -43,8 +43,8 @@
\begin{tikzpicture}
\begin{axis}[
xmode=log, ymode=log,
-xmin=60, xmax=10000,
-ymin=1e-4, ymax=2e4,
+xmin=30, xmax=10000,
+ymin=1e-5, ymax=2e4,
grid=both,
major grid style={black!50},
xlabel = data Input ($n$),
@@ -57,35 +57,36 @@ width=12cm, height=8cm,
]
\addlegendentry{Winograd}
\addplot[ color=purple,
+ error bars/.cd, y dir=both, y explicit,
] coordinates {
-% (2, 0.000001)
-% (4, 0.000001)
-% (8, 0.000002)
-% (16, 0.000011)
-% (32, 0.000100)
-(64, 0.000654)
-(128, 0.005229)
-(256, 0.057440)
-(512, 0.517850)
-(1024,4.539413)
-(2048,130.627663)
+%(2,1e-07)
+%(4,5e-07)
+%(8,2.0000000000000003e-06)
+%(16,1.1999999999999999e-05)
+(32,8.329999999999999e-05)
+(64,0.0006479)
+(128,0.0052873)
+(256,0.052674599999999995)
+(512,0.5249752000000001)
+(1024,4.671161)
+(2048,136.6769777)
(4096,1179.261048)
(8192,10071.512655)
};
\addlegendentry{Strassen}
\addplot [ color=black,
]coordinates {
- % (2,0.000001 )
- % (4,0.000003 )
- % (8,0.000010 )
- % (16,0.000066 )
- % (32,0.000470 )
- (64,0.003368 )
- (128,0.024232 )
- (256,0.172000 )
- (512,1.209262 )
-(1024,8.457472 )
-(2048,59.267256)
+%(2,1e-07)
+%(4,2.1e-06)
+%(8,1.13e-05)
+%(16,7.07e-05)
+(32,0.0005041)
+(64,0.003596)
+(128,0.0254481)
+(256,0.1781817)
+(512,1.2555)
+(1024,8.8302371)
+(2048,61.9018691)
(4096,414.648901)
(8192,3014.235467)
};
@@ -93,17 +94,17 @@ width=12cm, height=8cm,
\addlegendentry{MM div and conq}
\addplot[ color=green,
] coordinates {
- % (2,0.000003 )
- % (4,0.000002 )
- % (8,0.000010 )
- % (16,0.000068 )
- % (32,0.000594 )
- (64,0.004264 )
- (128,0.036289 )
- (256,0.324645 )
- (512,2.612010 )
-(1024,19.928951 )
-(2048,159.333884 )
+%(2,3e-07)
+%(4,1.1e-06)
+%(8,8.6e-06)
+%(16,7.819999999999999e-05)
+(32,0.0005940000000000001)
+(64,0.0044339)
+(128,0.0348443)
+(256,0.29484730000000003)
+(512,2.2228507)
+(1024,17.659234500000004)
+(2048,141.6103936)
(4096,1147.106865)
(8192,9606.402522)
};
@@ -111,34 +112,34 @@ width=12cm, height=8cm,
\addlegendentry{MM}
\addplot [ color=red,
]coordinates {
- % (2,0.000001 )
- % (4,0.000001 )
- % (8,0.000001 )
- % (16,0.000010 )
- % (32,0.000081 )
- (64,0.000654 )
- (128,0.005556 )
- (256,0.054253 )
- (512,0.487317 )
-(1024,4.162845 )
-(2048,125.909034 )
+%(2,0.0)
+%(4,3e-07)
+%(8,1.8000000000000001e-06)
+%(16,1.1999999999999999e-05)
+(32,8.93e-05)
+(64,0.0006923)
+(128,0.0056842)
+(256,0.051771500000000005)
+(512,0.5062468000000001)
+(1024,4.5048086)
+(2048,129.2894619)
(4096,1111.312696)
(8192,9376.173434)
};
\addlegendentry{BLAS}
\addplot[ color=blue,
] coordinates {
- % (2,0.000001 )
- % (4,0.000001 )
- % (8,0.000001 )
- % (16,0.000003 )
- % (32,0.000022 )
- (64,0.000179 )
- (128,0.001278 )
- (256,0.010165 )
- (512,0.074739 )
-(1024,0.704748 )
-(2048,6.845095 )
+%(2,1e-07)
+%(4,0.0)
+%(8,1e-07)
+%(16,3.9e-06)
+(32,2.1000000000000002e-05)
+(64,0.00018580000000000002)
+(128,0.0012649)
+(256,0.0096489)
+(512,0.0773765)
+(1024,0.7643868)
+(2048,7.6320993999999995)
(4096,55.845038)
(8192,478.429957)
};
diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf
index cea2232..cea4f4b 100644
Binary files a/buch/papers/multiplikation/images/meas_python.pdf and b/buch/papers/multiplikation/images/meas_python.pdf differ
diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex
index ee4db43..c8892be 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=1050,
-ymin=0.01, ymax=900,
+xmin=30, xmax=4100,
+ymin=0.00001, ymax=60000,
grid=both,
major grid style={black!50},
xlabel = data input ($n$),
@@ -68,7 +68,8 @@ width=12cm, height=8cm,
(256, 8.29899 )
(512, 68.3699 )
(1024,537.374 )
-
+(2046,4884.61)
+(4096,43597.1)
};
\addlegendentry{Strassen}
\addplot [ color=black,
@@ -79,10 +80,12 @@ width=12cm, height=8cm,
% (16,0.00475407 )
(32,0.0485256 )
(64,0.220414 )
- (128,1.44718 2 )
- (256,9.93866 0 )
- (512,63.961 2 )
-(1024,461.494 2 )
+ (128,1.44718 )
+ (256,9.93866 )
+ (512,63.961 )
+(1024,461.494 )
+(2046,3860.57)
+(4096,22904.3)
};
\addlegendentry{MM div and conq}
@@ -98,6 +101,8 @@ width=12cm, height=8cm,
(256,13.27 )
(512,105.397 )
(1024,847.321 )
+(2046,7375.93)
+(4096,58466)
};
\addlegendentry{MM}
@@ -113,25 +118,33 @@ width=12cm, height=8cm,
(256, 11.0062 )
(512, 85.4768)
(1024,750.757 )
+(2046,6154.18)
+(4096,46813.3)
};
-% \addlegendentry{NumPy}
-% \addplot[ color=blue,
-% ] coordinates {
+ \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 )
-% };
+ (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)$}
\end{axis}
\end{tikzpicture}
\end{document}
-
-
-
diff --git a/buch/papers/multiplikation/images/x.pdf b/buch/papers/multiplikation/images/x.pdf
new file mode 100644
index 0000000..da4956f
Binary files /dev/null and b/buch/papers/multiplikation/images/x.pdf differ
--
cgit v1.2.1
From 6bab37ba5c4d1875f3c99f338a554537219013f6 Mon Sep 17 00:00:00 2001
From: Nunigan <michael.schmid2@ost.ch>
Date: Wed, 11 Aug 2021 21:22:29 +0200
Subject: update multiplikation
---
buch/papers/multiplikation/images/meas_python.pdf | Bin 26004 -> 22384 bytes
buch/papers/multiplikation/images/meas_python.tex | 44 ++++++++++------------
buch/papers/multiplikation/images/x.pdf | Bin 23603 -> 0 bytes
buch/papers/multiplikation/loesungsmethoden.tex | 30 ++++++++++-----
4 files changed, 39 insertions(+), 35 deletions(-)
delete mode 100644 buch/papers/multiplikation/images/x.pdf
(limited to 'buch/papers/multiplikation')
diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf
index cea4f4b..ab3b14b 100644
Binary files a/buch/papers/multiplikation/images/meas_python.pdf and b/buch/papers/multiplikation/images/meas_python.pdf 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
Binary files a/buch/papers/multiplikation/images/x.pdf and /dev/null 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
--
cgit v1.2.1
From 2b6637fb99a4aaebadc739b323b0ae440eb805e7 Mon Sep 17 00:00:00 2001
From: Nunigan <michael.schmid2@ost.ch>
Date: Wed, 11 Aug 2021 21:31:37 +0200
Subject: typo
---
buch/papers/multiplikation/loesungsmethoden.tex | 12 ++++++------
1 file changed, 6 insertions(+), 6 deletions(-)
(limited to 'buch/papers/multiplikation')
diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex
index be8c2d4..0760719 100755
--- a/buch/papers/multiplikation/loesungsmethoden.tex
+++ b/buch/papers/multiplikation/loesungsmethoden.tex
@@ -265,7 +265,7 @@ N=2n, \quad T = n^2 \\
\end{equation}
sein, damit man etwas einspart.
Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden.
-Falls $m=n=p$ werden $\frac{n^3}/{2}$ Multiplikationen benötigt.
+Falls $m=n=p$ werden $\frac{n^3}{2}$ Multiplikationen benötigt.
Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \rightarrow \infty$ können Konstanten vernachlässigt werden und
somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}(n^3 )$.
\begin{algorithm}\footnotesize\caption{Winograds Matrizenmultiplikation}
@@ -391,11 +391,11 @@ Anzumerken ist, dass die Matrizenmultiplikation von \texttt{NumPy} als einzige I
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.
+den.
+Bei den Algorithmen von Winograd und der Standardmethode hat bei einer Matrizengrösse von $n = 2048$ wohl eine Zeile der Matrize nicht an einer Cache Speicherstelle platzt.
+Diese beiden 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 Algorithmen ist dies nicht der Fall.
Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{multiplikation:tab:pc_config} aufgelistet.
--
cgit v1.2.1