Ordenação Bitônica Paralela

No último post apresentei o algoritmo de ordenação bitônica. Aqui apresentarei uma versão paralela da ordenação bitônica, que na verdade é um híbrido da ordenação bitônica com algoritmo de ordenação usual como o quicksort. Para simplificar, vamos considerar novamente que o tamanho do vetor é uma potência de 2, assim como o número de processadores. Rotulamos os processadores de 0 a p-1. Dividimos o vetor de entrada em partes iguais de tamanho n/p. Vamos definir m = n/p para facilitar a notação. Assim, o processador 0 contém os elementos 0 a m-1, o processador 1 os elementos de m a 2m-1 e assim por diante.

Divisão Bitônica

Primeiramente, vamos relembrar como era feita a divisão bitônica. Dada uma sequência bitônica, consideramos os pares (0, n/2), (1, n/2+1), … (n/2-1, n-1) para gerar as sequências A1 e A2.

Os elementos 0 a m-1, sob posse do processador 0, devem formar pares com os elementos de n/2 a m+n/2-1, que estão sob posse do processador p/2.

Vamos considerar um exemplo com p=8. Podemos abstrair o tamanho do vetor n, considerando que cada processador tem um bloco de tamanho m. Numeremos os blocos de acordo com o processador. Assim, para gerar as sequências A1 e A2 na divisão bitônica, devemos parear o bloco 0 com o bloco 4, o bloco 1 com o 5, o 2 com o 6 e o bloco 3 com o 7, conforme a Figura abaixo.

Divisão bitônica de um vetor com 8 blocos.

Na recursão, dividiremos o vetor em duas metades, uma do bloco 0 ao bloco 3 e a outra do bloco 4 ao bloco 7. Para fazer a divisão bitônica da primeira metade, pareamos os blocos 0 e 2 e os blocos 1 e 3. Na segunda metade o pareamento é análogo. No último nível da recursão formamos os pares com os adjacentes, ou seja, (0,1), (2,3), (4,5) e (6,7).

Observe que para gerar a subsequência correspondente ao processador 0, decorrente da primeira divisão bitônica, só precisamos da subsequência do processador 4, ficando independente do restante das outras subsequências. Na segunda divisão, o processador 0 só precisou da informação em 2 e na terceira apenas da informação em 1. Fica fácil ver que com trocas de mensagens entre pares a cada divisão bitônica, podemos obter a sequência ordenada no final.

Para determinar qual o par correto de cada processador em cada divisão bitônica, podemos usar a representação binária do número de cada processador. É possível mostrar que na primeira divisão bitônica, pareamos os processadores cujo rótulo difere apenas no bit mais significativo. Por exemplo, (000 e 100), (001 e 101), (010 e 110) e (011 e 111). Na segunda divisão, aqueles que diferem apenas no segundo bit mais significativo, ou seja, (000 e 010), (001 e 011), (100 e 110) e (101 e 111). O procedimento é análogo parra os níveis subsequentes.

Gerando uma sequência bitônica

Como no caso sequencial, partimos de uma sequência bitônica. Portanto, precisamos transformar uma sequência arbitrária em bitônica antes de aplicar o método acima. A ideia geral era, em um dado nível, quebrar a sequência em 2, ordenar a primeira metade em ordem crescente e a outra metade em descrescente, juntar e aplicar a divisão bitônica.

Podemos transformar a recursão em um processo iterativo. Inicialmente ordenamos conjuntos de blocos consecutivos de tamanho 2. Assim, por exemplo, para p = 8, devemos ordenar os pares de blocos (0,1) e (4, 5) em ordem crescente e os pares (2, 3) e (6, 7) em ordem descrescente. Na próxima iteração ordenamos o bloco (0,1,2,3) em ordem crescente e (4,5,6,7) em ordem descrescente. Finalmente, na terceira iteração ordenamos (0,1,2,3,4,5,6,7) em ordem crescente. A Tabela abaixo sumariza esse procedimento, onde l é o tamanho dos conjuntos de blocos.


Estratégia bottom-up para obter sequências bitônicas.

Podemos determinar quando ordernar uma sequência em ordem crescente ou decrescente, novamente de acordo com a representação binária. No primeiro nível, os processadores com bit menos significativo 0 ordenam em ordem crescente e os com bit menos significativo 1, em ordem decrescente. No segundo nível, o segundo bit mais significativo é usado para determinar a ordem.

Bitonic split vs. Merge split

Observe que em um certo estágio das divisões bitônicas, a sequência em questão vai estar toda contida em um só processador. A princípio poderíamos continuar as divisões para ordenar esse trecho, mas como não podemos mais explorar o paralelismo, é mais viável usar um algoritmo O(n log n) ao invés do O(n log^2 n).

