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?