wyk.8, Informatyka PWr, Algorytmy i Struktury Danych, Architektura Systemów Komputerowych, Assembler, wykłady

poziomy hierarchii pamięci:

CCPPUU

CACHE- schowki

Main memory- pamięć główna

External memory- pamięć zewnętrzna

Przydatne definicje

- kiedy CPU znajdzie wymaganą daną w schowku, nazywa się to trafieniem schowka (cache hit.)

- kiedy CPU nie znajdzie wymaganą daną w schowku nazywa się to chybieniem schowka (cache miss.)

-ustalony zbiór danych zawierających wymagane słowo, nazywane blokiem, jest pobierane z pamięci głównej i kierowane do schowka

- tymczasowe umiejscowienie mówi nam, że będziemy mogli potrzebować tego słowa w niedalekiej przyszłości, więc przydatne jest umiejscowienie go w schowku

- z powodu umiejscowienia przestrzennego, istnieje wysokie prawdopodobieństwo, że inne dane z bloku będą wkrótce potrzebne

Chybienia na instrukcję.

-zamiast stosunku chybień, możesz zastosować `chybienia na instrukcję'. Oba pomiary są ekwiwalentne (równoważne). (patrz równanie w slajdzie)

-np. `chybienia na instrukcję' instruction = 0.02 *1.5 = 0.030.

- `chybienia na instrukcję' są również raportowane jako chybienia na 1000 instrukcji (w naszym przykładzie mamy 30 chybień na 1000 instrukcji).

Gdzie w schowku może być umieszczony blok?

- jeżeli każdy blok ma tylko jedno miejsce, w którym może znaleźć się w schowku, schowek jest wtedy zmapowany bezpośrednio (adres bloku) MOD (liczba bloków w schowku)

- jeżeli blok może być umiejscowiony obojętnie gdzie w schowku, schowek jest wtedy w pełni `łączny'.

-jeżeli blok może być umiejscowiony w określonym zestawie miejsc w schowku, schowek jest wtedy `łączny zestawowo'.

Zestaw jest to grupa bloków w schowku. Blok jest najpierw zmapowany na zestaw i wtedy blok może być umiejscowiony obojętnie gdzie w tym zestawie. Zestaw jest zwykle wybierany przez wybór bitów; to znaczy (adres bloków) MOD (liczba zestawów w schowku). Jeżeli w zestawie jest n bloków, umiejscowienie schowka jest nazywane n-sposobów łączny zestawowo'.

Jak znajdowany jest blok jeżeli znajduje się w schowku?

- Schowki mają znaczniki adresów na każdej ramie bloku, która daje adres bloku. Znacznik każdego bloku schowka, który może zawierać potrzebną informację jest sprawdzany, czy zgadza się z adresem bloku z CPU. (patrz na coś tam na slajdzie)

- Znaczniki są używane w celu sprawdzenia wszystkich bloków w zestawie, index jest używany, aby wybrać zestaw, offset bloku (przesunięcie bloku) jest to adres w bloku. Schowki w pełni łączne nie mają pola indeksu.

- Musi być sposób, żeby dowiedzieć się, że blok schowka nie posiada ważnej/obowiązującej informacji. Najbardziej powszechną procedurą jest dodanie ważnego/obowiązującego bitu/elementu do znacznika, żeby stwierdzić, czy to wejście zawiera ważny/obowiązujący adres. Jeżeli bit/element nie jest zestawem (w zestawie?), nie ma zgodności na tym adresie.

Który blok należy wymienić przy chybieniu schowka?

Ogólnie, stosowane są 3 różne strategie:

- przypadkowa/losowa - rozprzestrzenić alokację/przydział jednolicie, bloki kandydujące są wybierane losowo (czasami stosuje się strategię pseudolosową, aby osiągnąć odtwarzalne zachowanie)

- ostatnio używany (LRU)- aby zmniejszyć ryzyko odrzucenia informacji, która będzie wkrótce potrzebna, dostęp do bloków jest rejestrowany. Polegając na przeszłości, aby przewidzieć przyszłość, blok, który ma być usunięty to ten, który nie był używany najdłużej.

- `pierwszy do, pierwszy z” - First in, first out (FIFO) - ponieważ wyliczenie LRU może być skomplikowane, to zaokrągla LRU poprzez określenie najstarszego bloku a nie LRU.

10.

Co dzieje się przy zapisie?

- ruch w danych schowka, zapisy to 10% lub około 12%

- nie ma problemu z odczytem- można odczytywać blok w tym samym czasie co znacznik.

-problemy z odczytem: po pierwsze, nie można zmodyfikować bloku zanim nie jest sprawdzony znacznik, czy adres jest trafiony; po drugie, zwykle procesor określa wielkość zapisów.

