[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:

Codice PHP:

unknown exception 


qualcuno puoi aiutarmi a capire dove sbaglio...

[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

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