Architektura Komputerów/Wykład 9: Kieszenie jako warstwa hierarchii pamięci

Plan wykładu





Kieszenie - podstawy




Kieszenie



Działanie kieszeni


  • Przy każdym odwołaniu procesora do pamięci następuje sprawdzenie, czy dana spod określonego adresu znajduje się w kieszeni
  • Brak danej w kieszeni - chybienie kieszeni (cache miss)
    • dana zostaje odczytana z pamięci i przesłana do procesora
    • „po drodze" dana wraz z jej adresem jest zapisywana do kieszeni
      • jeśli kieszeń była pełna - trzeba z niej coś usunąć
    • przy następnym odwołaniu dana będzie już w kieszeni 
  • Odnalezienie danej w kieszeni - trafienie kieszeni (cache hit)
    • dana zostaje odczytana z kieszeni
    • odwołanie do pamięci operacyjnej jest zbędne
    • czas odwołania do danej w kieszeni jest znacznie krótszy, niż czas dostępu do pamięci operacyjnej


Zasada lokalności odwołań


  • W ograniczonym odcinku czasu odwołania procesora do pamięci są skupione na niewielkim fragmencie przestrzeni adresowej
  • Wykres przedstawia orientacyjny rozkład prawdopodobieństwa odwołań do poszczególnych adresów w czasie od t0 do t0+∆t. przy założeniu, że w chwili t0 nastąpiło odwołanie do A0


Wnioski z zasady lokalności


  • Zakres odwołań jest ograniczony
    • zakres adresów, do których odwołuje się procesor w ograniczonym odcinku czasu nazywa się zbiorem roboczym
    • stosunkowo niewielki bufor może przechowywać znaczącą część obiektów, do których w danym odcinku czasu odwołuje się procesor
  • Odwołania są na ogół powtarzane
    • należy zapamiętywać dane, do których procesor wykonuje dostęp, bo zapewne wkrótce będzie znów ich potrzebował
  • Bardzo prawdopodobne są kolejne odwołania do kolejnych adresów
    • przy napełnianiu bufora wskutek dostępu ze strony procesora warto pobrać z pamięci kilka kolejnych komórek "na zapas"


Kieszeń pełnoasocjacyjna


  • Najbardziej intuicyjny typ kieszeni 
  • Trudna i niezbyt efektywna w implementacji
    • małe pojemności
    • obecnie nie stosowana
  • Zbudowana na bazie pamięci asocjacyjnej
    • pamięć asocjacyjna nie ma adresów
    • dostęp do danej następuje poprzez porównanie danej w kieszeni z wzorcem dostarczonym z zewnątrz
    • pamięć odpowiada poprzez wystawienie danych zgodnych ze wzorcem lub informacji, że takich danych nie ma w pamięci
    • działanie można wytłumaczyć na przykładzie książki telefonicznej
      • szukamy znanego nazwiska
      • odczytujemy numer telefonu
      • nie zwracamy uwagi na położenie nazwiska w książce (nr strony, kolumnę)


Kieszeń pełnoasocjacyjna - model



Kieszeń pełnoasocjacyjna - charakterystyka


  • W każdej komórce kieszeni może być przechowywana dana spod dowolnego adresu
    • kieszeń może równocześnie przechowywać dane spod dowolnych adresów - duża elastyczność w porównaniu z następnymi architekturami
  • Wyznaczanie linii do zastępowania - LRU lub losowe
    • LRU - algorytm kosztowny w implementacji sprzętowej
    • algorytm losowy- daje zróżnicowane wyniki
  • Każda komórka wyposażona w komparator znacznika
    • trudna implementacja
    • niewielka pojemność (do ok. 16 KB), ograniczenie szybkości dostępu
  • Jeśli rozmiar zbioru roboczego przekracza pojemność kieszeni-wszystkie odwołania będą kończyły się chybieniami


Kieszeń - konstrukcja


  • Dane są przechowywane w kieszeni nie w postaci pojedynczych słów czy bajtów, lecz bloków, zazwyczaj o długości 4× większej od rozmiaru słowa pamięci
    • bloki te są wyrównane naturalnie - adres pierwszego bajtu jest podzielny przez długość bloku
  • Element kieszeni zawierający blok danych i związane z nim znaczniki (w tym znacznik adresu) jest nazywany linią
  • Najmniej znacząca część adresu służy do wyboru bajtu lub słowa z linii
    • kolejne, bity adresu są używane do stwierdzenia, czy poszukiwana dana znajduje się w kieszeni