- dodatkowo, musimy rozwiązać problem spójności znaku $.

- stosowane są 2 różne strategie:

- Write through- informacje są zapisywane zarówno na bloku w schowku, jak i w bloku w pamięci niższego poziomu.

- Write back - informacje są zapisywane tylko na bloku w schowku. Zmodyfikowany blok schowka jest zapisany w pamięci głównej tylko wtedy kiedy jest wymieniony/usunięty.

11.

Co dzieje się przy zapisie?

- multiprocesory i I/O chcą `write back' dla schowków procesorów w celu zmniejszenia ruchu pamięci i `write through' w celu utrzymania schowka w zgodności z hierarchią niższych poziomów pamięci.

- Kiedy CPU musi czekać na zakończenie zapisów podczas `write through', CPU opóźnia (można to zmienijszyć poprzez wprowadzenie buforów zapisu)

- skoro dane nie są potrzebne przy zapisie / do zapisu, istnieją 2 opcje na chybienie zapisu:

- alokowanie/przydzielanie zapisu - blok jest przydzielany na chybienie zapisu, a następnie mają miejsce działania trafności zapisu jak wyżej

- brak alokowania/przydzielania zapisu - ta najwyraźniej nietypowa alternatywa, że chybienia zapisu nie mają wpływu/ nie dotyczą schowka

12.

Działanie schowka - stosunek chybień

Stosunek chybień jest niezależny od prędkości sprzętu, jednak tak jak liczba instrukcji może być zwodnicza.
Lepszym pomiarem działania hierarchii pamięci jest średni czas dostępu pamięci: średni czas dostępu pamięci=czas trafień+stosunek chybień*kara chybień; gdzie czas trafień jest to czas trafienia schowka
Komponenty średniego czasu dostęu mogą być mierzone albo w czasie absolutnym lub w czasie cyklów zegara
Jest to nadal niebezpośrednie mierzenie działania

13.

Przykład- pytanie

Który niższy stosunek chybień: 16kB schowek pamięci z 16kB schowkiem danych czy 32kB zjednoczony/połączony schowek (chybienie na 1000 instrukcji dla połączonego schowka jest równa 43.3 i dla 16kB schowka instrukcji i schowków danych 3.82 i 40,9 odpowienio, procent referencji instrukcji to około 7%).

Przyjmij, że 36%instrukcji są transferem danych, trafienie trwa 1 cykl zegarowy i kara chybienia to 100 cyklów zegarowych. Załadowanie i przechowywanie trafienia zajmuje 1 cykl zegarowy na połączonym schowku jeżeli jest tylko jeden port schowka dla 2 równoczesnych żądań. Jaki jest średni czas dostępu pamięci w każdym przypadku? Dodatkowo, przyjmij schowki `write-through' z buforem zapisu i zignoruj opóźnienia z powodu buforu zapisu.

16.

Wpływ schowków na działanie I

Pytanie: weź pod uwagę wersję komputera in-order. Przyjmij karę chybienia schowka 100 cyklów zegarowych i wszystkie instrukcje zajmują zwykle 1.0 cykl zegarowy. Przyjmując, że stosunek chybień to 2%, średnia 1.5 referencji pamięci na instrukcję, i średnia liczba chybień schowka na 1000 instrukcji wynosi 30. Jaki jest wpływ na działanie kiedy włączymy zachowanie schowka? Oblicz wpływ przy użyciu chybień na instrukcję i stosunku chybień.

18.

Wpływ chybień schowka na działanie.

Chybienia schowka mają podwójny wpływ na CPU z niskim CPI i szybkim zegarem:

-im niższe wykonanie CPI, tym wyższy relatywny wpływ na stałą liczbę chybień schowka w cyklach zegarowych

- podczas obliczeń CPI, kara chybień schowka jest mierzona w cyklach zegarowych CPU na chybienie.

Dlatego, nawet jeżeli hierarchie pamięci dla 2 komputerow sa identyczne, CPU z wyższym stosunkiem zegarowym ma większą liczbę cyklów zegarowych na chybienie i większą porcję pamięci CPI.

19.

Zmniejszanie kary chybień schowka

Trendy w technologii zwiększyły prędkość precesorów szybszych od DRAMs, zwiększając tym samym relatywny koszt kary chybień.
Jednym ze sposobów zmniejszenia kary chybień jest dodanie kolejnego poziomu schowka pomiędzy oryginalny schowek i główną pamięć- w ten sposób schowek staje się „większy i szybszy”.
Pierwszopoziomowy schowek może być wystarczająco mały, żeby pasować do czasu cyklu zegarowego szybkiego CPU, a drugopoziomowy schowek może być wystarczająco duży, żeby złapać wiele dostępów, które poszłyby do pamięci głównej.

