24 noiembrie 2010

Lumini

Sortare OETS in MPI

Pentru descrierea problemei vezi si OETS in OpenMP .

=======

compilare: mpicc oets.c -o oets
rulare: mpiexec -np 7 oets
(np inseamna nr de procese, identic cu nr de procese angajate sa ruleze in program)

=======

#include "mpi.h"
#include "stdio.h"

int main(argc,argv)
int argc;
char *argv[]; {

int numtasks, rank, dest, source, rc, count, tag=1;
MPI_Status Stat;
int v[7];
v[0] = 5;
v[1] = 3;
v[2] = 6;
v[3] = 8;
v[4] = 4;
v[5] = 2;
v[6] = 7;
int n = 7;

MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

int i;
int val ;
MPI_Scatter (v, 1, MPI_INT, &val, 1, MPI_INT, 0, MPI_COMM_WORLD);

for(i=1;i<=n; i++) {

if(i%2==1) {
if (rank %2 == 0 && rank+1<=n-1) {
dest = rank+1;
source = rank+1;
int val2;
rc = MPI_Send(&val, 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
rc = MPI_Recv(&val2, 1, MPI_INT, source, tag, MPI_COMM_WORLD, &Stat);
val = (val < val2)?val:val2;
}
else if(rank%2==1 && rank > 0){
dest = rank-1;
source = rank-1;
int val2;
rc = MPI_Recv(&val2, 1, MPI_INT, source, tag, MPI_COMM_WORLD, &Stat);
rc = MPI_Send(&val, 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
val = (val > val2)?val:val2;
}
}
else {
if(rank%2 == 1 && rank+1<=n-1 ) {
dest = rank+1;
source = rank+1;
int val2;
rc = MPI_Send(&val, 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
rc = MPI_Recv(&val2, 1, MPI_INT, source, tag, MPI_COMM_WORLD, &Stat);
val = (val < val2)?val:val2;
}
else if(rank%2==0 && rank>0 ) {
dest = rank-1;
source = rank-1;
int val2;
rc = MPI_Recv(&val2, 1, MPI_INT, source, tag, MPI_COMM_WORLD, &Stat);
rc = MPI_Send(&val, 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
val = (val > val2)?val:val2;
}
}

MPI_Barrier (MPI_COMM_WORLD);

}

MPI_Gather (&val, 1, MPI_INT, v, 1, MPI_INT, 0, MPI_COMM_WORLD);

if(rank==0) {
for(i=0; i<=6; i++)
printf("%d ", v[i]);
printf("\n");
}

MPI_Finalize();

}

=== explicatii ===

In principiu, pasii sunt la fel ca la varianta in OpenMI, cu deosebirea ca intr-un pas se realizeaza o comunicatie intre oricare 2 procese alaturate, stanga si dreapta. Stanga prin conventie va trimite o valoare in dreapta si va primi valoarea din dreapta dupa care va stoca minimul, iar dreapta primeste o valoare din stanga si si-o trimite si pe a ei in stanga dupa care stocheaza maximul; etc...
MPI_Scatter (v, 1, MPI_INT, &val, 1, MPI_INT, 0, MPI_COMM_WORLD) are semnificatia: din vectorul v se ia cate 1 element, de tip MPI_INT, care se transmite celorlalte procese in variabila val, care este 1 singura valoare, si ea de tip MPI_INT. Root-ul este procesul cu rangul 0, iar mediul este MPI_COMM_WORLD.
MPI_Gather are acelasi tip de parametri, insa cu semnificatia ca valoarea val din fiecare proces este depusa in v.
MPI_Barrier
este pus pentru a se asigura ca la sfarsitul iteratiei fiecare proces si-a terminat treaba.

13 noiembrie 2010

Makefile pt Java

=== makefile ===

JFLAGS = -g
JC = javac
.SUFFIXES: .java .class
.java.class:
$(JC) $(JFLAGS) $*.java

CLASSES = \
clasa1.java \
clasa2.java \
clasa3.java \

default: classes

classes: $(CLASSES:.java=.class)

clean:
$(RM) *.class

=== script care ruleaza clasa principala (care are main si parametri pt main) ===

java clasa1 $1 $2 $3 [...]

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

03 noiembrie 2010

Desenarea in OpenGL

Prezentarea laboratorului

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

01 noiembrie 2010

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;
}

Problema producator-consumator

Fie un vector numit buffer la care in permanenta au acces 2 entitati: un producator, care adauga elemente ori de cate ori bufferul permite acest lucru (nu se depaseste capacitatea), si un consumator care extrage elemente ori de cate ori este posibil (pana cand se ajunge la vectorul vid). In Java, simularea poate arata in felul urmator:

// clasa care creeaza cele 2 thread-uri si le porneste

import java.util.*;

class ProdCons {


public static void main (String args[]) {

Vector buffer;
int nmax;
nmax = 10;
buffer = new Vector(nmax);
for(int i=0; i<=nmax-1; i++)
buffer.addElement(i);

Prod prod = new Prod(buffer, nmax);
Cons cons = new Cons(buffer);

cons.start();
prod.start();
}

// producatorul

import java.util.*;

public class Prod extends Thread {

Vector buffer;
int cap;
int i;

public Prod (Vector buffer, int cap) {
this.cap = cap;
this.buffer = buffer;
i = 11;
}

public void run() {
while (true) {
try {
if (buffer.size()<=cap-1) {
System.out.println("Produc "+i);
buffer.addElement(i);
i++;
synchronized (buffer) {
buffer.notify(); //wakes up the first thread that called wait( ) on the same object.
}
}
synchronized (buffer) {
buffer.wait(); // tells the calling thread to give up the monitor and go to sleep until some other
//thread enters the same monitor and calls notify( ).
}
sleep(4);
}
catch (Exception e) {};
}
}

}

}

// consumatorul

import java.util.*;

public class Cons extends Thread {

Vector buffer;

public Cons (Vector buffer) {
this.buffer = buffer;
}

public void run() {
while(true) {
try {
if(buffer.size()>=1) {
System.out.println("Consum "+buffer.firstElement());
buffer.remove(buffer.firstElement());
System.out.println("buffer.size in Cons="+buffer.size());
synchronized (buffer) {
buffer.notify();
}
}
synchronized (buffer) {
buffer.wait();
}
sleep(10);
}
catch(Exception e) {};
}
}

}

Un alt exemplu mai puteti gasi AICI .