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