20.

2-poziomowe schowki

Zdefiniujmy średni czas dostępu pamięci dla 2-poziomowego schowka (L1 I L2 odnoszą się do pierwszego I drugiego poziomu)
średni czas dostępu pamięci = czas trafień L1+stosunek chybień L1*kara chybieńL1

Kiedy kara chybieńL1=czas trafień L2 + stosunek chybień L2*kara chybień L2

- wtedy średni czas dostępu pamięci=czas trafień L1+stosunek chybieńL1

-*(czas trafień L2+stosunek chybień L2*kara chybień L2)

-stosunek lokalnych chybień - to liczba chybień w schowku podzielona przez całą liczbę dostępów do pamięci tego schowka

-stosunek globalnych chybień - liczba chybień w schowku podzielona przez całą liczbę dostępów do pamięci generowanych przez CU.

Średnie opóźnienia pamięci na instrukcję= chybienia na instrukcjęL1 *czas trafieńL2+ chybienia na instrukcjęL2 * kara chybień L2

24.

3 kategorie chybień

obowiązkowe- pierwszy dostęp do bloku nie może być w schowku, więc blok musi zostać przyniesiony do schowka (również nazywane chbienia cold-start)
wydajność - jeżeli schowek nie może pomieścić wszystkich bloków potrzebnych do wykonania programu, pojawią się chybienia wydajności z powodu bloków odrzuconych a później przywróconych.
Konflikt - jeżeli strategia umiejscowienia bloku jest łączna zestawowo lub zmapowana bezpośrednio, pojawią się konflikty chybień ponieważ blok może być odrzucony a później przywrócony jeżeli zbyt wiele bloków mapuje się do zestawu.

27.

Organizacja pamięci głównej w celu poprawy działania

- pomiary działania pamięci głównej podkreślają zarówno opóźnienie jak i przepustowość (szerokość pasma) (liczba przeczytanych lub zapisanych bajtów w jednostce czasu)

- przyjmij, że działanie organizacji pamięci podstawowej to:

- 4 cykle zegarowe do wysłania

- 56 cykli zegarowych dla czasu dostępu na słowo

- 4 cykle zegarowe aby wysłać słowo z danych

�� Mając blok schowka złożonego z 4 słów, a słowo to 8 bajtów, kara chybienia to

4*(4+56+4) = 256

Cyklów zegarowych z przepustowością pamięci 1/8 bajta.

28.

Organizacja pamięci głównej w celu poprawy działania

Szersza pamięć główna

- 1-poziomowe schowki są często zorganizowane z fizyczną szerokością 1 słowa ze względu na to, że dostępy CPU sa tej wielkości

- kiedy podwoimy szerokość schowka i pamięci, przepustowość pamięci się podwoi

- z pamięcią 2 słów, kara chybień w naszym przykładzie spadłaby z 256 cyklów zegarowych do 128 (potrzebujemy połowę dostępu do pamięci i przepustowość wynosi ¼ bajta na cykl zegarowy.)

29.

Interleaving - przeplatanie

Pytanie; co może kupić przeplatanie i szeroka pamięć?

31.

Pamięć wirtualna

Pamięć wirtualna dzieli pamięć fizyczną na bloki i alokuje je na różne procesy
2 hierarchie poziomów pamięci są kontrolowane przez pamięć wirtualną (DRAM i dyski magnetyczne)
Pamięć wirtualna dzieli chronioną przestrzeń pamięci, automatycznie zarządza hierarchią pamięci i ułatwia ładowanie programu do wykonania
Program może być umiejscowiony obojętnie gdzie w pamięci fizycznej lub dysku poprzez zmianę mapowania pomiędzy nimi (relokacja)
Są 2 klasy pamięci wirtualnej: stronicowanie (metoda przyznawania pamięci) ze stałą wielkością bloków (do potęgi 2) i segmentacja ze zmienną wielkością bloków.

32.

Przydatne definicje:

-Strona lub segment są używane dla bloków pamięci.

-błąd strony lub błąd adresu jest używany dla chybień.

-CPU używa wirtualnych adresów, które są tłumaczone przez kombinację sprzętu i oprogramowania na fizyczne adresy, co daje dostęp do pamięci głównej.

-powyższy proces nazywany jest mapowaniem pamięci lub tłumaczeniem adresu.

33.

Różnice pomiędzy stronicowaniem a segmentacją

Strona segment

Słowa na jedno dwa (segment i przesunięcie)

adres

widoczny niewidoczny dla programatora

programator? aplikacji

wyk.8, Informatyka PWr, Algorytmy i Struktury Danych, Architektura Systemów Komputerowych, Assembler, wykłady - Assembler