Matris-multiplikation i C

Varför just matrismultiplikationer? På min tid körde vi Towers of Hanoi.

Javisst Towers of Hanoi har man nästan alltid kört på datorer. De flesta språk harTowers of Hanoi på rosettacode.org.
Matrismultiplikationer kan man styra beroende på hur cachen ser ut i varje CPU.

Eftersom TS visar ett intresse för matris-multiplikation så rekommenderar jag Virginia Vassilevska Williams algoritm som har tidskomplexiteten O(n^2,373) att jämföra med O(n^3) för "vanlig" matrismultiplikation.

https://en.wikipedia.org/wiki/Copper...grad_algorithm

–

Ja det finns många teoretiska modeller men de tar sällan hänsyn till hur mycket man vinner på att läsa från cache i ställer för från RAM. Så det är väl alltid enklare att prova algoritmen med tex -m -m 16 -m 40 beroende på hur cachen i CPUn ser ut.

Vill man göra matrismultiplikationer idag, 2019. Så använder man fördelaktigt SSE eller AVX instruktioner.

Javisst men inte så stor effekt på alla varianter:
64bit GCC -O3
i7-8700 2000x2000
-n......... 15.5 sek
-t........... 9.5 sek
-b 80..... 8.3 sek
-w 80.....2.3 sek
-m 80.....7.1 sek

GCC -O3 -mavx
-n......... 7.5 sek
-t........... 7.4 sek
-b 80..... 1.7 sek
-w 80.....2.2 sek
-m 80.....2.1 sek
Troligen betydligt större effekt på de som har AVX512 typ Sky Lake X