Cautarea "binara" folosind un algoritm paralel

Fiind dat un sir sortat (crescator) de lungime n si un numar de thread-uri N care sa prelucreze sirul, vom incerca sa aflam pozitia unui element de cautat in acest sir.
Sirul dat se va fragmenta in N subsiruri, primele N-1 fiind de o lungime fixa chunk=max(1, n/N), iar ultimul fiind de lungime cat a mai ramas. Fiecare thread va prelua capatul din stanga al unui subsir si il va compara cu nr.cautat. Se creeaza o variabila partajata- vectorul de decizie vd - in care thread-urile vor pune valori de -1 si 1 astfel: 1 daca nr de cautat se afla in dreapta capatului primit, si -1 daca nr de cautat de afla in stanga sa.
Dupa ce toate cele N thread-uri si-au terminat treaba, se analizeaza vectorul de decizie obtinut si in momentul cand se observa trecerea de la 1 la -1, se pastreaza indicele elementului 1 ultim, care va deveni capatul noului sir de analizat (start), se seteaza noul capat care va fi start+chunk-1, si procedeul continua pana cand s-a gasit numarul cautat sau start>=stop.

====== Cautare.java =====

import java.util.concurrent.CyclicBarrier;

class MyThread extends Thread {

int elem;
int cautat;
int vd[];
int k; //nr.thread-ului
int i; //index
CyclicBarrier bar;

public MyThread (int elem, int vd[], int cautat,int k, int i, CyclicBarrier bar) {
this.elem = elem;
this.cautat = cautat;
this.vd = vd;
this.i = i;
this.bar = bar;
this.k = k;
}

public void run() {
try {
if(elem>=cautat-1) {
vd[k] = -1;
}
else
if(elem<=cautat-1) {
vd[k] = 1;
}
else {
System.out.println("Gasit la pozitia "+i);
return ;
}
bar.await();
sleep(100);

} catch (Exception e) {}
}
}

public class Cautare {

public static void main (String args[]) {

int n = 20, v[] = new int[n];

for(int i=0; i<=n-1; i++)
v[i] = i*2+1;

int N = 5;
int vd[] = new int[N];

for(int i=0; i<=N-1; i++)
vd[i] = 0;

int cautat = 17;

try {

MyThread [] mt = new MyThread[N];
int start = 0, stop = n-1;
int chunk = n/N,chaux;
if(chunk==0)
chunk++;

CyclicBarrier barrier = new CyclicBarrier(6); //5 + 1 master
do {

chaux = chunk;
for(int i=0; i<=N-1; i++) {
mt[i] = new MyThread(v[start], vd, cautat, i, start, barrier);
mt[i].start();
start = start+chunk;
}
barrier.await(); // asteapta toate thread-urile sa-si termine treaba

int j;

boolean ok = true;

for(j=0; j<=N-2; j++)

if(vd[j]+vd[j+1]==0) {
start = j*chaux;
stop = start+chaux-1;
if(chaux!=chunk)
stop = n-1;
n = stop-start+1;
chunk = n/N;
if(chunk==0)
chunk++;
ok = false;
break;
}

if(vd[N-1]==1 && ok) {
start = (N-1)*chaux;
stop = start+chaux-1;
if(chaux!=chunk)
stop = n-1;
n = stop-start+1;
chunk = n/N;
if(chunk==0)
chunk++;
}

} while(start<=stop-1);

} catch (Exception e) {}
}
}

Citirea si scrierea de fisiere in Java

Desenarea in OpenGL

Prezentarea laboratorului

Exemple: http://dl.dropbox.com/u/24465060/Laborator4_EGC.zip

Modelul "Replicated Workers" si rezolvarea problemei reginelor

1. Pentru rezolvarea problemei se folosesc mai multe procese similare, muncitorii (workers), care ruleaza pe procesoare diferite. Acestor muncitori li se atribuie dinamic sarcini (tasks) in timpul executiei programului.
2. Pentru gestiunea sarcinilor se foloseste o structura de date abstracta numita Work Pool (WP). Un WP reprezinta o colectie de descriptori, fiecare caracterizand un task ce poate fi executat de catre oricare dintre muncitori.
3. Cand un muncitor devine inactiv, preia o noua sarcina din WP si executa calculele necesare. In timpul acestei executii un muncitor poate genera noi sarcini ce se adauga in WP. Sarcinile trebuie concepute astfel incat sa poata fi rezolvate de catre oricare dintre munictori.
4. Activitatea comuna (paralela) a muncitorilor se considera terminata atunci cand:
a. Toti muncitorii sunt inactivi (cer un nou task).
b. WP este gol (nu mai exista taskuri de executat). (Observam ca WP poate fi gol insa cativa muncitori activi. In acest caz nu putem fi siguri de terminare activitatii, pentru ca pot fi generate noi taskuri).

Primitivele de lucru cu WP sunt:

* getWork - pentru primirea unei sarcini din WP si
* putWork - pentru plasarea unei sarcini in WP

*

Urmatoarele clase Java implementeaza problema reginelor folosind modelul Replicated Workers, cu ajutorul a 3 worker-i. Fiecare worker isi ia cate un task din WorkPool si prelucreaza solutiile partiale, conform regulilor impuse de problema reginelor.
Rezolvarea: http://dl.dropbox.com/u/24465060/Replicated%20Workers.zip

Impartirea unui for pe mai multe thread-uri

#include "stdio.h"
#include "omp.h"

int main() {
int i, n, tid;
float a[10], b[10], sum;

/* initializari */

n = 10;
for (i=0; i < n; i++)
a[i] = b[i] = i * 1.0;
sum = 0.0;

omp_set_num_threads(3); // setam 3 thread-uri

// la final, fiecare thread va aduna la variabila sum, valoarea calculata
#pragma omp parallel for reduction(+:sum) private(tid)
for (i=0; i < n; i++)
{
sum = sum + (a[i] * b[i]);
tid = omp_get_thread_num();
printf("Sum = %f, from thread %d\n",sum, tid);
}

printf(" Sum = %f\n",sum); // suma finala
return 0;
}