Skrivet av Greyguy1948:
@Yoshman: Du glömmer minnes-hanteringen. Den tar tid då cachen inte är perfekt. Trådarna ska väl vara 8, 16 och 12?
Men dessa program kör enkeltråd.
Antal trådar är inte relevant. Just applikationer som primärt jobbar med stora matriser är en av rätt få fall där SMT kan ge lägre prestanda. Orsaken till det är just cache, varje tråd får relativt sett halverad cache-storlek.
En av optimeringarna som matrisbiblioteken gör, framförallt MKL (som är lite snabbare än de andra) är att dela upp multiplikationen i flera delmoment som var för sig är tillräckligt litet för att få plats i lokal CPU-cache (L1/L2 på dagens CPUer) till väldigt stor del.
Finns väldigt mycket potentiell parallellism i matrismultiplikation, så är relativt enkelt att skapa en instruktionsström som helt kommer sysselsätta de beräkningsenheter som finns (både Intels och AMDs senare modeller fixar två FMA per cykel, d.v.s två d = a * b +c operationer, perfekt instruktion för matrismultiplikation).
Vidare är matrismultiplikation relativt enkelt att förutsäga minnesaccesserna för om man vet storleken på matriserna och hur de är representerade i minnet (vilket BLAS vet då APIet har krav på detta). Det gör att de håroptimerade matrisbiblioteken kan i god tid lägga ut prefetches så att framtida minnesaccesser finns i cache när det är dags att använda.
Problemet bli därför väldigt cache-snällt och beror betydligt mer på bandbredd mot L3 och RAM än typiska program.
Allt ovan står i rätt stor kontrast till i princip alla program vi normalt kör på vår PC. Där är flaskhalsen ytterst sällan kapaciteten på beräkningsenheterna, flaskhalsen är saker som minnesaccesser (då det här inte alls är lika lätt att gissa framtida accesser), beroenden mellan instruktioner (då väldigt mycket logik består av sekvenser med relativt liten instruktionsparallellism) och liknande.
I praktiken får man vara nöjd om man ser en "IPC" på runt 2,0 x86 instruktioner per cykel utanför micro-benchmarks. Rent teoretiskt kan dagens Intel/AMD CPUer hantera 4-5 x86 instruktioner per cykel, vilket i praktiken bara händer i peak:ar (hög peak-rate ökar dock genomsnittet till viss del, så inte värdelöst med peak långt över vad man får i praktiken).
Skrivet av Alotiat:
Intressant tråd. Är inte jätteinsatt i vare sig OpenBLAS eller matrismultiplikation i C från 1993. Däremot tänkte bara flika in en sak, oavsett teknikaliteter och routine/process-optimeringar:
En vanlig matrismultiplikation A*B mellan matriserna A och B med dimensionerna NxN har en komplexitet på
. Minimum är
. Det kan "bevisas" genom det logiska resonemanget: Varje värde i minst en av matriserna måste läsas minst en gång, eftersom en matris har N^2 element så följer det att O(N^2) är teoretiskt minimum. Var den praktiska gränsen går har ingen ännu visat.
Finns att läsa mer om optimeringar kring matrismultiplikation på matrix multiplication
Om någon vill veta mer så finns en lista på beräkningskomplexitet för matematiska funktioner på wikipedia
Helt rätt, är O(N^3) och inte O(N^2) i normalfallet. Och den praktiska optimerade gränsen är också ett högre än vad jag skrev ovan, d.v.s. O(N^~2,5) för det som matrisbiblioteken använder på stora matriser (på små är det mer effektivt att använda det "normala" sättet).
Rätt uppenbart om man tänker lite på det och än mer uppenbart om man tittar på C-koden som postades och räknar antalet nästlade for-loopar... Får skylla på att jag själv aldrig skrivit matriskod som hanterar mer än 4x4 matriser (homogena koordinater för t.ex. 3D), för den storleken är tidskomplexiteten rätt irrelevant (en SSE/AVX tar en hel rad i en instruktion för 32- reps 64-bitars flyttal om det är 4x4) 🤡
För alla större matriser än så har jag alltid använt Matlab, Octave, NumPy, R eller liknande. Alla dessa använder i botten någon form av BLAS-bibliotek.