[C++] programmazione multithreads

[alessia86]

Salve..non ho capito bene come funziona la programmazione multithreads..ad es. ho questo problema:

Devo implementare qst funzione:



int * expr(int * X,int * Y,int * Z,int * W,int N);



Qst funzione prende in input i puntatori a 4 vettori X,Y,Z,W di dimensione N e deve ritornare ed allocare un puntatore al vettore R ottenuto calcolando l'espressione vettoriale :



R=X*X+Y*Y+Z*Z+W*W



La funzione deve essere ottimizzata in termini di prestazioni,tenendo conto di avere a disposizione 8 processori. Implementazioni sequenziali non vengono prese in considerazione.




Siccome i processori sono 8 come faccio metà gli faccio fare il quadrato e l'altra metà la somma?
poi non ho capito qnd partono i threads insieme come fanno ognuno ad eseguire il proprio lavoro?
Non ci ho capito nulla con qst programmazione multithreads
Spero mi aiuterete..
Grazie :)

[alessia86]

io ho provato a risolverlo cosi:




#include<JTC/JTC.h>
#include<iostream.h>

int * sum(int * X,int * Y,int N)
{
int * result=new int[N];

for(int i=0;i<N;i++){

result[i]=X[i]+Y[i];

}

return result;
}


int * prod(int * X,int N)
{
int * result=new int[N];

for(int i=0;i<N;i++)
{
result[i]=X[i]*X[i];
}

return result;

}


class CalcolaEspressione:public JTCMonitor
{
int nThreads;
int ThreadsFiniti;

public:

int * X;
int * Y;
int N;


int * R;

CalcolaEspressione(int nt)
{
nThreads=nt;

ThreadsFiniti=0;
};

void setDone()
{
JTCSynchronized sync(*this);

ThreadsFiniti++;

if(ThreadsFiniti==nThreads)
notify();

}

void waitForCompletion()
{
JTCSynchronized sync(*this);

if(ThreadsFiniti<nThreads)
wait();
}

};

class Espressione:public JTCThread
{
CalcolaEspressione * c;

bool sp;

public:

Espressione(CalcolaEspressione * c,bool sp)
{
this->c=c;

this->sp=sp;

}

virtual void run()
{
c->R=(sp?sum(c->X,c->Y,c->N):prod(c->X,c->N));

c->setDone();

}

};


int * expr(int * X,int * Y,int * Z,int * W,int N)
{
CalcolaEspressione * cal=new CalcolaEspressione(8);

Espressione * e[8];



for(int i=0;i<8;i++)
{
e[i]=new Espressione(cal,false);
e[i]->start();

}


e[N-1]=new Espressione(cal,true);

e[N-1]->start();

cal->waitForCompletion();

return cal->R;

}















int X[] = {1, 2, -1, 0, 3, 0, 0, 0, 1, 0, 0, 0, 0};
int Y[] = {1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0};
int Z[] = {1, 2, -1, 0, 3, 0, 0,0, 0, 1, 0, 0, 0, 0};
int K[] = {1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0};


int main()

{
JTCInitialize init;
int* R = expr(X,Y,Z,K,13);
for(int i = 0; i < 13; i++)
{
cout << R[i] << " ";
}
cout<<endl;
return 0;
}




però quando lo faccio partire mi dice:



unknown exception


qualcuno puoi aiutarmi a capire dove sbaglio...:muro:

[alessia86]

Allora l'ho risolto utilizzando la classe buffer


#include<JTC/JTC.h>
#include<iostream.h>
#include"Buffer.h"

int * sum(int * X,int * Y,int N)
{
int * result=new int[N];

for(int i=0;i<N;i++)
{
result[i]=X[i]+Y[i];
}
return result;
}

int * prod(int * X,int N)
{
int * result=new int[N];

for(int i=0;i<N;i++)
{
result[i]=X[i]*X[i];
}

return result;
}


class Request
{
public:

int * X;
int * Y;
//int * Z;
//int * W;

int N;

bool sommaProd;

public:

Request(int * X,int * Y,/*int * Z,int * W,*/int N,bool sp)
{
this->X=X;
this->Y=Y;
/*this->Z=Z;
this->W=W;*/

this->N=N;
this->sommaProd=sp;

}

};

class CalcolaEspressione:public JTCMonitor
{
int nThreads;
int threadsFiniti;

public:

CalcolaEspressione(int n)
{
nThreads=n;
threadsFiniti=0;
};


void done()
{
JTCSynchronized sync(*this);

threadsFiniti++;

if(threadsFiniti==nThreads)
notify();

}

void waitForCompletion()
{
JTCSynchronized sync(*this);

if(threadsFiniti<nThreads)
wait();
}

};

class Espressione:public JTCThread
{
Buffer<Request*>* bufRichieste;

Buffer<int*>* bufRisultati;

CalcolaEspressione * esp;

public:

Espressione(Buffer<Request*>*bric,Buffer<int*>*bris,CalcolaEspressione * b)
{
bufRichieste=bric;
bufRisultati=bris;
this->esp=b;
}

virtual void run()
{
Request * r;

while(r=bufRichieste->get())
{
bufRisultati->put(r->sommaProd?sum(r->X,r->Y,r->N):prod(r->X,r->N));

delete r;

}

esp->done();
}
};









