Algorisme oblit de la memòria cau

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]

Història

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++.

Model de memòria cau idealitzada

En general, un programa es pot fer més conscient de la memòria cau: ^[4]

• Localitat temporal, on l'algoritme recupera les mateixes peces de memòria diverses vegades;
• Localitat espacial, on els accessos de memòria posteriors són adreces de memòria adjacents o properes.

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 ${\displaystyle O(1)}$ 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:

La memòria cau de l'esquerra es manté ${\displaystyle {\tfrac {M}{B}}}$ blocs de mida ${\displaystyle B}$ cadascun, per a un total de M objectes. La memòria externa de la dreta és il·limitada.

• La memòria es trenca en blocs de objectes cadascun.
• Una càrrega o un emmagatzematge entre la memòria principal i un registre de la CPU ara es pot atendre des de la memòria cau.
• Si una càrrega o una emmagatzematge no es poden atendre des de la memòria cau, s'anomena cache miss.
• Un error de memòria cau fa que un bloc es carregui de la memòria principal a la memòria cau. És a dir, si la CPU intenta accedir a Word i és la línia que conté , doncs es carrega a la memòria cau. Si la memòria cau anteriorment estava plena, també es desallotjarà una línia (vegeu la política de substitució a continuació).
• La memòria cau es manté ${\displaystyle M}$ objectes, on ${\displaystyle M=\Omega (B^{2})}$. Això també es coneix com a suposició de la memòria cau alta.
• La memòria cau és totalment associativa: cada línia es pot carregar a qualsevol ubicació de la memòria cau.
• La política de substitució és òptima. En altres paraules, se suposa que a la memòria cau se li dona tota la seqüència d'accés a la memòria durant l'execució de l'algorisme. Si cal desallotjar una línia a l'hora , examinarà la seva seqüència de sol·licituds futures i desallotjarà la línia el primer accés de la qual és més llunyà en el futur. Això es pot emular a la pràctica amb la política Least Recently Used, que es mostra dins d'un petit factor constant de l'estratègia de substitució òptima fora de línia.

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 (${\displaystyle B}$ i ${\displaystyle M}$). 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.

Il·lustració de l'ordre principal de fila i columna

Exemples

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 ${\displaystyle \Theta (mn)}$.

Principi de l'algorisme d'oblit de la memòria cau per a la transposició de matrius mitjançant un enfocament dividir i conquerir. El gràfic mostra el pas recursiu (a → b ) de dividir la matriu i transposar cada part individualment.

L'algoritme de la memòria cau té una complexitat de treball òptima ${\displaystyle O(mn)}$ i una complexitat de memòria cau òptima ${\displaystyle O(1+mn/B)}$. 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 ${\displaystyle m\times n}$ i una matriu de sortida de mida ${\displaystyle n\times m}$ s'ajusten a la memòria cau, donen lloc a les travessaments de la fila principal i de la columna principal ${\displaystyle O(mn)}$ treball i ${\displaystyle O(mn/B)}$ 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 ${\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}$, que coincideix amb un límit inferior i, per tant, és asimptòticament òptim.

Referències

1. «Cache Oblivious Algorithm» (en anglès americà), 29-01-2022. [Consulta: 3 setembre 2023].
2. «Lecture 23: Cache-oblivious Algorithms I» (en anglès). https://ocw.mit.edu.+[Consulta: 3 setembre 2023].
3. «[https://people.csail.mit.edu/xchen/parallel-computing/cache-oblivious.pdf 4 Cache-Oblivious Algorithms]» (en anglès). [Consulta: març 2023].
4. Askitis, Nikolas; Zobel, Justin International Symposium on String Processing and Information Retrieval, 2005, pàg. 93. DOI: 10.1007/11575832_1.