Kieszeń bezpośrednio adresowana


  • Zbudowana na bazie zwykłej, szybkiej pamięci RAM i jednego komparatora
    • bardzo prosta w realizacji, szybka i wydajna
    • dzięki prostocie budowy może mieć stosunkowo dużą pojemność 
  • Proste, lecz zupełnie nieintuicyjne działanie
    • najmniej znaczące bity adresu służą do wyboru bajtu z linii
    • „środkowa', mniej znacząca część adresu procesora służy jako adres pamięci RAM: na jej podstawie w każdym cyklu dostępu jest wybierana pojedyncza linia
    • każda linia zawiera znacznik adresu i dane
    • pole znacznika adresu zawiera bardziej znaczącą część adresu danej zapamiętanej w polu danych - jest ono porównywane z najbardziej znaczącą częścią adresu wystawionego przez procesor


Kieszeń bezpośrednio adresowane



Kieszeń bezpośrednio adresowana - działanie


  • W każdym cyklu następuje wybór jednej linii, zaadresowanej przez mniej znaczącą część adresu
  • Kieszeń stwierdza trafienie, jeśli znacznik adresu wybranej linii jest równy najbardziej znaczącej części adresu wystawionego przez procesor
  • W przypadku trafienia dane są transmitowane z kieszeni do procesora
  • W przypadku chybienia wymianie podlega wybrana linia
    • w polu znacznika zostaje zapisana najbardziej znacząca część adresu
    • w polu danych zostają zapamiętane dane odczytane z pamięci


Kieszeń bezpośrednio adresowana - charakterystyka


  • Niskie koszty, duża pojemność, wysoka wydajność
  • Algorytm zastępowania linii wymuszony przez budowę kieszeni
    • dane spod określonego adresu mogą znaleźć się wyłącznie w jednej, z góry określonej linii kieszeni
    • w kieszeni nie można zapamiętać dwóch danych, których środkowe części adresu są identyczne
      • w praktyce nie jest to bardzo częsty przypadek, ale niekiedy się zdarza
  • Przy ciągłym zakresie adresów zbioru roboczego (pętla programu, tablica) kieszeń przyspiesza odwołania do pamięci, dopóki zbiór roboczy jest mniejszy niż 2× pojemność kieszeni
    • lepiej niż w przypadku kieszeni pełno asocjacyjnej


Kieszeń zbiorowo-asocjacyjna


  • Powstaje przez połączenie pewnej liczby kieszeni bezpośrednio adresowanych (zwanych blokami)
  • Dana spod określonego adresu może być przechowywana w tylu miejscach, ile jest bloków
    • w każdym cyklu dostępu następuje poszukiwanie danej w pojedynczej linii każdego z bloków
    • zestaw linii wybieranych w każdym cyklu jest nazywany zbiorem
    • zbiór zachowuje się jak mała kieszeń pełnoasocjacyjna
  • Liczba bloków jest zwana stopniem asocjacyjności kieszeni
    • używa się również określeń "kieszeń dwudrożna'" lub "czterodrożna" 
  • Kieszeń zbiorowo-asocjacyjna może być rozpatrywana również jako złożenie pewnej liczby kieszeni pełnoasocjacyjnych


Kieszeń zbiorowo-asocjacyjna



Kieszeń zbiorowo-asocjacyjna - działanie


  • Budowa kieszeni musi gwarantować, że dana spod określonego adresu może zostać zapisana tylko w jednym bloku
  • W przypadku chybienia należy wyznaczyć ze zbioru jedną linię do zastąpienia
    • można użyć algorytmu LRU. który przy małej liczbie linii daje się zrealizować w sprzęcie
    • przy większej liczbie linii - algorytm pseudoLRU lub losowy
  • Charakterystyka ogólnie podobna do kieszeni bezpośrednio adresowanej, ale z eliminacją przypadku z pokrywającymi się środkowymi częściami adresu
    • mniejsza wrażliwość kieszeni na nakładanie się adresów danych -podobnie jak w przypadku kieszeni pełnoasocjacyjnej


Rodzaje kieszeni - podsumowanie


  • Najczęściej spotykanym typem kieszeni są kieszenie zbiorowo-asocjacyjne
    • charakterystyka lepsza od bezpośrednio adresowanych przy niewielkim wzroście komplikacji
    • tam, gdzie jest krytyczny czas dostępu - używa się kieszeni o małej asocjacyjności
  • Przy bardzo ostrych wymaganiach na szybkość używa się kieszeni bezpośrednio adresowanych lub dwudrożnych zbiorowo-asocjacyjnych
  • Kieszenie pełnoasocjacyjne nie są stosowane do przechowywania danych i kodu
    • niekiedyznajdują one zastosowanie w innych miejscach komputera


