[C++]Paralellizzazione: prestazioni,convenienza

[Albitexm]

Ho visto che si può paralellizzare parte del codice in Visual C++ 2010, con le librerie PPL o MP come da voi anche spiegato.
Volevo utilizzare "paralle for" e "parallel for_each" per paralellizare porzioni del mio codice. Ma a prescindere da quale libreria si usi, mi sono chiesto se a livello di prestazioni conveniva.
Io ho dei loop con espressioni relativamente semplici, di dimensioni di 8 variabili , che vengono eseguiti nel programma decine di volte, con una seguenza non definibile a priori. Il tutto ripetuto migliaia di volte, sempre in quantità non definibile a priori (ovvero non si può usare dei loop for next).
Quindi potendo parallelizzare (almeno con parallel for/for each) solo loop di dimensioni di 8 variabili, mi chiedo se ciò convenga. Se consideriamo i tempi di accesso alla memoria, di trasmissione sul bus, e di lavoro softwarre del compilatore, otterrò realmente un miglioramento di prestazioni?
A livello generale, quando si prende in considerazione la parallelizzazione di un codice, bisogna credo valutare la convenienza, considerando certi parametri e contestualità soggettive del codice in oggetto. Le modalità di operare non seguono ("ancora") standar e metodologie consolidate.
Ma a livello pratico, rimane il fatto che i programmi "paralleli" funzionano.. Anche a livello di prestazioni

[cionci]

Fai un esempio di codice che vuoi parallelizzare.
Se la parte più interna del codice che vuoi parallelizzare non è molto grande (come tempo di esecuzione), allora non conviene sempre parallelizzare. Però si possono studiare altri tipi di partizione dei dati, che possono dimezzare, o anche di più, il tempo di esecuzione.

Ad esempio, un caso semplice ed abbastanza tipico:

for(int i = 0; i < 8000; i++)
for(int j = 0; j < 8000; j++)
{
c[i][j] = 0;
for(int k = 0; k < 8000; k++)
c[i][j] += a[i][k] * b[k][j]
}

Parallelizzare il for interno ha veramente poco senso. Il tempo di esecuzione è assolutamente troppo basso per creare un thread che lo esegua.

Potrebbe avere già più senso parallelizzare il secondo for, ma anche qui è possibile che il tempo di esecuzione possa essere troppo basso da non determinare un tempo di esecuzione consistente rispetto all'overhead.
Puoi quindi attuare una ulteriore partizione...ad esempio supponiamo di voler utilizzare 16 thread (valore decente per poter essere sfruttato con qualsiasi architettura di processore moderna).

Riscrivi il codice così:

for(int p = 0; p < 16; p++)
for(int i = p*500; i < (p+1)*500; i++)
for(int j = 0; j < 8000; j++)
{
c[i][j] = 0;
for(int k = 0; k < 8000; k++)
c[i][j] += a[i][k] * b[k][j]
}

E parallelizzi il for esterno ;) Volendo si può fare una trasposta della matrice b per sfruttare meglio il principio di località, in modo da avere anche i dati di b disponibili subito in cache. Bisogna valutare se ne valga o meno la pena.

[Albitexm]

Fai un esempio di codice che vuoi parallelizzare.


esempio di tipica espressione del mio programma:
4 funzioni usate dala porzione di codice:
// funzione controllo casa occupata da pezzo
int cop(int r,char c)
{
if (r==Krx&&c==Kcx)
co=1;
else if (r==Prx&&c==Pcx)
co=1;
else if (r==P1rx&&c==P1cx)
co=1;
else if (r==P2rx&&c==P2cx)
co=1;
else if (r==P3rx&&c==P3cx)
co=1;
else if (r==P4rx&&c==P4cx)
co=1;
else if (r==P5rx&&c==P5cx)
co=1;
else if (r==Rrx&&c==Rcx)
co=1;
else if (r==krx&&c==kcx)
co=1;
else if (r==prx&&c==pcx)
co=1;
else if (r==p1rx&&c==p1cx)
co=1;
else if (r==p2rx&&c==p2cx)
co=1;
else if (r==p3rx&&c==p3cx)
co=1;
else if (r==p4rx&&c==p4cx)
co=1;
else if (r==p5rx&&c==p5cx)
co=1;
else if (r==rrx&&c==rcx)
co=1;
else
co=0;
return co;
}

