diff options
Diffstat (limited to 'buch/papers/multiplikation')
56 files changed, 1853 insertions, 388 deletions
diff --git a/buch/papers/multiplikation/code/MM b/buch/papers/multiplikation/code/MM Binary files differdeleted file mode 100755 index f07985f..0000000 --- a/buch/papers/multiplikation/code/MM +++ /dev/null diff --git a/buch/papers/multiplikation/code/MM.c b/buch/papers/multiplikation/code/MM.c index 04c4dab..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 626b82d..8057850 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 @@ -132,6 +133,7 @@ def winograd2(A, B): return C def test_perfomance(n): + t_mm = [] t_mm_dc = [] t_mm_strassen = [] @@ -174,17 +176,18 @@ def test_perfomance(n): 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() plt.xlabel("n") plt.ylabel("time (s)") - plt.grid(True) + plt.grid(True, which="both", ls="-") 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) - return arr + return t_np def plot(num): @@ -198,10 +201,11 @@ def plot(num): plt.plot(n, t_mm, label='3 For Loops', 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_wino, label='Winograd', lw=5) plt.plot(n, t_np, label='NumPy A@B', lw=5) plt.legend() plt.xlabel("n") + # plt.yscale('log', base=10) plt.ylabel("time (s)") plt.grid(True) plt.tight_layout() @@ -211,36 +215,39 @@ def plot(num): return arr def plot_c_res(ave, num): + MM = np.loadtxt("meas/MM.txt", delimiter=',') - # winograd = np.loadtxt("meas/winograd.txt", delimiter=',') + winograd = np.loadtxt("meas/winograd.txt", delimiter=',') blas = np.loadtxt("meas/blas.txt", delimiter=',') MM_dc = np.loadtxt("meas/MM_dc.txt", delimiter=',') strassen = np.loadtxt("meas/strassen.txt", delimiter=',') MM_t = MM[:,0] MM_n = MM[:,1] - MM_t = np.mean(MM_t.reshape(-1,ave),axis=1) - MM_n = np.mean(MM_n.reshape(-1,ave),axis=1) + # MM_t = np.mean(MM_t.reshape(-1,ave),axis=1) + # MM_n = np.mean(MM_n.reshape(-1,ave),axis=1) MM_dc_t = MM_dc[:,0] MM_dc_n = MM_dc[:,1] - MM_dc_t = np.mean(MM_dc_t.reshape(-1,ave),axis=1) - MM_dc_n = np.mean(MM_dc_n.reshape(-1,ave),axis=1) + # MM_dc_t = np.mean(MM_dc_t.reshape(-1,ave),axis=1) + # MM_dc_n = np.mean(MM_dc_n.reshape(-1,ave),axis=1) strassen_t = strassen[:,0] strassen_n = strassen[:,1] - strassen_t = np.mean(strassen_t.reshape(-1,ave),axis=1) - strassen_n = np.mean(strassen_n.reshape(-1,ave),axis=1) + # strassen_t = np.mean(strassen_t.reshape(-1,ave),axis=1) + # strassen_n = np.mean(strassen_n.reshape(-1,ave),axis=1) - # winograd_t = winograd[:,0] - # winograd_n = winograd[:,1] + winograd_t = winograd[:,0] + winograd_n = winograd[:,1] # winograd_t = np.mean(winograd_t.reshape(-1,ave),axis=1) # winograd_n = np.mean(winograd_n.reshape(-1,ave),axis=1) blas_t = blas[:,0] blas_n = blas[:,1] - blas_t = np.mean(blas_t.reshape(-1,ave),axis=1) - blas_n = np.mean(blas_n.reshape(-1,ave),axis=1) + # 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 @@ -254,14 +261,16 @@ def plot_c_res(ave, num): plt.rc('axes', labelsize=23) plt.rc('xtick', labelsize=23) plt.rc('ytick', labelsize=23) - plt.plot(MM_n, MM_t, label='3 For Loops', lw=5) - # plt.plot(winograd_n, winograd_t, label='Winograd MM', lw=5) - plt.plot(blas_n, blas_t, label='Blas', lw=5) - plt.plot(strassen_n, strassen_t, label='Strassen', lw=5) - plt.plot(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) plt.ylabel("time (s)") - plt.grid(True) + plt.grid(True, which="both", ls="-") plt.tight_layout() plt.legend(fontsize=19) plt.savefig('c_meas_' + str(num)+ '.pdf') @@ -271,23 +280,42 @@ def plot_c_res(ave, num): # plt.plot(blas_n, func(blas_n, *popt2), 'r-', label='fit MM: a=%5.5f, b=%5.10f' % tuple(popt2)) 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, h # test%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% if __name__ == '__main__': - plot_c_res(1, 4096) - - - # plot(8) - # n = np.logspace(1,10,10,base=2,dtype=(np.int)) + # 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) - A = np.random.randint(-10, 10, (5,3)) - B = np.random.randint(-10, 10, (3,5)) + # A = np.random.randint(-10, 6, (5,3)) + # B = np.random.randint(-10, 6, (3,5)) - C = winograd2(A, B) - C_test = A@B - print(C) - print(C_test) + # C = winograd2(A, B) + # C_test = A@B + # print(C) + # print(C_test) # print(np.equal(C, C_test)) # t_np = test_perfomance(n) diff --git a/buch/papers/multiplikation/code/c_matrix.h b/buch/papers/multiplikation/code/c_matrix.h index 13df55d..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, 30/05/2021, 22:00:57 */ +/* Seminar Matrizen, autogenerated File, Michael Schmid, 10/08/2021, 05:46:32 */ #include <stdint.h> const int A0[][2] = { - {-15,68}, - {49,86} + {60,-84}, + {-66,-1} }; const int B0[][2] = { - {33,73}, - {38,-76} + {-45,87}, + {-38,-73} }; const double dB0[][2] = { - {33,73}, - {38,-76} + {-45,87}, + {-38,-73} }; const double dA0[][2] = { - {-15,68}, - {49,86} + {60,-84}, + {-66,-1} }; const int A1[][4] = { - {75,-38,-32,-65}, - {37,74,-31,29}, - {15,-62,-20,-20}, - {-31,-35,-89,47} + {-72,-19,-91,62}, + {-36,-74,-44,-47}, + {-39,-31,50,-93}, + {-81,2,-17,-86} }; const int B1[][4] = { - {71,90,78,-98}, - {4,63,12,-47}, - {11,-44,75,-69}, - {95,-15,64,23} + {-66,39,-23,52}, + {-88,-13,13,-13}, + {-45,-70,28,-20}, + {96,5,88,96} }; const double dB1[][4] = { - {71,90,78,-98}, - {4,63,12,-47}, - {11,-44,75,-69}, - {95,-15,64,23} + {-66,39,-23,52}, + {-88,-13,13,-13}, + {-45,-70,28,-20}, + {96,5,88,96} }; const double dA1[][4] = { - {75,-38,-32,-65}, - {37,74,-31,29}, - {15,-62,-20,-20}, - {-31,-35,-89,47} + {-72,-19,-91,62}, + {-36,-74,-44,-47}, + {-39,-31,50,-93}, + {-81,2,-17,-86} }; const int A2[][8] = { - {80,42,3,-16,6,55,87,16}, - {-99,-14,21,-1,-94,-56,91,10}, - {-47,-55,-59,62,12,-53,87,-65}, - {-60,94,-67,23,-62,33,-63,-72}, - {12,-75,16,21,22,-37,1,16}, - {-100,-99,82,-66,2,64,-13,44}, - {59,-100,-90,8,36,-24,18,88}, - {73,-58,75,-100,-19,-29,85,-19} + {-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] = { - {-61,88,69,49,-53,47,73,45}, - {16,14,-88,-11,-67,-73,-20,43}, - {-60,-63,26,32,-29,18,-44,-69}, - {1,21,21,38,7,-100,-61,-76}, - {-90,95,-99,88,49,-80,27,-36}, - {24,-12,-47,-7,29,15,52,37}, - {-98,-76,29,76,-41,-75,97,79}, - {62,-90,-35,-14,-30,-42,-95,52} + {-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] = { - {-61,88,69,49,-53,47,73,45}, - {16,14,-88,-11,-67,-73,-20,43}, - {-60,-63,26,32,-29,18,-44,-69}, - {1,21,21,38,7,-100,-61,-76}, - {-90,95,-99,88,49,-80,27,-36}, - {24,-12,-47,-7,29,15,52,37}, - {-98,-76,29,76,-41,-75,97,79}, - {62,-90,-35,-14,-30,-42,-95,52} + {-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] = { - {80,42,3,-16,6,55,87,16}, - {-99,-14,21,-1,-94,-56,91,10}, - {-47,-55,-59,62,12,-53,87,-65}, - {-60,94,-67,23,-62,33,-63,-72}, - {12,-75,16,21,22,-37,1,16}, - {-100,-99,82,-66,2,64,-13,44}, - {59,-100,-90,8,36,-24,18,88}, - {73,-58,75,-100,-19,-29,85,-19} - }; -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 Binary files differindex 547d794..f637ae4 100644 --- a/buch/papers/multiplikation/code/c_meas_4096.pdf +++ b/buch/papers/multiplikation/code/c_meas_4096.pdf diff --git a/buch/papers/multiplikation/code/ci.txt b/buch/papers/multiplikation/code/ci.txt new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/buch/papers/multiplikation/code/ci.txt diff --git a/buch/papers/multiplikation/code/helper_class.py b/buch/papers/multiplikation/code/helper_class.py index 485fa76..3b74f67 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)) - C = helper.write_c_matrix(n) + n = np.logspace(1,11,11,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 1a0cd5d..7bffb6e 100644 --- a/buch/papers/multiplikation/code/meas/MM.txt +++ b/buch/papers/multiplikation/code/meas/MM.txt @@ -1,12 +1,110 @@ 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.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.000653,64 -0.005397,128 -0.045147,256 -0.487710,512 -3.964180,1024 -128.863544,2048 -996.370209,4096 +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 0d5580a..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.000006,2 -0.000007,4 -0.000035,8 -0.000228,16 -0.001310,32 -0.007204,64 -0.034338,128 -0.267511,256 -2.131212,512 -17.177403,1024 -146.112874,2048 -1156.777565,4096 +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.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 6b7cd0b..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.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.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.001240,128 -0.009657,256 -0.072523,512 -0.735149,1024 -6.895747,2048 -56.812183,4096 +0.001216,128 +0.001233,128 +0.001364,128 +0.001278,128 +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..e69de29 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/MM.txt 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..e69de29 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/Wino.txt 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..e69de29 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/blas.txt 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..e69de29 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/dc.txt 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..e69de29 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/strassen.txt 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 89cf41a..d6e040e 100644 --- a/buch/papers/multiplikation/code/meas/strassen.txt +++ b/buch/papers/multiplikation/code/meas/strassen.txt @@ -1,12 +1,110 @@ 0.000000,2 -0.000003,4 -0.000010,8 -0.000086,16 -0.000476,32 -0.003366,64 -0.025547,128 -0.184593,256 -1.248713,512 -9.007700,1024 -61.079879,2048 -424.493037,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.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 3a4d88b..970a3f4 100644 --- a/buch/papers/multiplikation/code/meas/winograd.txt +++ b/buch/papers/multiplikation/code/meas/winograd.txt @@ -1,11 +1,110 @@ +0.000001,2 0.000000,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,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.000091,32 -0.000663,64 -0.005182,128 -0.046038,256 -0.533429,512 -4.257458,1024 -130.378038,2048 +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_1024.pdf b/buch/papers/multiplikation/code/meas_1024.pdf Binary files differindex fd0a108..f489a7d 100644 --- a/buch/papers/multiplikation/code/meas_1024.pdf +++ b/buch/papers/multiplikation/code/meas_1024.pdf diff --git a/buch/papers/multiplikation/code/meas_1024.txt b/buch/papers/multiplikation/code/meas_1024.txt index c5ce619..ab507a2 100644 --- a/buch/papers/multiplikation/code/meas_1024.txt +++ b/buch/papers/multiplikation/code/meas_1024.txt @@ -1,6 +1,6 @@ 2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 1.280000000000000000e+02 2.560000000000000000e+02 5.120000000000000000e+02 1.024000000000000000e+03 -1.502037048339843750e-05 6.628036499023437500e-05 4.780292510986328125e-04 2.713203430175781250e-03 2.115225791931152344e-02 1.758832931518554688e-01 1.338865518569946289e+00 1.009106445312500000e+01 8.192077994346618652e+01 7.835870332717895508e+02 -6.675720214843750000e-06 7.200241088867187500e-05 5.540847778320312500e-04 3.144979476928710938e-03 2.545046806335449219e-02 2.083067893981933594e-01 1.659256219863891602e+00 1.319160294532775879e+01 1.046767003536224365e+02 9.679818902015686035e+02 -1.668930053710937500e-05 1.628398895263671875e-04 7.648468017578125000e-04 4.426956176757812500e-03 2.922415733337402344e-02 1.800994873046875000e-01 1.286747694015502930e+00 9.412034273147583008e+00 6.263725924491882324e+01 4.427414393424987793e+02 -2.408027648925781250e-05 8.463859558105468750e-05 4.761219024658203125e-04 2.339839935302734375e-03 1.682758331298828125e-02 1.299476623535156250e-01 1.048770904541015625e+00 8.114667415618896484e+00 6.373566389083862305e+01 6.489995403289794922e+02 -1.573562622070312500e-05 7.152557373046875000e-06 7.152557373046875000e-06 2.074241638183593750e-05 5.388259887695312500e-05 6.365776062011718750e-05 3.257751464843750000e-03 1.396179199218750000e-03 3.274917602539062500e-03 2.186250686645507812e-02 +1.859664916992187500e-05 8.296966552734375000e-05 5.471706390380859375e-04 3.053665161132812500e-03 2.407431602478027344e-02 1.868948936462402344e-01 1.563691616058349609e+00 1.100623321533203125e+01 8.547679090499877930e+01 7.507572824954986572e+02 +8.106231689453125000e-06 9.012222290039062500e-05 7.290840148925781250e-04 4.970788955688476562e-03 2.718997001647949219e-02 2.652802467346191406e-01 1.777865171432495117e+00 1.327002429962158203e+01 1.053971357345581055e+02 8.473208103179931641e+02 +2.098083496093750000e-05 1.742839813232421875e-04 9.438991546630859375e-04 4.754066467285156250e-03 4.852557182312011719e-02 2.204136848449707031e-01 1.447179555892944336e+00 9.938656568527221680e+00 6.396102952957153320e+01 4.614939928054809570e+02 +2.789497375488281250e-05 1.049041748046875000e-04 5.528926849365234375e-04 4.555702209472656250e-03 1.871442794799804688e-02 1.530685424804687500e-01 1.194762229919433594e+00 8.298985958099365234e+00 6.836994743347167969e+01 5.373736469745635986e+02 +1.835823059082031250e-05 7.867813110351562500e-06 1.001358032226562500e-05 5.412101745605468750e-05 4.267692565917968750e-05 1.184940338134765625e-04 2.441406250000000000e-04 6.957054138183593750e-04 2.217054367065429688e-03 1.880884170532226562e-02 diff --git a/buch/papers/multiplikation/code/meas_128.pdf b/buch/papers/multiplikation/code/meas_128.pdf Binary files differindex ed1ec63..c54648f 100644 --- a/buch/papers/multiplikation/code/meas_128.pdf +++ b/buch/papers/multiplikation/code/meas_128.pdf diff --git a/buch/papers/multiplikation/code/meas_128.txt b/buch/papers/multiplikation/code/meas_128.txt index 976bbdf..f3a5beb 100644 --- a/buch/papers/multiplikation/code/meas_128.txt +++ b/buch/papers/multiplikation/code/meas_128.txt @@ -1,6 +1,6 @@ 2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 1.280000000000000000e+02 -1.978874206542968750e-05 1.134872436523437500e-04 4.298686981201171875e-04 2.815246582031250000e-03 2.616596221923828125e-02 1.767718791961669922e-01 1.293319463729858398e+00 -6.675720214843750000e-06 1.251697540283203125e-04 4.818439483642578125e-04 3.490447998046875000e-03 2.465796470642089844e-02 2.014584541320800781e-01 1.630620479583740234e+00 -2.408027648925781250e-05 2.126693725585937500e-04 1.172780990600585938e-03 4.364490509033203125e-03 3.148293495178222656e-02 2.010228633880615234e-01 1.429297924041748047e+00 -2.932548522949218750e-05 1.466274261474609375e-04 4.270076751708984375e-04 2.837419509887695312e-03 1.723575592041015625e-02 1.308519840240478516e-01 1.015527009963989258e+00 -3.337860107421875000e-05 1.096725463867187500e-05 9.536743164062500000e-06 3.600120544433593750e-05 2.837181091308593750e-05 5.912780761718750000e-05 1.981019973754882812e-03 +1.239776611328125000e-05 5.507469177246093750e-05 3.888607025146484375e-04 2.762079238891601562e-03 2.097773551940917969e-02 1.672370433807373047e-01 1.410297393798828125e+00 +5.483627319335937500e-06 5.888938903808593750e-05 3.871917724609375000e-04 3.364324569702148438e-03 2.481031417846679688e-02 2.047052383422851562e-01 1.712310314178466797e+00 +1.358985900878906250e-05 1.189708709716796875e-04 6.430149078369140625e-04 5.586385726928710938e-03 3.101944923400878906e-02 1.874091625213623047e-01 1.327976465225219727e+00 +1.978874206542968750e-05 7.224082946777343750e-05 4.618167877197265625e-04 3.294944763183593750e-03 1.755571365356445312e-02 1.360688209533691406e-01 1.028253555297851562e+00 +1.215934753417968750e-05 5.722045898437500000e-06 2.074241638183593750e-05 4.339218139648437500e-05 2.813339233398437500e-05 5.292892456054687500e-05 1.921653747558593750e-04 diff --git a/buch/papers/multiplikation/code/meas_256.pdf b/buch/papers/multiplikation/code/meas_256.pdf Binary files differindex 5f049dc..2eb177b 100644 --- a/buch/papers/multiplikation/code/meas_256.pdf +++ b/buch/papers/multiplikation/code/meas_256.pdf diff --git a/buch/papers/multiplikation/code/meas_256.txt b/buch/papers/multiplikation/code/meas_256.txt index 15035c6..62e77cb 100644 --- a/buch/papers/multiplikation/code/meas_256.txt +++ b/buch/papers/multiplikation/code/meas_256.txt @@ -1,6 +1,6 @@ 2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 1.280000000000000000e+02 2.560000000000000000e+02 -1.049041748046875000e-05 5.340576171875000000e-05 5.936622619628906250e-04 2.707719802856445312e-03 2.246093750000000000e-02 1.631326675415039062e-01 1.335460901260375977e+00 1.052024245262145996e+01 -4.768371582031250000e-06 5.531311035156250000e-05 8.208751678466796875e-04 3.099203109741210938e-03 2.490711212158203125e-02 2.070860862731933594e-01 1.739669799804687500e+00 1.384817218780517578e+01 -1.478195190429687500e-05 1.132488250732421875e-04 5.970001220703125000e-04 3.906726837158203125e-03 3.041696548461914062e-02 2.000186443328857422e-01 1.392681598663330078e+00 9.388872385025024414e+00 -1.716613769531250000e-05 6.866455078125000000e-05 5.314350128173828125e-04 2.688407897949218750e-03 1.695108413696289062e-02 1.297233104705810547e-01 1.087257385253906250e+00 8.699601650238037109e+00 -2.336502075195312500e-05 4.529953002929687500e-06 8.106231689453125000e-06 4.291534423828125000e-05 6.008148193359375000e-05 8.988380432128906250e-05 1.647472381591796875e-04 4.460811614990234375e-04 +1.144409179687500000e-05 5.507469177246093750e-05 3.774166107177734375e-04 3.177404403686523438e-03 2.508044242858886719e-02 2.120554447174072266e-01 1.431464910507202148e+00 1.076412820816040039e+01 +5.722045898437500000e-06 5.745887756347656250e-05 4.494190216064453125e-04 3.611087799072265625e-03 3.317713737487792969e-02 2.292332649230957031e-01 2.090558290481567383e+00 1.306217479705810547e+01 +1.788139343261718750e-05 1.168251037597656250e-04 5.981922149658203125e-04 4.416465759277343750e-03 3.002405166625976562e-02 2.104022502899169922e-01 1.488269329071044922e+00 9.164114713668823242e+00 +1.955032348632812500e-05 7.224082946777343750e-05 3.829002380371093750e-04 2.558946609497070312e-03 2.043128013610839844e-02 1.361320018768310547e-01 1.089214324951171875e+00 8.553364753723144531e+00 +2.384185791015625000e-05 5.245208740234375000e-06 6.437301635742187500e-06 2.455711364746093750e-05 4.148483276367187500e-05 8.702278137207031250e-05 3.793239593505859375e-04 6.709098815917968750e-04 diff --git a/buch/papers/multiplikation/code/meas_32.pdf b/buch/papers/multiplikation/code/meas_32.pdf Binary files differindex 94c3731..b926095 100644 --- a/buch/papers/multiplikation/code/meas_32.pdf +++ b/buch/papers/multiplikation/code/meas_32.pdf diff --git a/buch/papers/multiplikation/code/meas_32.txt b/buch/papers/multiplikation/code/meas_32.txt index afdb6d5..0fdc18d 100644 --- a/buch/papers/multiplikation/code/meas_32.txt +++ b/buch/papers/multiplikation/code/meas_32.txt @@ -1,6 +1,6 @@ 2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 -1.215934753417968750e-05 5.459785461425781250e-05 3.700256347656250000e-04 3.249406814575195312e-03 1.996850967407226562e-02 -4.529953002929687500e-06 5.650520324707031250e-05 4.577636718750000000e-04 4.029273986816406250e-03 2.444481849670410156e-02 -1.311302185058593750e-05 1.165866851806640625e-04 6.275177001953125000e-04 4.323244094848632812e-03 2.624726295471191406e-02 -1.835823059082031250e-05 6.890296936035156250e-05 3.914833068847656250e-04 2.423048019409179688e-03 1.761770248413085938e-02 -1.263618469238281250e-05 5.006790161132812500e-06 5.960464477539062500e-06 1.144409179687500000e-05 3.600120544433593750e-05 +1.239776611328125000e-05 5.507469177246093750e-05 3.802776336669921875e-04 2.795457839965820312e-03 2.073740959167480469e-02 +5.006790161132812500e-06 5.841255187988281250e-05 3.988742828369140625e-04 3.505229949951171875e-03 2.511668205261230469e-02 +1.335144042968750000e-05 1.149177551269531250e-04 6.387233734130859375e-04 4.088878631591796875e-03 2.969408035278320312e-02 +1.955032348632812500e-05 8.058547973632812500e-05 3.998279571533203125e-04 2.514839172363281250e-03 1.842117309570312500e-02 +1.215934753417968750e-05 8.583068847656250000e-06 6.675720214843750000e-06 2.694129943847656250e-05 2.789497375488281250e-05 diff --git a/buch/papers/multiplikation/code/meas_4096.pdf b/buch/papers/multiplikation/code/meas_4096.pdf Binary files differnew file mode 100644 index 0000000..ecf2cff --- /dev/null +++ b/buch/papers/multiplikation/code/meas_4096.pdf diff --git a/buch/papers/multiplikation/code/meas_4096.txt b/buch/papers/multiplikation/code/meas_4096.txt new file mode 100644 index 0000000..cae1bc6 --- /dev/null +++ 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/code/meas_64.pdf b/buch/papers/multiplikation/code/meas_64.pdf Binary files differindex 3a90949..92af29b 100644 --- a/buch/papers/multiplikation/code/meas_64.pdf +++ b/buch/papers/multiplikation/code/meas_64.pdf diff --git a/buch/papers/multiplikation/code/meas_64.txt b/buch/papers/multiplikation/code/meas_64.txt index ae6ff9b..b4fc7a1 100644 --- a/buch/papers/multiplikation/code/meas_64.txt +++ b/buch/papers/multiplikation/code/meas_64.txt @@ -1,6 +1,6 @@ 2.000000000000000000e+00 4.000000000000000000e+00 8.000000000000000000e+00 1.600000000000000000e+01 3.200000000000000000e+01 6.400000000000000000e+01 -1.645088195800781250e-05 7.295608520507812500e-05 3.807544708251953125e-04 2.672195434570312500e-03 2.010774612426757812e-02 1.662156581878662109e-01 -7.390975952148437500e-06 7.843971252441406250e-05 4.265308380126953125e-04 3.107070922851562500e-03 2.457642555236816406e-02 2.122807502746582031e-01 -1.931190490722656250e-05 1.568794250488281250e-04 7.593631744384765625e-04 3.937005996704101562e-03 3.596329689025878906e-02 2.131938934326171875e-01 -2.622604370117187500e-05 9.226799011230468750e-05 3.504753112792968750e-04 2.469539642333984375e-03 1.652932167053222656e-02 1.281068325042724609e-01 -1.788139343261718750e-05 7.152557373046875000e-06 6.914138793945312500e-06 1.120567321777343750e-05 2.884864807128906250e-05 6.914138793945312500e-05 +2.145767211914062500e-05 6.175041198730468750e-05 4.422664642333984375e-04 3.235816955566406250e-03 2.289748191833496094e-02 1.855163574218750000e-01 +1.025199890136718750e-05 6.341934204101562500e-05 5.202293395996093750e-04 3.566026687622070312e-03 3.026723861694335938e-02 2.312932014465332031e-01 +2.384185791015625000e-05 1.807212829589843750e-04 6.821155548095703125e-04 4.796504974365234375e-03 2.968001365661621094e-02 2.291278839111328125e-01 +3.504753112792968750e-05 1.106262207031250000e-04 4.322528839111328125e-04 2.696514129638671875e-03 2.188420295715332031e-02 1.477701663970947266e-01 +3.218650817871093750e-05 1.144409179687500000e-05 7.390975952148437500e-06 4.625320434570312500e-05 3.814697265625000000e-05 5.435943603515625000e-05 diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index bc4bfcf..21fa9df 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -3,28 +3,22 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Einleitung \label{multiplikation:section:einleitung}} -\rhead{Einleitung} +\section{Matrizenmultiplikation \label{multiplikation:section:einleitung}} +\rhead{Matrizenmultiplikation} -Die Multiplikation zweier Matrizen ist eine wichtige Operation die in verschiedensten Teilen der Mathematik Anwendung findet. -Die Beschreibung der Multiplikation aus der Definition 2.10 (\textcolor{blue} {Kein Hyperlink zu einer Definition?)}: +Die Multiplikation zweier Matrizen ist eine wichtige Operation, die in verschiedensten Teilen der Mathematik Anwendung findet. +Die Beschreibung der Multiplikation aus der Definition 2.10: Eine $m\times n$-Matrix $\mathbf{A}\in M_{m\times n}(\Bbbk)$ und eine $n\times p$-Matrix $\mathbf{B}\in M_{n\times l}(\Bbbk)$ haben als Produkt eine $n\times l$-Matrix $\mathbf{C}=\mathbf{AB}\in M_{n\times l}(\Bbbk)$ mit den Koeffizienten \begin{equation} -c_{ij} = \sum_{k=1}^n a_{ik} b_{kj}. +C_{ij} = \sum_{k=1}^n A_{ik} B_{kj}. \label{multiplikation:eq:MM} \end{equation} -Grafisch kann die Matrizenmultiplikation $AB=C$ wie in \ref{multiplikation:fig:mm_viz} visualisiert werden. -\begin{figure} - \center - \includegraphics[]{papers/multiplikation/images/mm_visualisation} - \caption{Matrizen Multiplikation} - \label{multiplikation:fig:mm_viz} -\end{figure} -Im Fall einer Matrizengr\"osse von $2\times 2$ +Grafisch kann die Matrizenmultiplikation $\mathbf{AB}=\mathbf{C}$ wie in Abbildung \ref{multiplikation:fig:mm_viz} visualisiert werden. +Im Fall einer Matrizengr\"osse von $2\times 2$ kann die Matrixgleichung \begin{equation} \begin{bmatrix} A_{11} & A_{12}\\ @@ -40,7 +34,7 @@ C_{11} & C_{12}\\ C_{21} & C_{22} \end{bmatrix} \end{equation} -kann die Gleichung der einzelnen Terme +explizt als Gleichungen \begin{equation} \label{multiplikation:eq:MM_exp} \begin{split} C_{11} &= A_{11} \cdot B_{11} + A_{12} \cdot B_{21}\\ @@ -49,4 +43,10 @@ C_{21} &= A_{21} \cdot B_{11} + A_{22} \cdot B_{21}\\ C_{22} &= A_{21} \cdot B_{12} + A_{22} \cdot B_{22} \end{split} \end{equation} -explizit geschrieben werden. +der einzelnen Terme geschrieben werden. +\begin{figure} + \center + \includegraphics[]{papers/multiplikation/images/mm_visualisation} + \caption{Grafische Illustration der Matrizenmultiplikation} + \label{multiplikation:fig:mm_viz} +\end{figure} diff --git a/buch/papers/multiplikation/images/algo_tab.pdf b/buch/papers/multiplikation/images/algo_tab.pdf Binary files differnew file mode 100644 index 0000000..7f2bb4f --- /dev/null +++ b/buch/papers/multiplikation/images/algo_tab.pdf 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/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf Binary files differindex dfa2ba4..2519553 100644 --- a/buch/papers/multiplikation/images/bigo.pdf +++ b/buch/papers/multiplikation/images/bigo.pdf diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex index e3293e4..63fd0fd 100644 --- a/buch/papers/multiplikation/images/bigo.tex +++ b/buch/papers/multiplikation/images/bigo.tex @@ -39,67 +39,72 @@ \begin{document} \begin{tikzpicture} + \begin{axis}[ - axis lines = left, - xlabel = $n$ (Data Input), - ylabel = {$t$ (time)}, - legend pos=north east, + xmode=log, ymode=log, + xmin=1e-0, xmax=5000, + ymin=10e-1, ymax=1e7, + grid=both, + major grid style={black!50}, + xlabel = data input size, + ylabel = {time}, + legend pos=north west, very thick, - ymax = 500, yticklabels=\empty, xticklabels=\empty, scale only axis=true, - width=12cm, height=6cm, + width=12cm, height=8cm, + legend cell align={left} ] \addplot [ - domain= 1:20, + domain= 1:5000, samples=100, color=red, ] {1}; \addlegendentry{$\mathcal{O}(1)$} \addplot [ - domain= 1:20, + domain= 1:5000, samples=100, color=green, ] {x}; \addlegendentry{$\mathcal{O}(n)$} \addplot [ - domain= 1:20, + domain= 1:50000, samples=100, color=blue, ] {x^2}; -\addlegendentry{$\mathcal{O}(n^2)$} +\addlegendentry{$\mathcal{O}\left(n^2\right)$} \addplot [ - domain= 1:10, + domain= 1:500, samples=100, color=purple, ] {x^3}; -\addlegendentry{$\mathcal{O}(n^3)$} +\addlegendentry{$\mathcal{O}\left(n^3\right)$} \addplot [ - domain= 1:10, + domain= 1:500, samples=100, color=black, ] -{exp(x)}; -\addlegendentry{$\mathcal{O}(e^n)$} +{exp(x) - 1.7}; +\addlegendentry{$\mathcal{O}\left(e^n\right)$} \addplot [ - domain= 1:20, + domain= 1:5000, samples=100, color=orange, ] -{log2(x)}; +{log2(x)+1}; \addlegendentry{$\mathcal{O}(\log n)$} \addplot [ - domain= 1:20, + domain= 1:5000, samples=100, color=gray, ] -{x*log2(x)}; +{x*log2(x)+1}; \addlegendentry{$\mathcal{O}(n \log n)$} \end{axis} \end{tikzpicture} diff --git a/buch/papers/multiplikation/images/c_meas_4096.pdf b/buch/papers/multiplikation/images/c_meas_4096.pdf Binary files differnew file mode 100644 index 0000000..304015a --- /dev/null +++ b/buch/papers/multiplikation/images/c_meas_4096.pdf diff --git a/buch/papers/multiplikation/images/meas_1024.pdf b/buch/papers/multiplikation/images/meas_1024.pdf Binary files differnew file mode 100644 index 0000000..70c7ec1 --- /dev/null +++ b/buch/papers/multiplikation/images/meas_1024.pdf diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf Binary files differnew file mode 100644 index 0000000..521151e --- /dev/null +++ b/buch/papers/multiplikation/images/meas_c.pdf diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex new file mode 100644 index 0000000..12d3527 --- /dev/null +++ b/buch/papers/multiplikation/images/meas_c.tex @@ -0,0 +1,150 @@ + +\documentclass[border=10pt,varwidth]{standalone} +\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{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{cite} +\usepackage{url} +\usepackage{amsmath,amsfonts,amssymb} +\usepackage{tikz} +\usepackage{pgfplotstable} +\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{tikzpicture} +\begin{axis}[ +xmode=log, ymode=log, +xmin=30, xmax=10000, +ymin=1e-5, ymax=2e4, +grid=both, +major grid style={black!50}, +xlabel = data input ($n$), +ylabel = {time ($s$)}, +legend pos=north west, +very thick, +scale only axis=true, +width=12cm, height=8cm, + log basis x={10}, + legend cell align={left} +] +\addlegendentry{Winograd} +\addplot[ color=blue, + error bars/.cd, y dir=both, y explicit, +] coordinates { +%(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,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) +}; + +\addlegendentry{MM div and conq} +\addplot[ color=green, +] coordinates { +%(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) +}; + +\addlegendentry{MM} +\addplot [ color=red, +]coordinates { +%(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=purple, +] coordinates { +%(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) +}; +\end{axis} +\end{tikzpicture} + +\end{document} diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf Binary files differnew file mode 100644 index 0000000..fe89773 --- /dev/null +++ b/buch/papers/multiplikation/images/meas_python.pdf diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex new file mode 100644 index 0000000..ad43cf6 --- /dev/null +++ b/buch/papers/multiplikation/images/meas_python.tex @@ -0,0 +1,145 @@ + +\documentclass[border=10pt,varwidth]{standalone} +\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{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{cite} +\usepackage{url} +\usepackage{amsmath,amsfonts,amssymb} +\usepackage{tikz} +\usepackage{pgfplotstable} +\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{tikzpicture} +\begin{axis}[ +xmode=log, ymode=log, +xmin=30, xmax=4200, +ymin=0.01, ymax=70000, +grid=both, +major grid style={black!50}, +xlabel = data input ($n$), +ylabel = {time ($s$)}, +legend pos=north west, +very thick, +scale only axis=true, +width=12cm, height=8cm, + log basis x={10}, + legend cell align={left} +] +\addlegendentry{Winograd} +\addplot[ color=blue, +] coordinates { +% (2, 2.7895e-05 ) +% (4, 0.000104904) +% (8, 0.000552893) +% (16, 0.0045557 ) +(32, 0.0187144 ) +(64, 0.153069 ) +(128, 1.19476 ) +(256, 8.29899 ) +(512, 68.3699 ) +(1024,537.374 ) +(2046,4884.61) +(4096,43597.1) +}; +\addlegendentry{Strassen} +\addplot [ color=black, +]coordinates { + % (2,2.09808e-05 ) + % (4,0.000174284 ) + % (8,0.000943899 ) + % (16,0.00475407 ) + (32,0.0485256 ) + (64,0.220414 ) + (128,1.44718 ) + (256,9.93866 ) + (512,63.961 ) +(1024,461.494 ) +(2046,3860.57) +(4096,22904.3) +}; + +\addlegendentry{MM div and conq} +\addplot[ color=green, +] coordinates { + % (2,8.10623e-06 ) + % (4,9.01222e-05 ) + % (8,0.000729084 ) + % (16,0.00497079 ) + (32,0.02719 ) + (64,0.26528 ) + (128,1.77787 ) + (256,13.27 ) + (512,105.397 ) +(1024,847.321 ) +(2046,7375.93) +(4096,58466) +}; + +\addlegendentry{MM} +\addplot [ color=red, +]coordinates { + % (2,1.85966e-05) + % (4,8.29697e-05 ) + % (8,0.000547171) + % (16,0.00305367 ) + (32, 0.0240743 ) + (64, 0.186895 ) + (128, 1.56369 ) + (256, 11.0062 ) + (512, 85.4768) +(1024,750.757 ) +(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) +% }; + +\end{axis} +\end{tikzpicture} + +\end{document} diff --git a/buch/papers/multiplikation/images/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf Binary files differindex 9899dcb..d150125 100644 --- a/buch/papers/multiplikation/images/strassen.pdf +++ b/buch/papers/multiplikation/images/strassen.pdf diff --git a/buch/papers/multiplikation/images/strassen.tex b/buch/papers/multiplikation/images/strassen.tex index 797772b..b51a9d5 100644 --- a/buch/papers/multiplikation/images/strassen.tex +++ b/buch/papers/multiplikation/images/strassen.tex @@ -56,7 +56,7 @@ A_{11}B_{11} \& A_{12}B_{12} \& A_{21}B_{12} \& A_{22}B_{12} \\ A_{11}B_{22} \& A_{12}B_{22} \& A_{21}B_{22} \& A_{22}B_{22} \\ };} - + \foreach \j in {1,...,7} { \matrix(M\i\j)[matrix of math nodes,nodes in empty cells, @@ -76,18 +76,18 @@ } \huge{ - \node at (-3,-20) {$C_{22}=$}; - \node at (-3,-15) {$C_{21}=$} ; - \node at (-3,-10) {$C_{12}=$} ; - \node at (-3,-5) {$C_{11}=$} ; - - \node at (5,-2) {I}; - \node at (10,-2) {II}; - \node at (15,-2) {III}; - \node at (20,-2) {IV}; - \node at (25,-2) {V}; - \node at (30,-2) {VI}; - \node at (35,-2) {VII}; + \node at (-3,-20) {$\mathbf{C}_{22}=$}; + \node at (-3,-15) {$\mathbf{C}_{21}=$} ; + \node at (-3,-10) {$\mathbf{C}_{12}=$} ; + \node at (-3,-5) {$\mathbf{C}_{11}=$} ; + + \node at (5,-2) {$\mathbf{P}$}; + \node at (10,-2) {$\mathbf{Q}$}; + \node at (15,-2) {$\mathbf{R}$}; + \node at (20,-2) {$\mathbf{S}$}; + \node at (25,-2) {$\mathbf{T}$}; + \node at (30,-2) {$\mathbf{U}$}; + \node at (35,-2) {$\mathbf{V}$}; } @@ -100,41 +100,132 @@ \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X4-3-3)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X4-4-4)] {}; +% P \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-4-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-1-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-4-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-1-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M14-1-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M14-2-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-2)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-2-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-4-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-2-2)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-4-2)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M23-3-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M23-4-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M21-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M21-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M21-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M21-1-1)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-3)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M34-1-4)] {}; -\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M34-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M31-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M31-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M31-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M31-1-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-4-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-1-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-4-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-1-1)] {}; + +% Q +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M12-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M12-1-3)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M22-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M22-1-3)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-3)] {}; + \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M42-1-4)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M42-1-3)] {}; + +% R + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M13-3-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M13-4-1)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M23-3-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M23-4-1)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M33-3-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M33-4-1)] {}; + \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M43-3-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M43-4-1)] {}; + +% S + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M14-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M14-2-4)] {}; + + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M24-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M24-2-4)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M34-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M34-2-4)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M44-1-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M44-2-4)] {}; + +%T + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M35-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M35-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M45-4-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M45-4-2)] {}; + +% U + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M16-1-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M16-1-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M16-3-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M16-3-1)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M26-1-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M26-1-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M26-3-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M26-3-1)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M36-1-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M36-1-1)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M36-3-3)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M36-3-1)] {}; + \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M46-1-3)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M46-1-1)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M46-3-3)] {}; \node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M46-3-1)] {}; + +%V + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-2-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-4-2)] {}; + + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M27-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M27-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M27-2-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M27-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M37-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M37-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M37-2-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M37-4-2)] {}; + +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M47-2-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M47-4-4)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M47-2-2)] {}; +\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=gray, fit=(M47-4-2)] {}; + + + + + \end{tikzpicture} \end{document} diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 83be814..51872f5 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -4,18 +4,17 @@ % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{L\"osungsmethoden} -\rhead{L\"osungsmethoden} +\section{Algorithmen} +\rhead{Algorithmen} -In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultiplikation vorgestellt, auch werden Libraries zur automatisierten Verwendung von vordefinierten Algorithmen gezeigt. +In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultiplikation vorgestellt, auch werden Bibliotheken zur unkomplizierten Verwendung von vordefinierten Algorithmen gezeigt. \subsection{Standard Algorithmus} -Der Standard Methode kann im Algorithmus \ref{multiplikation:alg:smm} entnommen werden. -Hierf\"ur wurde die Gleichung \eqref{multiplikation:eq:MM} direkt implementiert. -Die \texttt{For i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, die \texttt{For j} Schleife iteriert \"uber alle Spalten der $\mathbf{B}$ Matrix und die \texttt{For k} Schleife iteriert \"uber alle Eintr\"age dieser Zeilen bzw. Spalten. - -\begin{algorithm}\caption{Matrix Multiplication} +Die Standardmethode ist im Algorithmus \ref{multiplikation:alg:smm} implementiert. +Hierf\"ur wurde die Gleichung \eqref{multiplikation:eq:MM} direkt umgesetzt. +Die \texttt{for i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, die \texttt{for j} Schleife iteriert \"uber alle Spalten der $\mathbf{B}$ Matrix und die \texttt{for k} Schleife iteriert \"uber alle Eintr\"age dieser Zeilen bzw. Spalten. +\begin{algorithm}\footnotesize\caption{Matrizenmultiplikation} \label{multiplikation:alg:smm} \setlength{\lineskip}{7pt} \begin{algorithmic}[1] @@ -38,17 +37,18 @@ Die \texttt{For i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, \EndFunction \end{algorithmic} \end{algorithm} - -Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O}(n^3)$ +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 zu markant besseren Laufzeiten. -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. +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} (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. -Die Matrizen $\mathbf{A}$ und $\mathbf{B}$ werden in jeweils vier Blockmatrizen der gr\"osse $2^{n-1} \times 2^{n-1}$ +Zur vereinfachten Veranschaulichung kann die Situation mit $\mathbf{A}$ und $\mathbf{B}$ der Gr\"osse $2^n \times 2^n$ verwendet werden. +Die Matrizen $\mathbf{A}$ und $\mathbf{B}$ werden in jeweils vier Blockmatrizen der Gr\"osse $2^{n-1} \times 2^{n-1}$ aufgeteilt. +Das Matrizen Produkt \begin{equation} \mathbf{A}\mathbf{B}= \begin{bmatrix} @@ -63,20 +63,18 @@ Die Matrizen $\mathbf{A}$ und $\mathbf{B}$ werden in jeweils vier Blockmatrizen \begin{bmatrix} \mathbf{C}_{11} & \mathbf{C}_{12}\\ \mathbf{C}_{21} & \mathbf{C}_{22} -\end{bmatrix} +\end{bmatrix}, \end{equation} -aufgeteilt. -Die Berechnung -\begin{equation} -\mathbf{C}_{ij} = \sum_{k=1}^n \mathbf{A}_{ik} \mathbf{B}_{kj} +mit \begin{equation} +\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}, wobei hier f\"ur die Multiplikation die Matrizenmultiplikation verwendet wird. +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. Der Algorithmus \ref{multiplikation:alg:devide_mm} zeigt den \textit{Divide and Conquer} Ansatz, Der Grundstruktur dieser Methode besteht aus dem rekursiven Aufruf der Funktion mit den erzeugten Blockmatrizen. Der rekursive Aufruf wird bis zu der Gr\"osse der Matrizen von $N = 2 \times 2$ durchgef\"uhrt. -\begin{algorithm}\caption{Divide and Conquer Matrix Multiplication} +\begin{algorithm}\footnotesize\caption{Divide and Conquer Matrizenmultiplikation} \setlength{\lineskip}{7pt} \label{multiplikation:alg:devide_mm} \begin{algorithmic} @@ -105,37 +103,33 @@ Der rekursive Aufruf wird bis zu der Gr\"osse der Matrizen von $N = 2 \times 2$ \end{algorithmic} \end{algorithm} -Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} berechnet werden. -Ohne auf diesen vertieft einzugehen, bestimmt die Anzahl rekursiver Aufrufe der Funktion die Laufzeit. -In diesem Fall wird die Funktion pro Durchlauf acht mal rekursiv aufgerufen, dies f\"uhrt +Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} \cite{multiplikation:master_theorem} berechnet werden. Das \textit{Master Theorem} bestimmt die Zeitkomplexit\"at von rekursiven Algorithmen. +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 zu \begin{equation} \label{multiplikation:eq:laufzeitdac} - \mathcal{T}(n) = - \begin{cases} - 1 & \text{if } n \leq 2\\ - 8 \cdot \mathcal{T}(\frac{n}{2}) + n^2 & \text{if } n > 2 - \end{cases} = \mathcal{O}(n^{\log_2 8}) = \mathcal{O}(n^{3}) + \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. +also 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. In diesem Fall hat der \textit{Divide and Conquer} Ansatz zu keiner Verbesserung gef\"uhrt. -\subsection{Strassen's Algorithmus} +\subsection{Strassens Algorithmus} -Strassen's Algorithmus \cite{multiplikation:strassen_1969} beschreibt die Matrizenmultiplikation mit einer Vielzahl von Additionen, Subtraktionen und Multiplikationen. -Die Grundlegenden Terme +Strassens Algorithmus \cite{multiplikation:strassen_1969} beschreibt die Matrizenmultiplikation mit einer Vielzahl von Additionen, Subtraktionen und Multiplikationen von Blockmatrizen. +Die sieben grundlegenden Terme \begin{equation} \label{multiplikation:eq:strassen} \begin{split} -\text{\textbf{P}} &= (\mathbf{A}_{11} + \mathbf{A}_{22}) \cdot (\mathbf{B}_{11} + \mathbf{B}_{22}) \\ -\text{\textbf{Q}} &= (\mathbf{A}_{21} + \mathbf{A}_{22}) \cdot \mathbf{B}_{11} \\ -\text{\textbf{R}} &= \mathbf{A}_{11} \cdot (\mathbf{B}_{12}-\mathbf{B}_{22}) \\ -\text{\textbf{S}} &= \mathbf{A}_{22} \cdot (-\mathbf{B}_{11}+\mathbf{B}_{21}) \\ -\text{\textbf{T}} &= (\mathbf{A}_{11} + \mathbf{A}_{12}) \cdot \mathbf{B}_{22} \\ -\text{\textbf{U}} &= (-\mathbf{A}_{11} + \mathbf{A}_{21}) \cdot (\mathbf{B}_{11} + \mathbf{B}_{12}) \\ -\text{\textbf{V}} &= (\mathbf{A}_{12} - \mathbf{A}_{22}) \cdot (\mathbf{B}_{21} + \mathbf{B}_{22}) +\text{\textbf{P}} &= \left(\mathbf{A}_{11} + \mathbf{A}_{22}\right ) \cdot \left(\mathbf{B}_{11} + \mathbf{B}_{22}\right ) \\ +\text{\textbf{Q}} &= \left(\mathbf{A}_{21} + \mathbf{A}_{22}\right ) \cdot \mathbf{B}_{11} \\ +\text{\textbf{R}} &= \mathbf{A}_{11} \cdot \left(\mathbf{B}_{12}-\mathbf{B}_{22}\right ) \\ +\text{\textbf{S}} &= \mathbf{A}_{22} \cdot \left(-\mathbf{B}_{11}+\mathbf{B}_{21}\right ) \\ +\text{\textbf{T}} &= \left(\mathbf{A}_{11} + \mathbf{A}_{12}\right ) \cdot \mathbf{B}_{22} \\ +\text{\textbf{U}} &= \left(-\mathbf{A}_{11} + \mathbf{A}_{21}\right ) \cdot \left(\mathbf{B}_{11} + \mathbf{B}_{12}\right ) \\ +\text{\textbf{V}} &= \left(\mathbf{A}_{12} - \mathbf{A}_{22}\right ) \cdot \left(\mathbf{B}_{21} + \mathbf{B}_{22}\right ) \end{split} \end{equation} -aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Matrix $\mathbf{C}$ +aus $\mathbf{A}$ und $\mathbf{B}$ werden f\"ur die Berechnung der Bl\"ocke \begin{equation} \label{multiplikation:eq:strassen2} \begin{split} \mathbf{C}_{11} &= \text{\textbf{P}} + \text{\textbf{S}} - \text{\textbf{T}} + \text{\textbf{V}} \\ @@ -144,8 +138,8 @@ aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Matrix $\math \mathbf{C}_{22} &= \text{\textbf{P}} + \text{\textbf{R}} - \text{\textbf{Q}} + \text{\textbf{U}} \end{split} \end{equation} -gebraucht. -\begin{algorithm}\caption{Strassen Matrix Multiplication} +der Matrix $\mathbf{C}$ gebraucht. +\begin{algorithm}\footnotesize\caption{Strassen Matrizenmultiplikation} \label{multiplikation:alg:strassen} \setlength{\lineskip}{7pt} \begin{algorithmic} @@ -190,63 +184,86 @@ gebraucht. \EndFunction \end{algorithmic} \end{algorithm} -Strassens's Methode wird in der Abbildung \ref{multiplikation:fig:strassen} grafisch dargestellt. +Strassens Methode wird in der Abbildung \ref{multiplikation:fig:strassen} grafisch dargestellt. +Jedes Feld steht f\"ur eine Multiplikation zweier Matrizenelementen von $\mathbf{A}$ oder $\mathbf{B}$ . +Die gr\"unen Felder auf der linken Seite, zeigen die Addition, welche f\"ur den dazugeh\"origen Term ben\"otigt wird. +Die sieben Spalten beschreiben die Matrizen $\mathbf{P,Q,R, \ldots, V}$. +Rote Felder stehen f\"ur eine Subtraktion und die gr\"unen f\"ur eine Addition. \begin{figure} \center \includegraphics[width=\linewidth]{papers/multiplikation/images/strassen.pdf} - \caption{Strassen's Algorithmus} + \caption{Der Algorithmus von Strassen verwendet Multiplikationen zur Berechnung der sieben Block-Matrizen $\mathbf{P}$ bis $\mathbf{V}$ aus $\mathbf{A}$ und $\mathbf{B}$, aus denen sich die Blöcke es Produktes $\mathbf{C}=\mathbf{AB}$ ausschliesslich durch Addition und Subtraktion bilden lassen. Die einzelnen Felder in den Quadraten stellen alle möglichen Produkte von Matrizen $\mathbf{A}_{ik}$ und $\mathbf{B}_{jl}$ dar. In den grossen Quadraten am linken Rand sind diejenigen Produkte grün markiert, welche zusammen die entsprechenden Blöcke $\mathbf{C}_{il}$ von $\mathbf{C}$ ergeben. In den Spalten $\mathbf{P}$ bis $\mathbf{V}$ sind die Produkte farblich hervorgehoben, die in der Definition der entsprechenden Matrix vorkommen. Grün und rot symbolisieren die Vorzeichen, mit denen die Produkte kombiniert werden müssen} \label{multiplikation:fig:strassen} \end{figure} Die Funktion wird sieben mal rekursiv aufgerufen. -Dies f\"uhrt zu einer Laufzeit von +Dies f\"uhrt nach dem \textit{Master Theorem} zu einer Laufzeit von \begin{equation} \label{multiplikation:eq:laufzeitstrassen} \mathcal{T}(n) = -\begin{cases} -1 & \text{if } n \leq 2\\ -7 \cdot \mathcal{T}(\frac{n}{2}) + n^2 & \text{if } n > 2 -\end{cases} = \mathcal{O}(n^{\log_2 7}) = \mathcal{O}(n^{2.8074}) +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 Standard Methode. +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. -\subsection{Winograd's Algorithmus} +\subsection{Winograds Algorithmus} -Ein weiterer Ansatz lieferte Shmuel Winograd im Jahre 1968 \cite{multiplikation:winograd_1968}. -Er zeigte einen neuen Algorithmus f\"ur das -\begin{equation} - \langle x,y \rangle = \sum_{i=1}^{n}x_i y_i +Einen weiteren Ansatz lieferte Shmuel Winograd im Jahre 1968 \cite{multiplikation:winograd_1968}. +Er beschrieb einen neuen Algorithmus f\"ur das Skalarprodukt +\begin{equation} \label{multiplikation:eq:skalar} + \langle x,y \rangle = \sum_{i=1}^{n}x_i y_i. \end{equation} -Skalarprodukt. F\"ur jeden Vektor berechne \begin{equation} \xi = \sum_{j=1}^{ \lfloor n/2 \rfloor} x_{2j-1} \cdot x_{2j} \end{equation} und \begin{equation} - \eta = \sum_{j=1}^{ \lfloor n/2 \rfloor} y_{2j-1} \cdot y_{2j}. + \eta = \sum_{j=1}^{ \lfloor n/2 \rfloor} y_{2j-1} \cdot y_{2j}, \end{equation} +die jeweils nur von $x$ und $y$ abhängen. +Dazu werden $2 \cdot \lfloor n/2 \rfloor \leq n$ Multiplikationen benötigt. Das Skalarprodukt ist nun geben mit \begin{equation} \langle x,y \rangle = \begin{cases} - \displaystyle \quad \sum_{j=1}^{ \lfloor n/2 \rfloor} (x_{2j-1} + y_{2j})(x_{2j}+y_{2j-1})-\xi - \eta & \text{if $n$ is even}\\ - \displaystyle \quad \sum_{j=1}^{ \lfloor n/2 \rfloor} (x_{2j-1} + y_{2j})(x_{2j}+y_{2j-1})-\xi - \eta + x_n y_n & \text{if $n$ is odd}. + \displaystyle \quad \sum_{j=1}^{ \lfloor n/2 \rfloor} (x_{2j-1} + y_{2j})(x_{2j}+y_{2j-1})-\xi - \eta & \text{wenn $n$ gerade}\\ + \displaystyle \quad \sum_{j=1}^{ \lfloor n/2 \rfloor} (x_{2j-1} + y_{2j})(x_{2j}+y_{2j-1})-\xi - \eta + x_n y_n & \text{wenn $n$ ungerade}. \end{cases} \end{equation} - -Angenommen man hat $N$ Vektoren mit welchen man $T$ Skalarprodukte berechnen m\"ochte. +Das Skalarprodukt kann also mit $ \lfloor \frac{n+1}{2} \rfloor$ weiteren Multiplikationen berechnet werden. +Angenommen man hat $N$ Vektoren, mit welchen man $T$ Skalarprodukte berechnen m\"ochte. Daf\"ur werden $N\lfloor n/2 \rfloor + T\lfloor (n+1)/2 \rfloor $ Multiplikationen ben\"otigt. +Die Summen f\"ur $\xi$ und $\eta$ m\"ussen nur einmal berechnet werden. +Für die ursprüngliche Gleichung \eqref{multiplikation:eq:skalar} für das Skalarprodukt benötigt man $Tn$ Multiplikationen. +Damit können wir die Laufzeit der Methode von Winograd mit der Laufzeit der Standardmethode vergleichen. Sie ist kleiner als die Laufzeit für die Standardmethode, wenn gilt +\begin{equation}\label{multiplikation:eq:eff} +\begin{array}{crcl} + & N\lfloor n/2\rfloor + T\lfloor(n+1)/2\rfloor \approx Nn/2 + Tn/2 & \le & Tn \\ +\Leftrightarrow & Nn/2 & \le & Tn/2 \\ +\Leftrightarrow & N & \le & T. +\end{array} +\end{equation} Eine Matrizenmultiplikation mit $\mathbf{A}$ einer $m \times n$ und $\mathbf{B}$ einer $n \times p$ Matrix, entspricht $N=m+p$ Vektoren mit welchen man $T=mp$ Skalarprodukte berechnet. Dies f\"uhrt zu \begin{equation} (m+p) \left \lfloor \frac{n}{2} \right \rfloor + mp \left \lfloor \frac{n+1}{2} \right \rfloor = \frac{mn}{2} + \frac{pn}{2} + \frac{mpn}{2} + \frac{mp}{2} \end{equation} Multiplikationen. -Wenn $m,p,n$ gross werden, dominiert der Term $\frac{mpn}{2}$ und es werden $\frac{mpn}{2}$ Multiplikationen ben\"otigt. -Was im Vergleich zu den $mpn$ Multiplikation der Standard Methode nur die H\"alfte ist. -Die Implementation kann im Algorithmus \ref{multiplikation:alg:winograd} entnommen werden. - -\begin{algorithm}\caption{Winograd Matrix Multiplication} +Wenn $m,p,n$ gross werden, dominiert der Term $\frac{mpn}{2}$ und es werden $\frac{mpn}{2}$ Multiplikationen ben\"otigt, was im Vergleich zu den $mpn$ Multiplikation der Standardmethode nur die H\"alfte ist. +Mit dem gleichen Ansatz wie in der Gleichung \eqref{multiplikation:eq:eff} aber mit quadratischen Matrizen, muss +\begin{align} + \begin{split} +N=2n, &\quad T = n^2 \\ + 2n &\leq n^2 \\ + 2 &\leq n +\end{split} +\end{align} +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}(n^3 )$. +\begin{algorithm}\footnotesize\caption{Winograds Matrizenmultiplikation} \setlength{\lineskip}{7pt} \label{multiplikation:alg:winograd} \begin{algorithmic} @@ -297,13 +314,188 @@ Die Implementation kann im Algorithmus \ref{multiplikation:alg:winograd} entnomm \end{algorithmic} \end{algorithm} -\subsection{Weitere Algorithmen} -\textcolor{red}{TODO: BLAS} +\subsection{Basic Linear Algebra Subprograms (BLAS)} + +Die gebräuchliche Methode f\"ur die Anwendung einer optimierten Matrizenmultiplikation ist die Verwendung einer Subroutine aus den \textit{Basic Linear Algebra Subprograms (BLAS)} \cite{multiplikation:BLAS}. +Die meisten numerischen Bibliotheken von high-level Skriptsprachen wie \texttt{Matlab}, \texttt{NumPy (Python)}, \texttt{GNU Octave} oder \texttt{Mathematica} ben\"utzen eine Form von \textit{BLAS}. + +\textit{BLAS} sind dabei in drei unterschiedliche Levels aufgeteilt. + +\begin{itemize} + \item Level 1 + \begin{itemize} + \item Operationen der Art: $\mathbf{y} \leftarrow \alpha \mathbf{x}+\mathbf{y}$ + \item Dieses Level hat $\mathcal{O}(n)$ Charakteristik + \end{itemize} + \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}(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}(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. + -\section{Implementation} +%\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] +%cblas_dgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans, +% m, n, k, 1, A, m , B, k, 0, C, m); +%\end{lstlisting} +%definiert. + + + +\section{Implementation}\label{multiplikation:section:Implementation} \rhead{Implementation} -\textcolor{red}{TODO: messresultate} + +Folgende Algorithmen wurden jeweils in \texttt{C} und \texttt{Python} implementiert. +\begin{itemize} + \item Standard Matrizenmultiplikation + \item \textit{Divide and Conquer} Matrizenmultiplikation + \item Strassens Matrizenmultiplikation + \item Winograds Matrizenmultiplikation + \item \texttt{BLAS} Matrizenmultiplikation in \texttt{C} + \item \texttt{Numpy} Matrizenmultiplikation in \texttt{Python} +\end{itemize} + +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. + +Die gezeigten Algorithmen haben alle eine Laufzeit der Form $\mathcal{O}(n^k) $. +Bei einer doppelt logarithmischen Darstellung unterscheiden sich diese in Geraden mit unterschiedlichen Steigungen. +Bei den grafisch gezeigten Messresultate, können diese Steigungen gut erkannt werden, wobei die tiefere Laufzeit des Strassen Algorithmus eindrücklich zu sehen ist. +Der benötigte Overhead der Algorithmen zeigt sich in unterschiedlichen $y$-Achsenschnittpunkte. + +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 Matrizengrösse von $n = 2048$ wohl eine Zeile der Matrix nicht an einer Cache Speicherstelle Platz. +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. + + +\begin{table} + \begin{center} + \begin{tabular}{r l l l l l} + \hline + \hline + \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} & \phantom{000}0.000089 & \phantom{000}0.000594 & \phantom{000}0.0005 & \phantom{0000}0.00008 & \phantom{00}0.000021 \\ + \textbf{64} & \phantom{000}0.00069 & \phantom{000}0.0044 & \phantom{000}0.0036 & \phantom{0000}0.00064 & \phantom{00}0.00018 \\ + \textbf{128} & \phantom{000}0.0057 & \phantom{000}0.035 & \phantom{000}0.025 & \phantom{0000}0.0052 & \phantom{00}0.0012 \\ + \textbf{256} & \phantom{000}0.052 & \phantom{000}0.29 & \phantom{000}0.178 & \phantom{0000}0.053 & \phantom{00}0.0096 \\ + \textbf{512} & \phantom{000}0.51 & \phantom{000}2.22 & \phantom{000}1.25 & \phantom{0000}0.55 & \phantom{00}0.077 \\ + \textbf{1024} & \phantom{000}4.50 & \phantom{00}17.65 & \phantom{000}8.83 & \phantom{0000}4.67 & \phantom{00}0.764 \\ + \textbf{2048} & \phantom{0}129.28 & \phantom{0}141.61 & \phantom{00}61.901 & \phantom{00}136.67 & \phantom{00}7.63 \\ + \textbf{4096} & 1111.31 & 1147.10 & \phantom{0}414.64 & \phantom{0}1179.26 & \phantom{0}55.84 \\ + \textbf{8192} & 9376.17 & 9606.40 & 3014.23 & 10071.51 & 478.42 \\ + \multicolumn{6}{c}{} \\ + \hline + \hline + \end{tabular} + \end{center} + \caption{Laufzeiten der verschieden Algorithmen in der Programmiersprache \texttt{C}} + \label{multiplikation:tab:messung_C} + \end{table} + + + + \begin{table} + \begin{center} + \begin{tabular}{r l l l l l} + \hline + \hline + \textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{NumPy(\textit{s})} \\ + \hline + \multicolumn{6}{c}{} \\ + \textbf{32} & \phantom{000}0.0240 & \phantom{0000}0.0271& \phantom{0000}0.04852 & \phantom{0000}0.01871 & 0.0000426 \\ + \textbf{64} &\phantom{000} 0.186 & \phantom{0000}0.265 & \phantom{0000}0.2204 & \phantom{0000}0.1530& 0.000118 \\ + \textbf{128} &\phantom{000} 1.563 & \phantom{0000}1.777 & \phantom{0000}1.447 & \phantom{0000}1.1947 & 0.000244 \\ + \textbf{256} &\phantom{00} 11.006 & \phantom{000}13.27 & \phantom{0000}9.938 & \phantom{0000}8.298& 0.000695 \\ + \textbf{512} &\phantom{00} 85.476 & \phantom{00}105.397 & \phantom{000}63.961 & \phantom{000}68.360 & 0.00221\\ + \textbf{1024} &\phantom{0} 750.757 & \phantom{00}847.321 & \phantom{00}461.494 & \phantom{00}537.374 & 0.0188 \\ + \textbf{2048} & 6154.18 & \phantom{0}7375.93 & \phantom{0}3860.57 & \phantom{0}4884.61 & 0.215 \\ + \textbf{4096} & 46813.30 & 58466.00 & 22904.30 & 43597.10 & 1.49 \\ + \multicolumn{6}{c}{} \\ + \hline + \hline + \end{tabular} + \end{center} + \caption{Laufzeiten der verschieden Algorithmen in der Skriptsprache \texttt{Python}} + \label{multiplikation:tab:messung_Python} + \end{table} + + \begin{table} + \begin{center} + \begin{tabular}{c c c c} + \hline + \hline + \textbf{CPU} & \textbf{OS} & \textbf{GPU } & \textbf{Memory } \\ + \hline + \multicolumn{4}{c}{} \\ + Intel® Core™ i7-4770K CPU & Ubuntu 20.04.2 LTS & Radeon RX 570 & 32 GB 1600 MHz \\ + @ 3.50GHz × 8 & 64-bit & & \\ + \multicolumn{4}{c}{} \\ + \hline + \hline + \end{tabular} + \end{center} + \caption{Messsystem} + \label{multiplikation:tab:pc_config} + \end{table} + +\begin{figure} + \center + \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_c} + \caption{Doppelt logarithmisch dargestellte Laufzeiten, der verschieden Algorithmen, in der Programmiersprache \texttt{C}} + \label{multiplikation:fig:c_meas_4096} +\end{figure} + + +\begin{figure} + \center + \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_python} + \caption{Doppelt logarithmisch dargestellte Laufzeiten, der verschieden Algorithmen, in der Skriptsprache \texttt{Python}} + \label{multiplikation:fig:python} +\end{figure} \section{Fazit} \rhead{Fazit} + +Wie man im Abschnitt \ref{multiplikation:section:Implementation} sehen kann, sind die gezeigten Algorithmen trotz der theoretisch geringeren Zeitkomplexitäten den Implementationen der numerischen Bibliotheken klar unterlegen. +Ein optimierter Speicherzugriff hat einen weitaus grösseren Einfluss auf die Laufzeit als die Zeitkomplexität des Algorithmus. + +Doch haben Entdeckungen wie jene von Strassen und Winograd ihre Daseinsberechtigung. +Nicht auf jeden Computersystemen können die \textit{BLAS} angewandt werden. +Denke man an sehr kleine Mikrocontroller ohne Floatingpoint Recheneinheiten oder auch an \textit{Field Programmable Gate Arrays (FPGA's)}. +Der Overhead der gezeigten Algorithmen ist in allen Fällen grösser als bei der Standardmethode (z.B. sieben rekursive Aufrufe gegenüber drei \texttt{for}-Schleifen). +Um diesem entgegenzuwirken muss der Laufzeitunterschied zwischen Addition und Multiplikation gross genug sein. +Wenn dies gegeben ist und dazu noch grosse Matritzen multipliziert werden, kann die Verwendung der Algorithmen von Strassen oder Winograd zu einer Senkung der Laufzeit führen. diff --git a/buch/papers/multiplikation/main.tex b/buch/papers/multiplikation/main.tex index 8d0a8df..ca93e92 100755 --- a/buch/papers/multiplikation/main.tex +++ b/buch/papers/multiplikation/main.tex @@ -4,8 +4,30 @@ % % (c) 2021 Hochschule Rapperswil % -\chapter{Schnelle Matrizen Multiplikation\label{chapter:multiplikation}} -\lhead{FMM} +\definecolor{mygreen}{RGB}{28,172,0} % color values Red, Green, Blue +\definecolor{mylilas}{RGB}{170,55,241} +\definecolor{backcolour}{rgb}{0.95,0.95,0.92} +\lstdefinestyle{multiplikationC}{ + numbers=left, + belowcaptionskip=1\baselineskip, + breaklines=true, + frame=l, + framerule=0pt, + framesep=-1pt, + xleftmargin=1em, + language=C, + showstringspaces=false, + basicstyle=\ttfamily, + keywordstyle=\bfseries\color{green!40!black}, + commentstyle=\itshape\color{purple!40!black}, + identifierstyle=\color{blue}, + stringstyle=\color{red}, + numberstyle=\ttfamily\tiny, + backgroundcolor=\color{backcolour} +} + +\chapter{Schnelle Matrizenmultiplikation\label{chapter:multiplikation}} +\lhead{MM} \begin{refsection} \chapterauthor{Michael Schmid} diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index b20a791..604ea36 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -3,102 +3,135 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Problemstellung} +\section{Laufzeiten von Algorithmen} \rhead{Problemstellung} -Dank der breiten Anwendung der Matrizenmultiplikation ist eine effiziente L\"osung dieser Operation von grosser Bedeutung. -Das Ziel dieses Papers ist verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen. -Wobei gezielt auf Algorithmen, welche das Problem schneller als der Standard Algorithmus L\"osen eingegangen wird. - -\subsection{Big $\mathcal{O}$ Notation} -Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus \cite{multiplikation:bigo}. -$f(x) \in \mathcal{O}(g(x))$ besagt das die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$. -Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet: +Wegen der breiten Anwendung der Matrizenmultiplikation ist eine effiziente Ausführung dieser Operation von grosser Bedeutung. +Das Ziel dieses Papers ist, verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen. +Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der Standardalgorithmus l\"osen. + +\label{muliplikation:sec:bigo} +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$. +Dies ist gegeben, wenn es für $f \in \mathcal{O}(n^k)$ eine Konstante $C$ gibt, mit $f(n) \leq Cn^k$. +% Es gibt eine Konstante $K$ derart, dass $f(x) \le K g(x)$ für $x\to\infty$. +Vereinfacht werden f\"ur Algorithmen die folgende Sprechweise 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}(n^2) \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}(e^n) \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. +Konstanten werden nicht beachtet, eine Laufzeit von $4n^2$ führt, falls $n \rightarrow \infty$ zu $\mathcal{O}(n^2)$. +In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden. +Bei einer doppelt 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 abgebildet. + -\begin{figure} - \center - \includegraphics[]{papers/multiplikation/images/bigo} - \caption{Verschiedene Laufzeiten} - \label{multiplikation:fig:bigo} -\end{figure} \subsubsection{Beispiel Algorithmen} + +Es folgen einige Beispiele von Algorithmen, welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen. + + +\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} +Algorithmus \ref{multiplikation:alg:b1} ist ein Beispiel mit beschränkter Laufzeit $\mathcal{O}(1)$ +Da $a$ und $b$ Skalare sind, hat keine Gr\"osse $n$ einen Einfluss auf die Laufzeit. + +Wie erwähnt, werden konstanten nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$. -Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden. - -\begin{algorithm}\caption{} - \label{multiplikation:alg:b1} - \setlength{\lineskip}{7pt} - \begin{algorithmic} - \Function{B1}{$a, b$} - \State \textbf{return} $a+b$ - \EndFunction - \end{algorithmic} -\end{algorithm} - -Wobei Konstanten nicht beachtet werden, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$. - -\begin{algorithm}\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} \paragraph{Linearer Algorithmus} -Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares $\mathcal{O}(n)$ Verhalten. - -\begin{algorithm}\caption{} - \setlength{\lineskip}{7pt} - \begin{algorithmic} - \label{multiplikation:alg:l1} - \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} +Der Algorithmus \ref{multiplikation:alg:linear} hat ein lineares Verhalten. +Die \texttt{for}-Schleife wird $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}(n)$. \paragraph{Quadratischer Algorithmus} -Folgender Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches $\mathcal{O}(n^2)$ Verhalten. - -\begin{algorithm}[H]\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} +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} (n^2 )$. +\begin{figure} + \center + \includegraphics[]{papers/multiplikation/images/bigo} + \caption{Laufzeiten von verschiedensten Zeitkomplexitäten. 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.} + \label{multiplikation:fig:bigo} +\end{figure} diff --git a/buch/papers/multiplikation/references.bib b/buch/papers/multiplikation/references.bib index 9d76e8e..8815386 100755 --- a/buch/papers/multiplikation/references.bib +++ b/buch/papers/multiplikation/references.bib @@ -63,3 +63,40 @@ month = {7}, day = {27} } + +@online{multiplikation:master_theorem, + title = {Master theorem (analysis of algorithms)}, + url = {https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)}, + date = {2021-07-28}, + year = {2021}, + month = {7}, + day = {28} +} + + +@online{multiplikation:DAC, + title = {Divide-and-conquer algorithm}, + url = {https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm}, + date = {2021-07-28}, + year = {2021}, + month = {7}, + day = {28} +} + +@online{multiplikation:BLAS, + title = {BLAS (Basic Linear Algebra Subprograms)}, + url = {http://www.netlib.org/blas/}, + date = {2021-08-01}, + year = {2021}, + month = {8}, + day = {01} +} + +@online{multiplikation:DGEMM, + title = {DGEMM}, + url = {http://www.netlib.org/lapack/explore-html/d1/d54/group__double__blas__level3_gaeda3cbd99c8fb834a60a6412878226e1.html#gaeda3cbd99c8fb834a60a6412878226e1}, + date = {2021-08-01}, + year = {2021}, + month = {8}, + day = {01} +} |