30 decembrie 2010

Conversii hexa <-> zecimal (probleme)

; zecimal cu semn in hexazecimal cu directive simplificate -32768..0..32767

.286
.model small
.DATA
sirin DB CR,LF,"Dati numarul in zecimal:$"
erro DB CR,LF,"EROARE-numar neacceptat$"
zecimal db 7,9 DUP(?)
zece DW 10
CR=10
LF=13
.STACK 64
.CODE

assume DS:@DATA

include cio.h
include ascii.h
include bascii.h

start:
MOV AX,@DATA
MOV DS,AX
main:
outstr sirin

in_str zecimal
co CR
co LF

mov AH,zecimal[2]
cmp AH,'-'
je bit_semn
cmp AH,'+'
je bit_semn
mov AH,zecimal[1]
cmp AH,6
je eroare
mov SI,2
mov CL,zecimal[1]
mov CH,0
jmp conversie
bit_semn:
MOV SI,3
mov CL,zecimal[1]
mov CH,0
dec CL
jmp conversie

eroare:
outstr erro
jmp main

conversie:
mov ax,0
bucla:
mov bh,0
mov BL,zecimal[si]
mov dx,0
sub bl,30h
jb eroare
cmp bl,9
ja eroare
mul zece
add ax,bx
inc si
loop bucla
cmp dx,0
jne eroare
or ax,ax ;seteaza indicatori pt ax
jns preg
mov dx,ax
and dx,7fffh
cmp dx,0
jne eroare
mov ch,zecimal[2]
cmp ch,'-'
jne eroare
mov ax,8000h
jmp afisare
preg: ;pregatire afisare
mov BH, zecimal[2]
cmp BH,'-'
jne afisare
neg ax
afisare:
mov DL,AL
mov AL,AH
call bascii
co AH
co AL
mov AL,DL
call bascii
co AH
co AL
jmp main


END start


; conversie din hexazecimal in zecimal cu semn, cu directive complete, format .com, asciitab, prin stiva

.286

prog segment
assume CS:prog, DS:prog, SS:prog

org 100h
start:
jmp inceput

; date
hexMsg db 0ah, 0dh, 'Hexa:$'
zecMsg db 0ah, 0dh, 'Zecimal:$'
zece dw 10
BUFIN DB 5, 7 DUP (?)
semn db 0
tabela db '0123456789ABCDEF'

; stiva
dw 100 dup(?)
varf label word

include hexa.h
include cio.h
include asciitab.h
include citcuv.h
include bascii.h
inceput:
MOV AX, CS
MOV DS, AX
MOV SS, AX
lea SP, varf
reiahex:
outstr hexMsg
call citcuv
jc reiahex
MOV AX,DX
or AX,AX
outstr zecMsg

jns continua
co '-'
neg AX
continua:
xor CX, CX
conversie_cif:
xor DX, DX
div zece
push DX
inc CX
cmp AX, 0
jne conversie_cif

afisareNr:
pop AX
call ascii
co AL
loop afisareNr
jmp reiahex
prog ends
end start

25 decembrie 2010

Terminarea programelor distribuite

In cazul programelor distribuite, determinarea momentului cand acestea s-au terminat nu este o problema simpla. Printre dificultatile care apar amintim urmatoarele: este aproape imposibil sa observam ce se intampla pe mai multe masini in exact acelasi timp; de asemenea, chiar daca toate procesele sunt inactive, mai pot exista mesaje in tranzit intre ele - deci nu putem lua decizia terminarii bazandu-ne numai pe aceasta conditie.

Exista diverse tipuri de algoritmi pentru detectia terminarii intr-un program distribuit. Prezentam mai jos doua tipuri de algoritmi:

* algoritmi bazati pe tehnica jetoanelor (token): in acesti algoritmi, se genereaza un mesaj special de tip "token", care va traversa toate legaturile dintre procese, asigurand faptul ca pe aceste legaturi nu exista mesaje in tranzit. Cea mai simpla varianta este aceea in care procesele sunt conectate intr-o topologie de tip inel, dar algoritmul se poate aplica si la o topologie generala de graf, daca se poate construi un ciclu care sa parcurga toate legaturile grafului
** algoritmi bazati pe confirmarea mesajelor: in acesti algoritmi, mesajele transmise prin legaturile grafului de procese vor fi confirmate de catre procesele destinatie (prin trimiterea unui mesaj de confirmare catre sursa); in acest fel, daca pentru toate mesajele transmise printr-un canal s-au primit confirmari, se poate trage concluzia ca acesta este gol. Un exemplu de algoritm din aceasta categorie este algoritmul Dijkstra-Scholten.

Algoritmul Dijkstra - Scholten

