On 05.10.2014 13:16, 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.

Zapominasz o jednym. Odczyt jednego bajtu z ramu zajmuje niemal
tyle samo czasu co odczyt 128 bajtów. Sczytuje się wiec na raz
całą linię cache albo i więcej (nie wiem, co w tej dyskusji robi
słowo "strona").

Wyobraź sobie, że składasz wibratory na atmega.

Bez cache zamawiasz w TME jedeną sztukę. Przychodzi za tydzień.
lutujesz w kilka godzin, zamawiasz kolejną, przychodzi za tydzień.

Z cache zamawiasz na raz 200 procków. czekasz tydzeiń, Lutujesz
100 ... sztuk produktu w trzy tygodnie (bo po zlutowaniu sięgnięcie
na półkę po następny procek zajmuje 30s, a nie tydzień) i zamawiasz
kolejne 200, czekasz tydzień na dostawę.

Dodatkowo dla dostępu sekwencyjnego mamy coś takiego jak prefetching,
albo Ty mozesz przewidzieć, żę potrzebujesz jeszcze wiećej niż
standardowa paczka i zamawiać na przyszłość, albo i sam dostawca
zauważa schemat i podsyła Ci pod dzwi kolejną paczkę.


Bez cache zawsze byłoby wolniej. Sprowadzenie bajtu czy całej linii to
tyle samo roboty, a jeśli linię zapamiętamy sobie w podręcznym
schowku, to być mozę się te dane za moment przydadzą. Jeśli tak, mamy
je natychmiast, jeśli nie, strata jest pomijalna.


Musisz pozbyć się wyobrażenia z 8051, gdzie zapytanie XRAM o komórkę
pamięci to dwa (nie pamietam dokłądnie) cykle procesora. W ciagu
Zapytanie współczesnego szybkiego procesora (x86, ARM) o pamieć
z ram to wysłanie listu z zapotrzebowaniem do magazynu na drugim
końcu kraju. Aby działać sprawnie, trzeba trochę energii poświęcić
na logistykę.


>> 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?

Pleciesz. Tablica translacji nie ma nic wspolnego z przewidywaniem
skoków.


> Czyżby kompilator najpierw
> wykonywał wszelakia możliwe obliczenia, a następnie odpowiednio to
> kompilował? David Copperfield?

O przywidywaniu skoków, nie tablicy translacji.

Nie. Procek zgaduje. Jeśli ostatnio 10 razy test na mniejszość wypadł
pozytywnie, to zakłada, ze tak dalej będzie.
Pod koniec pętli for oczywisćie to zgadniecie jest niepoprwne.
I co z tego, sprowadziliśmy pamięć, która była niepotrzebna.
Jakbyśmy tego nie zrobili, zużylibyśmy mniej prądu, ale nic
dla samych obliczeń się nie zmieni, i tak musimy sprowadzić jakieś
inne dane.


>> 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.

A moze byś jednak wziął internet i go poczytał;-)

Nikt nie mówił o kompilatorze. On to tez robi, ale niezależnie.
Ustawia tam skoki, aby skok wymagany był w mniej prawdopodobnym
przypadku.

Co jest prawdopodobne? Możesz kompilatorowi powiedzieć, a możesz
postestować. poczytaj o :
-fprofile-generate
-fprofile-use

Ale to zupełnie inny mechanizm niż przewidywanie skoku przez procek.



>
> Ano właśnie ta magia.. Na czym owa predykcja polega? Może się mylę,
> ale coś mi tu pachnie marketingowym bełkotem.

Mylisz się. Niech by ta predyckja działałą 50/50, już byłaby
korzyść. Jeśli jakieś cześci procesora nic nie robią w jakejś
chwili, niech robią choćby coś, co się przyda na 50%.
A w takiej pętli po 1010 elementów predykcja trafi ~1000 razy.


>
>> 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ę.

Zobacz, jak BLAS(i praktycznie wszystko) trzyma macierz.


>> 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ę.

Jeszce lepiej. Napisz mnożenie macierzy. C=A*B.
będziesz miał tam trzy pętle
for i
for j
for k

Poprzestawiaj kolejność pętli (zachowując sens matematyczny),
przyszpieszenie potrafi być 10 krotne*).
Jeszcze bardziej dopieszczając traktowanie cache można zbić prędkość
3 razy*) prostą pętlą i kolejne 4 razy*) jak naprawdę wiesz, co robisz
(czytaj, biblioteka).
http://wazniak.mimuw.edu.pl/index.php?title=MN06

*) konkretne wartosći przyszpieszń mocno zależą od procesora.
Jak testowałem cuit inne wyniki były.


> 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?

Jakim znowu stronnicowaniem? Sprawdź, co znaczy to pojęcie,
a o czym tu rozmawiacie.

> Kompilator to zrobi za mnie? Nie wierzę !!

Nie wierzę w to kierowanie przez GPS. Skąd mechanik
auta ma wiedzieć, gdzie będę jechać!!

Procesror i kontroler pamięci to za Ciebie robi, nie kompilator.

pzdr
bartekltg