Multithreading, SMP...

[ Mr. NiceGuy @ 07.11.2006. 18:25 ] @

Budući da sam totalni početnik kad je u pitanju multithreading, molim za jedno objašnjenje.
Na jednoj starijoj temi sam pronašao kod i unakazio ga, zbog čega se ispricavam Ivanu D.:

Code:

#include <windows.h>
#include <stdio.h>
#include <time.h>

long double N = 300000000;

long double i1, i2;

void nit1(){

    while(++i1 < N);
}

void nit2(){

    while(--i2 > 0);
}

void main(){


    DWORD dwTID1, dwTID2;
    HANDLE trds[2];

    double time1, time2;
    clock_t start, finish;

    i1 = 0;
    i2 = N;

    printf ("\nPrvo brojanje...");

    start = clock();

    trds[0] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)nit1, 0, 0, &dwTID1);
    trds[1] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)nit2, 0, 0, &dwTID2);

    WaitForMultipleObjects(2, trds, 1, INFINITE);
    CloseHandle(trds[0]);
    CloseHandle(trds[1]);

    finish = clock();
    time1 = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("\n...%3.3lf sec \n", time1);

    printf ("\nDrugo brojanje(samo main)...");

    start = clock();
    while(--i1 > 0);
    while(++i1 < N);

    finish = clock();
    time2 = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("\n...%3.3lf sec \n\n", time2);

}

Kako imam dvojezgreni procesor, očekivao sam barem malo brže izvršavanje prvog dijela koji paralelno mijenja vrijednosti dva brojača. Međutim, vrijeme potrebno da se izvrši prvi dio je dvostruko veće, iako u tom slučaju task manager pokazuje da su opterećene obje jezgre! Što krivo radim?
Kod sam kompajlirao sa VS6.

[ genuine @ 08.11.2006. 02:05 ] @

Napravio si pocetnicku gesku deklarisanjem oba brojaca tako da padaju u istu kes liniju... naime ono sto se kod tebe desava je veoma izrazen Coherence False Sharing Miss koji ti drasticno degradira performanse... ono sto treba da uradis je da uradis sledecu deklaraciju brojaca
__declspec(align(64)) double counter1;
__declspec(align(64)) double counter2;
na ovaj nacin se brojaci nalaze u razlicitim kes blokovima tako da ce svaki procesor imati uvek u svom lokalnom L1 kesu ispravnu verziju bloka u M stanju i radice paralelno bez i jednog False Sharing Coherence promasaja..
ono sto bi trebalo da pazis je kod postizanja vecih perfomansi izbegavaj while ( nesto ) uradi_nesto_jednostavno() ; vec uradi ako je moguce loop unrolling tako da imas u tvom primeru

while (a<n) {
a++;
a++;
a++;
a++;

}
primer je glup ali je mix mnogo bolji jer ovde na 4 korisne instrukcije ide 1 instrukcija uslovnog skoka sto je mnogo bolje nego 1 korisna i 1 uslovni skok... ali da ne kenj.m za ovo postoji cela teorija...

licno ti preporucujem da batalis standardne niti i da pogledas OpenMP 2.0 biblioteku koja se dobija uz VisualC++ 2005 ili Intelov C++ kompajler.. i da sav posao radis u njoj.. mnogo je jednostavnija i veoma lako mozes da pratis koja ti je sekcija serijska a koja paralelna....

primer :

#include <omp.h>
__declspec(align(64)) a=10000000;
__declspec(align(64)) b=10000000;
int main()
{

#pragma omp parallel sections shared(a,b)
{
#pragma omp section
while (--a > 0 );

#pragma omp section
while (--b > 0 );
}

return 0;
}

pozdrav..

p.s.
Inace ako nije bilo jasno False Sharing promasaji se javljaju jer se koherencija izvodi na nivou celog bloka a ne na nivou reci... kod tebe je recimo procesor A dovukao blok sa oba brojaca i dekrementirao prvi.. tada procesor B zazeli isto pa sada taj isti blok u A mora da se ponisti i prosledi procesoru B.. Sada B izvrsi modifikovanje drugog brojaca ali A to isto hoce da uradi i onda se u kesu B-a blok ponisti i prosledi procesoru A i tako redom... sa onim declspec align direktivama si rekao da hoces da ti brojaci budu u razlicitim blokovima tako da nema ovog gore .... inace onaj broj 64 se odnosi na velicinu kes bloka ( 64 bajta ) i zavisi od platforme... obicno je ili 64 ili 128 kod savremenih multiprocesora...