// funzione controllo case intermedia occupate
//x mossa riga bianco
int cio(int rg1,int rg2)
{
int y;
int z;
int i;

if (rg1>rg2)
{
y=rg1;z=rg2;
}
else
{
y=rg2;z=rg1;
}

i=z+1;
for (i;i<y;i++)
{
cop(i,pdc);
if (co==1)
break;
}
if (co==1)
s=1;
else
s=0;
return s;
}

// funzione controllo case intermedia occupate x mossa colonna
int cioC(int cg1,int cg2)
{
int y;
int z;
int i;



if (cg1>cg2)
{
y=cg1;z=cg2;
}
else
{
y=cg2;z=cg1;
}

i=z+1;
for (i;i<y;i++)
{
tcic(i);

cop(pdr,pdc);
if (co==1)
break;
}
if (co==1)
s=1;
else
s=0;
return s;
}

// funzione trasformazione cordinate char colonna in int.
int tcci(char C)
{
if (C=='A')
npc=1;
else if (C=='B')
npc=2;
else if (C=='C')
npc=3;
else if (C=='D')
npc=4;
else if (C=='E')
npc=5;
else if (C=='F')
npc=6;
else if (C=='G')
npc=7;
else if (C=='H')
npc=8;
else
cout<<" error2";
return npc;
}
"porzione da paralellizzare":
//verifica che le case intermedie tra la casa di partenza e di arrivo
//della mossa Torre, non siano occupate da nessun pezzo.

// Per mossa di riga (Torre):
else if (pp=="R")
{
if (Rrc==0)
{
cio(pdr,Ppr);
}
// Per mossa di colonna (Torre):
else if (Rrc==1)
{
tcci (Ppc);
cioC (np,npc);
}
else
nl=0;
}

Una decina di algoritmi tipo questo, costituiscono il corpo maggiore del programma, che verrà eseguito tutto per migliaia di volte.