int * expr(int * X,int * Y,int * Z,int * W,int N)
{
Buffer<Request*> * bufRichieste=new Buffer<Request*>(0);
Buffer<int*> * bufRisultati=new Buffer<int*>(0);


CalcolaEspressione * c=new CalcolaEspressione(8);

Espressione * e[8];

for(int i=0;i<8;i++)
{
e[i]=new Espressione(bufRichieste,bufRisultati,c);

e[i]->start();
}


//moltiplicaz

// for(i=0;i<4;i++)
// {
bufRichieste->put(new Request(X,X,/*Z,W,*/N,false));
bufRichieste->put(new Request(Y,Y,N,false));
bufRichieste->put(new Request(Z,Z,N,false));
bufRichieste->put(new Request(W,W,N,false));


// }

//somma

for(int j=0;j<3;j++)
{
int * r0=bufRisultati->get();
int * r1=bufRisultati->get();
//int * r2=bufRisultati->get();
//int * r3=bufRisultati->get();

bufRichieste->put(new Request(r0,r1,N,true));
}

int * result=bufRisultati->get();

bufRichieste->close();

c->waitForCompletion();

delete bufRisultati;

delete bufRichieste;

delete c;

return result;
}



int X[] = {1, 2, -1, 0, 3, 0, 0, 0, 1, 0, 0, 0, 0};
int Y[] = {1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0};
int Z[] = {1, 2, -1, 0, 3, 0, 0, 0, 0, 1, 0, 0, 0};
int K[] = {1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0};


int main()

{
JTCInitialize init;
int* R = expr(X,Y,Z,K,13);
for(int i = 0; i < 13; i++)
{
cout << R[i] << " ";
}
cout<<endl;
return 0;
}




Cosi' mi da..però vorrei provare in un altro modo e cioè senza usare la classe buffer..Ma non riesco a capire poi come memorizzare i risultati..Spero che stavolta qualcuno mi risp :cry:

[cionci]

Purtroppo credo che molti non conoscano la libreria che stai usando. Come si chiama ?

[alessia86]

Uso la libreria JTC-2.0.0...purtroppo il mio prof vuole che si usi questa.. :(

[Ikon O'Cluster]

Io penso si possa fare di meglio... Non conosco la libreria, ma cmq una volta stabilita la sincronizzazione è facile individuare i costrutti necessari in base al particolare formalismo usato. L'operazione è:

R = X^2 +Y^2 + Z^2 + W^2

Un'idea è quella di creare 4 threads che fanno singolarmente i 4 prodotti e poi altri 3 che calcolano le 3 somme. Tuttavia i 4 threads per i prodotti sono effettivamente paralleli, poi ci saranno i 2 threads per le somme S1=X^2+Y^2 e S2=Z^2+W^2 che saranno tra loro paralleli, ma cmq non potranno partire prima dei precedenti 4 threads di prodotto. Poi un ultimo thread di somma che parte quando anche questi 2 sono terminati sommando S1+S2. Tuttavia si nota che in questo modo il grado di parallelismo è troppo basso. Io non considererei una operazione in termini vettoriali, ma in termini scalari elemento per elemento. In tal senso gli elementi di R, cioè R[i] saranno calcolati come:

R[i] = X[i]^2 + Y[i]^2 + Z[i]^2 + W[i]^2

Adesso le vie sono 2. Una è ovvia anche se non troppo efficiente e sarebbe quella di strutturare i threads come ho detto prima in base alle operazioni in modo che operino in una sorta di pipeline: quando sono pronti X[i]^2 e Y[i]^2 allora l'atro thread calcola S1[i] nel frattempo sarà pronto Z[i]^2 e W[i]^2 quindi S2[i] pertanto l'altro thread si avvia e calcola R[i]. Nel frattempo gli altri threads stanno già calcolando gli indici i+1, i+2 ecc... I problemi di questa soluzione che si può implementare tanto così per esercizio è quella di avere soli 7 threads, inoltre ci saranno periodi in cui il numero di threads attivi sarà < 7! Tuttavia un buon modo è quello di considerare N threads, dove un generico thread lo indichiamo con l'indice i. In tal modo il thread i-esimo calcola R[i] con la formula detta prima. In questo modo se N>8 allora ogni processore elabora un elemento del risultato e appena uno finisce passa a schedulare il thread per un altro elemento. Questa soluzione è quella a max parallelismo in generale su una macchina ad M processori, dove M può anche essere 1! L'altra soluzione invece è subottimale e cmq è meglio se hai M<8. Tuttavia è interessante applicare entrambe le soluzioni, soprattutto quella non ottimale perchè richiede una maggiore complessità nel realizzare le sincronizzazioni tra i vari threads.

Una possibile altra soluzione è l'unione di entrambe:

R[i] = X[i]^2 + Y[i]^2 + Z[i]^2 + W[i]^2

Viene calcolato dal thread i-esimo... e se invece venisse calcolato da ben 7 threads organizzati come detto nella prima soluzione? Avresti per ogni elemento i 4 threads di prodotto, 2 threads di somma parziale e 1 thread di somma finale. Un totale di N*7 threads... più multithread di così si muore!!!

[cionci]

Imho la soluzione più semplice è questa: 4 thread che fanno i prodotti ed uno che fa le somme (può essere anche il chiamante).
4 semafori da incrementare alla fine di ogni prodotto e da decrementare quando il chiamante recupera i dati. In questo modo i thread svolgono tutti i prodotti in parallelo e man mano che i prodotti necessari ad ogni somma sono terminati, il chiamante effettua la somma.
Tra l'altro si possono implementare i 4 thread anche come una unica classe passando il puntatore al vettore ed al semaforo e questo rende la soluzione molto compatta

[Ikon O'Cluster]

Se il prof specifica di avere 8 processori forse è un chiaro avvertimento che li vuole tenere tutti occupati, nel senso che vuole che ci siano più di 8 threads...

[Ikon O'Cluster]

Se il prof specifica di avere 8 processori forse è un chiaro avvertimento che li vuole tenere tutti occupati, nel senso che vuole che ci siano più di 8 threads...