Prestandan av både seriella och parallella implementationer av matris multiplikation är mycket känslig för minne systemets beteende. Falska delnings- och cachekonflikter gör att traditionella kolumn-store eller rad-store array layouter medför stora variationer i minnessystemets prestanda eftersom matrisstorleken varierar. Detta papper undersöker användningen av rekursiva array layouter för att förbättra prestanda och minska variabilitet. Tidigare arbete på rekursiv matris multiplikation utvidgas för att undersöka flera rekursiva array layouter och tre rekursiva algoritmer: standard matris multiplikation, och de mer komplexa algoritmer Strassen och Winograd. Medan rekursiva layouter avsevärt överträffar traditionella layouter (minskar exekveringstiderna med en faktor på 1,2-2,5) för standardalgoritmen, erbjuder de liten förbättring för Strassens och Winograds algoritmer. För ett rent sekventiellt genomförande är det möjligt att beställa om beräkning för att spara minnesutrymme och förbättra prestandan mellan 10 och 20 %. Att bära rekursiv layout ner till nivån av enskilda matriselement visas vara kontraproduktivt; en kombination av rekursiva layouter ner till kanoniskt ordnade matrisplattor ger istället högre prestanda. Fem rekursiva layouter med successivt ökande komplexitet av adressberäkning utvärderas, och det visas att adresserande overheads kan hållas i kontroll även för de mest beräkningskrävande av dessa layouter.
Chaterjee et al REF visar att rekursiva layouter avsevärt kan överträffa traditionella layouter för standardmatrismatrismultiplikation.
Recursive Array Layouts and Fast Matrix Multiplication
{'venue': 'IEEE Trans. Parallel Distrib. Syst.', 'journal': None, 'mag_field_of_study': ['Computer Science']}