Algoritmul se bazeaza pe trimiterea intre procese a unor semnale de confirmare. Schema de semnalare a terminarii este separata si suplimentara fata de prelucrarea propriu-zisa pe care o realizeaza procesul. Ea urmareste informarea sursei despre terminarea colectiei de procese. Procesele pot receptiona si transmite semnale, chiar si atunci cand sunt libere, deci au terminat prelucrarea caracteristica a datelor. Semnalele se transmit in sens invers datelor, reprezentand confirmari ale prelucrarii acestora de catre destinatar.

Algoritmul rezolva problema in cazul general, in care sunt permise cicluri in graful proceselor. Rezolvarea se face prin generarea unui arbore de acoperire, pe parcursul transferului mesajelor de date: fiecare proces pastreaza o variabila prim a carei valoare este egala cu identificatorul procesului de la care s-a receptionat primul mesaj de date.

Rezolvarea implica trei faze:
# trimiterea semnalelor pe toate legaturile de intrare, cu exceptia celei de la prim;
# receptia semnalelor pe toate legaturile de iesire;
# transmiterea semnalelor spre prim.

~~~~~~~~~~~~~~~~~ aplicatie ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Intr-un graf aciclic(1) sau ciclic(2) radacina initiaza semnalul de terminare, il propaga in intreg graful/arborele iar programul se termina cu adevarat cand radacina primeste confirmari de la toti urmasii .
Aceasta afiseaza distanta dintre ea si cel mai indepartat nod.
Pentru cazul existentei unui ciclu(2), se pastreaza un vector numit primit care tine minte daca un proces i si-a aflat parintele sau nu, pentru a nu accepta primirea mesajului de la 2 parinti si astfel incurca fluxul mesajelor. Daca nu se doreste apelarea la o astfel de variabila "globala", vectorul primit se poate trimite updatat la fiecare transmisie intre procese...

======== (1) ============
#include "mpi.h"
#include "stdio.h"

/* terminarea unui prog distribuit
* ---- graf aciclic -------------
*/

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

int m[7][7],i,j;
for(i=0;i<=6;i++)
for(j=0;j<=6; j++)
m[i][j] = 0;
m[0][1] = m[1][0] = 1;
m[0][2] = m[2][0] = 1;
m[1][3] = m[3][1] = 1;
m[4][1] = m[1][4] = 1;
m[5][2] = m[2][5] = 1;
m[5][6] = m[6][5] = 1;

int numtasks, rank, dest, source, rc, count, tag=1;
int inmsg, outmsg=0;
MPI_Status Stat;
MPI_Request req;

MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (rank == 0) {
inmsg = 0;
int nr_copii = 0;
for(i=1;i<=6;i++)
if(m[0][i]==1) {
nr_copii++;
rc = MPI_Send(&inmsg, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
}
for(i=0;i<=nr_copii-1;i++) {
rc = MPI_Recv(&outmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
if(outmsg > inmsg)
inmsg = outmsg;
}
printf("S-a terminat\nDistanta maxima: %d\n", inmsg);
}

else {
MPI_Status src;
rc = MPI_Recv(&inmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &src);
inmsg++;
int nr_copii = 0;
for(i=0; i<=6; i++)
if(m[rank][i]==1 && i!=src.MPI_SOURCE) {
nr_copii++;
rc = MPI_Send(&inmsg, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
}
if(nr_copii==0) { //frunza, trimite in sus
rc = MPI_Send(&inmsg, 1, MPI_INT, src.MPI_SOURCE, tag, MPI_COMM_WORLD); }
else { // primeste de jos
for(i=0; i<=nr_copii-1; i++) {
rc = MPI_Recv(&outmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
if(outmsg > inmsg)
inmsg = outmsg;
}
rc = MPI_Send(&inmsg, 1, MPI_INT, src.MPI_SOURCE, tag, MPI_COMM_WORLD);
}
}

MPI_Finalize();
}

======= (2) ========

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

/* terminarea unui prog distribuit
* ---- graful contine cicluri -------------
*/

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

int m[6][6],i,j;
for(i=0;i<=5;i++)
for(j=0;j<=5; j++)
m[i][j] = 0;
m[0][1] = m[1][0] = 1;
m[0][2] = m[2][0] = 1;
m[1][3] = m[3][1] = 1;
m[4][1] = m[1][4] = 1;
m[5][2] = m[2][5] = 1;
m[1][2] = m[2][1] = 1;

int numtasks, rank, dest, source, rc, count, tag=1;
int inmsg, outmsg=0;
MPI_Status Stat;
MPI_Request req;

MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
int primit[6];
for(i=0;i<=5; i++)
primit[i] = 0;
if (rank == 0) {
inmsg = 0;
int nr_copii = 0;
for(i=1;i<=5;i++)
if(m[0][i]==1) {
nr_copii++;
rc = MPI_Send(&inmsg, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
}
for(i=0;i<=nr_copii-1;i++) {
rc = MPI_Recv(&outmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
if(outmsg > inmsg)
inmsg = outmsg;
}
printf("S-a terminat\nDistanta maxima: %d\n", inmsg);
}

else {
MPI_Status src;
rc = MPI_Recv(&inmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &src);
int parinte = src.MPI_SOURCE;
primit[rank] = 1;
inmsg++;
int nr_copii = 0;
for(i=0; i<=5; i++)
if(m[rank][i]==1 && i!=parinte && primit[i]==0) {
nr_copii++;
rc = MPI_Send(&inmsg, 1, MPI_INT, i, tag, MPI_COMM_WORLD);//, &req);
}
if(nr_copii==0) { //frunza, trimite in sus
rc = MPI_Send(&inmsg, 1, MPI_INT, parinte, tag, MPI_COMM_WORLD); } // &req); }
else { // primeste de jos
for(i=0; i<=nr_copii-1; i++) {
rc = MPI_Recv(&outmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
if(outmsg > inmsg)
inmsg = outmsg;
}
rc = MPI_Send(&inmsg, 1, MPI_INT, parinte, tag, MPI_COMM_WORLD);
}
}

MPI_Finalize();
}

24 decembrie 2010

Aflarea topologiei unei retele distribuite (avand ca reprezentare un graf aciclic)

O astfel de retea este de fapt un arbore. Fiecare nod isi cunoaste doar vecinii, iar radacina fiind procesul initiator trebuie sa cunoasca intreaga topologie.
Initial, radacina ca oricare nod isi cunoaste doar propriii fii. Isi creeaza propria matrice de adiacenta pe care o trimite fiilor, care la randul lor o completeaza cu informatiile cunoscute de ei referitoare la fii. Cand matricea ajunge intr-un nod frunza, se incepe trimiterea in sens invers catre radacina a matricei. Daca procesul nu este frunza, odata ce a primit de sub el isi completeaza matricea proprie cu informatiile adunate de la fii, si o trimite mai departe pana cand se ajunge la radacina si se afiseaza topologia.


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

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

// un arbore cu n=7 noduri
int m[7][7],i,j;
for(i=0; i<=6 ;i++)
for(j=0; j<=6 ; j++)
m[i][j] = 0;
m[0][1] = m[1][0] = 1;
m[0][2] = m[2][0] = 1;
m[1][3] = m[3][1] = 1;
m[4][1] = m[1][4] = 1;
m[5][2] = m[2][5] = 1;
m[5][6] = m[6][5] = 1;

int numtasks, rank, dest, source, rc, count, tag=1;
MPI_Status Stat;
MPI_Request req;

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

if (rank == 0) {
int newm[7][7],j; //matricea de la care porneste
for(i=0; i<=6 ;i++)
for(j=0; j<=6 ; j++) {
if(j==rank) {
newm[rank][i] = m[rank][i];
newm[i][rank] = newm[rank][i];
}
else {
newm[j][i] = 0;
newm[i][j] = 0;
}
}
int nr_copii = 0;
for(i=1; i<=6 ; i++)
if(m[0][i]==1) {
nr_copii++;
rc = MPI_Send(newm, 7*7, MPI_INT, i, tag, MPI_COMM_WORLD);
}
int rec[7][7];
for(i=0; i<=nr_copii-1; i++) {
rc = MPI_Recv(&rec, 7*7, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
int k;
for(j=0; j<=6 ; j++)
for(k=0; k<=6 ; k++)
if(rec[j][k] == 1)
newm[j][k] = 1;
}
int k;
for(j=0; j<=6; j++) {
for(k=0; k<=6 ; k++)
printf("%d ", newm[j][k]);
printf("\n");
}
}

else {
int newm[7][7],j; //matricea de la care porneste
for(i=0; i<=6 ;i++)
for(j=0; j<=6 ; j++) {
if(j==rank) {
newm[rank][i] = m[rank][i];
newm[i][rank] = newm[rank][i];
}
else {
newm[j][i] = 0;
newm[i][j] = 0;
}
}
MPI_Status src;
int recv[7][7];
rc = MPI_Recv(&recv, 7*7, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &src);
for(i=0; i<=6 ; i++)
for(j=0; j<=6 ; j++)
if(recv[i][j]==1)
newm[i][j] = 1;
int nr_copii = 0;
for(i=0; i<=6 ; i++)
if(m[rank][i]==1 && i!=src.MPI_SOURCE) {
nr_copii++;
rc = MPI_Send(newm, 7*7, MPI_INT, i, tag, MPI_COMM_WORLD);
}
if(nr_copii==0) { //frunza, trimite in sus
rc = MPI_Send(&newm, 7*7, MPI_INT, src.MPI_SOURCE, tag, MPI_COMM_WORLD); }
else { // primeste de jos
for(i=0; i<=nr_copii-1; i++) {
rc = MPI_Recv(&recv, 7*7, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
for(i=0; i<=6; i++)
for(j=0; j<=6 ; j++)
if(recv[i][j]==1)
newm[i][j] = 1;
}
rc = MPI_Send(&newm, 7*7, MPI_INT, src.MPI_SOURCE, tag, MPI_COMM_WORLD);
}
}

MPI_Finalize();
}

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 .