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

> W dniu niedziela, 5 października 2014 11:01:21 UTC+2 użytkownik Jacek
> Radzikowski napisał:
>> s...@g...com wrote:
>>
>>
>>
>> > W dniu niedziela, 5 października 2014 01:47:28 UTC+2 użytkownik Jacek
>>
>> > Radzikowski napisał:
>>
>> >
>>
>> >> Jak już wspomniał Andrzej, w takim przypadku strona pamięci z danymi
>>
>> >>
>>
>> >> zostanie przepisana do pamięci cache i problem jednoczesnego dostępu
>> >> do
>>
>> >>
>>
>> >> zewnętrznej kostki przestanie istnieć.
>>
>> >>
>>
>> >
>>
>> > Dlaczego?! Cóż tam za magia jest zaszyta w tym cache'u, że pozwala na
>>
>> > jednoczesny dostęp do dwóch albo i więcej(ilość rdzeni/wątków) adresów
>>
>> > jednocześnie?
>>
>>
>>
>> L1 jest najczęściej do wyłącznego użytku rdzenia. A jeśli nie - to działa
>>
>> mechanizm identyczny do opisanego. Z tą drobną różnicą że pamięć cache
>> jest
>>
>> o wiele szybsza i przestoje są krótsze.
>>
>
> OK, czas dostępu do cache jest argumentem przekonywującym. Zapomnijmy na
> chwilę o wielowątkowości/wielordzeniowości. A co w przypadku jeżeli mamy
> program, którego kod znacznie objętościowo przekracza pojemność cache'a? A
> z reguły tak jest. No i teraz w wyniku działania programu przy spełnieniu
> jakiś tam warunków mamy dłuuuugie skoki do innej części kodu? Nie mam
> zamiaru się tutaj wymądrzać i deprecjonować sensu pakowania cache'a do
> procka, ale czy zawsze ten mechanizm jest porządany? No bo w przypadku
> dłuuugich skoków o ile dobrze rozumiem pamięć cache powinna być
> przeładowana na nowy obszar kodu. No a to przeładowanie, to jakby na to
> nie patrzeć zaś komunikacja z pamięcią zewnętrzną, a co za tym idzie zaś
> trzeba na to trochę czasu... Bilans zysków i strat wydaje mi się może być
> przy spełnieniu pewnych warunków wręcz niekorzystny. Tak se gdybam...

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. Tym żeby wiedzieć jaki adres w cache odpowiada adresowi w pamięci
zajmuje się tablica translacji.
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.

Oddzielnym zagadnieniem jest synchronizacja zapisywanych danych. Nie może
dojść do sytuacji że jeden procesor zapisze coś do do pamięci, ale to utknie
w jego lokalnym cache i inny procesor będzie dalej czytać starą wartość. Na
to poświęca się sporą część z tych milionów tranzystorów jakie są pakowane w
krzem.

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

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

pzdr,
j.

do góry

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.

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

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

>
>
>
> Oddzielnym zagadnieniem jest synchronizacja zapisywanych danych. Nie może
>
> dojść do sytuacji że jeden procesor zapisze coś do do pamięci, ale to utknie
>
> w jego lokalnym cache i inny procesor będzie dalej czytać starą wartość. Na
>
> to poświęca się sporą część z tych milionów tranzystorów jakie są pakowane w
>
> krzem.
>

To jest oczywiste. Implikacja tego co napisałem wcześniej.

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

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

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

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

==============

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

do góry

On 05.10.2014 00:25, s...@g...com wrote:
> .. i do tego programowanie wielowątkowe. Ja tu czegoś nie rozumiem.
> Weźmy na przykład program do obliczenia sumy liczb od 1 do N. Ot,
> zwykły ciąg arytmetyczny S(N)=N*(N+1)/2. Zakładając, że wzoru nie
> znamy, zlecamy to kompowi. Soft jest banalny:
>
> s:=0; for i:=0 to N do begin s:=s+1; end;
>
> Powyższe jest nasmarowane w Pascalu, którego składnia jest podobna
> do C, ino jest to bardziej czytelne.

Odpowiedź napiszę po po łacinie, jest częściowo podobna do polskiego,
ale bardziej zwięzłą ;-)

> Nie w tym rzecz.. Rozbijmy to na 2 wątki:
>
> 1) s1:=0; for i:=0 to k do ........... .......... 2) s2:=0; for
> i:=k+1 do ............. ..............
>
> Wiasomo o co biega,no i na koniec s:=s1+s2. Czyli wykonujemy jak
> gdyby 2 programy na 2-ch różnych kompach, kompilator ładnie nam to

Nie jest to do końca równoznaczne z dwoma różnymi kompami.
Pewne rzeczy nadal są wspólne, jak L2 i L3 czy rurka łącząca
cache z RAM.

> rozdzielił i klawo jak cholera. No to teraz skomplikujmy zagadnienie
> ciuta bardziej.. Chcemy policzyć sumę wyrazów jakiegoś ciągu,
> którego wyrazy są zapisane w wektorze A[i] (i=0..N). Robimy zaś 2
> wątki:
>
> 1) s1:=0; for i:=0 to k do begin s1:=s1+A[i]; end;
>
> 2) s2:=0; for i:=k+1 to N do begin s2:=s2+A[i]; end;
>
> s:=s1+s2. A co jeżeli elementy ciągu A[m] i A[n] są zapisane
> fizycznie w tej samej kostce pamięci? Co w takiej sytuacji dają mi 2
> rdzenie?

Nie wiem, co to jest kostka pamięci. To naprawdę zależy od tego, na
czym piszesz. Niby grupa elektronika, ale zakładam, że to x86/x64,
arm będzie miał podobnie, 8051 miał tylko jeden rdzeń ;-)

Tak więc dane siedzą w RAM.
Jeśli operacja jest szybka, jak dodawanie, najbardziej kosztowną
operacją będzie sprowadzenie danych da cache. I tutaj wiele
rdzeni praktycznie nic nie pomaga, bo rurka RAM-cache jest jedna,
i ma ograniczoną przepustowość *)

Jeśli operacja jest bardziej skomplikowana i zajmuje dużo czasu,
możesz mieć przyspieszenie nawet do x(ilość rdzeni).


*) A przynajmniej tak mi się wydaje, chyba jednak czegoś nie wiem;-)

#include <iostream>
#include <chrono>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;


class stoper
{public:
chrono::time_point<chrono::high_resolution_clock> a,b;
void start(){a = chrono::high_resolution_clock::now();}
void stop() {b = chrono::high_resolution_clock::now();}
void show()
{
chrono::duration<double> elapsed_seconds = b-a;
cout << elapsed_seconds.count()<<"s "<<endl;
}
};


const int N = 1000000000; //tak, uwaga 4GB

int main()
{
vector<int> tab(N,0);

stoper st;

for (int i=1;i<N;i++)
{
tab[i] =(i+167489)*i+1647;
}

st.start();
int64_t aku1=0, aku2=0,aku3=0, aku4=0, aku0=0;


for (int i=0;i<N;i++)
{
aku0+=tab[i];
}

st.stop();
st.show();
cout<<aku0<<endl;

st.start();

#pragma omp parallel sections
{
#pragma omp section
{
for (int i=0;i<N/4;i+=1)
{
aku1+=tab[i];
}
}
#pragma omp section
{
for (int i=N/4;i<N/2;i+=1)
{
aku2+=tab[i];
}
}
#pragma omp section
{
for (int i=N/2;i<3*(N/4);i+=1)
{
aku3+=tab[i];
}
}
#pragma omp section
{
for (int i=3*(N/4);i<N;i+=1)
{
aku4+=tab[i];
}
}

}
st.stop();
st.show();
cout<<aku1+aku2+aku3+aku4<<endl;
return 0;
}


wynik:
1.12046s
-5376503094895
0.371874s
-5376503094895

Przyspieszyło trzykrotnie na 4 rdzeniach.

