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 */  
}