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.

VLSM

Open publication - Free publishing - More vlsm

Introducere in bash scripting

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 [...]

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