En informàtica, un algorisme oblit de la memòria cau (o algorisme transcendent de la memòria cau) és un algorisme dissenyat per aprofitar la memòria cau d'un processador sense tenir la mida de la memòria cau (o la longitud de les línies de la memòria cau, etc.) com a paràmetre explícit. Un algorisme òptim d'oblit de memòria cau és un algorisme d'oblit de memòria cau que utilitza la memòria cau de manera òptima (en un sentit asimptòtic, ignorant els factors constants). Per tant, un algorisme de memòria cau està dissenyat per funcionar bé, sense modificacions, en diverses màquines amb diferents mides de memòria cau o per a una jerarquia de memòria amb diferents nivells de memòria cau amb mides diferents. Els algorismes que obliden a la memòria cau es contrasten amb el mosaic de bucle explícit, que divideix explícitament un problema en blocs que tenen la mida òptima per a una memòria cau determinada.[1]
Els algorismes òptims que obliden a la memòria cau són coneguts per a la multiplicació de matrius, la transposició de matrius, l'ordenació i diversos altres problemes. Alguns algorismes més generals, com ara Cooley–Tukey FFT, són òptimament oblidats de la memòria cau sota determinades opcions de paràmetres. Com que aquests algorismes només són òptims en un sentit asimptòtic (ignorant els factors constants), pot ser que calgui més ajustament específic de la màquina per obtenir un rendiment gairebé òptim en sentit absolut. L'objectiu dels algorismes de memòria cau és reduir la quantitat d'ajustos necessaris.[2]
Normalment, un algorisme oblivi de la memòria cau funciona mitjançant un algorisme recursiu de dividir i conquerir, on el problema es divideix en subproblemes cada cop més petits. Finalment, s'arriba a una mida de subproblema que encaixa a la memòria cau, independentment de la mida de la memòria cau. Per exemple, s'obté una multiplicació òptima de matrius sense memòria cau dividint recursivament cada matriu en quatre submatrius que s'han de multiplicar, multiplicant les submatrius d'una manera primerenca en profunditat. En l'ajustament per a una màquina específica, es pot utilitzar un algorisme híbrid que utilitza mosaics de bucle ajustats per a les mides específiques de la memòria cau al nivell inferior, però que, en cas contrari, utilitza l'algoritme de la memòria cau.[3]
La idea (i el nom) dels algorismes de cache-obvious va ser concebuda per Charles E. Leiserson ja el 1996 i publicat per primera vegada per Harald Prokop en la seva tesi de màster al Massachusetts Institute of Technology el 1999. Hi havia molts predecessors, normalment analitzant problemes específics; aquests es discuteixen en detall a Frigo et al. 1999. Els primers exemples citats inclouen Singleton 1969 per a una transformada ràpida de Fourier recursiva, idees similars a Aggarwal et al. 1987, Frigo 1996 per a la multiplicació de matrius i descomposició LU, i Todd Veldhuizen 1996 per als algorismes de matrius a la biblioteca Blitz++.
En general, un programa es pot fer més conscient de la memòria cau: [4]
Els algorismes de la memòria cau s'analitzen normalment utilitzant un model idealitzat de la memòria cau, de vegades anomenat model de la memòria cau. Aquest model és molt més fàcil d'analitzar que les característiques d'una memòria cau real (que tenen associativitat complicada, polítiques de substitució, etc.), però en molts casos es provably dins d'un factor constant del rendiment d'una memòria cau més realista. És diferent del model de memòria externa perquè els algorismes de memòria cau no coneixen la mida del bloc ni la mida de la memòria cau.
En particular, el model cache-oblivious és una màquina abstracta (és a dir, un model teòric de càlcul). És similar al model de màquina RAM que substitueix la cinta infinita de la màquina de Turing per una matriu infinita. Es pot accedir a cada ubicació de la matriu temps, similar a la memòria d'accés aleatori en un ordinador real. A diferència del model de màquina RAM, també introdueix una memòria cau: el segon nivell d'emmagatzematge entre la memòria RAM i la CPU. Les altres diferències entre els dos models s'enumeren a continuació. En el model de memòria cau:
Per mesurar la complexitat d'un algorisme que s'executa dins del model de memòria cau, mesurem el nombre de faltes de memòria cau que experimenta l'algorisme. Com que el model captura el fet que l'accés als elements de la memòria cau és molt més ràpid que l'accés a les coses de la memòria principal, el temps d'execució de l'algorisme només es defineix pel nombre de transferències de memòria entre la memòria cau i la memòria principal. Això és similar al model de memòria externa, que totes les característiques anteriors, però els algorismes de memòria cau són independents dels paràmetres de la memòria cau ( i ). L'avantatge d'aquest algorisme és que el que és eficient en una màquina oblida de la memòria cau és probable que sigui eficient en moltes màquines reals sense ajustar els paràmetres concrets de la màquina real. Per a molts problemes, un algorisme òptim de memòria cau també serà òptim per a una màquina amb més de dos nivells de jerarquia de memòria.
L'algoritme més senzill d'oblit de memòria cau presentat a Frigo et al. és una operació de transposició de matrius fora de lloc (també s'han ideat algorismes in situ per a la transposició, però són molt més complicats per a matrius no quadrades). Donada la matriu m × n A i la matriu n × m B, ens agradaria emmagatzemar la transposició de A a B La solució ingènua travessa una matriu en ordre de fila principal i una altra en columna principal. El resultat és que quan les matrius són grans, obtenim un error de memòria cau a cada pas del recorregut per columnes. El nombre total d'errors de memòria cau és .
L'algoritme de la memòria cau té una complexitat de treball òptima i una complexitat de memòria cau òptima . La idea bàsica és reduir la transposició de dues matrius grans a la transposició de (sub)matrius petites. Ho fem dividint les matrius per la meitat al llarg de la seva dimensió més gran fins que només hem de realitzar la transposició d'una matriu que encaixarà a la memòria cau. Com que l'algorisme no coneix la mida de la memòria cau, les matrius continuaran dividint-se recursivament fins i tot després d'aquest punt, però aquestes subdivisions addicionals estaran a la memòria cau. Una vegada que les dimensions m i n són prou petites com per a una matriu d'entrada de mida i una matriu de sortida de mida s'ajusten a la memòria cau, donen lloc a les travessaments de la fila principal i de la columna principal treball i falla la memòria cau. Mitjançant aquest enfocament de divideix i vencem podem aconseguir el mateix nivell de complexitat per a la matriu general.
(En principi, es podria continuar dividint les matrius fins que s'arribi a un cas base de mida 1 × 1, però a la pràctica s'utilitza un cas base més gran (per exemple, 16 × 16) per amortitzar la sobrecàrrega de les trucades recursives de subrutina).
La majoria d'algoritmes oblidats de la memòria cau es basen en un enfocament dividit i vençut. Redueixen el problema, de manera que finalment s'adapta a la memòria cau per molt petita que sigui la memòria cau, i acaben la recursivitat amb una mida petita determinada per la sobrecàrrega de la trucada de funció i optimitzacions similars no relacionades amb la memòria cau, i després utilitzen un accés eficient a la memòria cau. patró per combinar els resultats d'aquests petits problemes resolts.
Igual que l'ordenació externa en el model de memòria externa, l'ordenació sense memòria cau és possible en dues variants: funnelsort, que s'assembla a mergesort, i cache-oblivious distribution sort, que s'assembla a quicksort. Igual que els seus homòlegs de memòria externa, tots dos aconsegueixen un temps d'execució de , que coincideix amb un límit inferior i, per tant, és asimptòticament òptim.