Dá para fazer algo melhor ainda! Se mantivermos as sequências em cada processador sempre ordenadas, quando chegarmos ao ponto em que a sequência está contida em um só processador, não precisaremos fazer nada!

Para trabalharmos com as sequências ordenadas dentro de cada processador, precisamos modificar o algoritmo que gera a sequência A1 e A2. Ao gerar essas sequências entre um par de processadores, ao invés de receber uma sequência crescente e outra decrescente, por hipótese recebemos duas sequências crescentes. Aí então executamos a etapa de intercalação do merge sort e distribuímos a metade menor para A1 e a metade maior para A2. Observe que os elementos de A1 e A2 são os mesmos se tivéssemos executado a divisão bitônica, só mudando a ordem deles. Para podermos usar a hipótese das sequências ordenadas, basta que cada processador ordene sua sequência inicialmente.

Por exemplo, considere a sequência bitônica {2, 4, 6, 8, 7, 5, 3, 1} e 2 processadores A e B, sendo que {2, 4, 6, 8} está no processador A e {7, 5, 3, 1} no processador B. A divisão usual resultaria em {2, 4, 3, 1} e {7, 5, 6, 8}. A proposta é que A tivesse {2, 4, 6, 8}, B tivesse {1, 3, 5, 7} (ordenado!) e a divisão resultasse em {1, 2, 3, 4} e {5, 6, 7, 8}.

Complexidade

Como foi descrito, cada processador deve ordenar sua sequência localmente. Usando um algoritmo eficiente como o quicksort, obtemos a complexidade O(m log m). Já a ordenação bitônica consiste de O(log p) estágios, cada qual usado para obter uma sequência bitônica. Para tanto usamos O(log p) trocas de mensagens entre um dado processador e seus pares. Tanto a troca de mensagens quanto a operação de intercalação é O(m). Assim, a complexidade total do algoritmo pode ser dada por .

Código

Decidi implementar a versão paralela usando C++ e MPI. Sacrifiquei um pouco de legibilidade para o código ficar menor. Esse template que estou usando tem pouco espaço horizontal, o que é bem ruim para postar códigos :(

#include <algorithm>
#include <cmath>
#include <cstdio>
#include "mpi.h"

/* Faz a intercalacao entre v e u e guarda em r */
void Merge(int *v, int *u, int n, int *t){
    int i=0, j=0, k=0;
    while(i < n && j < n)
        t[k++] = (v[i] < u[j]) ? v[i++] : u[j++];
    while(i < n) t[k++] = v[i++];
    while(j < n) t[k++] = u[j++];
}
/* Ordena conjuntos de blocos de tamanho set_size */
void BitonicSplit(int myrank, int *v, int n, 
                  int set_size, bool inc){
    
    int u[n], t[2*n];
    int set_dim = log(set_size)/M_LN2 + 1e-8;
    int eor_bit = 1 << (set_dim - 1);
    for(int i = 0; i < set_dim; i++){
        int pair = myrank ^ eor_bit;
        MPI_Status st;
        MPI_Send(v, n, MPI_INT, pair, 0,
                 MPI_COMM_WORLD);
        MPI_Recv(u, n, MPI_INT, pair, 0, 
                 MPI_COMM_WORLD, &st);

        Merge(v, u, n, t);

        int offset = ((inc && myrank < pair) || 
                      (!inc && myrank > pair)) ? 0 : n;
        for(int j=0; j<n; j++)
            v[j] = t[j+offset];
        eor_bit >>= 1;
    }   
}
void BitonicSort(int myrank, int np, int *v, 
                 int n){
    for(int ssize = 2; ssize <= np; ssize *= 2)
        BitonicSplit(myrank, v, n, ssize, 
                     !(myrank & ssize));
}
int main (int argc, char *argv[]){

    int myrank, np;
 
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &np);
    MPI_Comm_rank(MPI_COMM_WORLD, &myrank);

    /* Para simplificar, considere que a distribuição 
       dos dados já foi feita p/ cada processador */
    int t[ ] = {9, 12, 16, 23, 26, 39, 42, 61,
                43, 17, 14, 13, 12, 7, 6, 5};

    int n = 16/np;
    int *v = t + myrank*n;

    /* Ordena localmente */
    std::sort(v, v+n);

    BitonicSort(myrank, np, v, n);

    /* Cada processador tem a parcela correspondente
       do vetor ordenado total */
    printf("[%d]", myrank);
    for(int i=0; i<n; i++)
        printf(" %d", v[i]);
    printf("\n");

    MPI_Finalize();

    return 0;
}

Os comentários estão fechados.

%d bloggers like this: