Wielordzeniowe procesory a programowanie wielowątkowe: jak unikać konfliktów pamięci?

Sun Oct 05, 2014 12:25 am   

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

Sun Oct 05, 2014 12:25 am   

On Sat, 4 Oct 2014 15:25:04 -0700 (PDT), stchebel@gmail.com wrote:


A o czyms takim jak "cache memory" slyszales? Poczytaj sobie cos o
architekturze procesora wielordzeniowego

A.L.

Sun Oct 05, 2014 12:25 am   

stchebel@gmail.com wrote:

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

Ale załóżmy że tech cache nie ma i przy każdym odczycie procesor będzie
musiał sięgnąć do pamięci zewnętrznej.
Jeśli cały program by się składał wyłącznie z odczytów z pamięci, wtedy
byłby problem, bo rdzenie by sobie przeszkadzały nawzajem. Ale nawet przy
tak prostym programie jak przytoczyłeś, odczyt z pamięci jest jedną z kilku-
kilkunastu instrukcji które muszą zostać wykonane podczas jednego obiegu
pętli. Podczas kiedy jeden rdzeń zajmuje się wykonaniem dodawania,
przepisywaniem pomiędzy rejestrami sprawdzaniem warunku końca czy czy
skokiem do początku pętli, szyna pamięci danych leży odłogiem i może być
wykorzystana przez drugi rdzeń do pobrania danych.

Nawet jeśli założymy najbardziej niekorzystny przypadek, że podczas każdego
obiegu pętli obydwa rdzenie będą chciały czytać w tym samym momencie, i tak
spowolnienie będzie ledwie zauważalne. W większości przypadków każdy rdzeni
nawet nie zauważy że dostęp do pamięci jest dzielony z kimś innym.

pzdr.
j.

Sun Oct 05, 2014 8:44 am   

W dniu 2014-10-05 00:25, stchebel@gmail.com pisze:

he he nie mogłeś się opanować?

Sun Oct 05, 2014 9:01 am   

stchebel@gmail.com wrote:


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.

pzdr,
j.

Sun Oct 05, 2014 9:33 am   

W dniu 2014-10-05 11:20, stchebel@gmail.com pisze:

ale chodzi, ze ma być po polsku czy że na grupie? bo tu:
http://en.wikibooks.org/wiki/Microprocessor_Design/Cache#Memory_Stall_Cycles
jest wszystko ładnie rozkminione..

@

Sun Oct 05, 2014 10:01 am   

stchebel@gmail.com wrote:


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.

Sun Oct 05, 2014 10:47 am   

W dniu niedziela, 5 października 2014 00:41:48 UTC+2 użytkownik A. L. napisał:

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?

Sun Oct 05, 2014 10:51 am   

W dniu niedziela, 5 października 2014 10:44:49 UTC+2 użytkownik Jawi napisał:

Ano nie ) Widzę że znasz moją "miłość" do C z innych grup, ale akurat w tym wątku nie o to chodzi.

Sun Oct 05, 2014 10:56 am   

W dniu niedziela, 5 października 2014 01:47:28 UTC+2 użytkownik Jacek Radzikowski napisał:


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?

Sun Oct 05, 2014 11:20 am   

W dniu niedziela, 5 października 2014 11:01:21 UTC+2 użytkownik Jacek Radzikowski napisał:

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

Sun Oct 05, 2014 12:30 pm   

On 05.10.2014 00:25, stchebel@gmail.com wrote:

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


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.


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, stchebel@gmail.com wrote:

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

Sun Oct 05, 2014 12:41 pm   

stchebel@gmail.com pisze:
[..]

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

Sun Oct 05, 2014 1:16 pm   

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


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?


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 jest oczywiste. Implikacja tego co napisałem wcześniej.


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


Hah!! Właśnie ja tak robię. Dzięki paru GB pamięci, DSP mogę robić na najpodlejszym laptopie w czasie rzeczywistym.


Upsss.. Nie za bardzo kojarzę.


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

Sun Oct 05, 2014 1:18 pm   

On 05.10.2014 13:16, stchebel@gmail.com wrote:

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



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



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.



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.




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.



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



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.



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


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