nota: siccome le due espressioni "per mossa riga" e per "mossa colonna" sono
uguali, portando "fuori" da mossa colonna la chiamata alla funzione tcci(), forse si potreppe paralellizzare la cosa con "parallel_invoke" di PPL (http://msdn.microsoft.com/en-us/library/dd470426.aspx#parallel_invoke) o relativa istruzione di MP.

[cionci]

Scusa, ma sono un po' bruttine queste funzioni...

int tcci(char C) la puoi scrivere come:

int tcci(char C)
{
npc = C - 'A' + 1;
if(npc > 8)
cout<<" error2";
return npc;
}

Nei valori controllati da cop cosa c'è dentro ? Sono costanti ? Che relazione c'è tra le variabili con lo stesso nome con la prima lettera maiuscola o minuscola ?

Prima di pensare alla parallelizzazione sarà bene ottimizzare il codice. Se solo riusciamo ad eliminare tutti quegli else-if abbiamo già ridotto il tempo di esecuzione di almeno un ordine di grandezza...

[cionci]

Anche cio e cioC si possono ridurre ulteriormente, c'è poco guadagno, ma se le devi eseguire un milione di volte allora cambia:

//x mossa riga bianco
int cio(int rg1,int rg2)
{
int y;
int z;
int i;

if (rg1>rg2)
{
y=rg1;z=rg2;
}
else
{
y=rg2;z=rg1;
}


for (i=z+1;i<y;i++)
{
if(cop(i,pdc))
break;
}
s = co;
return co;
}

// funzione controllo case intermedia occupate x mossa colonna
int cioC(int cg1,int cg2)
{
int y;
int z;
int i;



if (cg1>cg2)
{
y=cg1;z=cg2;
}
else
{
y=cg2;z=cg1;
}

for (i=z+1;i<y;i++)
{
tcic(i);
if (cop(pdr,pdc))
break;
}
s = co;
return co;
}

[Albitexm]

Nei valori controllati da cop cosa c'è dentro ? Sono costanti ? Che relazione c'è tra le variabili con lo stesso nome con la prima lettera maiuscola o minuscola ?
..

Sono tutte variabili di tipo intero (quelle che finiscono per r,riga) e di tipo
char quelle che finiscono con c (colonna). Sono le cordinate dei pezzi sulla scacchiera.Non sono costanti, perchè possono variare dopo l'eseguzione di
ogni mossa. La lettera maiuscola o minuscola distingue i pezzi bianchi dai neri.
Quindi c'è una relazione sono "umana", per la comprensione del codice, ma per il programma sono variabili intere con nessuna relazione di dipendenza diretta.
La funzione "verifica" che la casa della scacchiera rappresentata dalle cordinate passate alla funzione, è occupata da un pezzo o no. (Se la torre parte da una casa per arrivare a un'altra casa, le case intermedie devono essere libere, altrimenti la mossa non è eseguibile).

[cionci]

Ogni quanto variano queste variabili ?
Quando le aggiorni ? Se ad esempio le aggiorni al di fuori di un ciclo for molto lungo, potresti precalcolare una matrice o un vettore con ogni corrispondenza riga-colonna e valore di co...

[Albitexm]

Scusa, ma sono un po' bruttine queste funzioni...



Considera che sono un principiante. Comunque trasformerò queste funzioni.
Vorrei specificare che il programma, (almeno per adesso,non è finito) gira abbastanza velocemente. Volevo provare a paralellizarlo per sperimentare le PPL, non per un motivo pratico. Ma se si può migliorare il codice, giustamente
come dici tu è meglio provare ad ottimizzare.

Ogni quanto variano queste variabili ?
Quando le aggiorni ? Se ad esempio le aggiorni al di fuori di un ciclo for molto lungo, potresti precalcolare una matrice o un vettore con ogni corrispondenza riga-colonna e valore di co.


Quando viene eseguita la mossa, quindi alla fine di diversi loop. Ma creare un vettore invece che ripetere delle istruzioni If porta dei miglioramenti come prestazioni?
Nei programmi moderni la scacchiera e i pezzi sono rappresentati in un'altro modo, con le bitboard, ovvero la scacchiera viene rappresentata con un byte di 64 bit. Ci sono poi bitboard per i pezzi e delle table per i movimenti dei pezzi. Questo dal punto
di vista delle prestazioni offre dei vantaggi, ovviamente in particolar modo in ambiente x64. Ma ho evitato questo perchè sarebbe stato troppo complesso per me.

[cionci]

In sostanza a te serve capire se una casella è occupata o meno, no ?
Senza ricorrere a strutture dati troppo complesse (dando una numerazione ai pezzi):

int scacchiera[8][8];

bool casella_libera(int scacchiera[8][8], int x, int y)
{
return scacchiera[x][y] == 0;
}

bool muovi_pezzo(int scacchiera[8][8], int x1, int y1, int x2, int y2)
{
if(!casella_libera(scacchiera, x2, y2))
return false;
scacchiera[x2][y2] = scacchiera[x1][y1];
scacchiera[x1][y1] = 0;
return true;
}

Ovviamente la scacchiera dovrà essere inizializzata contenente tutti 0.

In questo modo int cop(int r,char c) si riduce a:

int cop(int r,char c)
{
return (casella_libera(scacchiera, r, tcci(c))) ? 0 : 1;
}


In sostanza rivendendo meglio come mantenere i dati sulla posizione e sui pezzi, ottieni dei miglioramenti più che significativi.

[Albitexm]

.
thank