Jaki jest stan wiedzy w teorii algorytmów pamięci podręcznej?

Niedawno zainteresowałem się ogólnym problemem optymalizacji wykorzystania pamięci w sytuacji, gdy dostępny jest więcej niż jeden rodzaj pamięci, i istnieje kompromis między pojemnością danego segmentu pamięci a szybkością dostępu do niego.

Znanym przykładem jest program decydujący, kiedy odczytywać / zapisywać w pamięci podręcznej procesora, pamięci RAM i dysku twardym (za pośrednictwem pamięci wirtualnej).

Szczególnie interesuje mnie szczególny przypadek, w którym ilość danych (w tym samego programu), które należy załadować, znacznie przekracza pojemność najszybszej dostępnej pamięci (tj. Trywialne rozwiązanie „wystarczy załadować wszystko” nie ma zastosowania).

Odkryłem, że strona Wikipedii opisuje niektóre popularne algorytmy pamięci podręcznej, co jest prawie tym, czego chcę. Niestety są one nieco niskiego poziomu:

• Wiele, takich jak LRU lub MRU, ma sens tylko wtedy, gdy masz podprogramy, do których dostęp jest uzyskiwany wiele razy. Jeśli mam program z dużą liczbą podprogramów, z których niektóre nigdy nie są dostępne w danym przebiegu, a niektóre z nich są uzyskiwane raz lub dwa razy, ta strategia nigdy nie zadziała, ponieważ nie może zgromadzić wystarczającej ilości danych na temat tego, co jest powszechnie używany, a co nie.
• Inne, takie jak CLOCK, wydają się zajmować osobliwościami implementacji, zamiast faktycznie atakować źródło problemu.
• Wiem, że istnieje strategia polegająca na tym, że najpierw profiluje się program podczas uruchomienia testowego, a następnie zapewnia profil dla systemu operacyjnego, aby odpowiednio go zoptymalizować. Jednak nadal musimy rozwiązać problem zapewnienia prawdziwie reprezentatywnego „przykładowego użycia” podczas budowania profilu.

To, czego naprawdę chcę się nauczyć, to: kiedy odejmujemy wszystkie szczegóły techniczne sprzętu i oprogramowania i mówimy w czysto teoretycznym kontekście, czy można w jakiś sposób przeanalizować strukturę algorytmu i opracować skuteczną strategię pamięci podręcznej dla opiera się na wysokim poziomie zrozumienia tego, co robi algorytm?

Nie wiem o metodzie analizy dowolnego algorytmu, aby ogólnie opracować politykę pamięci podręcznej (brzmi to dość trudnie), ale zasadniczo to zrobiono (optymalnie, w sensie asymptotycznym) w przypadku -podstawowa podstawa dla najbardziej znanych algorytmów ignorowanych przez pamięć podręczną , poprzez analizę ich struktury dziel i zwyciężaj. Algorytmy niepamięci podręcznej są znane z FFT, mnożenia macierzy, sortowania i kilku innych. Zobacz stronę Wikipedii i odnośniki do niej.