Jednak każdy rdzeń ma własną rurkę, czy automatyczny prefetching
daje ciała?



Gdzie indziej:
On 05.10.2014 00:25, s...@g...com wrote:
> W dniu niedziela, 5 października 2014 00:41:48 UTC+2 użytkownik A. L.
> napisał:
>> On Sat, 4 Oct 2014 15:25:04 -0700 (PDT), s...@g...com wrote:
>>
>
>>
>> A o czyms takim jak "cache memory" slyszales? Poczytaj sobie cos o
>> architekturze procesora wielordzeniowego
>>
>
> Pamięć cache to też taka "kostka" tyle że zaszyta w kostce procka. No
> i co w sytuacji, gdy 2 procesory odwołują się jednocześnie do dwóch
> różnych adresów w obrębie tej pamięci?

I właśnie na to pytanie odpowiedź znajdziesz, czytając o cache.

L1 każdy procek ma własne. Te same dane mogą być w cache każdego
rdzenia i być swobodnie czytane, nie przeszkadza to nikomu.
Jeśli ktoś jednak zmodyfikuje coś, informacja o tym wędruje
po procesorze i jeśli inny rdzeń będzie chciał odczytać tę informację,
zobaczy, że jest ona oznaczona jako 'nieaktualna' i ściągnie ją raz
jeszcze z wyższego poziomu.

Oczywiście, nie zabezpiecza to przed race condition, stąd potrzeba
użycia przy zapisywaniu i odczytywaniu tych samych danych poprzez różne
wątki tej całej zoologii narzędzi rozproszonych;)


pzdr
bartekltg

do góry

s...@g...com pisze:
[..]
> Pamięć cache to też taka "kostka" tyle że zaszyta w kostce procka. No i co w
sytuacji, gdy 2 procesory odwołują się jednocześnie do dwóch różnych adresów w
obrębie tej pamięci?

Porównaj szybkość pamięci cache i zewnętrznej.

--
AlexY
http://faq.enter.net.pl/simple-polish.html
http://www.pg.gda.pl/~agatek/netq.html

do góry

W dniu niedziela, 5 października 2014 14:30:25 UTC+2 użytkownik bartekltg napisał:
[ciach]

Wyciachałem, coby poprzez zmniejszoną ilość tekstu dalsza dyskusja była bardziej
czytelna. Zarówno dla mnie, dla Ciebie i Zainteresowanych wątkiem. Szczególy są do
odczytania w poprzednich wpisach.

1) Dzięki za podany przykład w języku krzaczastym (C, znasz moje zdanie w tym
temacie, ale proszę nie "uruchamiajmy" się w dyskusję Pascal/C, bo będzie
awantura/pyskówa).

2) Napisałeś jak to napisać, aby działało zgodnie z oczekiwaniem programisty. Chyba
mnie nie zrozumiałeś. To nie chodzi o to że a^2+b^2=c^2, tylko DLACZEGO a^2+b^2=c^2
!! Chodzi o to magiczne słowo "dlaczego?".

Wiem, że nie wiem jak w szczegółach działa mechanizm multicore/multithreade.

Odnoszę wrażenie, że umiesz ten mechanizm wykorzystywać, ale jak to funguje to chyba
podobnie jak i ja za bardzo nie wiesz. Ot jak moja Kobita. Autem jeździ, ale zasady
działania silnika nie zna.

do góry

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

do góry

On 05.10.2014 15:01, s...@g...com wrote:
> W dniu niedziela, 5 października 2014 14:30:25 UTC+2 użytkownik
> bartekltg napisał: [ciach]
>
> Wyciachałem, coby poprzez zmniejszoną ilość tekstu dalsza dyskusja
> była bardziej czytelna. Zarówno dla mnie, dla Ciebie i
> Zainteresowanych wątkiem. Szczególy są do odczytania w poprzednich
> wpisach.

Wycinanie wycinanienm, wazne, czy przeczytałeś.

> 1) Dzięki za podany przykład w języku krzaczastym