Współczynnik trafień (hit ratio)


  • Definiowany jako stosunek liczby trafień do całkowitej liczby odwołań w badanym przedziale czasu

                                   h=\frac{n_{cache} }{n_{total} }

  • Zależy od:
    • pojemności kieszeni
    • organizacji kieszeni i wynikającego z niej algorytmu wymiany
    • wykonywanego programu
      • dla każdej kieszeni można podać przykład programu o h = 0 i innjego, o h bliskim 1
  • Wiarygodny pomiar i porównanie współczynnika trafień wymaga uzgodnienia budowy testu
    • zwykle używa się serii programów o zróżnicowanej charakterystyce odwołań, np. kompilatora, edytora, bazy danych, programu obliczeniowego


Współczynnik trafień


  • Wykres przedstawia orientacyjny przebieg zależności współczynnika trafień od pojemności kieszeni
  • W zakresie wartości od 0 do 0,9 h zależy głównie od pojemności kieszeni
  • wartość 0,9 jest osiągana przy pojemności kieszeni rzędu 8 KB
  • W zakresie powyżej 0,9 istotny wpływ ma również organizacja i algorytm wymiany
    • wyższa asocjacyjność daje wyższy współczynnik trafień


Współczynnik trafień a wydajność


  • Współczynnik trafień jest liczbą niemianowaną
  • Nie wyraża wzrostu wydajności wynikającego z użycia kieszeni
  • Kieszeń służy przyspieszeniu odwołań do hierarchii pamięci
  • Wydajność może być wyrażona poprzez odniesienie ilości danych do czasu
    • poprzez szybkość transmisji, np. w MB/s
    • poprzez średni czas transmisji, w jednostkach czasu na transfer
      • niezależnie od częstotliwości procesora - w cyklach procesora na transfer


Średni czas dostępu


  • Średni czas dostępu dla hierarchii pamięci złożonej z kieszeni i pamięci operacyjnej:

                t_{AVG}=h\cdot t_{CACHE}+\left(1-h \right) \cdot t_{MEM}

        h - współczynnik trafień kieszeni 
        m = 1-h - współczynnik chybień kieszeni (miss ratio)
  • Kieszeń dołączona do procesora musi być skonstruowana tak, aby mogła dostarczać dane z szybkością wymaganą przez procesor (bez zatrzymań)  
  • dla dalszych rozważań przyjmujemy tCACHE = 1



Średni czas dostępu hierarchii pamięci


  • Tabelka przedstawia średni czas dostępu w zależności od współczynnika trafień i dysproporcji wydajności pamięci i kieszeni
  • Wartości odpowiadają wartości spowolnienia procesor w stosunku do sytuacji idealnej
  • W zakresie „czerwonym" procesor pracuje kilkakrotnie wolniej niż przy idealnej hierarchii pamięci


Wydajność kieszeni - wnioski


  • Intuicyjnie „wysoki" współczynnik trafień nie zapewnia zbalansowania wydajności procesora i hierarchii pamięci
    • istotny jest nie tyle współczynnik trafień, co dysproporcja pomiędzy wydajnością kieszeni i pamięci
  • We współczesnych komputerach czas dostępu pamięci może być ponad 100 razy dłuższy od czasu cyklu procesora
    • z tabelki wynika, że nawet bardzo wysoki współczynnik trafień nie umożliwi wyrównania wydajności
  • Pojedyncza kieszeń może skutecznie zniwelować różnicę wydajności nie przekraczającą jednego rzędu dziesiętnego
  • Poprawa średniego czasu dostępu wymaga poprawy czasu dostępu poza kieszenią - można to uzyskać zastępując pamięć operacyjną kolejnym kieszeni i pamięci
    • w ten sposób powstaje wielopoziomowy system kieszeni


Kieszenie wielopoziomowe


  • Wymóg nadążania kieszeni pierwszego poziomu (L1) ogranicza jej pojemność i asocjacyjność
    • im większa kieszeń - tym wolniejsza
    • im wyższa asocjacyjność - tym dłuższy czas dostępu
  • Kieszeń drugiego poziomu (L2) może być wolniejsza (np. 5 razy) - dzięki temu:
    • może mieć wyższą asocjacyjność
    • może być znacząco większa
  • Jeśli kieszeń L2 nie zapewnia odpowiednio krótkiego średniego czasu dostępu, w strukturze komputera umieszcza się kieszeń L3, większą i wolniejszą od L2


