Architektura komputerów 2
Prof. PWr dr hab. inż. Janusz Biernat
Wykład 09
BUFORY PAMI
CI
Bufor zawiera kopie aktualnie przetwarzanych danych.
organizacja sekwencyjne  kolejka
" bufor rozkazów (instruction queue), bufor zapisów (write buffer)
organizacja blokowo-skojarzeniowa
" pamięć podręczna (cashe memory)  zawiera kopie używanych danych
organizacja skojarzeniowo-sekwencyjna
" bufor przywracania kolejności (reorder buffer) (PISO parallel-in serial-out)
Bufor programowy jest niewidoczny z poziomu użytkownika, służy do przechowywania trwałych
kopii danych lub do przygotowania trwałych kopii danych do użycia. (na wyjściu przerzutnika jest
bramka trójstanowa  albo stan logiczny albo stan wysokiej impendancji czyli bufor wyłączony), do
adresów bufory jednokierunkowe, do danych bufory dwukierunkowe. Buforów używa się tam gdzie
z dużym prawdopodobieństwem można przewidzieć jakie słowa z pamięci będą kolejno potrzebne.
Mogą być w nich też przechowywane stałe dane przeznaczone do póz
niejszego użycia.
Najczęstszym przykładem są bufory magistrali, które zbierają dane i wysyłają je dopiero gdy
zbierze się ich odpowiednio dużo.
Transmisja kolejnej paczki do kolejki odbywa się zazwyczaj kiedy połowa kolejki jest pusta
(najwięcej 7 elementów kolejki, czyli puste 4 transmitowane blokowo).
Bufor skojarzeniowo-sekwencyjny zapewnia kolejność rozkazów zgodną z algorytmem, można
byłoby to pominąć gdyby w systemie nie byłoby przerwań, ale ponieważ są, to należy mieć
pewność, że mozna będzie powrócić do wcześniej wykonywanego miejsca programu. Najwięcej
czasu zajmuje dostarczenie kodu (programu i danych) do procesora.
Zasada lokalności odwołań
W komputerze z programem zintegrowanym programy i dane majÄ… tendencjÄ™ do skupiania w
wymiarze przestrzennym i czasowym.
lokolność przestrzenna (spatial locality)
Jest prawdopodobne użycie informacji z sąsiednich lokacji pamięci.
" kody rozkazów  zależność lokacyjna sekwencyjna (licznik rozkazów)
" struktury danych  skupione (zmienne robocze) lub regularne (tablice)
lokalność tymczasowa (temporal locality)
Kod użyty będzie zapewne ponownie użyty w nieodległym czasie.
" kody rozkazów  pętle programowe
" struktury danych  zmienne robocze: ciągle używane
- struktury regularne: wielokrotne użycie elementów
WNIOSEK: Utworzyć w pobliżu procesora bufor zawierający kopie danych z pamięci (głównej)
aktualnie używanych i korzystać z kopii zamiast oryginału.
Programem bez lokalności jest taki, w którym po każdej instrukcji występuje skok bezwarunkowy.
Lokalność jest też obniżana przez używanie rejestrów zamiast zmiennych indeksowanych.
Programy  nielokalnościowe możemy też wykorzystać do  fałszywych benchmarków , bo w
takich programach bufory będą puste (albo prawie puste), co będzie miało widoczny wpływ na
szybkość ich wykonania. Prawdopodobieństwo, że dwa sąsiednie rozkazy są ze sobą powiązane to
ok. 70%, trzy - 30%, cztery - 5%.
Zasady użycia buforów cashe
użycie bufora musi być przez
roczyste dla programu
" niewidoczne na poziomie ISA (listy rozkazów),
" realizowane na poziomie HSA (organizacji procesora/komputera)
!!sposób wykonania rozkazu nie może być zależny od obecności bufora, ale czas wykonywania
rozkazu w obecności bufora powinien być krótszy.
!!użycie bufora pamięci podręcznej nie otwiera osobnej przestrzeni adresowej -> nie są potrzebne
specjalne rozkazy dostępu do bufora.
bufor pamięci podręcznej powinien
" być wykonany w szybszej technologii (statycznej)
" być umieszczany w bezpośrednim sąsiedztwie procesorach
" bufor umożliwia wykorzystanie zalet szybkich pamięci statycznych i pojemnych lecz
wolnych pamięci dynamicznych.
Bufor nie może być strukturą uporządkowaną (bo to że kilka rozkazów będą kolejno w pamięci jest
prawdopodobne, to, że wszystkie będą jest całkowicie nieprawdopodobne), dlatego musimy dla
obszarów spójnych (danych) musimy stworzyć etykiety.
Skuteczność bufora cashe
Zasada lokalności nie gwarantuje obecności kopii danych w buforze cashe.
Skuteczność użycia pamięci podręcznej zależy od organizacji (struktury) bufora.
Ilościowa ocena skuteczności:
" współczynnik trafień (hit rate) h
" współczynnik chybień (miss rate) m=1-h
" tmp - średnia strata czasu w razie chybienia (miss penalty)
Średni czas dostępu do pamięci
" w pamięci jednopoziomowej
ta=śą1-mźątcaƒÄ…mśątramƒÄ…tmpźą
L1‚" L2
" w pamięci dwupoziomowej (inkluzywnej - )
ta=śą1-m1źątca1ƒÄ…śąm1-m2źąśątca2ƒÄ…tmp1źąƒÄ…m2śątramƒÄ…tmp1ƒÄ…tmp2źą
m1ąm2 , bo każde trafienie w L1 jest trafieniem w L2, a każde chybienie w L2 jest
(
chybieniem w L1)
Organizacja pamięci podręcznej
Konieczna jest identyfikacja kopii w buforze cashe:
" jedynym identyfikatorem danej (także kodu rozkazu) jest adres
" kopiowanie pojedynczych bajtów/słów jest sprzeczne z zasadą lokalności  jedna lokacja
(linia) w buforze zawiera wiele bajtów/słów
" jednorodna struktura ułatwia identyfikację, upraszcza i przyśpiesza dostęp  ustalony
rozmiar pojedynczej lokacji (linii) w buforze
Schemat organizacji bufora pamięci podręcznej
Etykieta obecności jest bezwzględnie konieczna żeby nie wykonywać przypadkowych rozkazów
lub nie używać nieaktualnych danych w pewnym momencie może się pojawić zapotrzebowanie na
dane nieobecne w buforze, a bufor jest pełny, trzeba zastosować jakiś sposób zarządzania
zawartością bufora.
Organizacja odwzorowania danych w pamięci podręcznej
" linia  jednostka wymiany danych między buforem a pamięcią główną
" rozmiarem lokacji powinno być s=2k bajtów/słów (linia wymiany)
ć% przestrzeń adresowa procesora = suma rozłącznych linii
ć% identyfikatorem lokacji w buforze może być skrócony adres
ć% przestrzeń adresowa procesora = suma rozłącznych linii
#log2 N #
" czas wyszukiwania w buforze (zbiór nieuporządkowany) - (N-liczna linii) ->
optymalny rozmiar bufora N =2n linii
Odwzorowanie (i(B)  linia w buforze, r(P)  linia w pamięci głównej)
`" `"
BUFOR(linia i(B)) BUFOR(linia i(B) j(B))
PAMI
Ć -> BUFOR; identyfikator || [linia i(B)] = adres (linia r(P)) || [linia r(P)]
Jeśli s=2k bajtów, to adres linii = bity adresu bez k najniższych.
Jednostka informacji w buforze cashe jest większa niż 1 słowo, bo jeżeli używamy jedno słowo, to
istnieje duże prawdopodobieństwo, że będziemy używać zaraz następne lub poprzednie.
Max rozmiar jednostki informacji -> względy konstrukcyjne, np. procesor PENTIUM II+ ma 64-
bitową magistralę danych (8 bajtów = 2 słowa) oraz zdolność transmisji blokowej 4x64b (8 słów)
(nie koniecznie trzeba używać 8 słów, bo może się to okazać za dużo, ale kilka słów należy.
Wyróżniamy tryby transmisji pojedynczej i wielokrotnej. W tej pierwszej za jeden adres
otrzymujemy jedną daną (słowo), podczas gdy w tej drugiej - za jeden adres mamy parę słów.
Zaletą jest to, że koszt wyciągnięcia danych (jednego słowa) z pamięci spada do ok. 1,25 cyklu.
kilka słów ( ą1,d"8 ): 2/4/8
jednostka  8 słów
Charakterystyki skuteczności
" większa liczba linii (N)  lepsza lokalność czasowa
" większy rozmiar linii (s)  lepsza lokalność przestrzenna
" dla ustalonej pojemności, ze zwiększeniem rozmiaru linii, dominujący staje się wpływ
znikania lokalności czasowej i następuje wzrost strat czasu w razie chybienia (czas wymiany
jest proporcjonalny do liczby transferów)
ta
Zależność współczynnik chybień m i średniego czasu dostępu do pamięci od rozmiaru linii s
dla ustalonej pojemności C=s*N bufora cashe.
Jeżeli w buforze nie ma wszystkich potrzebnych danych to procesor z buforem jest wolniejszy od
procesor bez bufora.
Jak taki bufor zorganizować?
ORGANIZACJA BUFORA CASHE
całkowity nieporządek  odwzorowanie bloków pamięci głównej w cashe jest całkowicie losowe,
cena: bardzo długi czas wyszukiwania
totalny porzÄ…dek  odwzorowanie deterministyczna: podzbiorom linii przypisujemy 1 konkretnÄ…
lokację w buforze, zaleta: łatwość, wada: efekt ping-ponga.
jak uzyskać ten totalny porządek:
1) odwzorowanie z przeplotem (niewielki spadek lokalności czasowej), kolejne linie w kolejnych
miejscach bufora, ale jeżeli chcemy używać równocześnie np. pierwszych linii z 2 bloków to jest to
niemożliwe -> efekt ping-ponga.
2) odwzorowanie bez przeplotu -> tu gubimy lokalność przestrzenną (bo sąsiedniość 2 sąsiednich
linii znika)
Jedno i drugie rozwiązanie ma wady. Dużą zaletą przyporządkowania z i bez przeplotu jest
stosunkowa łatwość ich adresowania, jako że adres będzie się składał kolejno z numeru grupy,
następnie numeru podzbioru i numeru bajtu.
Kompromis:
uporzÄ…dkowany system,
nieuporzÄ…dkowanych
wewnętrznie bloków (czas jest
niewiele dłuższy jeżeli chodzi
o wyszukiwanie, a nie ma
efektu ping-ponga)