Język językiem. Przeanalizowałeś?

> 2) Napisałeś jak to napisać, aby działało zgodnie z oczekiwaniem
> programisty. Chyba mnie nie zrozumiałeś. To nie chodzi o to że
> a^2+b^2=c^2, tylko DLACZEGO a^2+b^2=c^2 !! Chodzi o to magiczne
> słowo "dlaczego?".

Dlaczego co? W zapędach wycinania wyciąłeś pytanie.


pzdr
bartekltg

do góry

Dnia Sun, 5 Oct 2014 04:16:25 -0700 (PDT), s...@g...com
> W dniu niedziela, 5 października 2014 12:01:53 UTC+2 użytkownik Jacek Radzikowski
napisał:
> 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

To robi sprzet a nie program. Ale owszem, trwa.

> kurdelebelans, nie da się z jednej kostki odczytać w tym samym
> czasie danych z 2-ch różnych adresów!! No bo niby jak ?

No, pamieci dwuportowe sa, moga byc i wiecej portowe, ale glowny RAM
taki nie jest. Natomiast cache ... kto wie.

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

Nie, to sie dzieje automatycznie.

Masz pamiec cache C, moze i 32-bit, ale podzielona na ramki po np 16
bajtow. Adres w niej dzielimy bitowo na f:w, gdzie f to nr ramki, a w
- slowa/bajtu w ramce. Podobnie pamiec glowna R, gdzie adres dzielimy
na p:f:w.
f i w w obu pamieciach sa takie same, wiec kazda ramka f:* w C jest
przypisana do jednej z mozliwych lokalizacji *:f:* w pamieci R.
Do ktorej aktualnie - to jest zapisane w osobnej pamieci S, ktora
przechowuje starsza czesc adresu p.

No i teraz - jak procesor ma potrzebuje siegnac do jakiegos adresu
pamieci, to dzieli go na p:f:w, odczytuje S(f), i jesli tam jest
akurat p, to wie ze moze odczytac z pamieci C(f:w).
A jesli nie ma, to przepisujemy cala ramke R(p:f:*) do cache C(f:*),
a do S(f) zapisujemy p. I nastepnym razem juz jest.
Sam odczyt calej ramki z SDRAM idzie w miare szybko, bo sa do tego
stosowne funkcje.

Tak wyglada pierwsza wersja, ktora ma te wade, ze procesor moze sie
odwolywac do roznych obszarow pamieci o przypadkowo zgodnym f.
Wiec powiekszamy pamiec C np 4 razy, adresujac ja s:f:w, dajemy 4
pamieci S - nazwijmy je S0 do S3, i teraz jesli procesor potrzebuje
adresu p:f:w, odczytujemy wszystkie Sn(f), sprawdzamy czy jest w
ktorejs p, i jesli jest, do odczytujemy dane z C(n:f:w).
A jak nie ma, to dobrze by bylo znalezc najdawniej uzywane n,
po czym ponownie przepisujemy ramke do C(n:f), i w odpowiednia
Sn(f) wpisujemy p.

To wszystko robi sprzet wbudowany w procesor, a moze wrecz zewnetrzny
kontroler, tylko w procesorze szybciej.

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

No, to sie raczej nowym procesorom przypisuje.
Predykcja adresow itp.


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

No, potrafi byc np taka ze jak jest skok warunkowy w tyl, to zaklada
sie ze on bedzie, i wstepnie odczytuje rozkaz spod adresu skoku. Bo to
jakas petla w programie jest, a petla jest po to aby sie petlic :-)

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

Jak trzeba to trzeba i tego nie unikniesz. Zlosliwe jest tu raczej
mnozenie, potrzebne do obliczenia adresu, plus np to ze robisz funkcje
biblioteczna, ktora nie zna rozmiaru, wiec kompilator nie moze
zoptymalizowac, a czesto nawet nie umozliwia .

