Encontro 13 - Utilização de MPI

Nesta reunião, o grupo discutiu e debateu sobre implementações e aplicações de MPI em problemas previamente estudados e paralelizados em OpenMP.
Foram estudados 3 algoritmos já vistos em encontros passados e foram propostas soluções e observadas diferenças de implementação com processamento paralelo utilizando MPI - Multiplicação de Matrizes, Conjunto de Mandelbrot e Permutation Flowshop Scheduling.

Multiplicação de Matrizes

Em nossa paralelização posterior, foram utilizados duas marcações #pragma que paralelizaram a multiplicação, dando desempenho. A modificação de paradigma em MPI exige modificações no código, dividindo a matriz de multiplicação para que seja distribuída a execução entre os processos.

Mandelbrot

Foram observadas semelhanças entre implementações em OpenMP e MPI (ambos dividindo tarefas para diferentes threads/processos).

Permutation Flowshop Scheduling

Foram apresentadas soluções para o problema em MPI e constatada a ineficiência (baixo speedUp) do OpenMP nesse caso.

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 .