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