Patrzac na opis powyzej, to cache nie lubi:
a) obszarow polozonych pod "okraglymi" adresami, bo jak sie okaze ze
np jedna tablica jest pod 1A0000, druga pod 1B0000 a trzecia pod 1D000
i chcemy dodac z pierwszej i drugiej i zapisac w trzeciej, to za
wszystkie maja te sama czesc adresu f i koliduja w cache. Lepiej zdac
sie na dynamiczny przydzial pamieci, moze lepiej rozrzuci.

b) skakania po adresach co kilkanascie bajtow - my tu cachujemy cala
ramke, a program uzywa z niej 1 bajt i przeskakuje do nastepnej.

J.

do góry

W dniu niedziela, 5 października 2014 15:21:41 UTC+2 użytkownik bartekltg napisał:

>
>
>
> > 2) Napisałeś jak to napisać, aby działało zgodnie z oczekiwaniem
>
> > programisty. Chyba mnie nie zrozumiałeś. To nie chodzi o to że
>
> > a^2+b^2=c^2, tylko DLACZEGO a^2+b^2=c^2 !! Chodzi o to magiczne
>
> > słowo "dlaczego?".
>
>
>
> Dlaczego co? W zapędach wycinania wyciąłeś pytanie.
>

W zapędach wycinania wyciąłem chyba pytanie "jak to działa?" , a nie "dlaczego?". Być
może, ale nie chce mi się przeglądać dyskusji od początku.W ogóle chyba (?) stricte
takiego pytania nie zadałem. Nie neguję sensu implementowania w prockach pamięci
cache, nie neguję sensu produkowania procków wielordzeniowych/programowania
wielowątkowego, ale po prostu pytam jak jest to zrealizowane. W notach aplikacyjnych
HW/SW jest napisane jak to obsługiwać, ale jak jest to zrobione to ni cholery.
Pytanie ot, z czystej ciekawości. Ale są pewne wątpliwości o których wcześniej
napisałem. Czy aby w pewnych szczególnych przypadkach częstych i dłuuugich skoków ten
mechanizm jest porządany? Sądzę, że w takich przypadkach może być wręcz szkodliwy.

do góry

On Sun, 5 Oct 2014 06:52:32 -0700 (PDT), s...@g...com wrote:

>W dniu niedziela, 5 października 2014 15:21:41 UTC+2 użytkownik bartekltg napisał:
>
>>
>>
>>
>> > 2) Napisałeś jak to napisać, aby działało zgodnie z oczekiwaniem
>>
>> > programisty. Chyba mnie nie zrozumiałeś. To nie chodzi o to że
>>
>> > a^2+b^2=c^2, tylko DLACZEGO a^2+b^2=c^2 !! Chodzi o to magiczne
>>
>> > słowo "dlaczego?".
>>
>>
>>
>> Dlaczego co? W zapędach wycinania wyciąłeś pytanie.
>>
>
>W zapędach wycinania wyciąłem chyba pytanie "jak to działa?" , a nie "dlaczego?".
Być może, ale nie chce mi się przeglądać dyskusji od początku.W ogóle chyba (?)
stricte takiego pytania nie zadałem. Nie neguję sensu implementowania w prockach
pamięci cache, nie neguję sensu produkowania procków wielordzeniowych/programowania
wielowątkowego, ale po prostu pytam jak jest to zrealizowane. W notach aplikacyjnych
HW/SW jest napisane jak to obsługiwać, ale jak jest to zrobione to ni cholery.
Pytanie ot, z czystej ciekawości. Ale są pewne wątpliwości o których wcześniej
napisałem. Czy aby w pewnych szczególnych przypadkach częstych i dłuuugich skoków ten
mechanizm jest porządany? Sądzę, że w takich przypadkach może być wręcz szkodliwy.

Z che3cia bym wzial udzial w dyskusji, ale wezme dopiero wtedy gdy
nauczysz sie wtsylac posty tak aby nie byly one jedna linia dluga na
kilometr.

Ciezko widze programowanie wieloprocesorow jak ktos nie umie wyslac
posat na usenet

A.L.

do góry