s...@g...com wrote:

> W dniu niedziela, 5 października 2014 12:01:53 UTC+2 użytkownik Jacek
> Radzikowski napisał:
>> Zarządzanie zawartością pamięci cache to bardzo skomplikowany temat, na
>>
>> którym zrobiono wiele doktoratów i sporo zostanie zrobionych w
>> przyszłości.
>>
>> W skrócie wygląda to tak, że zawartość cache nie odwzorowuje liniowo
>> jednego
>>
>> wielkiego obszaru pamięci, a wiele stosunkowo niedużych stron. Strony
>>
>> sąsiadujące ze sobą w cache mogą w pamięci głównej być położone daleko od
>>
>> siebie.
>
> Fakt, że nie jest to odwzorowanie "wielkiego" obszaru pamiąci jest
> oczywisty. Natomiast mechanizm kojarzenia stron jest dla mnie
> niezrozumiały. Od strony HW, mamy jakiś tam adres zapisany na n-bitach.
> Jasne, że możemy ten adres w przypadku "dużych" pamięci podzielić na
> strony, bądź innymi słowy na kostki pamięci. OK, no ale wtedy cykl dostępu
> do pamięci to 2 kliknięcia zegarka na licznik adresowy, bądź 2 rozkazy
> zapisu od strony procka do jakiegoś tam rejestru adresowego. O co mi
> chodzi? Nosz kurdelebelans, nie da się z jednej kostki odczytać w tym
> samym czasie danych z 2-ch różnych adresów!! No bo niby jak ? Zakładam że
> kostka ma liniową przestrzeń adresową A(N downto 0). Szerokość słowa
> danych nie ma znaczenia.

Dzięki temu że pamięć cache jest szybka i lokalna dla rdzenia, nie zajmuje
ani trochę czasu.
Mechanizm "klasyczny" jest dość prosty. Procesor chcąc odczytać komórkę
pamięci wystawia adres na szynę adresową. Ta nie jest podpięta bezpośrednio
do pamięci RAM, a do układu zarządzającego cache. Adres jest dzielony na
logiczne kawałki: w dużym uproszczeniu wygląda to tak, że najmłodsze bity
określają przesunięcie na stronie, a starsze numer strony. Trochę jak
intelowe offset i segment, ale sensowniej zrobione.
Numer strony jest porównywany z numerami stron ściągniętymi do cache, i
jeśli strona jest załadowana, odpowiednia wartość jest zwracana do
procesora, a jeśli nie - układ (podkreślam że to jest układ, program nic o
tym nie wie) zarządzania cache ściąga stronę z pamięci wyższego poziomu
(czyli kolejny poziom cache, albo pamięć RAM.)

Jeśli strona siedzi w cache to cała procedura nie zajmuje nawet jednego
cyklu zegara. Dzieje się tak dlatego, że tablica translacji jest
zaimplementowana jako pamięć asocjacyjna - taka sprzętowa baza danych
adresowana zawartością. Na wejście podajesz numer strony do której się
odwołujesz, na wyjściu otrzymujesz albo informację gdzie ta strona jest w
cache, albo że jej nie ma. To w którym wierszu tabeli ta informacja jest
zapisana nie ma najmniejszego znaczenia.


>> Tym żeby wiedzieć jaki adres w cache odpowiada adresowi w pamięci
>>
>> zajmuje się tablica translacji.
>
> A skąd owa tablica ma wiedzieć o wynikach działania programu/obliczeń i
> jak przypisać skoki tam gdie trzeba? Czyżby kompilator najpierw wykonywał
> wszelakia możliwe obliczenia, a następnie odpowiednio to kompilował? David
> Copperfield?

W nowych procesorach może to wyglądać na sztuczki magiczne, ale magii tam
nie ma. Tablica translacji jest uaktualniana przez układ zarządzania cache
który wie dokładnie które strony są załadowane do cache i pod jakimi
adresami. Ani kompilator ani procesor nie muszą o tym wiedzieć.


>> Jeśli strona do której procesor chce się odwołać nie znajduje się w cache
>> -
>>
>> wykonanie programu jest wstrzymywane i strona jest ładowana. To, którą
>>
>> stronę w cache zastąpić nową zawartością - to jeden z tematów na
>> doktorat.
>
> Bez jaj. Tego się nie da zrobić w sposób predykcyjny z poziomu
> kompilatora. Jeżeli ktoś podejmie się takiego doktoratu, to równie dobrze
> może się chwycić za doktorat z wróżenia z fusów.

