Encontro 12 - Odd Even Sort

Ainda no objetivo da paralelização do Bubble Sort, neste encontro foi testada a abordagem Odd-Even (Par e Ímpar) paralelizada na ordenação de um vetor numérico.

A paralelização do Bubble Sort ocorreu bem, porém foi encontrada uma falha em alguns casos de testes, quando duas threads tentavam a Swap em uma mesma posição do vetor, ocorreram perdas de dados e portanto, não foi possível garantir a integridade do vetor.

Após pesquisa, foi-se decidida a tentativa de alteração para o enfoque "Par Ímpar", que avalia as trocas em dois momentos, primeiramente nas posições pares e em seguida nas posições ímpares. Garantindo que não será acessada uma mesma posição do vetor no mesmo momento.

A aplicação do algoritmo foi eficiente e rendeu um speedUp de 1,61 vezes mais rápido do algoritmo paralelo com duas threads sobre o mesmo algoritmo sequencial.

Algoritmo em Paralelo

void par_impar(int a[], int N){
    int i, j, metade, swap, ultimoPar, ultimoImpar;
    for(j=0;j<N;j++){
        #pragma omp parallel for private(i, swap)
        for(i=0;i<N-1;i=i+2){
            if(a[i] > a[i+1]){
                swap = a[i];
                a[i] = a[i+1];
                a[i+1] = swap;
            }
        }
        #pragma omp parallel for private(i, swap)
        for(i=1;i<N-2;i=i+2){
            if(a[i] > a[i+1]){
                swap = a[i];
                a[i] = a[i+1];
                a[i+1] = swap;
            }
        }
    }
}

Tempos

O algoritmo sequencial executou em 43.001s .
O algoritmo paralelizado executou em 26.092 .