01 noiembrie 2010

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 .

24 octombrie 2010

Row-Column Sort

Row Column Sort este o metoda de sortare in paralel, cu o complexitate aproape de complexitatea medie pentru o sortare: n*log(n).
Ideea este ca vectorul de elemente pentru sortat trebuie pus intr-o matrice (completata cu elemente fara valoare la nevoie), dupa care se aplica un numar de 2*log2(n) pasi dupa cum urmeaza:
Pasul impar: se sorteaza liniile (in mod independent), liniile impare se sorteaza crescator, cele pare descrescator
Pasul par: se sorteaza coloanele (independent), toate crescator de sus in jos
In final, matricea se parcurge de la coltul stanga sus in mod serpuit pana la coltul dreapta jos.

=======

#include "stdio.h"
#include "omp.h"
#include "math.h"
#include "stdlib.h"

int n, a[9] = {2,7,1,0,8,5,10,17,2};
int dim;
int mat[3][3];

void sort_linii (int i, int mod) {

int ok=0, k,aux;
if(mod == 1) {
while (!ok) {
for(k=0; k<=dim-2; k++) {
ok = 1;
if(mat[i][k]=>mat[i][k+1]+1) {
//printf("1)schimb %d cu %d \n", mat[i][k], mat[i][k+1]);
ok = 0;
aux = mat[i][k];
mat[i][k] = mat[i][k+1];
mat[i][k+1] = aux;
}
}
}
}
else {
while (!ok) {
for(k=0; k<=dim-2; k++) {
ok = 1;
if(mat[i][k]<=mat[i][k+1]-1) {
//printf("2)schimb %d cu %d \n", mat[i][k], mat[i][k+1]);
ok = 0;
aux = mat[i][k];
mat[i][k] = mat[i][k+1];
mat[i][k+1] = aux;
}
}
}
}
}

void sort_coloane (int j) {

int k, ok = 0;
while (!ok) {
for(k=0; k<=dim-2; k++) {
ok = 1;
if(mat[k][j]=>mat[k+1][j]+1) {
//printf("!!schimb %d cu %d \n", mat[k][j], mat[k+1][j]);
ok = 0;
int aux = mat[k][j];
mat[k][j] = mat[k+1][j];
mat[k+1][j] = aux;
}
}
}
}

void afisare() {
int i,j;
printf("\n");
for(i=0;i<=dim-1;i++) {
for(j=0;j<=dim-1;j++)
printf("%d ", mat[i][j]);
printf("\n");
}
}

int main () {

n = 9 ;
dim = 3;
int pas, i,j,aux;
i=0; j=0,pas=0;
do {
mat[i][j] = a[pas];
j++;
if(j==dim) {
j = 0; i++;
}
pas++;
} while(pas<=n-1);

afisare();

int final = log(n);
final = final/log(2)*2;
//printf("final=%d\n",final);
#pragma omp parallel shared(mat,dim,final) private(pas)
for(pas=0; pas<=n-1; pas++) {

if(pas%2==1) { //impar, sortez liniile
#pragma omp for private(i)
for(i=0; i<=dim-1; i++) //pt fiecare linie
if(i%2==1) {
sort_linii(i,1); //crescator
//afisare();
}
else {
sort_linii(i,0); //descrescator
//afisare();
}
}
else { //par, sortez coloane
#pragma omp for private(j)
for(j=0;j<=dim-1;j++) {
sort_coloane(j); //toate de sus in jos crescator
//afisare();
}
}
#pragma omp single
afisare();
}

printf("\nSIR SORTAT:\n");
i=0;
do {
if(i<=dim-1)
for(j=dim-1; j>=0; j--)
printf("%d ", mat[i][j]);
i++;
if(i<=dim-1)
for(j=0;j<=dim-1; j++)
printf("%d ", mat[i][j]);
i++;
} while(i<=dim-1);

printf("\n");
return 0;
}

20 octombrie 2010

Sortare OETS

OETS (odd even transposition sort) este o versiune paralela a metodei bulelor (Bubble Sort). Se utilizeaza n procesoare, unde n este numarul de elemente de sortat, fiecare numar fiind distribuit unui procesor. Algoritmul are n pasi si functioneaza astfel:
* in pasii impari, fiecare procesor cu numar de ordine impar comunica cu procesorul din dreapta; cele doua procesoare isi trimit unul altuia numerele si, daca este necesar, acestea sunt interschimbate
* in pasii pari, fiecare procesor cu numar de ordine par comunica cu procesorul din dreapta, executand operatii similare cu cele din pasii pari

Operatiile fiecarui pas se executa in paralel, insa pasii se desfasoara unul dupa altul (gen bariera). Numarul maxim de pasi este n, complexitatea finala fiind O(n), dat fiind ca avem n procesoare.

#include "stdio.h"

#include "omp.h"

int main () {

int n = 6, a[6] = {2,7,1,0,8,5};

int pas, i, aux;

#pragma omp parallel shared(a,n) private(pas)

for(pas=0; pas<=n-1; pas++) {

if(pas%2==1) { //impar

#pragma omp for private(i,aux)

for(i=0; i<=n-2; i+=2)

if(a[i]>a[i+1]) {

aux = a[i];

a[i] = a[i+1];

a[i+1] = aux;

}

}

else { //par

#pragma omp for private(i,aux)

for(i=1;i<=n-2;i+=2)

if(a[i]>a[i+1]) {

aux = a[i];

a[i] = a[i+1];

a[i+1] = aux;

}

}

}

for(i=0;i<=n-1;i++)

printf("%d ", a[i]);

printf("\n");

return 0;

}

19 octombrie 2010

Transmiterea seriala


Folosind sursele si protocolul micro-UART, realizati o comunicatie seriala care sa utilizeze bitul de paritate in transmisia si receptia informatiei.
Rezolvare: http://dl.dropbox.com/u/24465060/CN-rx_tx.zip

06 octombrie 2010

Exemplu simplu de algoritm paralel

compilarea se face: gcc -fopenmp sursa.c -o sursa

#include "mp.h"  
void main ()  {  
int nthreads, tid;  
/* Fork a team of threads with each thread having a private tid variable */ 
#pragma omp parallel private(tid)   {    
  /* Obtain and print thread id */   
  tid = omp_get_thread_num();   
  printf("Hello World from thread = %d\n", tid);    
  /* Only master thread does this */    
  if (tid == 0)      {     
    nthreads = omp_get_num_threads();     
    printf("Number of threads = %d\n", nthreads);     
  }    
  }  /* All threads join master thread and terminate */  
}