_{[Ovu poruku je menjao genuine dana 08.11.2006. u 03:19 GMT+1]}

[ Mr. NiceGuy @ 08.11.2006. 22:15 ] @

genuine, hvala na odgovoru!

Pokušao sam sa ovakvom deklaracijom, ali mi kompajler izbacuje greške:
error C2485: 'align' : unrecognized extended attribute
error C2059: syntax error : '('

Trebam li uključiti još neki header?

[ genuine @ 09.11.2006. 00:08 ] @

Ups.. ako koristis visual c++ 6.0, onda nisam siguran kakve su direktive u njemu za poravnavanje promenljivih.... u najgorem slucaju mozes da uradis sledece

double c1; // to je 8 bajtova
char nesto [56] ; // to je jos 56 bajtova
double c2;

i da se nadas da kompajler nece da reorganizuje promenljive i da opet gurne c1 i c2 u isti blok... probaj da pogedas na google-u kako se vrsi poravnavanje u vc++ 6.0

[ Mr. NiceGuy @ 09.11.2006. 16:35 ] @

Hvala, ovo radi - vrijeme je sada gotovo dvostruko kraće.

Ova tema izgleda puno kompleksnija nego što sam mislio i čini mi se da traži bolje poznavanje hardvera.

[ genuine @ 09.11.2006. 16:50 ] @

Evo bas sada spremam ispit iz multiprocesorskih sistema ( koji se tice hardware-a istih ) i nije naivna stvar.. inace za software moras mnogo da pazis...
na primer X86 ima relexed consistency model to jest ako kazes a=5; b=6; niko ti ne garantuje da ce prvo da upis u a bude vidljiv od upisa u b.. jedino sinhronizacione instrukcije daju totalno uredjenje tih blokova... takodje pazi na false sharing na koji si se vec opekao.. to jest pazi da podaci koji su lokalni za procesore tj. niti budu u razlicitim kes blokovima... pazi na to kako ces da izvrsis k oordinaciju izmedju procesora tj. sinhronizaciju jer se sada ne koriste semafori ili muteksi kao sto je to bio slucaj kod uniprocesora zato sto oni ukljucuju operativni sistem i blokiranje niti vec tzv. spin lock-ovi koji ne blokiraju nit vec se vrte u nekoj petlji tipa while ( lock == 1 ); ovo naravno jede 100% procesora ali ima mnooogo manju latenciju od semafora.... takodje koristi thread pool ( koji je vec implementiran u openmp-u) koji eliminise latencije pri kreiranju niti... to jest napravis dve niti ( koliko imas procesora ) i onda one izvrsavaja poslove koji se nalaze u redu poslova... kada nema poslova niti se blokiraju ( idealan primer semafora )... i sl... upravo si usao u novi svet programiranja... :)

[ Mr. NiceGuy @ 09.11.2006. 18:21 ] @

Samo da dodam - kompajler ih je zaista utrpao u isti blok.
Deklaracija tipa: double c1, ..., c9 - rješava problem (ako se koriste c1 i c9)

Međutim, kada radim s poljem double tipa, ne dolazi do degradacije, čak i ako koristim dva susjedna člana.

_{[Ovu poruku je menjao Mr. NiceGuy dana 09.11.2006. u 20:02 GMT+1]}

_{[Ovu poruku je menjao Mr. NiceGuy dana 09.11.2006. u 20:03 GMT+1]}

[ genuine @ 09.11.2006. 20:19 ] @

to je cista slucajnost sto ne dolazi.... tebi se zapravo desilo sledece

.......X
X.......

na kraju prvog bloka ti je prvi brojac, a na pocetku drugog je drugi... probaj da ubacis jos jedan double ispred pa ces dobiti degradaciju... jedino sto ti je potrebno je nacin da poravnas tvoju promenljivu sa nekom adresom ( u ovom slucaju deljivom sa 64 )... u VC++ 8.0 se radi sa __declspec(align(koliko))
ili ako koristis OpenMP to se radi automatski kada kazes promenljivoj da je private... u VC++ 6.0 stvarno ne znam kako se radi ali pogledaj u MSDN-u mora da pise....

[ Mr. NiceGuy @ 11.11.2006. 10:28 ] @

Riješio sam problem.
"__declspec" je moguće koristiti, ali uz instalaciju processor pack-a. Prethodno je potrebno
instalirati VS6 service pack 5 (~130 MB)