Kieszeń a zapis danych


  • W dotychczasowych rozważaniach rozpatrywaliśmy wyłącznie odczyt danych lub instrukcji z pamięci
  • Możliwe zachowanie kieszeni przy zapisie:
    • zapis przezroczysty - zapis wykonywany zawsze do pamięci, a w przypadku trafienia - również do kieszeni
    • zapis zwrotny- zapis do pamięci wykonywany tylko wtedy, kiedy jest to niezbędne
  • Warianty zapisu zwrotnego:
    • bez alokacji przy chybieniu zapisu - w razie chybienia zapis zachodzi tylko do pamięci, w razie trafienia - tylko do kieszeni
    • z alokacją przy chybieniu zapisu - zapis jest zawsze wykonywany tylko do kieszeni
  • Przy zapisie zwrotnym usunięcie linii z kieszeni może wymagać zapisu usuwanej linii do pamięci


Kieszenie - strategie zapisu danych



Kieszenie inkluzywne


  • Implementowane do ok. 2000 roku
  • Przepływ danych: pamięć L2 L1 procesor
  • Każdy obiekt zawarty w wyższej warstwie jest również obecny w warstwie niższej
  • Efektywna sumaryczna pojemność kieszeni jest równa pojemności największej z warstw kieszeni
  • Pojemność L2 musi być znacząco większa od L1


Kieszenie wyłączne


  • Od około 2000 roku
  • Kieszeń L2 jest napełniana wyłącznie obiektami usuwanymi z L1
    • jest to tzw. kieszeń ofiar (victim cache)
      • określenie odnosi się do linii - "ofiar" algorytmu zastępowania
  • Przepływ danych: pamięć L1 procesor, L1 L2
  • L2 zawiera głównie obiekty nieobecne w L1
  • Efektywna sumaryczna pojemność kieszeni jest równa sumie pojemności poszczególnych warstw kieszeni
  • Pojemność L2 może być równa lub większa od L1
  • Asocjacyjność L2 powinna być większa od asocjacyjności L1
    • w przeciwnym przypadku sprawność przechwytywania ofiar byłaby niewielka
  • Przykłady - K7 i K8 firmy AMD, Pentium 4 i Core firmy I ntel


Kieszenie wyłączne - główne ścieżki danych



Spójność hierarchii pamięci


  • Hierarchię pamięci musi cechować spójność:
    • każdy dostęp do danego adresu musi zwrócić tę samą wartość danej, niezależnie od warstwy, w której jest fizycznie realizowany
  • Problem z utrzymaniem spójności powstaje, gdy istnieje więcej niż jedna ścieżka dostępu do hierarchii pamięci, np.:
    • procesor o architekturze Harvard-Princeton z odzielnymi kieszeniami L1 kodu i danych
    • dwa procesory z oddzielnymi kieszeniami L1 i wspólną dalszą warstwą hierarchii pamięci
    • procesor z kieszenią i sterownik wejścia-wyjścia, wykonujący bezpośrednie dostępy do pamięci z pominięciem kieszeni
  • Spójność nie wymaga utrzymywania identycznej zawartości we wszystkich warstwach, a jedynie zagwarantowania, że każdy dostęp będzie dotyczył aktualnej wartości danej


Metody utrzymywania spójności


  • Unieważnianie całej kieszeni przy wykryciu odwołania zewnętrznego
    • stosowane dawniej przy b. małych kieszeniach
  • Selektywne unieważnianie linii potencjalnie zawierających adres odwołania zewnętrznego
    • stosowane do ok. 1990 roku przy kieszeniach o pojemnościach do kilku KB
  • Programowe unieważnianie całej kieszeni
    • dostępne dla systemu operacyjnego, ograniczone zastosowanie z powodu spadku wydajności
  • Selektywna zmiana stanu linii po stwierdzeniu zgodności adresu, przesłania między kieszeniami
    • metody używane współcześnie, wydajne, ale złożone w realizacji
    • wymagają realizacji złożonych protokołów utrzymania spójności


Protokoły utrzymania spójności


  • Automat zrealizowany oddzielnie dla każdej linii
  • Stany linii:
    • M - modified - linia ważna, jedyna aktualna kopia we własnej kieszeni, zawartość pamięci nieaktualna
    • E - exclusive - linia ważna, jedyna kopia we własnej kieszeni, identyczna z zawartością pamięci
    • I - invalid - linia nieważna
    • S - shared - linia ważna, jednakowa kopia u wszystkich, identyczna z zawartością pamięci
    • O - owned - linia ważna, jednakowa kopia u wszystkich, u pozostałych stan S. zawartość pamięci nieaktualna
  • Protokoły - nazwy pochodzą od zbioru obsługiwanych stanów
    • MEI, MESI, MOESI
  • Im więcej stanów, tym mniej zbędnych unieważnień