Cache-oblivious algoritmer har avancerats som ett sätt att kringgå några av svårigheterna med att optimera applikationer för att dra nytta av minnet hierarki av moderna mikroprocessorer. Dessa algoritmer är baserade på split-and-conquer paradigm -varje division steg skapar sub-problem av mindre storlek, och när arbetsuppsättningen av ett sub-problem passar i någon nivå av minne hierarkin, beräkningar i att sub-problem kan utföras utan lidande kapacitet missar på den nivån. På detta sätt anpassar sig divideand-conquer algoritmer automatiskt till alla nivåer i minnet hierarkin; i själva verket, för problem som matris multiplikation, matris införliva, och FFT, dessa rekursiva algoritmer är optimala till inom konstanta faktorer för vissa teoretiska modeller av minne hierarkin. En viktig fråga är följande: hur väl gör noggrant avstämda cache-oblivious program fungerar jämfört med noggrant avstämda cache-medvetna program för samma problem? Finns det ett pris för glömska, och i så fall, hur mycket prestanda förlorar vi? Något överraskande är att det finns få studier i litteraturen som har tagit upp denna fråga. I detta dokument redovisas resultaten av en sådan studie inom området tät linjär algebra. Vårt huvudsakliga fynd är att i denna domän, även högt optimerade cache-oblivious program presterar betydligt värre än motsvarande cachemedvetet program. Vi ger insikter i varför detta är så, och föreslår forskningsriktningar för att göra cache-oblivious algoritmer mer konkurrenskraftiga.
En experimentell jämförelse av Cache-oblivious och Cache-medvetet program Referens REF jämför experimentellt cache-oblivious och cache-medvetet (tillverkande omvandling tillämpas) program för matris multiplikation och matris införlivande.
An experimental comparison of cache-oblivious and cache-conscious programs
{'venue': "SPAA '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}