10 noiembrie 2010

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) {}
}
}

Niciun comentariu: