From ce9f4591847c6bd2dc6ebaa30fc5d72714e0280c Mon Sep 17 00:00:00 2001 From: Nunigan Date: Tue, 10 Aug 2021 06:37:20 +0200 Subject: new measurements --- buch/papers/multiplikation/code/MM | Bin 26848 -> 0 bytes buch/papers/multiplikation/code/MM.c | 19 +- buch/papers/multiplikation/code/MM.py | 77 ++++---- buch/papers/multiplikation/code/c_matrix.h | 204 ++++++++++++++------- buch/papers/multiplikation/code/c_meas_4096.pdf | Bin 17448 -> 22360 bytes buch/papers/multiplikation/code/ci.txt | 0 buch/papers/multiplikation/code/helper_class.py | 3 +- buch/papers/multiplikation/code/meas/MM.txt | 118 +++++++++++- buch/papers/multiplikation/code/meas/MM_dc.txt | 118 +++++++++++- buch/papers/multiplikation/code/meas/blas.txt | 114 +++++++++++- buch/papers/multiplikation/code/meas/ci/MM.txt | 11 ++ buch/papers/multiplikation/code/meas/ci/Wino.txt | 11 ++ buch/papers/multiplikation/code/meas/ci/blas.txt | 11 ++ buch/papers/multiplikation/code/meas/ci/dc.txt | 11 ++ .../multiplikation/code/meas/ci/strassen.txt | 11 ++ .../multiplikation/code/meas/old/8196/MM.txt | 1 + .../multiplikation/code/meas/old/8196/MM_dc.txt | 1 + .../multiplikation/code/meas/old/8196/blas.txt | 1 + .../multiplikation/code/meas/old/8196/strassen.txt | 1 + .../multiplikation/code/meas/old/8196/winograd.txt | 1 + buch/papers/multiplikation/code/meas/old/MM.txt | 12 ++ buch/papers/multiplikation/code/meas/old/MM_dc.txt | 12 ++ buch/papers/multiplikation/code/meas/old/blas.txt | 12 ++ .../multiplikation/code/meas/old/strassen.txt | 12 ++ .../multiplikation/code/meas/old/winograd.txt | 12 ++ buch/papers/multiplikation/code/meas/strassen.txt | 122 ++++++++++-- buch/papers/multiplikation/code/meas/winograd.txt | 116 +++++++++++- buch/papers/multiplikation/code/meas_4096.pdf | Bin 12952 -> 17369 bytes buch/papers/multiplikation/code/meas_4096.txt | 6 + buch/papers/multiplikation/images/algo_tab.pdf | Bin 0 -> 34251 bytes buch/papers/multiplikation/images/algo_tab.tex | 122 ++++++++++++ buch/papers/multiplikation/images/meas_c.pdf | Bin 23161 -> 23552 bytes buch/papers/multiplikation/images/meas_c.tex | 9 +- buch/papers/multiplikation/loesungsmethoden.tex | 48 ++--- buch/papers/multiplikation/problemstellung.tex | 145 ++++++++------- 35 files changed, 1096 insertions(+), 245 deletions(-) delete mode 100755 buch/papers/multiplikation/code/MM create mode 100644 buch/papers/multiplikation/code/ci.txt create mode 100644 buch/papers/multiplikation/code/meas/ci/MM.txt create mode 100644 buch/papers/multiplikation/code/meas/ci/Wino.txt create mode 100644 buch/papers/multiplikation/code/meas/ci/blas.txt create mode 100644 buch/papers/multiplikation/code/meas/ci/dc.txt create mode 100644 buch/papers/multiplikation/code/meas/ci/strassen.txt create mode 100644 buch/papers/multiplikation/code/meas/old/8196/MM.txt create mode 100644 buch/papers/multiplikation/code/meas/old/8196/MM_dc.txt create mode 100644 buch/papers/multiplikation/code/meas/old/8196/blas.txt create mode 100644 buch/papers/multiplikation/code/meas/old/8196/strassen.txt create mode 100644 buch/papers/multiplikation/code/meas/old/8196/winograd.txt create mode 100644 buch/papers/multiplikation/code/meas/old/MM.txt create mode 100644 buch/papers/multiplikation/code/meas/old/MM_dc.txt create mode 100644 buch/papers/multiplikation/code/meas/old/blas.txt create mode 100644 buch/papers/multiplikation/code/meas/old/strassen.txt create mode 100644 buch/papers/multiplikation/code/meas/old/winograd.txt create mode 100644 buch/papers/multiplikation/images/algo_tab.pdf create mode 100644 buch/papers/multiplikation/images/algo_tab.tex (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/code/MM b/buch/papers/multiplikation/code/MM deleted file mode 100755 index d52dda4..0000000 Binary files a/buch/papers/multiplikation/code/MM and /dev/null differ diff --git a/buch/papers/multiplikation/code/MM.c b/buch/papers/multiplikation/code/MM.c index a897d4f..2588262 100755 --- a/buch/papers/multiplikation/code/MM.c +++ b/buch/papers/multiplikation/code/MM.c @@ -28,11 +28,12 @@ int main() { // omp_set_num_threads(4); // run_algo(openMP_MM, "openMP_MM",0); run_algo(MM_dc, "MM_dc",0); + run_algo(strassen, "strassen",0); run_algo(MM, "MM", 0); - run_algo(winograd, "winograd", 0); - run_algo_cblas(0); + run_algo(winograd, "winograd", 0); + run_algo_cblas(0); return 0; } @@ -414,12 +415,12 @@ void run_algo(void (*algo)(), char alog_name[], int print) for(int i=0; i const int A0[][2] = { - {75,47}, - {-41,-24} + {60,-84}, + {-66,-1} }; const int B0[][2] = { - {-53,-95}, - {-93,30} + {-45,87}, + {-38,-73} }; const double dB0[][2] = { - {-53,-95}, - {-93,30} + {-45,87}, + {-38,-73} }; const double dA0[][2] = { - {75,47}, - {-41,-24} + {60,-84}, + {-66,-1} }; const int A1[][4] = { - {47,11,-66,8}, - {36,98,39,82}, - {-32,12,40,-79}, - {61,-20,-85,-98} + {-72,-19,-91,62}, + {-36,-74,-44,-47}, + {-39,-31,50,-93}, + {-81,2,-17,-86} }; const int B1[][4] = { - {37,75,-53,9}, - {37,-33,-67,38}, - {70,39,-93,43}, - {43,41,23,-4} + {-66,39,-23,52}, + {-88,-13,13,-13}, + {-45,-70,28,-20}, + {96,5,88,96} }; const double dB1[][4] = { - {37,75,-53,9}, - {37,-33,-67,38}, - {70,39,-93,43}, - {43,41,23,-4} + {-66,39,-23,52}, + {-88,-13,13,-13}, + {-45,-70,28,-20}, + {96,5,88,96} }; const double dA1[][4] = { - {47,11,-66,8}, - {36,98,39,82}, - {-32,12,40,-79}, - {61,-20,-85,-98} + {-72,-19,-91,62}, + {-36,-74,-44,-47}, + {-39,-31,50,-93}, + {-81,2,-17,-86} }; const int A2[][8] = { - {-54,-87,87,69,52,-21,-86,55}, - {19,-75,-61,-50,-55,-23,66,-92}, - {-73,-67,-36,19,84,-11,24,46}, - {-98,62,-76,57,-100,6,-23,-51}, - {62,46,1,-64,42,-9,85,-12}, - {35,-59,-17,-47,78,86,-50,74}, - {-15,45,33,-59,-9,-81,49,96}, - {-57,22,-43,7,-30,-45,-5,13} + {-36,-2,-58,-32,34,-89,49,-55}, + {-68,-73,52,-3,-51,-37,-31,70}, + {73,-90,-21,-79,-15,96,-99,12}, + {68,-25,38,-73,-60,35,-99,72}, + {-43,-87,48,-84,-100,37,80,53}, + {-27,88,-5,-82,-57,-27,20,10}, + {-91,-47,54,-90,-99,-76,50,-18}, + {69,-36,76,5,-67,-38,-95,91} }; const int B2[][8] = { - {-71,-82,-80,-78,83,-97,48,-24}, - {15,75,15,-60,-63,-53,1,-50}, - {-84,63,67,-2,78,93,-13,95}, - {61,-26,-88,56,56,27,26,1}, - {2,54,21,36,9,-41,53,53}, - {85,-11,42,-51,-6,3,27,97}, - {10,-2,90,-76,-75,0,8,-37}, - {10,-64,47,-69,66,-50,89,-66} + {-84,22,-13,-66,-42,51,66,0}, + {37,-65,66,-85,-10,-23,77,5}, + {1,41,-79,0,63,-37,-10,29}, + {72,66,-99,92,-28,65,25,-40}, + {69,-49,65,-18,64,-97,-47,30}, + {36,86,66,-12,-17,89,1,-37}, + {-100,11,27,23,-75,-23,96,-9}, + {68,90,-87,-99,-70,-28,98,-76} }; const double dB2[][8] = { - {-71,-82,-80,-78,83,-97,48,-24}, - {15,75,15,-60,-63,-53,1,-50}, - {-84,63,67,-2,78,93,-13,95}, - {61,-26,-88,56,56,27,26,1}, - {2,54,21,36,9,-41,53,53}, - {85,-11,42,-51,-6,3,27,97}, - {10,-2,90,-76,-75,0,8,-37}, - {10,-64,47,-69,66,-50,89,-66} + {-84,22,-13,-66,-42,51,66,0}, + {37,-65,66,-85,-10,-23,77,5}, + {1,41,-79,0,63,-37,-10,29}, + {72,66,-99,92,-28,65,25,-40}, + {69,-49,65,-18,64,-97,-47,30}, + {36,86,66,-12,-17,89,1,-37}, + {-100,11,27,23,-75,-23,96,-9}, + {68,90,-87,-99,-70,-28,98,-76} }; const double dA2[][8] = { - {-54,-87,87,69,52,-21,-86,55}, - {19,-75,-61,-50,-55,-23,66,-92}, - {-73,-67,-36,19,84,-11,24,46}, - {-98,62,-76,57,-100,6,-23,-51}, - {62,46,1,-64,42,-9,85,-12}, - {35,-59,-17,-47,78,86,-50,74}, - {-15,45,33,-59,-9,-81,49,96}, - {-57,22,-43,7,-30,-45,-5,13} - }; -const int *Ap[3] = {(int*) A0,(int*) A1,(int*) A2}; -const int *Bp[3] = {(int*) B0,(int*) B1,(int*) B2}; -const double *dAp[3] = {(double*) dA0,(double*) dA1,(double*) dA2}; -const double *dBp[3] = {(double*) dB0,(double*) dB1,(double*) dB2}; -int n[3] = {2,4,8}; -int n_arrays = 3; + {-36,-2,-58,-32,34,-89,49,-55}, + {-68,-73,52,-3,-51,-37,-31,70}, + {73,-90,-21,-79,-15,96,-99,12}, + {68,-25,38,-73,-60,35,-99,72}, + {-43,-87,48,-84,-100,37,80,53}, + {-27,88,-5,-82,-57,-27,20,10}, + {-91,-47,54,-90,-99,-76,50,-18}, + {69,-36,76,5,-67,-38,-95,91} + }; +const int A3[][16] = + { + {-24,65,21,19,94,70,-90,-81,53,-41,-23,-1,58,-80,-54,59}, + {-42,76,-19,98,29,-56,92,14,45,11,82,83,48,-13,81,66}, + {43,-57,-67,95,5,72,11,0,-47,55,-24,36,84,54,-31,-54}, + {-39,-40,19,97,-82,-56,27,95,81,-21,-50,-74,-35,-87,-28,-26}, + {-74,-98,79,92,-24,-48,99,94,55,-83,70,98,-24,18,-67,14}, + {20,76,11,-23,-56,21,0,42,64,86,-74,44,93,-76,-30,97}, + {13,20,-73,-11,-30,80,53,-8,60,21,17,-42,82,-72,-6,-80}, + {36,-93,-64,-21,20,-85,15,24,99,81,-52,64,71,-56,52,63}, + {32,9,-2,-85,17,62,-98,-35,75,-58,-44,-20,-47,89,-95,52}, + {93,-43,86,68,-6,-25,90,57,60,-10,65,-97,43,46,-60,-41}, + {43,-33,0,50,-100,26,-60,95,39,-70,-61,-81,9,-23,-99,-4}, + {20,61,15,43,-96,93,-55,38,-29,-1,-10,26,-87,18,64,6}, + {-98,-84,51,16,-14,86,52,59,44,-39,-2,10,82,-66,54,19}, + {89,-49,-37,-6,-53,40,-11,46,-51,-56,86,34,11,13,-20,-49}, + {-90,14,28,-45,-25,-56,-51,-61,28,-8,51,91,95,-10,-85,58}, + {8,-44,88,-71,-27,11,89,37,86,-78,-44,-56,-87,0,-42,-61} + }; +const int B3[][16] = + { + {62,-30,62,92,29,-93,-95,44,-33,-88,-29,9,-88,-42,-90,-70}, + {60,37,-44,-93,-87,6,-53,2,-29,53,-49,59,6,83,-15,50}, + {-19,85,-49,-14,84,-4,12,88,-83,-81,-24,-16,-12,-42,-63,-71}, + {-42,-78,-58,-61,-29,67,-28,-46,64,7,6,-13,88,-42,95,-24}, + {-90,-56,8,-30,-89,70,37,-29,24,-8,-10,-2,-25,-63,-95,-91}, + {10,-81,42,-28,-13,-68,-72,-20,-22,5,-79,-50,-88,62,57,69}, + {-67,24,-71,-43,11,48,33,-93,-82,-65,-4,5,-15,25,-54,-45}, + {-49,19,-29,90,-97,-87,78,-39,-75,-85,-79,-35,54,3,-73,7}, + {-7,39,70,-42,32,-100,56,4,-24,-57,38,-49,-50,-44,79,-42}, + {37,-65,-55,22,-97,-42,-76,95,97,-27,38,11,0,-81,-23,35}, + {26,-70,10,-29,47,-70,-52,29,-13,-18,5,34,18,32,87,91}, + {-84,41,-19,96,-51,-19,81,75,81,92,2,-40,-42,-69,-10,-61}, + {-30,98,71,-51,91,-59,58,86,86,-22,-84,7,66,-55,-52,23}, + {-71,-44,-9,90,26,18,26,-10,-85,64,-47,3,72,81,74,-8}, + {52,-59,-91,22,8,-63,84,9,-11,-54,-78,-71,-98,42,96,57}, + {18,-39,34,-50,-62,-96,-2,-78,52,94,-33,2,-19,-9,-86,-75} + }; +const double dB3[][16] = + { + {62,-30,62,92,29,-93,-95,44,-33,-88,-29,9,-88,-42,-90,-70}, + {60,37,-44,-93,-87,6,-53,2,-29,53,-49,59,6,83,-15,50}, + {-19,85,-49,-14,84,-4,12,88,-83,-81,-24,-16,-12,-42,-63,-71}, + {-42,-78,-58,-61,-29,67,-28,-46,64,7,6,-13,88,-42,95,-24}, + {-90,-56,8,-30,-89,70,37,-29,24,-8,-10,-2,-25,-63,-95,-91}, + {10,-81,42,-28,-13,-68,-72,-20,-22,5,-79,-50,-88,62,57,69}, + {-67,24,-71,-43,11,48,33,-93,-82,-65,-4,5,-15,25,-54,-45}, + {-49,19,-29,90,-97,-87,78,-39,-75,-85,-79,-35,54,3,-73,7}, + {-7,39,70,-42,32,-100,56,4,-24,-57,38,-49,-50,-44,79,-42}, + {37,-65,-55,22,-97,-42,-76,95,97,-27,38,11,0,-81,-23,35}, + {26,-70,10,-29,47,-70,-52,29,-13,-18,5,34,18,32,87,91}, + {-84,41,-19,96,-51,-19,81,75,81,92,2,-40,-42,-69,-10,-61}, + {-30,98,71,-51,91,-59,58,86,86,-22,-84,7,66,-55,-52,23}, + {-71,-44,-9,90,26,18,26,-10,-85,64,-47,3,72,81,74,-8}, + {52,-59,-91,22,8,-63,84,9,-11,-54,-78,-71,-98,42,96,57}, + {18,-39,34,-50,-62,-96,-2,-78,52,94,-33,2,-19,-9,-86,-75} + }; +const double dA3[][16] = + { + {-24,65,21,19,94,70,-90,-81,53,-41,-23,-1,58,-80,-54,59}, + {-42,76,-19,98,29,-56,92,14,45,11,82,83,48,-13,81,66}, + {43,-57,-67,95,5,72,11,0,-47,55,-24,36,84,54,-31,-54}, + {-39,-40,19,97,-82,-56,27,95,81,-21,-50,-74,-35,-87,-28,-26}, + {-74,-98,79,92,-24,-48,99,94,55,-83,70,98,-24,18,-67,14}, + {20,76,11,-23,-56,21,0,42,64,86,-74,44,93,-76,-30,97}, + {13,20,-73,-11,-30,80,53,-8,60,21,17,-42,82,-72,-6,-80}, + {36,-93,-64,-21,20,-85,15,24,99,81,-52,64,71,-56,52,63}, + {32,9,-2,-85,17,62,-98,-35,75,-58,-44,-20,-47,89,-95,52}, + {93,-43,86,68,-6,-25,90,57,60,-10,65,-97,43,46,-60,-41}, + {43,-33,0,50,-100,26,-60,95,39,-70,-61,-81,9,-23,-99,-4}, + {20,61,15,43,-96,93,-55,38,-29,-1,-10,26,-87,18,64,6}, + {-98,-84,51,16,-14,86,52,59,44,-39,-2,10,82,-66,54,19}, + {89,-49,-37,-6,-53,40,-11,46,-51,-56,86,34,11,13,-20,-49}, + {-90,14,28,-45,-25,-56,-51,-61,28,-8,51,91,95,-10,-85,58}, + {8,-44,88,-71,-27,11,89,37,86,-78,-44,-56,-87,0,-42,-61} + }; +const int *Ap[4] = {(int*) A0,(int*) A1,(int*) A2,(int*) A3}; +const int *Bp[4] = {(int*) B0,(int*) B1,(int*) B2,(int*) B3}; +const double *dAp[4] = {(double*) dA0,(double*) dA1,(double*) dA2,(double*) dA3}; +const double *dBp[4] = {(double*) dB0,(double*) dB1,(double*) dB2,(double*) dB3}; +int n[4] = {2,4,8,16}; +int n_arrays = 4; diff --git a/buch/papers/multiplikation/code/c_meas_4096.pdf b/buch/papers/multiplikation/code/c_meas_4096.pdf index 5236afb..b42082f 100644 Binary files a/buch/papers/multiplikation/code/c_meas_4096.pdf and b/buch/papers/multiplikation/code/c_meas_4096.pdf differ diff --git a/buch/papers/multiplikation/code/ci.txt b/buch/papers/multiplikation/code/ci.txt new file mode 100644 index 0000000..e69de29 diff --git a/buch/papers/multiplikation/code/helper_class.py b/buch/papers/multiplikation/code/helper_class.py index 485fa76..ad67909 100755 --- a/buch/papers/multiplikation/code/helper_class.py +++ b/buch/papers/multiplikation/code/helper_class.py @@ -101,5 +101,6 @@ if __name__ == '__main__': helper = Helper() # n = np.arange(2,10) - n = np.logspace(1,3,3,base=2,dtype=(np.int)) + n = np.logspace(1,4,4,base=2,dtype=(np.int)) + # n=[8192] C = helper.write_c_matrix(n) diff --git a/buch/papers/multiplikation/code/meas/MM.txt b/buch/papers/multiplikation/code/meas/MM.txt index e296dd7..7bffb6e 100644 --- a/buch/papers/multiplikation/code/meas/MM.txt +++ b/buch/papers/multiplikation/code/meas/MM.txt @@ -1,12 +1,110 @@ -0.000001,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 0.000001,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000001,4 +0.000001,4 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000001,8 0.000001,8 -0.000010,16 -0.000081,32 -0.000654,64 -0.005556,128 -0.054253,256 -0.487317,512 -4.162845,1024 -125.909034,2048 -1111.312696,4096 +0.000011,16 +0.000011,16 +0.000011,16 +0.000011,16 +0.000011,16 +0.000021,16 +0.000011,16 +0.000011,16 +0.000011,16 +0.000011,16 +0.000090,32 +0.000093,32 +0.000083,32 +0.000082,32 +0.000090,32 +0.000080,32 +0.000080,32 +0.000080,32 +0.000089,32 +0.000126,32 +0.000771,64 +0.000651,64 +0.000651,64 +0.000651,64 +0.000731,64 +0.000673,64 +0.000745,64 +0.000672,64 +0.000671,64 +0.000707,64 +0.005642,128 +0.005579,128 +0.005768,128 +0.005745,128 +0.005518,128 +0.005877,128 +0.005513,128 +0.005850,128 +0.005769,128 +0.005581,128 +0.052188,256 +0.051988,256 +0.051888,256 +0.051518,256 +0.051709,256 +0.051543,256 +0.051707,256 +0.051845,256 +0.051495,256 +0.051834,256 +0.507020,512 +0.504111,512 +0.502049,512 +0.529743,512 +0.501028,512 +0.502097,512 +0.503490,512 +0.502079,512 +0.506688,512 +0.504163,512 +4.538722,1024 +4.291473,1024 +4.516302,1024 +4.374630,1024 +4.719557,1024 +4.438999,1024 +4.641680,1024 +4.407959,1024 +4.441451,1024 +4.677313,1024 +129.433279,2048 +129.277802,2048 +129.284817,2048 +129.086884,2048 +129.197444,2048 +129.350999,2048 +129.264250,2048 +129.295723,2048 +129.402601,2048 +129.300820,2048 diff --git a/buch/papers/multiplikation/code/meas/MM_dc.txt b/buch/papers/multiplikation/code/meas/MM_dc.txt index f6be928..b78b925 100644 --- a/buch/papers/multiplikation/code/meas/MM_dc.txt +++ b/buch/papers/multiplikation/code/meas/MM_dc.txt @@ -1,12 +1,110 @@ 0.000003,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 0.000002,4 -0.000010,8 -0.000068,16 -0.000594,32 -0.004264,64 -0.036289,128 -0.324645,256 -2.612010,512 -19.928951,1024 -159.333884,2048 -1147.106865,4096 +0.000001,4 +0.000001,4 +0.000001,4 +0.000001,4 +0.000001,4 +0.000001,4 +0.000001,4 +0.000001,4 +0.000001,4 +0.000008,8 +0.000008,8 +0.000008,8 +0.000008,8 +0.000007,8 +0.000007,8 +0.000007,8 +0.000007,8 +0.000018,8 +0.000008,8 +0.000075,16 +0.000063,16 +0.000088,16 +0.000062,16 +0.000086,16 +0.000092,16 +0.000081,16 +0.000080,16 +0.000070,16 +0.000085,16 +0.000581,32 +0.000659,32 +0.000584,32 +0.000714,32 +0.000666,32 +0.000574,32 +0.000616,32 +0.000534,32 +0.000506,32 +0.000506,32 +0.004567,64 +0.004502,64 +0.004332,64 +0.004578,64 +0.004543,64 +0.004426,64 +0.004497,64 +0.004329,64 +0.004288,64 +0.004277,64 +0.036456,128 +0.034901,128 +0.034545,128 +0.034283,128 +0.035150,128 +0.034663,128 +0.034901,128 +0.034022,128 +0.034368,128 +0.035154,128 +0.296292,256 +0.297592,256 +0.302464,256 +0.299557,256 +0.299367,256 +0.306394,256 +0.287616,256 +0.292630,256 +0.289542,256 +0.277019,256 +2.331956,512 +2.224501,512 +2.203910,512 +2.198937,512 +2.206083,512 +2.199477,512 +2.199847,512 +2.225379,512 +2.202491,512 +2.235926,512 +17.649432,1024 +17.636769,1024 +17.639024,1024 +17.625402,1024 +17.722286,1024 +17.611777,1024 +17.653120,1024 +17.748270,1024 +17.691817,1024 +17.614448,1024 +141.943689,2048 +141.580812,2048 +141.882050,2048 +141.516253,2048 +141.351237,2048 +141.641167,2048 +141.596407,2048 +141.607048,2048 +141.469723,2048 +141.515550,2048 diff --git a/buch/papers/multiplikation/code/meas/blas.txt b/buch/papers/multiplikation/code/meas/blas.txt index 92a61b9..9414d8f 100644 --- a/buch/papers/multiplikation/code/meas/blas.txt +++ b/buch/papers/multiplikation/code/meas/blas.txt @@ -1,12 +1,110 @@ 0.000001,2 -0.000001,4 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 0.000001,8 +0.000000,8 +0.000000,8 +0.000000,8 +0.000000,8 +0.000000,8 +0.000000,8 +0.000000,8 +0.000000,8 +0.000000,8 0.000003,16 -0.000022,32 -0.000179,64 +0.000003,16 +0.000003,16 +0.000003,16 +0.000003,16 +0.000003,16 +0.000012,16 +0.000003,16 +0.000003,16 +0.000003,16 +0.000021,32 +0.000019,32 +0.000030,32 +0.000020,32 +0.000020,32 +0.000020,32 +0.000020,32 +0.000020,32 +0.000020,32 +0.000020,32 +0.000180,64 +0.000192,64 +0.000163,64 +0.000153,64 +0.000153,64 +0.000197,64 +0.000163,64 +0.000267,64 +0.000226,64 +0.000164,64 +0.001216,128 +0.001233,128 +0.001364,128 0.001278,128 -0.010165,256 -0.074739,512 -0.704748,1024 -6.845095,2048 -55.845038,4096 +0.001211,128 +0.001295,128 +0.001206,128 +0.001371,128 +0.001225,128 +0.001250,128 +0.009733,256 +0.009497,256 +0.009586,256 +0.009600,256 +0.009768,256 +0.009566,256 +0.009731,256 +0.009550,256 +0.009664,256 +0.009794,256 +0.077453,512 +0.076616,512 +0.088812,512 +0.075990,512 +0.076925,512 +0.076303,512 +0.075915,512 +0.075600,512 +0.075122,512 +0.075029,512 +0.769186,1024 +0.775780,1024 +0.753906,1024 +0.757834,1024 +0.772001,1024 +0.770950,1024 +0.791317,1024 +0.753319,1024 +0.747228,1024 +0.752347,1024 +7.625205,2048 +7.652278,2048 +7.640682,2048 +7.649428,2048 +7.632806,2048 +7.579347,2048 +7.612317,2048 +7.676742,2048 +7.632979,2048 +7.619210,2048 diff --git a/buch/papers/multiplikation/code/meas/ci/MM.txt b/buch/papers/multiplikation/code/meas/ci/MM.txt new file mode 100644 index 0000000..e4ad1ba --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/MM.txt @@ -0,0 +1,11 @@ +0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00 +2.999999999999999864e-07 -4.555021440490437016e-08 6.455502144049043430e-07 +1.800000000000000130e-06 1.498379044967867836e-06 2.101620955032132425e-06 +1.199999999999999861e-05 9.737842837259007037e-06 1.426215716274099018e-05 +8.930000000000000221e-05 7.942767152586658090e-05 9.917232847413342352e-05 +6.922999999999999684e-04 6.611729768299406300e-04 7.234270231700593067e-04 +5.684200000000000363e-03 5.587928563282692010e-03 5.780471436717308717e-03 +5.177150000000000502e-02 5.161257221154376407e-02 5.193042778845624596e-02 +5.062468000000001078e-01 5.001729723042721565e-01 5.123206276957280592e-01 +4.504808599999999608e+00 4.404751183933223402e+00 4.604866016066775813e+00 +1.292894618999999921e+02 1.292188312556721144e+02 1.293600925443278697e+02 diff --git a/buch/papers/multiplikation/code/meas/ci/Wino.txt b/buch/papers/multiplikation/code/meas/ci/Wino.txt new file mode 100644 index 0000000..4ec0106 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/Wino.txt @@ -0,0 +1,11 @@ +9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07 +0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00 +2.000000000000000333e-06 1.999999999999999909e-06 2.000000000000000757e-06 +1.199999999999999861e-05 9.737842837259007037e-06 1.426215716274099018e-05 +8.329999999999999189e-05 7.952898408510092581e-05 8.707101591489905797e-05 +6.478999999999999733e-04 6.173195729945008762e-04 6.784804270054990705e-04 +5.287299999999999986e-03 5.226513788941518357e-03 5.348086211058481615e-03 +5.267459999999999504e-02 5.240389179019239174e-02 5.294530820980759833e-02 +5.249752000000000862e-01 5.233835466989910090e-01 5.265668533010091634e-01 +4.671160999999999675e+00 4.572509907501117965e+00 4.769812092498881384e+00 +1.366769777000000090e+02 1.363957928284978891e+02 1.369581625715021289e+02 diff --git a/buch/papers/multiplikation/code/meas/ci/blas.txt b/buch/papers/multiplikation/code/meas/ci/blas.txt new file mode 100644 index 0000000..5d7ff7b --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/blas.txt @@ -0,0 +1,11 @@ +9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07 +0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00 +9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07 +3.899999999999999929e-06 1.864058553533107683e-06 5.935941446466892176e-06 +2.100000000000000223e-05 1.871284586667546976e-05 2.328715413332453469e-05 +1.858000000000000168e-04 1.595988766828141249e-04 2.120011233171859087e-04 +1.264900000000000009e-03 1.221091632895032926e-03 1.308708367104967091e-03 +9.648900000000000185e-03 9.575266909835235610e-03 9.722533090164764760e-03 +7.737650000000000083e-02 7.445101996220353235e-02 8.030198003779646931e-02 +7.643868000000000329e-01 7.545731380187049586e-01 7.742004619812951072e-01 +7.632099399999999534e+00 7.613379481172315444e+00 7.650819318827683624e+00 diff --git a/buch/papers/multiplikation/code/meas/ci/dc.txt b/buch/papers/multiplikation/code/meas/ci/dc.txt new file mode 100644 index 0000000..df268a9 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/dc.txt @@ -0,0 +1,11 @@ +2.999999999999999864e-07 -3.786471488222973584e-07 9.786471488222972253e-07 +1.100000000000000056e-06 8.737842837259009412e-07 1.326215716274099171e-06 +8.600000000000000670e-06 6.210712693650135778e-06 1.098928730634986641e-05 +7.819999999999998990e-05 7.075203863371232107e-05 8.564796136628765873e-05 +5.940000000000001269e-04 5.439534118129448707e-04 6.440465881870553830e-04 +4.433900000000000167e-03 4.349138038034851966e-03 4.518661961965148369e-03 +3.484430000000000166e-02 3.435947773230259988e-02 3.532912226769740344e-02 +2.948473000000000344e-01 2.887830472415335303e-01 3.009115527584665384e-01 +2.222850699999999957e+00 2.193855611791002858e+00 2.251845788208997057e+00 +1.765923450000000372e+01 1.762601016688562439e+01 1.769245883311438305e+01 +1.416103936000000090e+02 1.414816028568733657e+02 1.417391843431266523e+02 diff --git a/buch/papers/multiplikation/code/meas/ci/strassen.txt b/buch/papers/multiplikation/code/meas/ci/strassen.txt new file mode 100644 index 0000000..983fed9 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/ci/strassen.txt @@ -0,0 +1,11 @@ +0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00 +2.099999999999999799e-06 1.572163328693768390e-06 2.627836671306231420e-06 +1.130000000000000023e-05 7.484018077564905836e-06 1.511598192243509547e-05 +7.069999999999999733e-05 6.500652995675561090e-05 7.639347004324438376e-05 +5.040999999999999474e-04 4.766428619697257881e-04 5.315571380302741610e-04 +3.595999999999999804e-03 3.528938496002300557e-03 3.663061503997699052e-03 +2.544810000000000128e-02 2.513634544137222787e-02 2.575985455862777468e-02 +1.781816999999999984e-01 1.773043765864557864e-01 1.790590234135442105e-01 +1.255500000000000060e+00 1.247847949398645628e+00 1.263152050601354492e+00 +8.830237099999999728e+00 8.790366960647805428e+00 8.870107239352194028e+00 +6.190186909999999898e+01 6.183048085945843297e+01 6.197325734054156499e+01 diff --git a/buch/papers/multiplikation/code/meas/old/8196/MM.txt b/buch/papers/multiplikation/code/meas/old/8196/MM.txt new file mode 100644 index 0000000..0edf9f6 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/8196/MM.txt @@ -0,0 +1 @@ +9376.173434,8192 diff --git a/buch/papers/multiplikation/code/meas/old/8196/MM_dc.txt b/buch/papers/multiplikation/code/meas/old/8196/MM_dc.txt new file mode 100644 index 0000000..36f6ff0 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/8196/MM_dc.txt @@ -0,0 +1 @@ +9606.402522,8192 diff --git a/buch/papers/multiplikation/code/meas/old/8196/blas.txt b/buch/papers/multiplikation/code/meas/old/8196/blas.txt new file mode 100644 index 0000000..b5989fb --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/8196/blas.txt @@ -0,0 +1 @@ +478.429957,8192 diff --git a/buch/papers/multiplikation/code/meas/old/8196/strassen.txt b/buch/papers/multiplikation/code/meas/old/8196/strassen.txt new file mode 100644 index 0000000..ca06e97 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/8196/strassen.txt @@ -0,0 +1 @@ +3014.235467,8192 diff --git a/buch/papers/multiplikation/code/meas/old/8196/winograd.txt b/buch/papers/multiplikation/code/meas/old/8196/winograd.txt new file mode 100644 index 0000000..2a529c4 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/8196/winograd.txt @@ -0,0 +1 @@ +10071.512655,8192 diff --git a/buch/papers/multiplikation/code/meas/old/MM.txt b/buch/papers/multiplikation/code/meas/old/MM.txt new file mode 100644 index 0000000..e296dd7 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/MM.txt @@ -0,0 +1,12 @@ +0.000001,2 +0.000001,4 +0.000001,8 +0.000010,16 +0.000081,32 +0.000654,64 +0.005556,128 +0.054253,256 +0.487317,512 +4.162845,1024 +125.909034,2048 +1111.312696,4096 diff --git a/buch/papers/multiplikation/code/meas/old/MM_dc.txt b/buch/papers/multiplikation/code/meas/old/MM_dc.txt new file mode 100644 index 0000000..f6be928 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/MM_dc.txt @@ -0,0 +1,12 @@ +0.000003,2 +0.000002,4 +0.000010,8 +0.000068,16 +0.000594,32 +0.004264,64 +0.036289,128 +0.324645,256 +2.612010,512 +19.928951,1024 +159.333884,2048 +1147.106865,4096 diff --git a/buch/papers/multiplikation/code/meas/old/blas.txt b/buch/papers/multiplikation/code/meas/old/blas.txt new file mode 100644 index 0000000..92a61b9 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/blas.txt @@ -0,0 +1,12 @@ +0.000001,2 +0.000001,4 +0.000001,8 +0.000003,16 +0.000022,32 +0.000179,64 +0.001278,128 +0.010165,256 +0.074739,512 +0.704748,1024 +6.845095,2048 +55.845038,4096 diff --git a/buch/papers/multiplikation/code/meas/old/strassen.txt b/buch/papers/multiplikation/code/meas/old/strassen.txt new file mode 100644 index 0000000..fdfbf2b --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/strassen.txt @@ -0,0 +1,12 @@ +0.000001,2 +0.000003,4 +0.000010,8 +0.000066,16 +0.000470,32 +0.003368,64 +0.024232,128 +0.172000,256 +1.209262,512 +8.457472,1024 +59.267256,2048 +414.648901,4096 diff --git a/buch/papers/multiplikation/code/meas/old/winograd.txt b/buch/papers/multiplikation/code/meas/old/winograd.txt new file mode 100644 index 0000000..d185906 --- /dev/null +++ b/buch/papers/multiplikation/code/meas/old/winograd.txt @@ -0,0 +1,12 @@ +0.000001,2 +0.000001,4 +0.000002,8 +0.000011,16 +0.000100,32 +0.000654,64 +0.005229,128 +0.057440,256 +0.517850,512 +4.539413,1024 +130.627663,2048 +1179.261048,4096 diff --git a/buch/papers/multiplikation/code/meas/strassen.txt b/buch/papers/multiplikation/code/meas/strassen.txt index fdfbf2b..d6e040e 100644 --- a/buch/papers/multiplikation/code/meas/strassen.txt +++ b/buch/papers/multiplikation/code/meas/strassen.txt @@ -1,12 +1,110 @@ -0.000001,2 -0.000003,4 -0.000010,8 -0.000066,16 -0.000470,32 -0.003368,64 -0.024232,128 -0.172000,256 -1.209262,512 -8.457472,1024 -59.267256,2048 -414.648901,4096 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000004,4 +0.000002,4 +0.000002,4 +0.000002,4 +0.000002,4 +0.000002,4 +0.000002,4 +0.000002,4 +0.000002,4 +0.000001,4 +0.000020,8 +0.000018,8 +0.000008,8 +0.000008,8 +0.000008,8 +0.000008,8 +0.000008,8 +0.000008,8 +0.000008,8 +0.000019,8 +0.000080,16 +0.000075,16 +0.000078,16 +0.000085,16 +0.000065,16 +0.000065,16 +0.000065,16 +0.000064,16 +0.000065,16 +0.000065,16 +0.000546,32 +0.000480,32 +0.000563,32 +0.000551,32 +0.000502,32 +0.000504,32 +0.000463,32 +0.000462,32 +0.000508,32 +0.000462,32 +0.003675,64 +0.003665,64 +0.003493,64 +0.003708,64 +0.003465,64 +0.003502,64 +0.003710,64 +0.003537,64 +0.003637,64 +0.003568,64 +0.025342,128 +0.025179,128 +0.026475,128 +0.025758,128 +0.025333,128 +0.024988,128 +0.025727,128 +0.025298,128 +0.025283,128 +0.025098,128 +0.181311,256 +0.178432,256 +0.177075,256 +0.177474,256 +0.177025,256 +0.177805,256 +0.177944,256 +0.178151,256 +0.177858,256 +0.178742,256 +1.283374,512 +1.246682,512 +1.245898,512 +1.251547,512 +1.250288,512 +1.250495,512 +1.257037,512 +1.255247,512 +1.255382,512 +1.259050,512 +8.784102,1024 +8.845725,1024 +8.771100,1024 +8.770184,1024 +8.955977,1024 +8.849161,1024 +8.806902,1024 +8.808937,1024 +8.848900,1024 +8.861383,1024 +61.787123,2048 +61.972599,2048 +61.822434,2048 +62.051331,2048 +61.946171,2048 +61.911404,2048 +61.872671,2048 +61.791260,2048 +61.818110,2048 +62.045588,2048 diff --git a/buch/papers/multiplikation/code/meas/winograd.txt b/buch/papers/multiplikation/code/meas/winograd.txt index d185906..970a3f4 100644 --- a/buch/papers/multiplikation/code/meas/winograd.txt +++ b/buch/papers/multiplikation/code/meas/winograd.txt @@ -1,12 +1,110 @@ 0.000001,2 -0.000001,4 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,2 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 +0.000000,4 0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000002,8 +0.000011,16 +0.000011,16 +0.000011,16 +0.000011,16 +0.000011,16 +0.000011,16 +0.000011,16 +0.000021,16 +0.000011,16 0.000011,16 -0.000100,32 -0.000654,64 -0.005229,128 -0.057440,256 -0.517850,512 -4.539413,1024 -130.627663,2048 -1179.261048,4096 +0.000092,32 +0.000092,32 +0.000081,32 +0.000081,32 +0.000081,32 +0.000081,32 +0.000088,32 +0.000079,32 +0.000079,32 +0.000079,32 +0.000670,64 +0.000739,64 +0.000609,64 +0.000609,64 +0.000700,64 +0.000648,64 +0.000626,64 +0.000626,64 +0.000626,64 +0.000626,64 +0.005321,128 +0.005286,128 +0.005180,128 +0.005223,128 +0.005249,128 +0.005299,128 +0.005205,128 +0.005268,128 +0.005464,128 +0.005378,128 +0.053123,256 +0.052325,256 +0.052729,256 +0.052930,256 +0.052207,256 +0.053178,256 +0.052122,256 +0.052681,256 +0.052965,256 +0.052486,256 +0.527028,512 +0.525201,512 +0.521822,512 +0.525147,512 +0.525241,512 +0.527725,512 +0.526321,512 +0.526479,512 +0.524020,512 +0.520768,512 +4.732299,1024 +4.617253,1024 +4.647425,1024 +4.519233,1024 +4.917471,1024 +4.564929,1024 +4.870771,1024 +4.555407,1024 +4.727473,1024 +4.559349,1024 +136.409028,2048 +136.390557,2048 +136.541672,2048 +136.598491,2048 +137.720790,2048 +136.825926,2048 +136.367686,2048 +136.650627,2048 +136.642195,2048 +136.622805,2048 diff --git a/buch/papers/multiplikation/code/meas_4096.pdf b/buch/papers/multiplikation/code/meas_4096.pdf index e889d17..9e8fcea 100644 Binary files a/buch/papers/multiplikation/code/meas_4096.pdf and b/buch/papers/multiplikation/code/meas_4096.pdf differ diff --git a/buch/papers/multiplikation/code/meas_4096.txt b/buch/papers/multiplikation/code/meas_4096.txt index e69de29..cae1bc6 100644 --- a/buch/papers/multiplikation/code/meas_4096.txt +++ b/buch/papers/multiplikation/code/meas_4096.txt @@ -0,0 +1,6 @@ +2.048000000000000000e+03 4.096000000000000000e+03 +6.154183513402938843e+03 4.681333474493026733e+04 +7.375929301261901855e+03 5.846600176072120667e+04 +3.860573610544204712e+03 2.290433094644546509e+04 +4.884613198995590210e+03 4.359707747149467468e+04 +2.157390117645263672e-01 1.491588830947875977e+00 diff --git a/buch/papers/multiplikation/images/algo_tab.pdf b/buch/papers/multiplikation/images/algo_tab.pdf new file mode 100644 index 0000000..7f2bb4f Binary files /dev/null and b/buch/papers/multiplikation/images/algo_tab.pdf differ diff --git a/buch/papers/multiplikation/images/algo_tab.tex b/buch/papers/multiplikation/images/algo_tab.tex new file mode 100644 index 0000000..50ce392 --- /dev/null +++ b/buch/papers/multiplikation/images/algo_tab.tex @@ -0,0 +1,122 @@ +\documentclass{article} +\usepackage[left=25mm,right=25mm,top=25mm,bottom=25mm]{geometry} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage{times} +\usepackage{geometry} +\usepackage{amsmath} +\usepackage{amssymb} +\usepackage{algorithm} +\usepackage{algpseudocode} +\usepackage{mathrsfs} +\usepackage{amsfonts} +\usepackage{amsthm} +\usepackage{lipsum} +\usepackage{amscd} +\usepackage{graphicx} +\usepackage{fancyhdr} +\usepackage{textcomp} +\usepackage{pgfplots} +\usepackage{txfonts} +\usepackage[all]{xy} +\usepackage{paralist} +\usepackage[colorlinks=true]{hyperref} +\usepackage{array} +\usepackage{tikz} +\usepackage{slashed} +\usepackage{pdfpages} +\usepackage{multicol} +\usepackage{cite} +\usepackage{url} +\usepackage{amsmath,amsfonts,amssymb} +\usepackage{tikz} +\usetikzlibrary{arrows,matrix,positioning} +\usetikzlibrary{overlay-beamer-styles} +\usetikzlibrary{matrix.skeleton} +\usetikzlibrary{automata,positioning} +\usetikzlibrary{decorations.text} +\usepackage{listings} +\usepackage{multirow} +\usepackage{color} + +\begin{document} + + + +\begin{table}[t] + \begin{tabular}{ll} + \begin{minipage}{0.4\textwidth} + \begin{algorithm}[H]\footnotesize\caption{} + \label{multiplikation:alg:b1} + \setlength{\lineskip}{7pt} + \begin{algorithmic} + \Function{B1}{$a, b$} + \State \textbf{return} $a+b$ + \EndFunction + \State + \State + \end{algorithmic} + \end{algorithm} + \end{minipage} + & + \begin{minipage}{0.4\textwidth} + \begin{algorithm}[H]\footnotesize\caption{} + \label{multiplikation:alg:b2} + \setlength{\lineskip}{7pt} + \begin{algorithmic} + \Function{B2}{$a, b$} + \State $ x \gets a+b $ + \State $ y \gets a \cdot b $ + \State \textbf{return} $x+y$ + \EndFunction + \end{algorithmic} +\end{algorithm} + + \end{minipage} + \end{tabular} +\end{table} + +\begin{table} + \begin{tabular}[t]{ll} + \begin{minipage}{0.4\textwidth} + \begin{algorithm}[H]\footnotesize\caption{} + \setlength{\lineskip}{7pt} + \begin{algorithmic} + \label{multiplikation:alg:linear} + \Function{L}{$\mathbf{a}, \mathbf{b}$,n} + \State $ sum \gets 0$ + \For{$i = 0,1,2 \dots,n$} + \State $ sum \gets sum + A[i] \cdot B[i] $ + \EndFor + + \State \textbf{return} $sum$ + + \EndFunction + \State + \State + \end{algorithmic} + \end{algorithm} + \end{minipage} + & + \begin{minipage}{0.4\textwidth} + \begin{algorithm}[H]\footnotesize\caption{} + \label{multiplikation:alg:q1} + \setlength{\lineskip}{7pt} + \begin{algorithmic} + \Function{Q}{$\mathbf{A}, \mathbf{B}$,n} + \State $ sum \gets 0$ + \For{$i = 0,1,2 \dots,n$} + \For{$j = 0,1,2 \dots,n$} + \State $ sum \gets sum + A[i] \cdot B[j] $ + \EndFor + \EndFor + \State \textbf{return} $sum$ + \EndFunction + \end{algorithmic} + \end{algorithm} + \end{minipage} + \end{tabular} +\end{table} + +dhdfh +\end{document} diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf index 3a4cfd8..e6af618 100644 Binary files a/buch/papers/multiplikation/images/meas_c.pdf and b/buch/papers/multiplikation/images/meas_c.pdf differ diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex index 818a7e6..647a322 100644 --- a/buch/papers/multiplikation/images/meas_c.tex +++ b/buch/papers/multiplikation/images/meas_c.tex @@ -43,8 +43,8 @@ \begin{tikzpicture} \begin{axis}[ xmode=log, ymode=log, -xmin=60, xmax=5000, -ymin=1e-4, ymax=2e3, +xmin=60, xmax=10000, +ymin=1e-4, ymax=2e4, grid=both, major grid style={black!50}, xlabel = data Input ($n$), @@ -70,6 +70,7 @@ width=12cm, height=8cm, (1024,4.539413) (2048,130.627663) (4096,1179.261048) +(8192,10071.512655) }; \addlegendentry{Strassen} \addplot [ color=black, @@ -86,6 +87,7 @@ width=12cm, height=8cm, (1024,8.457472 ) (2048,59.267256) (4096,414.648901) +(8192,3014.235467) }; \addlegendentry{MM div and conq} @@ -103,6 +105,7 @@ width=12cm, height=8cm, (1024,19.928951 ) (2048,159.333884 ) (4096,1147.106865) +(8192,9606.402522) }; \addlegendentry{MM} @@ -120,6 +123,7 @@ width=12cm, height=8cm, (1024,4.162845 ) (2048,125.909034 ) (4096,1111.312696) +(8192,9376.173434) }; \addlegendentry{BLAS} \addplot[ color=blue, @@ -136,6 +140,7 @@ width=12cm, height=8cm, (1024,0.704748 ) (2048,6.845095 ) (4096,55.845038) +(8192,478.429957) }; \end{axis} \end{tikzpicture} diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index a7612e1..464085d 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -39,13 +39,13 @@ Die \texttt{for i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, \end{algorithmic} \end{algorithm} -Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O}\left(n^3\right)$ +Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O} (n^3)$ \subsubsection{Divide and Conquer Methode} F\"ur gewisse Algorithmen f\"uhren \textit{Divide and Conquer} Ans\"atze \cite{multiplikation:DAC} zu markant besseren Laufzeiten. Die Grundidee ist, dass ein Problem in mehrere, meist simplere und kleinere Teilprobleme aufgeteilt wird. -Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die Laufzeit von $\mathcal{O}\left(n^2\right)$ zu $\mathcal{O}(n \log n)$ verbessert werden kann. +Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die Laufzeit von $\mathcal{O} (n^2)$ zu $\mathcal{O}(n \log n)$ verbessert werden kann. Die Matrizenmultiplikation kann ebenfalls mit solch einem Ansatz berechnet werden. Zur vereinfachten Veranschaulichung kann die Situation mit $\mathbf{A}$ und $\mathbf{B}$ der Gr\"osse $2^n \times 2^n$ verwendet werden. @@ -68,7 +68,7 @@ Das Matrizen Produkt \end{bmatrix}, \end{equation} \begin{equation} -\mathbf{C}_{ij} = \sum_{k=1}2n \mathbf{A}_{ik} \mathbf{B}_{kj} +\mathbf{C}_{ij} = \sum_{k=1}^{2n} \mathbf{A}_{ik} \mathbf{B}_{kj} \label{multiplikation:eq:MM_block} \end{equation} ist identisch zu der Gleichung \eqref{multiplikation:eq:MM}, f\"ur die Multiplikation der Untermatrize $\mathbf{A}_{ik}$ und $\mathbf{B}_{kj}$ wird die Matrizenmultiplikation verwendet. @@ -109,7 +109,7 @@ Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} \ci Ohne auf dieses vertieft einzugehen, bestimmt die Anzahl rekursiver Aufrufe $\mathcal{T} $ der Funktion die Laufzeit. In diesem Fall wird die Funktion pro Durchlauf acht mal rekursiv aufgerufen, dies f\"uhrt \begin{equation} \label{multiplikation:eq:laufzeitdac} - \mathcal{T}(n) = 8 \cdot \mathcal{T}\left (\frac{n}{2}\right ) + n^2 = \mathcal{O}(n^{\log_2 8}) = \mathcal{O}\left (n^{3} \right ) + \mathcal{T}(n) = 8 \cdot \mathcal{T} \left(\frac{n}{2}\right ) + n^2 = \mathcal{O}(n^{\log_2 8}) = \mathcal{O} (n^{3} ) \end{equation} zu einer kubischen Laufzeit. Die Addition zweier Matrizen $\mathbf{A} + \mathbf{B} = \mathbf{C}$ hat eine Laufzeit von $\mathcal{O}(n^{2})$ und kann neben dem dominierendem Anteil von $\mathcal{O}(n^{3})$ ignoriert werden. @@ -202,7 +202,7 @@ Die Funktion wird sieben mal rekursiv aufgerufen. Dies f\"uhrt nach dem \textit{Master Theorem} zu einer Laufzeit von \begin{equation} \label{multiplikation:eq:laufzeitstrassen} \mathcal{T}(n) = -7 \cdot \mathcal{T}(\frac{n}{2}) + n^2 = \mathcal{O}\left(n^{\log_2 7}\right ) = \mathcal{O}\left(n^{2.8074} \right ) +7 \cdot \mathcal{T}\left(\frac{n}{2}\right) + n^2 = \mathcal{O}(n^{\log_2 7} ) = \mathcal{O}(n^{2.8074} ) \end{equation} und ist somit schneller als die Standardmethode. Man beachte, dass die Anzahl von Additionen und Subtraktionen gr\"osser und die Anzahl der Multiplikationen kleiner wurde. @@ -267,7 +267,7 @@ sein, damit man etwas einspart. Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden. Falls $m=n=p$ werden $\frac{n^3}/{2}$ Multiplikationen benötigt. Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \rightarrow \infty$ können Konstanten vernachlässigt werden und - somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}\left(n^3 \right)$. + somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}(n^3 )$. \begin{algorithm}\footnotesize\caption{Winograds Matrizenmultiplikation} \setlength{\lineskip}{7pt} \label{multiplikation:alg:winograd} @@ -336,33 +336,33 @@ Die meisten Numerischen Bibliotheken von High-Level Skriptsprachen wie \texttt{M \item Level 2 \begin{itemize} \item Operationen der Art: $\mathbf{y} \leftarrow \alpha \mathbf{A}\mathbf{x}+\beta \mathbf{y}$ - \item Dieses Level hat $\mathcal{O}\left(n^2\right)$ Charakteristik + \item Dieses Level hat $\mathcal{O}(n^2)$ Charakteristik \end{itemize} \item Level 3 \begin{itemize} \item Operationen der Art: $\mathbf{C} \leftarrow \alpha \mathbf{A}\mathbf{B}+\beta\mathbf{C}$ - \item Dieses Level hat $\mathcal{O}\left(n^3\right)$ Charakteristik + \item Dieses Level hat $\mathcal{O}(n^3)$ Charakteristik \end{itemize} \end{itemize} Die \textit{BLAS} sind auf die modernen Computer Prozessoren optimiert und k\"onnen dank einer ausgeklügelter Verwendung der Speicherarchitektur zu erheblichen Leistungsoptimierungen f\"uhren. -\subsubsection{General Matrix Multiplication (GEMM)} - -Die \textit{Double-GEMM} \cite{multiplikation:DGEMM} ist definiert als: - -\textit{DGEMM performs one of the matrix-matrix operations} -$$ - C := \alpha \cdot op( A )\cdot op( B ) + \beta \cdot C, - $$ - \textit{where op( X ) is one of} -$$ -op( X ) = X \quad \text{ or } \quad op( X ) = X^T, -$$ - \textit{alpha and beta are scalars, and A, B and C are matrices, with op( A ) - an m by k matrix, op( B ) a k by n matrix and C an m by n matrix. - } +%\subsubsection{General Matrix Multiplication (GEMM)} +% +%Die \textit{Double-GEMM} \cite{multiplikation:DGEMM} ist definiert als: +% +%\textit{DGEMM performs one of the matrix-matrix operations} +%$$ +% C := \alpha \cdot op( A )\cdot op( B ) + \beta \cdot C, +% $$ +% \textit{where op( X ) is one of} +%$$ +%op( X ) = X \quad \text{ or } \quad op( X ) = X^T, +%$$ +% \textit{alpha and beta are scalars, and A, B and C are matrices, with op( A ) +% an m by k matrix, op( B ) a k by n matrix and C an m by n matrix. +% } %Die Implementation von $\alpha\mathbf{A}\mathbf{B} + \beta \mathbf{C} = \mathbf{C}$, wobei $\alpha = 1.0$ und $\beta = 0.0$ in der \texttt{C}-Version von \textit{BLAS}, ist als %\begin{lstlisting}[style=multiplikationC] @@ -379,7 +379,7 @@ $$ Folgende Algorithmen wurden jeweils in \texttt{C} und \texttt{Python} implementiert. \begin{itemize} \item Standard Matrizenmultiplikation - \item \textit{Devide and Conquer} Matrizenmultiplikation + \item \textit{Divide and Conquer} Matrizenmultiplikation \item Strassens Matrizenmultiplikation \item Winograds Matrizenmultiplikation \item \texttt{BLAS} Matrizenmultiplikation in \texttt{C} diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index e53b0de..c8ba274 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -14,87 +14,102 @@ Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der S Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Abhängigkeit zur Inputgrösse \cite{multiplikation:bigo}. $f(x) \in \mathcal{O}(g(x))$ besagt, dass die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$. % Es gibt eine Konstante $K$ derart, dass $f(x) \le K g(x)$ für $x\to\infty$ -Als Beispiel: benötigt eine Funktion $g$ $\mathcal{O}\left(n^2 \right)$ Multiplikationen, so wächst $f$ mit $\mathcal{O}\left(n+ n^2 \right)$ nicht wesentlich schneller falls $x\to\infty$. +Als Beispiel: benötigt eine Funktion $g$ $\mathcal{O} (n^2 )$ Multiplikationen, so wächst $f$ mit $\mathcal{O} (n+ n^2 )$ nicht wesentlich schneller falls $x\to\infty$. Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet: \begin{itemize} \item $f \in \mathcal{O}(1) \rightarrow f$ ist beschr\"ankt \item $f \in \mathcal{O}(n) \rightarrow f$ w\"achst linear - \item $f \in \mathcal{O}\left (n^2 \right ) \rightarrow f$ w\"achst quadratisch + \item $f \in \mathcal{O} (n^2 ) \rightarrow f$ w\"achst quadratisch \item $f \in \mathcal{O}(\log n) \rightarrow f$ w\"achst logarithmisch \item $f \in \mathcal{O}(n \log n) \rightarrow f$ hat super-lineares Wachstum - \item $f \in \mathcal{O}\left (e^n \right ) \rightarrow f$ w\"achst exponentiell + \item $f \in \mathcal{O} (e^n ) \rightarrow f$ w\"achst exponentiell \item usw. \end{itemize} In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden. Bei einer logarithmischen Darstellung werden Polynome der Form $f(x) = x^k$ als Gerade und Exponentialfunktionen der Form $f(x) = a^x$ als nach oben gekr\"ummte Kurven dargestellt. -Sch\"on zu erkennen ist, dass Logarithmische Kurven beschr\"ankt sind. + \subsubsection{Beispiel Algorithmen} Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen. -\begin{minipage}{0.4\textwidth} - \begin{algorithm}[H]\footnotesize\caption{} - \label{multiplikation:alg:b1} - \setlength{\lineskip}{7pt} - \begin{algorithmic} - \Function{B1}{$a, b$} - \State \textbf{return} $a+b$ - \EndFunction - \end{algorithmic} - \end{algorithm} - - \begin{algorithm}[H]\footnotesize\caption{} - \setlength{\lineskip}{7pt} - \begin{algorithmic} - \label{multiplikation:alg:linear} - \Function{L}{$\mathbf{a}, \mathbf{b}$,n} - \State $ sum \gets 0$ - \For{$i = 0,1,2 \dots,n$} - \State $ sum \gets sum + A[i] \cdot B[i] $ - \EndFor - - \State \textbf{return} $sum$ - - \EndFunction - \end{algorithmic} - \end{algorithm} -\end{minipage} -\hspace{2cm} -\begin{minipage}{0.4\textwidth} - - \begin{algorithm}[H]\footnotesize\caption{} - \label{multiplikation:alg:b2} - \setlength{\lineskip}{7pt} - \begin{algorithmic} - \Function{B2}{$a, b$} - \State $ x \gets a+b $ - \State $ y \gets a \cdot b $ - \State \textbf{return} $x+y$ - \EndFunction - \end{algorithmic} - \end{algorithm} - - - \begin{algorithm}[H]\footnotesize\caption{} - \label{multiplikation:alg:q1} - \setlength{\lineskip}{7pt} - \begin{algorithmic} - \Function{Q}{$\mathbf{A}, \mathbf{B}$,n} - \State $ sum \gets 0$ - \For{$i = 0,1,2 \dots,n$} - \For{$j = 0,1,2 \dots,n$} - \State $ sum \gets sum + A[i] \cdot B[j] $ - \EndFor - \EndFor - \State \textbf{return} $sum$ - \EndFunction - \end{algorithmic} - \end{algorithm} - -\end{minipage} + +\begin{table}[t] + \begin{tabular}{ll} + \begin{minipage}{0.48\textwidth} + \begin{algorithm}[H]\footnotesize\caption{} + \label{multiplikation:alg:b1} + \setlength{\lineskip}{7pt} + \begin{algorithmic} + \Function{B1}{$a, b$} + \State \textbf{return} $a+b$ + \EndFunction + \State + \State + \end{algorithmic} + \end{algorithm} + \end{minipage} + & + \begin{minipage}{0.48\textwidth} + \begin{algorithm}[H]\footnotesize\caption{} + \label{multiplikation:alg:b2} + \setlength{\lineskip}{7pt} + \begin{algorithmic} + \Function{B2}{$a, b$} + \State $ x \gets a+b $ + \State $ y \gets a \cdot b $ + \State \textbf{return} $x+y$ + \EndFunction + \end{algorithmic} + \end{algorithm} + + \end{minipage} + \end{tabular} +\end{table} + +\begin{table} + \begin{tabular}[t]{ll} + \begin{minipage}{0.48\textwidth} + \begin{algorithm}[H]\footnotesize\caption{} + \setlength{\lineskip}{7pt} + \begin{algorithmic} + \label{multiplikation:alg:linear} + \Function{L}{$\mathbf{a}, \mathbf{b}$,n} + \State $ sum \gets 0$ + \For{$i = 0,1,2 \dots,n$} + \State $ sum \gets sum + A[i] \cdot B[i] $ + \EndFor + + \State \textbf{return} $sum$ + + \EndFunction + \State + \State + \end{algorithmic} + \end{algorithm} + \end{minipage} + & + \begin{minipage}{0.48\textwidth} + \begin{algorithm}[H]\footnotesize\caption{} + \label{multiplikation:alg:q1} + \setlength{\lineskip}{7pt} + \begin{algorithmic} + \Function{Q}{$\mathbf{A}, \mathbf{B}$,n} + \State $ sum \gets 0$ + \For{$i = 0,1,2 \dots,n$} + \For{$j = 0,1,2 \dots,n$} + \State $ sum \gets sum + A[i] \cdot B[j] $ + \EndFor + \EndFor + \State \textbf{return} $sum$ + \EndFunction + \end{algorithmic} + \end{algorithm} + \end{minipage} + \end{tabular} +\end{table} \paragraph{Beschr\"ankter Algorithmus} @@ -111,7 +126,7 @@ Die \texttt{for}-Schleife wird $n$-mal durchlaufen und f\"uhrt deshalb zu $\math \paragraph{Quadratischer Algorithmus} Der Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalten. -Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$. +Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O} (n^2 )$. \begin{figure} -- cgit v1.2.1 From 3c59b60807e1d1238bf591e238a42574327246ca Mon Sep 17 00:00:00 2001 From: Nunigan Date: Tue, 10 Aug 2021 07:29:49 +0200 Subject: update plots --- buch/papers/multiplikation/code/MM.py | 22 ++-- buch/papers/multiplikation/code/c_meas_4096.pdf | Bin 22360 -> 22207 bytes buch/papers/multiplikation/code/helper_class.py | 4 +- buch/papers/multiplikation/code/meas/ci/MM.txt | 11 -- buch/papers/multiplikation/code/meas/ci/Wino.txt | 11 -- buch/papers/multiplikation/code/meas/ci/blas.txt | 11 -- buch/papers/multiplikation/code/meas/ci/dc.txt | 11 -- .../multiplikation/code/meas/ci/strassen.txt | 11 -- buch/papers/multiplikation/code/meas_4096.pdf | Bin 17369 -> 18300 bytes buch/papers/multiplikation/images/meas_c.pdf | Bin 23552 -> 24028 bytes buch/papers/multiplikation/images/meas_c.tex | 115 +++++++++++---------- buch/papers/multiplikation/images/meas_python.pdf | Bin 21700 -> 26004 bytes buch/papers/multiplikation/images/meas_python.tex | 53 ++++++---- buch/papers/multiplikation/images/x.pdf | Bin 0 -> 23603 bytes 14 files changed, 105 insertions(+), 144 deletions(-) create mode 100644 buch/papers/multiplikation/images/x.pdf (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/code/MM.py b/buch/papers/multiplikation/code/MM.py index 8a6824a..8057850 100644 --- a/buch/papers/multiplikation/code/MM.py +++ b/buch/papers/multiplikation/code/MM.py @@ -291,19 +291,21 @@ def mean_confidence_interval(data, confidence=0.95): n = len(a) m, se = np.mean(a), scipy.stats.sem(a) h = se * scipy.stats.t.ppf((1 + confidence) / 2., n-1) - return m, m-h, m+h + return m, h # test%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% if __name__ == '__main__': - A = plot_c_res(10, 4096) - name = ['MM', 'Wino', 'blas', 'strassen', 'dc'] - for i in range(5): - ci_inner = [] - for j in range(11): - ci_inner.append(mean_confidence_interval(A[i][j*10:(j+1)*10])) - np.savetxt('meas/ci/' + name[i]+'.txt',ci_inner) - - # arr = plot(1024) + # A = plot_c_res(10, 4096) + # name = ['MM', 'Wino', 'blas', 'strassen', 'dc'] + # for i in range(5): + # ci_inner = [] + # print(name[i]) + # for j in range(11): + # m,h=mean_confidence_interval(A[i][j*10:(j+1)*10]) + # print("({},{})".format(2**(j+1),m)) + # np.savetxt('meas/ci/' + name[i]+'.txt',ci_inner) + + arr = plot(4096) # n = np.logspace(1,12,12,base=2,dtype=(np.int)) # n=[2048,4096] # n = np.arange(1,50,2) diff --git a/buch/papers/multiplikation/code/c_meas_4096.pdf b/buch/papers/multiplikation/code/c_meas_4096.pdf index b42082f..f637ae4 100644 Binary files a/buch/papers/multiplikation/code/c_meas_4096.pdf and b/buch/papers/multiplikation/code/c_meas_4096.pdf differ diff --git a/buch/papers/multiplikation/code/helper_class.py b/buch/papers/multiplikation/code/helper_class.py index ad67909..3b74f67 100755 --- a/buch/papers/multiplikation/code/helper_class.py +++ b/buch/papers/multiplikation/code/helper_class.py @@ -101,6 +101,6 @@ if __name__ == '__main__': helper = Helper() # n = np.arange(2,10) - n = np.logspace(1,4,4,base=2,dtype=(np.int)) + n = np.logspace(1,11,11,base=2,dtype=(np.int)) # n=[8192] - C = helper.write_c_matrix(n) + # C = helper.write_c_matrix(n) diff --git a/buch/papers/multiplikation/code/meas/ci/MM.txt b/buch/papers/multiplikation/code/meas/ci/MM.txt index e4ad1ba..e69de29 100644 --- a/buch/papers/multiplikation/code/meas/ci/MM.txt +++ b/buch/papers/multiplikation/code/meas/ci/MM.txt @@ -1,11 +0,0 @@ -0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00 -2.999999999999999864e-07 -4.555021440490437016e-08 6.455502144049043430e-07 -1.800000000000000130e-06 1.498379044967867836e-06 2.101620955032132425e-06 -1.199999999999999861e-05 9.737842837259007037e-06 1.426215716274099018e-05 -8.930000000000000221e-05 7.942767152586658090e-05 9.917232847413342352e-05 -6.922999999999999684e-04 6.611729768299406300e-04 7.234270231700593067e-04 -5.684200000000000363e-03 5.587928563282692010e-03 5.780471436717308717e-03 -5.177150000000000502e-02 5.161257221154376407e-02 5.193042778845624596e-02 -5.062468000000001078e-01 5.001729723042721565e-01 5.123206276957280592e-01 -4.504808599999999608e+00 4.404751183933223402e+00 4.604866016066775813e+00 -1.292894618999999921e+02 1.292188312556721144e+02 1.293600925443278697e+02 diff --git a/buch/papers/multiplikation/code/meas/ci/Wino.txt b/buch/papers/multiplikation/code/meas/ci/Wino.txt index 4ec0106..e69de29 100644 --- a/buch/papers/multiplikation/code/meas/ci/Wino.txt +++ b/buch/papers/multiplikation/code/meas/ci/Wino.txt @@ -1,11 +0,0 @@ -9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07 -0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00 -2.000000000000000333e-06 1.999999999999999909e-06 2.000000000000000757e-06 -1.199999999999999861e-05 9.737842837259007037e-06 1.426215716274099018e-05 -8.329999999999999189e-05 7.952898408510092581e-05 8.707101591489905797e-05 -6.478999999999999733e-04 6.173195729945008762e-04 6.784804270054990705e-04 -5.287299999999999986e-03 5.226513788941518357e-03 5.348086211058481615e-03 -5.267459999999999504e-02 5.240389179019239174e-02 5.294530820980759833e-02 -5.249752000000000862e-01 5.233835466989910090e-01 5.265668533010091634e-01 -4.671160999999999675e+00 4.572509907501117965e+00 4.769812092498881384e+00 -1.366769777000000090e+02 1.363957928284978891e+02 1.369581625715021289e+02 diff --git a/buch/papers/multiplikation/code/meas/ci/blas.txt b/buch/papers/multiplikation/code/meas/ci/blas.txt index 5d7ff7b..e69de29 100644 --- a/buch/papers/multiplikation/code/meas/ci/blas.txt +++ b/buch/papers/multiplikation/code/meas/ci/blas.txt @@ -1,11 +0,0 @@ -9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07 -0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00 -9.999999999999999547e-08 -1.262157162740991459e-07 3.262157162740991104e-07 -3.899999999999999929e-06 1.864058553533107683e-06 5.935941446466892176e-06 -2.100000000000000223e-05 1.871284586667546976e-05 2.328715413332453469e-05 -1.858000000000000168e-04 1.595988766828141249e-04 2.120011233171859087e-04 -1.264900000000000009e-03 1.221091632895032926e-03 1.308708367104967091e-03 -9.648900000000000185e-03 9.575266909835235610e-03 9.722533090164764760e-03 -7.737650000000000083e-02 7.445101996220353235e-02 8.030198003779646931e-02 -7.643868000000000329e-01 7.545731380187049586e-01 7.742004619812951072e-01 -7.632099399999999534e+00 7.613379481172315444e+00 7.650819318827683624e+00 diff --git a/buch/papers/multiplikation/code/meas/ci/dc.txt b/buch/papers/multiplikation/code/meas/ci/dc.txt index df268a9..e69de29 100644 --- a/buch/papers/multiplikation/code/meas/ci/dc.txt +++ b/buch/papers/multiplikation/code/meas/ci/dc.txt @@ -1,11 +0,0 @@ -2.999999999999999864e-07 -3.786471488222973584e-07 9.786471488222972253e-07 -1.100000000000000056e-06 8.737842837259009412e-07 1.326215716274099171e-06 -8.600000000000000670e-06 6.210712693650135778e-06 1.098928730634986641e-05 -7.819999999999998990e-05 7.075203863371232107e-05 8.564796136628765873e-05 -5.940000000000001269e-04 5.439534118129448707e-04 6.440465881870553830e-04 -4.433900000000000167e-03 4.349138038034851966e-03 4.518661961965148369e-03 -3.484430000000000166e-02 3.435947773230259988e-02 3.532912226769740344e-02 -2.948473000000000344e-01 2.887830472415335303e-01 3.009115527584665384e-01 -2.222850699999999957e+00 2.193855611791002858e+00 2.251845788208997057e+00 -1.765923450000000372e+01 1.762601016688562439e+01 1.769245883311438305e+01 -1.416103936000000090e+02 1.414816028568733657e+02 1.417391843431266523e+02 diff --git a/buch/papers/multiplikation/code/meas/ci/strassen.txt b/buch/papers/multiplikation/code/meas/ci/strassen.txt index 983fed9..e69de29 100644 --- a/buch/papers/multiplikation/code/meas/ci/strassen.txt +++ b/buch/papers/multiplikation/code/meas/ci/strassen.txt @@ -1,11 +0,0 @@ -0.000000000000000000e+00 0.000000000000000000e+00 0.000000000000000000e+00 -2.099999999999999799e-06 1.572163328693768390e-06 2.627836671306231420e-06 -1.130000000000000023e-05 7.484018077564905836e-06 1.511598192243509547e-05 -7.069999999999999733e-05 6.500652995675561090e-05 7.639347004324438376e-05 -5.040999999999999474e-04 4.766428619697257881e-04 5.315571380302741610e-04 -3.595999999999999804e-03 3.528938496002300557e-03 3.663061503997699052e-03 -2.544810000000000128e-02 2.513634544137222787e-02 2.575985455862777468e-02 -1.781816999999999984e-01 1.773043765864557864e-01 1.790590234135442105e-01 -1.255500000000000060e+00 1.247847949398645628e+00 1.263152050601354492e+00 -8.830237099999999728e+00 8.790366960647805428e+00 8.870107239352194028e+00 -6.190186909999999898e+01 6.183048085945843297e+01 6.197325734054156499e+01 diff --git a/buch/papers/multiplikation/code/meas_4096.pdf b/buch/papers/multiplikation/code/meas_4096.pdf index 9e8fcea..ecf2cff 100644 Binary files a/buch/papers/multiplikation/code/meas_4096.pdf and b/buch/papers/multiplikation/code/meas_4096.pdf differ diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf index e6af618..faf347e 100644 Binary files a/buch/papers/multiplikation/images/meas_c.pdf and b/buch/papers/multiplikation/images/meas_c.pdf differ diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex index 647a322..fe2bd2f 100644 --- a/buch/papers/multiplikation/images/meas_c.tex +++ b/buch/papers/multiplikation/images/meas_c.tex @@ -43,8 +43,8 @@ \begin{tikzpicture} \begin{axis}[ xmode=log, ymode=log, -xmin=60, xmax=10000, -ymin=1e-4, ymax=2e4, +xmin=30, xmax=10000, +ymin=1e-5, ymax=2e4, grid=both, major grid style={black!50}, xlabel = data Input ($n$), @@ -57,35 +57,36 @@ width=12cm, height=8cm, ] \addlegendentry{Winograd} \addplot[ color=purple, + error bars/.cd, y dir=both, y explicit, ] coordinates { -% (2, 0.000001) -% (4, 0.000001) -% (8, 0.000002) -% (16, 0.000011) -% (32, 0.000100) -(64, 0.000654) -(128, 0.005229) -(256, 0.057440) -(512, 0.517850) -(1024,4.539413) -(2048,130.627663) +%(2,1e-07) +%(4,5e-07) +%(8,2.0000000000000003e-06) +%(16,1.1999999999999999e-05) +(32,8.329999999999999e-05) +(64,0.0006479) +(128,0.0052873) +(256,0.052674599999999995) +(512,0.5249752000000001) +(1024,4.671161) +(2048,136.6769777) (4096,1179.261048) (8192,10071.512655) }; \addlegendentry{Strassen} \addplot [ color=black, ]coordinates { - % (2,0.000001 ) - % (4,0.000003 ) - % (8,0.000010 ) - % (16,0.000066 ) - % (32,0.000470 ) - (64,0.003368 ) - (128,0.024232 ) - (256,0.172000 ) - (512,1.209262 ) -(1024,8.457472 ) -(2048,59.267256) +%(2,1e-07) +%(4,2.1e-06) +%(8,1.13e-05) +%(16,7.07e-05) +(32,0.0005041) +(64,0.003596) +(128,0.0254481) +(256,0.1781817) +(512,1.2555) +(1024,8.8302371) +(2048,61.9018691) (4096,414.648901) (8192,3014.235467) }; @@ -93,17 +94,17 @@ width=12cm, height=8cm, \addlegendentry{MM div and conq} \addplot[ color=green, ] coordinates { - % (2,0.000003 ) - % (4,0.000002 ) - % (8,0.000010 ) - % (16,0.000068 ) - % (32,0.000594 ) - (64,0.004264 ) - (128,0.036289 ) - (256,0.324645 ) - (512,2.612010 ) -(1024,19.928951 ) -(2048,159.333884 ) +%(2,3e-07) +%(4,1.1e-06) +%(8,8.6e-06) +%(16,7.819999999999999e-05) +(32,0.0005940000000000001) +(64,0.0044339) +(128,0.0348443) +(256,0.29484730000000003) +(512,2.2228507) +(1024,17.659234500000004) +(2048,141.6103936) (4096,1147.106865) (8192,9606.402522) }; @@ -111,34 +112,34 @@ width=12cm, height=8cm, \addlegendentry{MM} \addplot [ color=red, ]coordinates { - % (2,0.000001 ) - % (4,0.000001 ) - % (8,0.000001 ) - % (16,0.000010 ) - % (32,0.000081 ) - (64,0.000654 ) - (128,0.005556 ) - (256,0.054253 ) - (512,0.487317 ) -(1024,4.162845 ) -(2048,125.909034 ) +%(2,0.0) +%(4,3e-07) +%(8,1.8000000000000001e-06) +%(16,1.1999999999999999e-05) +(32,8.93e-05) +(64,0.0006923) +(128,0.0056842) +(256,0.051771500000000005) +(512,0.5062468000000001) +(1024,4.5048086) +(2048,129.2894619) (4096,1111.312696) (8192,9376.173434) }; \addlegendentry{BLAS} \addplot[ color=blue, ] coordinates { - % (2,0.000001 ) - % (4,0.000001 ) - % (8,0.000001 ) - % (16,0.000003 ) - % (32,0.000022 ) - (64,0.000179 ) - (128,0.001278 ) - (256,0.010165 ) - (512,0.074739 ) -(1024,0.704748 ) -(2048,6.845095 ) +%(2,1e-07) +%(4,0.0) +%(8,1e-07) +%(16,3.9e-06) +(32,2.1000000000000002e-05) +(64,0.00018580000000000002) +(128,0.0012649) +(256,0.0096489) +(512,0.0773765) +(1024,0.7643868) +(2048,7.6320993999999995) (4096,55.845038) (8192,478.429957) }; diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf index cea2232..cea4f4b 100644 Binary files a/buch/papers/multiplikation/images/meas_python.pdf and b/buch/papers/multiplikation/images/meas_python.pdf differ diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex index ee4db43..c8892be 100644 --- a/buch/papers/multiplikation/images/meas_python.tex +++ b/buch/papers/multiplikation/images/meas_python.tex @@ -43,8 +43,8 @@ \begin{tikzpicture} \begin{axis}[ xmode=log, ymode=log, -xmin=30, xmax=1050, -ymin=0.01, ymax=900, +xmin=30, xmax=4100, +ymin=0.00001, ymax=60000, grid=both, major grid style={black!50}, xlabel = data input ($n$), @@ -68,7 +68,8 @@ width=12cm, height=8cm, (256, 8.29899 ) (512, 68.3699 ) (1024,537.374 ) - +(2046,4884.61) +(4096,43597.1) }; \addlegendentry{Strassen} \addplot [ color=black, @@ -79,10 +80,12 @@ width=12cm, height=8cm, % (16,0.00475407 ) (32,0.0485256 ) (64,0.220414 ) - (128,1.44718 2 ) - (256,9.93866 0 ) - (512,63.961 2 ) -(1024,461.494 2 ) + (128,1.44718 ) + (256,9.93866 ) + (512,63.961 ) +(1024,461.494 ) +(2046,3860.57) +(4096,22904.3) }; \addlegendentry{MM div and conq} @@ -98,6 +101,8 @@ width=12cm, height=8cm, (256,13.27 ) (512,105.397 ) (1024,847.321 ) +(2046,7375.93) +(4096,58466) }; \addlegendentry{MM} @@ -113,25 +118,33 @@ width=12cm, height=8cm, (256, 11.0062 ) (512, 85.4768) (1024,750.757 ) +(2046,6154.18) +(4096,46813.3) }; -% \addlegendentry{NumPy} -% \addplot[ color=blue, -% ] coordinates { + \addlegendentry{NumPy} + \addplot[ color=blue, + ] coordinates { % (2,1.83582e-05 ) % (4,7.86781e-06) % (8,1.00136e-05) % (16,5.4121e-05 ) -% (32,4.26769e-05) -% (64,0.000118494) -% (128,0.000244141 ) -% (256,0.000695705 ) -% (512,0.00221705 ) -% (1024,0.0188088 ) -% }; + (32,4.26769e-05) + (64,0.000118494) + (128,0.000244141 ) + (256,0.000695705 ) + (512,0.00221705 ) + (1024,0.0188088 ) +(2046,0.215739) +(4096,1.49159) + }; + \addplot [ + domain= 1:5000, + samples=100, + color=yellow, + ] + {(x-1000)^3}; + \addlegendentry{$\mathcal{O}\left(n^3\right)$} \end{axis} \end{tikzpicture} \end{document} - - - diff --git a/buch/papers/multiplikation/images/x.pdf b/buch/papers/multiplikation/images/x.pdf new file mode 100644 index 0000000..da4956f Binary files /dev/null and b/buch/papers/multiplikation/images/x.pdf differ -- cgit v1.2.1 From 6bab37ba5c4d1875f3c99f338a554537219013f6 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Wed, 11 Aug 2021 21:22:29 +0200 Subject: update multiplikation --- buch/papers/multiplikation/images/meas_python.pdf | Bin 26004 -> 22384 bytes buch/papers/multiplikation/images/meas_python.tex | 44 ++++++++++------------ buch/papers/multiplikation/images/x.pdf | Bin 23603 -> 0 bytes buch/papers/multiplikation/loesungsmethoden.tex | 30 ++++++++++----- 4 files changed, 39 insertions(+), 35 deletions(-) delete mode 100644 buch/papers/multiplikation/images/x.pdf (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf index cea4f4b..ab3b14b 100644 Binary files a/buch/papers/multiplikation/images/meas_python.pdf and b/buch/papers/multiplikation/images/meas_python.pdf differ diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex index c8892be..d942f46 100644 --- a/buch/papers/multiplikation/images/meas_python.tex +++ b/buch/papers/multiplikation/images/meas_python.tex @@ -43,8 +43,8 @@ \begin{tikzpicture} \begin{axis}[ xmode=log, ymode=log, -xmin=30, xmax=4100, -ymin=0.00001, ymax=60000, +xmin=30, xmax=4200, +ymin=0.01, ymax=70000, grid=both, major grid style={black!50}, xlabel = data input ($n$), @@ -121,29 +121,23 @@ width=12cm, height=8cm, (2046,6154.18) (4096,46813.3) }; - \addlegendentry{NumPy} - \addplot[ color=blue, - ] coordinates { -% (2,1.83582e-05 ) -% (4,7.86781e-06) -% (8,1.00136e-05) -% (16,5.4121e-05 ) - (32,4.26769e-05) - (64,0.000118494) - (128,0.000244141 ) - (256,0.000695705 ) - (512,0.00221705 ) - (1024,0.0188088 ) -(2046,0.215739) -(4096,1.49159) - }; - \addplot [ - domain= 1:5000, - samples=100, - color=yellow, - ] - {(x-1000)^3}; - \addlegendentry{$\mathcal{O}\left(n^3\right)$} +% \addlegendentry{NumPy} +% \addplot[ color=blue, +% ] coordinates { +% % (2,1.83582e-05 ) +% % (4,7.86781e-06) +% % (8,1.00136e-05) +% % (16,5.4121e-05 ) +% (32,4.26769e-05) +% (64,0.000118494) +% (128,0.000244141 ) +% (256,0.000695705 ) +% (512,0.00221705 ) +% (1024,0.0188088 ) +% (2046,0.215739) +% (4096,1.49159) +% }; + \end{axis} \end{tikzpicture} diff --git a/buch/papers/multiplikation/images/x.pdf b/buch/papers/multiplikation/images/x.pdf deleted file mode 100644 index da4956f..0000000 Binary files a/buch/papers/multiplikation/images/x.pdf and /dev/null differ diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 464085d..be8c2d4 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -389,6 +389,14 @@ Folgende Algorithmen wurden jeweils in \texttt{C} und \texttt{Python} implementi Der Code kann im zum Buch gehörigem \textit{GitHub} \footnote{\url{https://github.com/AndreasFMueller/SeminarMatrizen.git}} Repository gefunden werden. Anzumerken ist, dass die Matrizenmultiplikation von \texttt{NumPy} als einzige Implementation Multiprocessing und Multithreading verwendet, dies f\"uhrt zu den tiefen Messzeiten. In Abbildung \ref{multiplikation:fig:python} und Abbildung \ref{multiplikation:fig:c_meas_4096} sind de Messresultate grafisch dargestellt. Die selben Messresultate sind tabellarisch in Tabelle \ref{multiplikation:tab:messung_Python} und Tabelle \ref{multiplikation:tab:messung_C} ersichtlich. + +In der Messung mit der Programmiersprache \texttt{C}, kann ein typischer Cache-Effekt beobachtet wer- +den. Bei den Algorithmen von Winograd und der Standardmethode hat bei einer Gr\"osse von +n = 2048 wohl eine Zeile der Matrix nicht an einer Cache Speicherstelle platzt. Diese beiden Al- +Algorithmen sind die Einzigen, welche \texttt{for}-Schleifen über die ganze Breite der Matrizen verwenden. +Dies führt dazu, dass ganze Zeilen zwischengespeichert werden müssen. Bei den anderen Algorith- +men ist dies nicht der Fall. + Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{multiplikation:tab:pc_config} aufgelistet. @@ -400,14 +408,15 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{BLAS (\textit{s})} \\ \hline \multicolumn{6}{c}{} \\ - \textbf{32} & 0.000081 &0.000594 & 0.00047& 0.00010 & 0.000022 \\ - \textbf{64} & 0.00065 & 0.0042& 0.0033& 0.00065& 0.00017 \\ - \textbf{128} & 0.0055 & 0.036& 0.024& 0.0052 & 0.0012 \\ - \textbf{256} & 0.054 & 0.32 & 0.17 & 0.057& 0.010 \\ - \textbf{512} & 0.48 & 2.61 & 1.20 & 0.51 & 0.074\\ - \textbf{1024} & 4.16 & 19.92& 8.45 & 4.53 & 0.704 \\ - \textbf{2048} & 125.90 & 159.33& 59.26 & 130.62 & 6.84 \\ - \textbf{4096} & 1111.31 & 1147.10& 414.64 & 1179.26 & 55.84\\ + \textbf{32} & 0.000089 & 0.000594 & 0.0005 & 0.00008 & 0.000021 \\ + \textbf{64} & 0.00069 & 0.0044 & 0.0036 & 0.00064 & 0.00018 \\ + \textbf{128} & 0.0057 & 0.035 & 0.025 & 0.0052 & 0.0012 \\ + \textbf{256} & 0.052 & 0.29 & 0.178 & 0.053 & 0.0096 \\ + \textbf{512} & 0.51 & 2.22 & 1.25 & 0.55 & 0.077 \\ + \textbf{1024} & 4.50 & 17.65 & 8.83 & 4.67 & 0.764 \\ + \textbf{2048} & 129.28 & 141.61 & 61.901 & 136.67 & 7.63 \\ + \textbf{4096} & 1111.31 & 1147.10 & 414.64 & 1179.26 & 55.84 \\ + \textbf{8192} & 9376.17 & 9606.40 & 3014.23 & 10071.51& 478.42 \\ \multicolumn{6}{c}{} \\ \hline \hline @@ -427,13 +436,14 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{\texttt{NumPy}(\textit{s})} \\ \hline \multicolumn{6}{c}{} \\ - \textbf{32} & 0.0240 &0.0271 & 0.04852& 0.01871 & 4.26e-05 \\ + \textbf{32} & 0.0240 &0.0271 & 0.04852& 0.01871 & 0.0000426 \\ \textbf{64} & 0.186 & 0.265& 0.2204& 0.1530& 0.000118 \\ \textbf{128} & 1.563 & 1.777& 1.447& 1.1947 & 0.000244 \\ \textbf{256} & 11.006 & 13.27 & 9.938 & 8.298& 0.000695 \\ \textbf{512} & 85.476 & 105.397 & 63.961 & 68.36 & 0.00221\\ \textbf{1024} & 750.757 & 847.321& 461.494 & 537.374 & 0.0188 \\ - \textbf{4096} & - & - & - & - & 1.633 \\ + \textbf{2048} & 6154.18 & 7375.93& 3860.57 & 4884.61 & 0.215 \\ + \textbf{4096} & 46813.3 & 58466 & 22904.3 & 43597.1 & 1.49 \\ \multicolumn{6}{c}{} \\ \hline \hline -- cgit v1.2.1 From 2b6637fb99a4aaebadc739b323b0ae440eb805e7 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Wed, 11 Aug 2021 21:31:37 +0200 Subject: typo --- buch/papers/multiplikation/loesungsmethoden.tex | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index be8c2d4..0760719 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -265,7 +265,7 @@ N=2n, \quad T = n^2 \\ \end{equation} sein, damit man etwas einspart. Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden. -Falls $m=n=p$ werden $\frac{n^3}/{2}$ Multiplikationen benötigt. +Falls $m=n=p$ werden $\frac{n^3}{2}$ Multiplikationen benötigt. Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \rightarrow \infty$ können Konstanten vernachlässigt werden und somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}(n^3 )$. \begin{algorithm}\footnotesize\caption{Winograds Matrizenmultiplikation} @@ -391,11 +391,11 @@ Anzumerken ist, dass die Matrizenmultiplikation von \texttt{NumPy} als einzige I In Abbildung \ref{multiplikation:fig:python} und Abbildung \ref{multiplikation:fig:c_meas_4096} sind de Messresultate grafisch dargestellt. Die selben Messresultate sind tabellarisch in Tabelle \ref{multiplikation:tab:messung_Python} und Tabelle \ref{multiplikation:tab:messung_C} ersichtlich. In der Messung mit der Programmiersprache \texttt{C}, kann ein typischer Cache-Effekt beobachtet wer- -den. Bei den Algorithmen von Winograd und der Standardmethode hat bei einer Gr\"osse von -n = 2048 wohl eine Zeile der Matrix nicht an einer Cache Speicherstelle platzt. Diese beiden Al- -Algorithmen sind die Einzigen, welche \texttt{for}-Schleifen über die ganze Breite der Matrizen verwenden. -Dies führt dazu, dass ganze Zeilen zwischengespeichert werden müssen. Bei den anderen Algorith- -men ist dies nicht der Fall. +den. +Bei den Algorithmen von Winograd und der Standardmethode hat bei einer Matrizengrösse von $n = 2048$ wohl eine Zeile der Matrize nicht an einer Cache Speicherstelle platzt. +Diese beiden Algorithmen sind die Einzigen, welche \texttt{for}-Schleifen über die ganze Breite der Matrizen verwenden. +Dies führt dazu, dass ganze Zeilen zwischengespeichert werden müssen. +Bei den anderen Algorithmen ist dies nicht der Fall. Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{multiplikation:tab:pc_config} aufgelistet. -- cgit v1.2.1 From 713ef9bbfa79eb2ae2b821da26271cdeea58834c Mon Sep 17 00:00:00 2001 From: Nunigan Date: Tue, 17 Aug 2021 07:41:22 +0200 Subject: update --- buch/papers/multiplikation/loesungsmethoden.tex | 54 ++++++++++++++----------- buch/papers/multiplikation/problemstellung.tex | 30 +++++++------- 2 files changed, 46 insertions(+), 38 deletions(-) (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 0760719..ac7cb85 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -11,10 +11,9 @@ In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultip \subsection{Standard Algorithmus} -Die Standardmethode kann im Algorithmus \ref{multiplikation:alg:smm} entnommen werden. +Die Standardmethode kann im Algorithmus \ref{multiplikation:alg:smm} gsehen 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}\footnotesize\caption{Matrizenmultiplikation} \label{multiplikation:alg:smm} \setlength{\lineskip}{7pt} @@ -38,7 +37,6 @@ 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)$ \subsubsection{Divide and Conquer Methode} @@ -131,7 +129,7 @@ Die sieben grundlegenden Terme \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 Bl\"ocke +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}} \\ @@ -233,29 +231,30 @@ Das Skalarprodukt ist nun geben mit \end{cases} \end{equation} 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. +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 Gleichung \eqref{multiplikation:eq:skalar} benötigt man $Tn$ Multiplikationen. -Im Vergleich mit der neuen Methode -\begin{equation} - \begin{split}\label{multiplikation:eq:eff} - N\lfloor n/2 \rfloor + T\lfloor (n+1)/2 \rfloor \leq Tn \\ - \approx \frac{Nn}{2} + \frac{Tn}{2} \leq Tn \\ - \frac{Nn}{2} \leq \frac{Tn}{2} \\ - N \leq T +Für die ursprüngliche Gleichung \eqref{multiplikation:eq:skalar} für das Skalarprodukt benötigt man $Tn$ Multiplikationen. +Im Vergleich mit der Methode von Winograd, +%\begin{equation}\label{multiplikation:eq:eff} + \begin{align}\label{multiplikation:eq:eff} + \begin{split} + N\lfloor n/2 \rfloor + T\lfloor (n+1)/2 \rfloor &\leq Tn \\ + \approx \frac{Nn}{2} + \frac{Tn}{2} &\leq Tn \\ + \frac{Nn}{2} &\leq \frac{Tn}{2} \\ + N &\leq T, \end{split} -\end{equation} -spart man etwas, falls $N\leq T$. +\end{align} +%\end{equation} +werden für die berechnung des Skalarproduktes weniger Multiplikationen benötigt, falls $N\leq T$. 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 Standardmethode nur die H\"alfte ist. -Mit dem gleichen Ansatz wie in der Gleichung \ref{multiplikation:eq:eff} aber mit quadratischen Matrizen, muss +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{equation} \begin{split} N=2n, \quad T = n^2 \\ @@ -265,7 +264,7 @@ N=2n, \quad T = n^2 \\ \end{equation} sein, damit man etwas einspart. Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden. -Falls $m=n=p$ werden $\frac{n^3}{2}$ Multiplikationen benötigt. +Falls $m=n=p$, werden $\frac{n^3}{2}$ Multiplikationen benötigt. Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \rightarrow \infty$ können Konstanten vernachlässigt werden und somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}(n^3 )$. \begin{algorithm}\footnotesize\caption{Winograds Matrizenmultiplikation} @@ -390,9 +389,14 @@ Der Code kann im zum Buch gehörigem \textit{GitHub} \footnote{\url{https://gith Anzumerken ist, dass die Matrizenmultiplikation von \texttt{NumPy} als einzige Implementation Multiprocessing und Multithreading verwendet, dies f\"uhrt zu den tiefen Messzeiten. In Abbildung \ref{multiplikation:fig:python} und Abbildung \ref{multiplikation:fig:c_meas_4096} sind de Messresultate grafisch dargestellt. Die selben Messresultate sind tabellarisch in Tabelle \ref{multiplikation:tab:messung_Python} und Tabelle \ref{multiplikation:tab:messung_C} ersichtlich. -In der Messung mit der Programmiersprache \texttt{C}, kann ein typischer Cache-Effekt beobachtet wer- +Die gezeigten Algorithmen haben alle eine Laufzeit der Form $\mathcal{O}(n^k) $. +Bei einer 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 beö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 Matrize nicht an einer Cache Speicherstelle platzt. +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. @@ -433,7 +437,7 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \begin{tabular}{l 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{\texttt{NumPy}(\textit{s})} \\ + \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} & 0.0240 &0.0271 & 0.04852& 0.01871 & 0.0000426 \\ @@ -490,10 +494,12 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \section{Fazit} \rhead{Fazit} -Wie man im Abschnitt \ref{multiplikation:section:Implementation} sehen kann, sind die gezeigten Algorithmen trotz den theoretisch geringeren Zeitkomplexitäten, den Implementationen der numerischen Bibliotheken klar unterlegen. +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)}. -Sobald sehr grosse Matrizen multipliziert werden müssen und eine Addition in weniger Taktzyklen als eine Multiplikation durchführt werden kann, können die gezeigten Algorithmen von Vorteil sein. +Der Overhead der gezeigten Alogorithmen ist in allen Fällen grösser als bei der Standardmethode (z.B. sieben rekursive Aufrufe gegenüber drei \texttt{for}-Schleifen). +Um diesem entegenzuwirken 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 Algortihmen von Strassen oder Winograd zu einer Senkung der Laufzeit führen. diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index c8ba274..a98d0e9 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -7,15 +7,15 @@ \rhead{Problemstellung} Wegen 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. -Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der Standard Algorithmus l\"osen. +Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der Standardalgorithmus l\"osen. \subsection{Big $\mathcal{O}$ Notation} \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$. -% Es gibt eine Konstante $K$ derart, dass $f(x) \le K g(x)$ für $x\to\infty$ -Als Beispiel: benötigt eine Funktion $g$ $\mathcal{O} (n^2 )$ Multiplikationen, so wächst $f$ mit $\mathcal{O} (n+ n^2 )$ nicht wesentlich schneller falls $x\to\infty$. -Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet: +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 @@ -26,6 +26,8 @@ Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet: \item usw. \end{itemize} +Konstanten werden nicht beachtet, eine Laufzeit von $\mathcal{O}(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 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. @@ -50,7 +52,7 @@ Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomple \State \end{algorithmic} \end{algorithm} - \end{minipage} + \end{minipage} & \begin{minipage}{0.48\textwidth} \begin{algorithm}[H]\footnotesize\caption{} @@ -64,13 +66,13 @@ Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomple \EndFunction \end{algorithmic} \end{algorithm} - + \end{minipage} \end{tabular} \end{table} \begin{table} - \begin{tabular}[t]{ll} + \begin{tabular}[t]{ll} \begin{minipage}{0.48\textwidth} \begin{algorithm}[H]\footnotesize\caption{} \setlength{\lineskip}{7pt} @@ -81,15 +83,15 @@ Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomple \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} + \end{minipage} & \begin{minipage}{0.48\textwidth} \begin{algorithm}[H]\footnotesize\caption{} @@ -112,10 +114,10 @@ Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomple \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. -Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden. Da $a$ und $b$ Skalare sind, hat keine Gr\"osse $n$ einen Einfluss auf die Laufzeit. - -Konstanten werden nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$. +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)$. \paragraph{Linearer Algorithmus} @@ -132,6 +134,6 @@ Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhrt \begin{figure} \center \includegraphics[]{papers/multiplikation/images/bigo} - \caption{Verschiedene Laufzeiten} + \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} -- cgit v1.2.1 From b8b22fc376e14491a556daeacb5e8e5d216a8251 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Thu, 19 Aug 2021 06:08:48 +0200 Subject: update --- buch/papers/multiplikation/einlteung.tex | 2 +- buch/papers/multiplikation/images/meas_c.pdf | Bin 24028 -> 23943 bytes buch/papers/multiplikation/images/meas_c.tex | 6 +++--- buch/papers/multiplikation/images/meas_python.pdf | Bin 22384 -> 22379 bytes buch/papers/multiplikation/images/meas_python.tex | 2 +- buch/papers/multiplikation/problemstellung.tex | 1 - 6 files changed, 5 insertions(+), 6 deletions(-) (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index 9f1cb04..fab23ef 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -47,6 +47,6 @@ der einzelnen Terme geschrieben werden. \begin{figure} \center \includegraphics[]{papers/multiplikation/images/mm_visualisation} - \caption{Matrizen Multiplikation} + \caption{Grafische illustration der Matrizenmultiplikation} \label{multiplikation:fig:mm_viz} \end{figure} diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf index faf347e..6e0e2cc 100644 Binary files a/buch/papers/multiplikation/images/meas_c.pdf and b/buch/papers/multiplikation/images/meas_c.pdf differ diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex index fe2bd2f..a2a0505 100644 --- a/buch/papers/multiplikation/images/meas_c.tex +++ b/buch/papers/multiplikation/images/meas_c.tex @@ -47,7 +47,7 @@ xmin=30, xmax=10000, ymin=1e-5, ymax=2e4, grid=both, major grid style={black!50}, -xlabel = data Input ($n$), +xlabel = data input ($n$), ylabel = {time ($s$)}, legend pos=north west, very thick, @@ -56,7 +56,7 @@ width=12cm, height=8cm, log basis x={10} ] \addlegendentry{Winograd} -\addplot[ color=purple, +\addplot[ color=blue, error bars/.cd, y dir=both, y explicit, ] coordinates { %(2,1e-07) @@ -127,7 +127,7 @@ width=12cm, height=8cm, (8192,9376.173434) }; \addlegendentry{BLAS} -\addplot[ color=blue, +\addplot[ color=purple, ] coordinates { %(2,1e-07) %(4,0.0) diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf index ab3b14b..9d7730d 100644 Binary files a/buch/papers/multiplikation/images/meas_python.pdf and b/buch/papers/multiplikation/images/meas_python.pdf differ diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex index d942f46..a30d342 100644 --- a/buch/papers/multiplikation/images/meas_python.tex +++ b/buch/papers/multiplikation/images/meas_python.tex @@ -56,7 +56,7 @@ width=12cm, height=8cm, log basis x={10} ] \addlegendentry{Winograd} -\addplot[ color=purple, +\addplot[ color=blue, ] coordinates { % (2, 2.7895e-05 ) % (4, 0.000104904) diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index a98d0e9..b8c4142 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -27,7 +27,6 @@ Vereinfacht werden f\"ur Algorithmen die folgende Sprechweise verwendet: \end{itemize} Konstanten werden nicht beachtet, eine Laufzeit von $\mathcal{O}(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 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. -- cgit v1.2.1 From 0c073915585da20db52db82958d50e159559e5c8 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Fri, 20 Aug 2021 08:50:43 +0200 Subject: update --- buch/papers/multiplikation/einlteung.tex | 8 +- buch/papers/multiplikation/images/bigo.pdf | Bin 28372 -> 28312 bytes buch/papers/multiplikation/images/bigo.tex | 1 + buch/papers/multiplikation/images/meas_c.pdf | Bin 23943 -> 23887 bytes buch/papers/multiplikation/images/meas_c.tex | 3 +- buch/papers/multiplikation/images/meas_python.pdf | Bin 22379 -> 22337 bytes buch/papers/multiplikation/images/meas_python.tex | 3 +- buch/papers/multiplikation/images/strassen.pdf | Bin 19970 -> 20700 bytes buch/papers/multiplikation/images/strassen.tex | 127 +++++++++++++++++++--- buch/papers/multiplikation/loesungsmethoden.tex | 62 +++++------ buch/papers/multiplikation/main.tex | 4 +- buch/papers/multiplikation/problemstellung.tex | 11 +- 12 files changed, 156 insertions(+), 63 deletions(-) (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index fab23ef..2cfbe21 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -3,10 +3,10 @@ % % (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 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 @@ -34,7 +34,7 @@ C_{11} & C_{12}\\ C_{21} & C_{22} \end{bmatrix} \end{equation} -explizt als Gleichung +explizt als Gleichungen \begin{equation} \label{multiplikation:eq:MM_exp} \begin{split} C_{11} &= A_{11} \cdot B_{11} + A_{12} \cdot B_{21}\\ diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf index 8a53398..2519553 100644 Binary files a/buch/papers/multiplikation/images/bigo.pdf and b/buch/papers/multiplikation/images/bigo.pdf differ diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex index 9ee3a68..63fd0fd 100644 --- a/buch/papers/multiplikation/images/bigo.tex +++ b/buch/papers/multiplikation/images/bigo.tex @@ -54,6 +54,7 @@ xticklabels=\empty, scale only axis=true, width=12cm, height=8cm, + legend cell align={left} ] \addplot [ domain= 1:5000, diff --git a/buch/papers/multiplikation/images/meas_c.pdf b/buch/papers/multiplikation/images/meas_c.pdf index 6e0e2cc..521151e 100644 Binary files a/buch/papers/multiplikation/images/meas_c.pdf and b/buch/papers/multiplikation/images/meas_c.pdf differ diff --git a/buch/papers/multiplikation/images/meas_c.tex b/buch/papers/multiplikation/images/meas_c.tex index a2a0505..12d3527 100644 --- a/buch/papers/multiplikation/images/meas_c.tex +++ b/buch/papers/multiplikation/images/meas_c.tex @@ -53,7 +53,8 @@ legend pos=north west, very thick, scale only axis=true, width=12cm, height=8cm, - log basis x={10} + log basis x={10}, + legend cell align={left} ] \addlegendentry{Winograd} \addplot[ color=blue, diff --git a/buch/papers/multiplikation/images/meas_python.pdf b/buch/papers/multiplikation/images/meas_python.pdf index 9d7730d..fe89773 100644 Binary files a/buch/papers/multiplikation/images/meas_python.pdf and b/buch/papers/multiplikation/images/meas_python.pdf differ diff --git a/buch/papers/multiplikation/images/meas_python.tex b/buch/papers/multiplikation/images/meas_python.tex index a30d342..ad43cf6 100644 --- a/buch/papers/multiplikation/images/meas_python.tex +++ b/buch/papers/multiplikation/images/meas_python.tex @@ -53,7 +53,8 @@ legend pos=north west, very thick, scale only axis=true, width=12cm, height=8cm, - log basis x={10} + log basis x={10}, + legend cell align={left} ] \addlegendentry{Winograd} \addplot[ color=blue, diff --git a/buch/papers/multiplikation/images/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf index a30fdaa..6d81ff5 100644 Binary files a/buch/papers/multiplikation/images/strassen.pdf and b/buch/papers/multiplikation/images/strassen.pdf differ diff --git a/buch/papers/multiplikation/images/strassen.tex b/buch/papers/multiplikation/images/strassen.tex index 5cf39b4..2e3b727 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, @@ -80,7 +80,7 @@ \node at (-3,-15) {$C_{21}=$} ; \node at (-3,-10) {$C_{12}=$} ; \node at (-3,-5) {$C_{11}=$} ; - + \node at (5,-2) {P}; \node at (10,-2) {Q}; \node at (15,-2) {R}; @@ -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 ac7cb85..90cb9ff 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -7,12 +7,12 @@ \section{Algorithmen} \rhead{Algorithmen} -In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultiplikation vorgestellt, auch werden Bibliotheken 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} -Die Standardmethode kann im Algorithmus \ref{multiplikation:alg:smm} gsehen werden. -Hierf\"ur wurde die Gleichung \eqref{multiplikation:eq:MM} direkt implementiert. +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} @@ -37,7 +37,7 @@ 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} @@ -65,8 +65,8 @@ Das Matrizen Produkt \mathbf{C}_{21} & \mathbf{C}_{22} \end{bmatrix}, \end{equation} -\begin{equation} -\mathbf{C}_{ij} = \sum_{k=1}^{2n} \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}, f\"ur die Multiplikation der Untermatrize $\mathbf{A}_{ik}$ und $\mathbf{B}_{kj}$ wird die Matrizenmultiplikation verwendet. @@ -105,11 +105,11 @@ Der rekursive Aufruf wird bis zu der Gr\"osse der Matrizen von $N = 2 \times 2$ 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 +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) = 8 \cdot \mathcal{T} \left(\frac{n}{2}\right ) + n^2 = \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. @@ -187,7 +187,7 @@ der Matrix $\mathbf{C}$ gebraucht. 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, \dotsb, V}$. +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 @@ -246,7 +246,7 @@ Im Vergleich mit der Methode von Winograd, \end{split} \end{align} %\end{equation} -werden für die berechnung des Skalarproduktes weniger Multiplikationen benötigt, falls $N\leq T$. +werden für die Berechnung des Skalarproduktes weniger Multiplikationen benötigt, falls $N\leq T$. 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} @@ -266,7 +266,7 @@ sein, damit man etwas einspart. Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden. Falls $m=n=p$, werden $\frac{n^3}{2}$ Multiplikationen benötigt. Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \rightarrow \infty$ können Konstanten vernachlässigt werden und - somit entsteht für diesen Algorithmus wieder die Ursprüngliche Laufzeit von $\mathcal{O}(n^3 )$. + 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} @@ -406,21 +406,21 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \begin{table} \begin{center} - \begin{tabular}{l l l l l l} + \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} & 0.000089 & 0.000594 & 0.0005 & 0.00008 & 0.000021 \\ - \textbf{64} & 0.00069 & 0.0044 & 0.0036 & 0.00064 & 0.00018 \\ - \textbf{128} & 0.0057 & 0.035 & 0.025 & 0.0052 & 0.0012 \\ - \textbf{256} & 0.052 & 0.29 & 0.178 & 0.053 & 0.0096 \\ - \textbf{512} & 0.51 & 2.22 & 1.25 & 0.55 & 0.077 \\ - \textbf{1024} & 4.50 & 17.65 & 8.83 & 4.67 & 0.764 \\ - \textbf{2048} & 129.28 & 141.61 & 61.901 & 136.67 & 7.63 \\ - \textbf{4096} & 1111.31 & 1147.10 & 414.64 & 1179.26 & 55.84 \\ - \textbf{8192} & 9376.17 & 9606.40 & 3014.23 & 10071.51& 478.42 \\ + \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 @@ -434,20 +434,20 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \begin{table} \begin{center} - \begin{tabular}{l l l l l l} + \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} & 0.0240 &0.0271 & 0.04852& 0.01871 & 0.0000426 \\ - \textbf{64} & 0.186 & 0.265& 0.2204& 0.1530& 0.000118 \\ - \textbf{128} & 1.563 & 1.777& 1.447& 1.1947 & 0.000244 \\ - \textbf{256} & 11.006 & 13.27 & 9.938 & 8.298& 0.000695 \\ - \textbf{512} & 85.476 & 105.397 & 63.961 & 68.36 & 0.00221\\ - \textbf{1024} & 750.757 & 847.321& 461.494 & 537.374 & 0.0188 \\ - \textbf{2048} & 6154.18 & 7375.93& 3860.57 & 4884.61 & 0.215 \\ - \textbf{4096} & 46813.3 & 58466 & 22904.3 & 43597.1 & 1.49 \\ + \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 diff --git a/buch/papers/multiplikation/main.tex b/buch/papers/multiplikation/main.tex index fb1908e..ca93e92 100755 --- a/buch/papers/multiplikation/main.tex +++ b/buch/papers/multiplikation/main.tex @@ -26,8 +26,8 @@ backgroundcolor=\color{backcolour} } -\chapter{Schnelle Matrizen Multiplikation\label{chapter:multiplikation}} -\lhead{FMM} +\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 b8c4142..a9aeda0 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -3,13 +3,12 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Problemstellung} +\section{Laufzeiten von Algorithmen} \rhead{Problemstellung} -Wegen der breiten Anwendung der Matrizenmultiplikation ist eine effiziente L\"osung dieser Operation von grosser Bedeutung. +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. -\subsection{Big $\mathcal{O}$ Notation} \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$. @@ -26,15 +25,15 @@ Vereinfacht werden f\"ur Algorithmen die folgende Sprechweise verwendet: \item usw. \end{itemize} -Konstanten werden nicht beachtet, eine Laufzeit von $\mathcal{O}(4n^2)$ führt, falls $n \rightarrow \infty$ zu $\mathcal{O}(n^2)$. +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 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. +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 abbgebildet. \subsubsection{Beispiel Algorithmen} -Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen. +Es folgen einige Beispiele von Algorithmen, welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen. \begin{table}[t] -- cgit v1.2.1 From 27bef650fb02f20f0f0a0980e810363583115cd9 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Sat, 21 Aug 2021 14:54:03 +0200 Subject: update multiplikation --- buch/papers/multiplikation/einlteung.tex | 4 +- buch/papers/multiplikation/images/strassen.pdf | Bin 20700 -> 22262 bytes buch/papers/multiplikation/images/strassen.tex | 24 +++++------ buch/papers/multiplikation/loesungsmethoden.tex | 52 +++++++++++------------- buch/papers/multiplikation/problemstellung.tex | 2 +- 5 files changed, 39 insertions(+), 43 deletions(-) (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index 2cfbe21..21fa9df 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -14,7 +14,7 @@ $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 $\mathbf{AB}=\mathbf{C}$ wie in Abbildung \ref{multiplikation:fig:mm_viz} visualisiert werden. @@ -47,6 +47,6 @@ der einzelnen Terme geschrieben werden. \begin{figure} \center \includegraphics[]{papers/multiplikation/images/mm_visualisation} - \caption{Grafische illustration der Matrizenmultiplikation} + \caption{Grafische Illustration der Matrizenmultiplikation} \label{multiplikation:fig:mm_viz} \end{figure} diff --git a/buch/papers/multiplikation/images/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf index 6d81ff5..d150125 100644 Binary files a/buch/papers/multiplikation/images/strassen.pdf and b/buch/papers/multiplikation/images/strassen.pdf differ diff --git a/buch/papers/multiplikation/images/strassen.tex b/buch/papers/multiplikation/images/strassen.tex index 2e3b727..b51a9d5 100644 --- a/buch/papers/multiplikation/images/strassen.tex +++ b/buch/papers/multiplikation/images/strassen.tex @@ -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) {P}; - \node at (10,-2) {Q}; - \node at (15,-2) {R}; - \node at (20,-2) {S}; - \node at (25,-2) {T}; - \node at (30,-2) {U}; - \node at (35,-2) {V}; + \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}$}; } diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 90cb9ff..51872f5 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -192,7 +192,7 @@ 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{Strassens 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} @@ -235,18 +235,14 @@ Angenommen man hat $N$ Vektoren, mit welchen man $T$ Skalarprodukte berechnen m\ 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. -Im Vergleich mit der Methode von Winograd, -%\begin{equation}\label{multiplikation:eq:eff} - \begin{align}\label{multiplikation:eq:eff} - \begin{split} - N\lfloor n/2 \rfloor + T\lfloor (n+1)/2 \rfloor &\leq Tn \\ - \approx \frac{Nn}{2} + \frac{Tn}{2} &\leq Tn \\ - \frac{Nn}{2} &\leq \frac{Tn}{2} \\ - N &\leq T, -\end{split} -\end{align} -%\end{equation} -werden für die Berechnung des Skalarproduktes weniger Multiplikationen benötigt, falls $N\leq T$. +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} @@ -255,13 +251,13 @@ Dies f\"uhrt zu 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 Standardmethode nur die H\"alfte ist. Mit dem gleichen Ansatz wie in der Gleichung \eqref{multiplikation:eq:eff} aber mit quadratischen Matrizen, muss -\begin{equation} +\begin{align} \begin{split} -N=2n, \quad T = n^2 \\ - 2n \leq n^2 \\ - 2 \leq n +N=2n, &\quad T = n^2 \\ + 2n &\leq n^2 \\ + 2 &\leq n \end{split} -\end{equation} +\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. @@ -322,7 +318,7 @@ Im Abschnitt \ref{muliplikation:sec:bigo} wurde bereits erläutert: falls $n \ri \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}. +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. @@ -390,9 +386,9 @@ Anzumerken ist, dass die Matrizenmultiplikation von \texttt{NumPy} als einzige I In Abbildung \ref{multiplikation:fig:python} und Abbildung \ref{multiplikation:fig:c_meas_4096} sind de Messresultate grafisch dargestellt. Die selben Messresultate sind tabellarisch in Tabelle \ref{multiplikation:tab:messung_Python} und Tabelle \ref{multiplikation:tab:messung_C} ersichtlich. Die gezeigten Algorithmen haben alle eine Laufzeit der Form $\mathcal{O}(n^k) $. -Bei einer logarithmischen Darstellung unterscheiden sich diese in Geraden mit unterschiedlichen Steigungen. +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 beötigte Overhead der Algorithmen zeigt sich in unterschiedlichen $y$-Achsenschnittpunkte. +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. @@ -426,7 +422,7 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \hline \end{tabular} \end{center} - \caption{Messresultate \texttt{C}} + \caption{Laufzeiten der verschieden Algorithmen in der Programmiersprache \texttt{C}} \label{multiplikation:tab:messung_C} \end{table} @@ -453,7 +449,7 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \hline \end{tabular} \end{center} - \caption{Messresultate \texttt{Python}} + \caption{Laufzeiten der verschieden Algorithmen in der Skriptsprache \texttt{Python}} \label{multiplikation:tab:messung_Python} \end{table} @@ -479,7 +475,7 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \begin{figure} \center \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_c} - \caption{Messresultate mit der Programmiersprache \texttt{C}} + \caption{Doppelt logarithmisch dargestellte Laufzeiten, der verschieden Algorithmen, in der Programmiersprache \texttt{C}} \label{multiplikation:fig:c_meas_4096} \end{figure} @@ -487,7 +483,7 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \begin{figure} \center \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_python} - \caption{Messresultate mit der Programmiersprache \texttt{Python}} + \caption{Doppelt logarithmisch dargestellte Laufzeiten, der verschieden Algorithmen, in der Skriptsprache \texttt{Python}} \label{multiplikation:fig:python} \end{figure} @@ -500,6 +496,6 @@ Ein optimierter Speicherzugriff hat einen weitaus grösseren Einfluss auf die La 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 Alogorithmen ist in allen Fällen grösser als bei der Standardmethode (z.B. sieben rekursive Aufrufe gegenüber drei \texttt{for}-Schleifen). -Um diesem entegenzuwirken 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 Algortihmen von Strassen oder Winograd zu einer Senkung der Laufzeit führen. +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/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index a9aeda0..604ea36 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -27,7 +27,7 @@ Vereinfacht werden f\"ur Algorithmen die folgende Sprechweise verwendet: 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 abbgebildet. +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. -- cgit v1.2.1 From bf1d8fd6cf8b1a40bb0a621fda1070ddefba277b Mon Sep 17 00:00:00 2001 From: Nunigan Date: Mon, 23 Aug 2021 11:00:26 +0200 Subject: update --- buch/papers/multiplikation/einlteung.tex | 1 - buch/papers/multiplikation/loesungsmethoden.tex | 37 ++++++++++++++----------- buch/papers/multiplikation/main.tex | 2 +- buch/papers/multiplikation/problemstellung.tex | 14 +++++----- 4 files changed, 29 insertions(+), 25 deletions(-) (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index 21fa9df..d31e0f7 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -8,7 +8,6 @@ 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 diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 51872f5..8d0c0a8 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -9,7 +9,7 @@ In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultiplikation vorgestellt, auch werden Bibliotheken zur unkomplizierten Verwendung von vordefinierten Algorithmen gezeigt. -\subsection{Standard Algorithmus} +\subsection{Standardalgorithmus} Die Standardmethode ist im Algorithmus \ref{multiplikation:alg:smm} implementiert. Hierf\"ur wurde die Gleichung \eqref{multiplikation:eq:MM} direkt umgesetzt. @@ -48,7 +48,7 @@ Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die 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}$ aufgeteilt. -Das Matrizen Produkt +Das Matrizenprodukt \begin{equation} \mathbf{A}\mathbf{B}= \begin{bmatrix} @@ -63,16 +63,16 @@ Das Matrizen Produkt \begin{bmatrix} \mathbf{C}_{11} & \mathbf{C}_{12}\\ \mathbf{C}_{21} & \mathbf{C}_{22} -\end{bmatrix}, +\end{bmatrix} \end{equation} 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}, f\"ur die Multiplikation der Untermatrize $\mathbf{A}_{ik}$ und $\mathbf{B}_{kj}$ wird die Matrizenmultiplikation verwendet. +ist identisch zu der Gleichung \eqref{multiplikation:eq:MM}, f\"ur die Multiplikation der Untermatrizen $\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. +Die 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}\footnotesize\caption{Divide and Conquer Matrizenmultiplikation} \setlength{\lineskip}{7pt} @@ -189,10 +189,11 @@ Jedes Feld steht f\"ur eine Multiplikation zweier Matrizenelementen von $\mathbf 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. +Graue Felder bedeuten, dass die dazugehörige Spalte nicht für die Berechnung benötigt wird. \begin{figure} \center \includegraphics[width=\linewidth]{papers/multiplikation/images/strassen.pdf} - \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} + \caption{Der Algorithmus von Strassen verwendet Multiplikationen zur Berechnung der sieben Blockmatrizen $\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. Graue Felder werden für die Berechnung von $\mathbf{C}_{il}$ nicht benötigt.} \label{multiplikation:fig:strassen} \end{figure} @@ -340,7 +341,7 @@ Die meisten numerischen Bibliotheken von high-level Skriptsprachen wie \texttt{M \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. +Die \textit{BLAS} sind auf die modernen Computerprozessoren optimiert und k\"onnen dank einer ausgeklügelter Verwendung der Speicherarchitektur zu erheblichen Leistungsoptimierungen f\"uhren. %\subsubsection{General Matrix Multiplication (GEMM)} @@ -436,13 +437,13 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \textbf{n} & \textbf{MM (\textit{s})} & \textbf{MM DC (\textit{s})} & \textbf{Strassen (\textit{s})} & \textbf{Winograd (\textit{s})} & \textbf{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{32} &\phantom{0000}0.0240 & \phantom{0000}0.0271& \phantom{0000}0.04852 & \phantom{0000}0.01871 & 0.0000426 \\ + \textbf{64} &\phantom{0000}0.186 & \phantom{0000}0.265 & \phantom{0000}0.2204 & \phantom{0000}0.1530& 0.000118 \\ + \textbf{128} &\phantom{0000}1.563 & \phantom{0000}1.777 & \phantom{0000}1.447 & \phantom{0000}1.1947 & 0.000244 \\ + \textbf{256} &\phantom{000}11.006 & \phantom{000}13.27 & \phantom{0000}9.938 & \phantom{0000}8.298& 0.000695 \\ + \textbf{512} &\phantom{000}85.476 & \phantom{00}105.397 & \phantom{000}63.961 & \phantom{000}68.360 & 0.00221\\ + \textbf{1024} &\phantom{00}750.757 & \phantom{00}847.321 & \phantom{00}461.494 & \phantom{00}537.374 & 0.0188 \\ + \textbf{2048} &\phantom{0}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 @@ -475,7 +476,9 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \begin{figure} \center \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_c} - \caption{Doppelt logarithmisch dargestellte Laufzeiten, der verschieden Algorithmen, in der Programmiersprache \texttt{C}} + \caption{Doppelt logarithmisch dargestellte Laufzeiten, der verschieden Algorithmen, in der Programmiersprache \texttt{C}. + Die Steigung der Messreihe mit Strassens Algorithmus ist deutlich kleiner als deren der anderen Algorithmen. + Die Messung von Winograd ist beinahe gleich wie die Messung mit der Standardmethode, deshalb ist sie nicht gut sichtbar.} \label{multiplikation:fig:c_meas_4096} \end{figure} @@ -483,7 +486,9 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \begin{figure} \center \includegraphics[width=\linewidth]{papers/multiplikation/images/meas_python} - \caption{Doppelt logarithmisch dargestellte Laufzeiten, der verschieden Algorithmen, in der Skriptsprache \texttt{Python}} + \caption{Doppelt logarithmisch dargestellte Laufzeiten, der verschieden Algorithmen, in der Skriptsprache \texttt{Python}. + Die Steigung der Messreihe mit Strassens Algorithmus ist deutlich kleiner als deren der anderen Algorithmen. +} \label{multiplikation:fig:python} \end{figure} diff --git a/buch/papers/multiplikation/main.tex b/buch/papers/multiplikation/main.tex index ca93e92..4a23109 100755 --- a/buch/papers/multiplikation/main.tex +++ b/buch/papers/multiplikation/main.tex @@ -27,7 +27,7 @@ } \chapter{Schnelle Matrizenmultiplikation\label{chapter:multiplikation}} -\lhead{MM} +\lhead{Schnelle Matrizenmultiplikation} \begin{refsection} \chapterauthor{Michael Schmid} diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index 604ea36..b3e0ab3 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -4,17 +4,17 @@ % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % \section{Laufzeiten von Algorithmen} -\rhead{Problemstellung} +\rhead{Laufzeiten von Algorithmen} 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}. +Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Relation 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: +Vereinfacht werden f\"ur Algorithmen die folgende Sprechweisen 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 @@ -25,13 +25,13 @@ Vereinfacht werden f\"ur Algorithmen die folgende Sprechweise verwendet: \item usw. \end{itemize} -Konstanten werden nicht beachtet, eine Laufzeit von $4n^2$ führt, falls $n \rightarrow \infty$ zu $\mathcal{O}(n^2)$. +Konstanten werden nicht beachtet, eine Laufzeit von $4n^2$ führt, für $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. -\subsubsection{Beispiel Algorithmen} +\subsubsection{Beispielalgorithmen} Es folgen einige Beispiele von Algorithmen, welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen. @@ -115,7 +115,7 @@ Es folgen einige Beispiele von Algorithmen, welche zu einer bestimmten Zeitkompl 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)$. +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)$. \paragraph{Linearer Algorithmus} @@ -132,6 +132,6 @@ Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhrt \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.} + \caption{Laufzeiten von verschiedensten Zeitkomplexitäten. 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 dargestellt.} \label{multiplikation:fig:bigo} \end{figure} -- cgit v1.2.1 From 583925fe5661c68f4ae90712c9d697618933ee6c Mon Sep 17 00:00:00 2001 From: Nunigan Date: Tue, 24 Aug 2021 15:34:33 +0200 Subject: typos --- buch/papers/multiplikation/einlteung.tex | 4 ++-- buch/papers/multiplikation/problemstellung.tex | 20 ++++++++++---------- 2 files changed, 12 insertions(+), 12 deletions(-) (limited to 'buch/papers/multiplikation') diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index d31e0f7..9b03a4e 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -9,8 +9,8 @@ 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 +$n\times p$-Matrix $\mathbf{B}\in M_{n\times p}(\Bbbk)$ haben als Produkt +eine $m\times p$-Matrix $\mathbf{C}=\mathbf{AB}\in M_{m\times p}(\Bbbk)$ mit den Koeffizienten \begin{equation} C_{ij} = \sum_{k=1}^n A_{ik} B_{kj}. diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index b3e0ab3..879b210 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -11,10 +11,10 @@ Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der S \label{muliplikation:sec:bigo} Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Relation 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$. +$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, falls 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 Sprechweisen verwendet: +Vereinfacht werden f\"ur Algorithmen die folgenden Sprechweisen 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 @@ -64,13 +64,7 @@ Es folgen einige Beispiele von Algorithmen, welche zu einer bestimmten Zeitkompl \EndFunction \end{algorithmic} \end{algorithm} - - \end{minipage} - \end{tabular} -\end{table} - -\begin{table} - \begin{tabular}[t]{ll} + \end{minipage} \\ \begin{minipage}{0.48\textwidth} \begin{algorithm}[H]\footnotesize\caption{} \setlength{\lineskip}{7pt} @@ -111,6 +105,12 @@ Es folgen einige Beispiele von Algorithmen, welche zu einer bestimmten Zeitkompl \end{tabular} \end{table} +%\begin{table} +% \begin{tabular}[t]{ll} + +% \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. -- cgit v1.2.1