To nie kompilator. Ten mechanizm jest wbudowany w krzem.
Najprostszy manager cache reaguje na to co procesor chce odczytać i ściąga w
razie potrzeby. Doktoraty są robione na "wróżeniu z fusów" które pomoże
ściągnąć stronę do cache zanim faktycznie będzie potrzebna.


[...]

>> Że to wszystko wymaga czasu - no cóż, "taką mamy pamięć". Dlatego szybkie
>>
>> procesory mają po kilka poziomów pamięci cache o różnych szybkościach,
>>
>> dlatego rozdziela się cache programu i danych. Temu też służą algorytmy
>>
>> przewidywania skoków i cała masa innej magii zaimplementowanej w
>> nowoczesnym
>>
>> procesorze.
> Ano właśnie ta magia.. Na czym owa predykcja polega? Może się mylę, ale
> coś mi tu pachnie marketingowym bełkotem.

To nie jest bełkot marketingowy, a jeden (kilka?) z doktoratów. Nie wiem jak
to działa w szczegółach, ale polega mniej-więcej na tym że jak układ
sterujący wykonaniem rozkazów widzi w kolejce instrukcję skoku to będzie się
starał przewidzieć która strona pamięci będzie potrzebna i zleca układowi
cache żeby ją ściągnął. W ostateczności może zawsze upewniać się że dostępny
jest kod dla obydwu wariantów, ale to jest bardzo naiwne i nie-ekonomiczne
podejście.


>> Na szybkość działania programu bardzo duży wpływ ma też to jak
>> zaplanujesz
>>
>> dostępy do pamięci. Numerycy bardzo nie lubią operować na tablicach
>>
>> wielowymiarowych, bo to potrafi dodać sporo niepotrzebnych przeładowań
>>
>> stron.
>
> Hah!! Właśnie ja tak robię. Dzięki paru GB pamięci, DSP mogę robić na
> najpodlejszym laptopie w czasie rzeczywistym.

Gratuluję odkrycia jednej z najprostszych optymalizacji możliwych do
zaimplementowania na etapie projektowania struktur danych :)


>> Zamiast tego indeksy są mapowane do liniowego obszaru pamięci i jak
>>
>> trzeba obliczyć stan w następnym kroku symulacji - solwer jedzie po
>>
>> kolejnych komórkach nie troszcząc się o indeksy (oczywiście wszystkie
>> dane
>>
>> wejściowe są odpowiednio przygotowane).
>
> Upsss.. Nie za bardzo kojarzę.

Tablica ma rozmiar A x B. Odwołujemy się do elementu (i, j). Adres elementu
w przestrzeni liniowej przy zapisywaniu danych wierszami to k = (j * A) + i


>> Zrób kiedyś eksperyment: zaalokuj wielką tablicę dwu-wymiarową i
>> przeskanuj
>>
>> ją iterując najpierw po wierszach później po kolumnach, a później odwróć
>>
>> kolejność iteracji: najpierw po kolumnach później po wierszach.
>> Przekonasz
>>
>> się o ile szybciej program będzie działać kiedy będziesz odwoływać się do
>>
>> pamięci bez skakania po stronach.
> Bez jaj !! Poważnie? Kurde, zrobię taki eksperyment, ale aż wierzyć mi się
> nie chce. Załóżmy że masz rację. No ale wróćmy do realu. Załóżmy że
> potrzebuję w koło macieju w jakiejś tam pętli odczytywać dane pomiarowe, z
> tych danych jest tworzona macierz (NxN), robimy z niej macierz odwrotną,
> następnie wykonujemy jakieś tam czary mary na elementach a(i,j), potem
> liczymy z tego wyznacznik i cholera wie co jeszcze. No i jak w takim
> burdelu mam zapanować nad stronicowaniem? Kompilator to zrobi za mnie? Nie
> wierzę !!

Kompilator może tak ułożyć kod żeby podprogram wykonywany przez dłuższy czas
w całości zmieścił się w cache. O tym żeby dane były tak ułożone musisz sam
zadbać. Poczytaj sobie o cache locality (możesz zacząć tutaj:
http://stackoverflow.com/questions/12065774/why-does
-cache-locality-matter-for-array-performance)
Ani kompilator ani Ty nie musicie się przejmować panowaniem nad
stronicowaniem. To jest robota układu zarządzania cache zaszytego w krzemie
tuż obok rdzenia procesora.


> Cholera, na grupie elektronicznej w zasadzie zjechaliśmy na matematykę.
> Ale cóż, nowoczesna elektronika bez matematyki/algorytmiki nie może
> funkcjonować.

Jak czytam wywody niektórych elektroników to chętnie bym wysłał ich na kurs
podstaw inżynierii programowania. Lekkie poszerzenie horyzontów na pewno nie
zaszkodzi :)

pzdr.
j.