Algorytmy i struktury danych ignorowane przez pamięć podręczną są raczej nową rzeczą, wprowadzoną przez Frigo i in. w algorytmach niepamięci Cache, 1999 . Teza Prokopa z tego samego roku wprowadza także wczesne pomysły.
Artykuł Frigo i in. przedstawić niektóre wyniki eksperymentalne pokazujące potencjał teorii oraz algorytmów i struktur danych nieobsługiwanych przez pamięć podręczną. Wiele struktur danych nieobsługujących pamięci podręcznej jest opartych na statycznych drzewach wyszukiwania. Metody przechowywania i poruszania się po tych drzewach zostały dość rozwinięte, być może przede wszystkim przez Bendera i in. a także Brodal i in. Demaine daje ładny przegląd .
Eksperymentalną pracę nad badaniem zachowania pamięci podręcznej w praktyce wykonali przynajmniej Ladner i in. w Porównanie drzewa pamięci podręcznej świadomej i pamięci podręcznej statycznego wyszukiwania przy użyciu Instrumentacji programowej, 2002 . Ladner i in. dokonał analizy porównawczej zachowania pamięci podręcznej algorytmów rozwiązujących problem wyszukiwania binarnego, wykorzystując klasyczny algorytm, algorytm nieobsługujący pamięci podręcznej i algorytm rozpoznający pamięć podręczną. Każdy algorytm został poddany testom porównawczym za pomocą ukrytych i jawnych metod nawigacji. Oprócz tego teza autorstwa Rønn, 2003 przeanalizowała te same algorytmy z dość dużą szczegółowością, a także przeprowadziła jeszcze dokładniejsze testy tych samych algorytmów, co Ladner i in.
Moje pytanie brzmi
Czy nastąpiły jakieś nowsze badania dotyczące analizy porównawczej zachowanie cache algorytmów Cache-niepomny w praktyce , ponieważ? Szczególnie interesuje mnie wydajność drzew wyszukiwania statycznego, ale byłbym również zadowolony z wszelkich innych algorytmów i struktur danych nieobsługiwanych przez pamięć podręczną.
Odpowiedzi:
Już dość dobrze opisałeś podstawowe badania algorytmów niepamięci podręcznej. Jeśli chodzi o testy porównawcze i praktyczne wyniki, ten ostatni artykuł Intela uważam za interesujący tekst:
Synergetyczne podejście do przetwarzania przepływności w wieloprocesorowych komputerach stacjonarnych z procesorem x86
źródło