Retrospectiva 2010

Dezembro 31, 2010

Não terei muito para falar sobre o ano de 2010. Já postei no fim do semestre passado, sobre os fatos que aconteceram naquele período. Vamos então aos acontecimentos do segundo semestre.

Maratona

Nesse segundo semestre aconteceram as provas regionais da maratona de programação. Já comentei que classificamos dois times para a final brasileira que aconteceu em Joinville e que ficamos em nono, mas para efeitos de vaga para o mundial é como se estivéssemos em sétimo. Infelizmente o número de vagas diminuiu para 6.

A comissão mundial do ICPC destina uma quantidade de vagas (que muda de ano para ano) para a América Latina como um todo. Cabe então aos diretores regionais distribuírem as vagas entre as sedes. Há as seguintes sedes na América Latina: o Brasil, o resto da América do Sul e México + América Central. Atualmente a divisão é proporcional ao número de escolas participantes em cada sede. Como esse ano houve um crescimento no número de escolas em países como Cuba, a nova distribuição acabou prejudicando o Brasil.

No final das contas, deixamos de ir para o Egito por uma posição >.< mas pelo menos esse ano convidaram todos os medalhistas a participarem do acampamento de verão que ocorrerá novamente na USP. Os três competidores do Unicamp Alpha confirmaram presença.

Atividades extra-curriculares

Logo no começo do semestre, um amigo do laboratório, o Mário, me convidou para fazer badminton na FEF. Já estava meio tarde e havia poucas vagas. As que restaram tinham o horário meio ruim, então decidi dar uma olhada em outros esportes. Acabei optando pela natação, num horário perigoso: das 11h ao meio-dia.

Fiz escola de natação quando pequeno, mas não cheguei a aprender a nadar. Sabia nadar aquele crawl desajeitado com a cabeça fora d’água (nem sei se pode chamar de crawl) e também sabia o suficiente para não me afogar. Nas aulas da FEF o professor ensinou os nados crawl, peito, costas e borboleta. Só aprendi o crawl e o peito. No nado de costas acho difícil nadar reto e no borboleta é ruim para respirar.

Prentendo fazer o curso de aprimoramento semestre que vem, mas é preciso passar em uma prova prática, que consiste basicamente em nadar 350 metros em 12 minutos.

Blog

Vou aproveitar para fazer uma retrospectiva sobre o blog. Comecei a escrevê-lo em Janeiro de 2009, ainda no domínio blogspot.com Na época eu escrevia sobre meus estudos de iniciação científica em algoritmos aproximados. Acabei deletando esses posts (infelizmente perdi o conteúdo deles… seria legal reler).

Daí dei uma desanimada e passei a fazer postagens esporádicas. No primeiro semestre de 2010, resolvi postar sobre os laboratórios de MC202 que eu preparava. Isso garantiu uma frequência de postagem maior, cerca de 2 a 3 vezes por mês. Nas férias fiquei com bastante tempo livre e acabei postando bastante sobre conteúdo que estava ou tinha estudado. Comecei a ver nesses posts uma maneira interessante de me motivar a estudar (porque gosto de escrever), de pontencializar o entendimento do assunto (há vezes que quando vamos explicar algo percebemos que não entendemos algum detalhe) e um meio de armazenar conteúdo estudado, que eu posso rever caso esqueça. Por esses motivos, comprometi-me a postar toda semana! Às vezes é difícil arranjar assunto sobre o que escrever ou a semana está muito apertada, mas tenho conseguido manter essa prática até agora :)

Além do mais, considero a hipótese que o conteúdo postado possa ajudar outras pessoas. O blog tem tido uma média de 20 acessos diários, mas infelizmente a maior parte dos termos pesquisados em sites de busca que levam ao blog não tem nada a ver. A título de curiosidade, alguns termos que trouxeram pessoas aqui: Tabuleiro “xadrez” shopping d pedro campinas, programação de final de ano joinville, origami passo a passo, etc.

Um dos grandes problemas é que a maior parte dos assuntos que eu posto são conteúdos relacionados ao meu mestrado, ou seja, são muito especializados para quem só está procurando breves referências na internet (em geral as pessoas com interesse mais específico vão atrás de artigos). Vez ou outra eu escrevi sobre assuntos mais introdutórios, como o Branch and Cut, o algoritmo de Dijkstra e a coloração em grafos. Confirmando minhas suspeitas, esses são os posts com mais acessos do blog.

Anúncios

Ordenação Bitônica Paralela

Dezembro 24, 2010

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;
}

Ordenação bitônica

Dezembro 17, 2010

Aprendi vários algoritmos de ordenação nos cursos da faculdade e na maratona. Entre eles estão o Bubble Sort, o Insertion Sort, o Selection Sort, o Heap Sort, Merge Sort e o Quick Sort. Porém, um no qual eu não tinha ouvido falar é o Bitonic Sort ou Ordenação Bitônica (em tradução livre).

Uma sequência monotonicamente crescente é equivalente a uma sequência não-descrescente, ou seja, seus elementos nunca diminuem, mas podem ficar iguais. A definição de monotonicamente decrescente é análoga. Já uma sequência bitônica, é uma sequência monotonicamente crescente seguida de uma monotonicamente decrescente (ou uma rotação cíclica dessa sequência).

Assim, por exemplo, {1, 2, 2, 3, 7, 6, 4} é uma sequência bitônica, formada pela sequência monotonicamente crescente {1, 2, 2, 3} e pela monotonicamente decrescente {7, 6, 4}. Como {3, 7, 6, 4, 1, 2, 2} é uma rotação cíclica da sequência original, então ela é também bitônica.

 

Figura 1: Exemplo de sequência bitônica

Para facilitar a descrição do algoritmo, vamos supor que o tamanho da sequência é uma pontência de 2.

Bitonic Split

Bitonic Split ou Divisão Bitônica (novamente, uma tradução livre), consiste em dividir a sequência bitônica A de tamanho n em duas novas sequências bitônicas, A1 e A2, de tamanho n/2, com a propriedade adicional de que todos os elementos de A1 são menores ou iguais a quaisquer elementos de A2.

Para isso, criamos a sequência A1 e A2 da seguinte forma:

 

Figura 2: Ilustração da divisão bitônica da Figura 1. A1 está destacado em azul, A2 em verde.

Por exemplo, se o vetor for {1, 5, 6, 9, 8, 7, 3, 0}, teremos A1 = {1, 5, 3, 0} e A2 = {8, 7, 6, 9}. Podemos fazer essa divisão recursivamente, até que restem sequências de apenas um elemento. Essa estratégia está esquematizada na figura a seguir:

Observe que pela propriedade dos elementos da subárvore da esquerda serem sempre menores do que os da direita, no nível das folhas o vetor estará ordenado. Se estivéssemos fazendo essas divisões no próprio vetor teríamos algo do tipo:

Sequência em cada etapa do algoritmo.

Não podemos aplicar esse algoritmo a qualquer subsequência porque usamos a hipótese de que a sequência de entrada era bitônica. Portanto, devemos transformar a sequência de entrada em uma sequência bitônica. Para tanto usaremos um algoritmo baseado no seguinte argumento indutivo: Suponha que sabemos transformar em bitônica cada uma das metades da sequência original. Como, a partir disso, transformar a sequência original em bitônica?

Como cada metade é bitônica, usamos a divisão bitônica para ordená-las. A primeira metade ordenamos em ordem não-decrescente e a segunda metade em ordem não-crescente (é só trocar A1 por A2 no algoritmo). Pronto! A sequência original passou a ser bitônica.

Só resta mostrar a base da indução, que é quando temos 4 elementos, por exemplo {a1, a2, a3, a4}. Nesse caso, quebramos em {a1, a2} e {a3, a4}. Se a1 > a2, trocamos esses elementos de posição. Se a3 < a4, também trocamos eles de posição. Temos então uma sequência bitônica.

Complexidade

Vamos analisar primeiro a complexidade de ordenar uma sequência bitônica com a divisão bitônica recursiva. A cada nível quebramos o array em 2, com um processamento linear para construir A1 e A2. Não há processamento após chamar a recursão. Temos então O(log n) níveis gastando O(n) cada. Portanto, temos O(n log n).

Agora a complexidade do algoritmo para transformar uma sequência qualquer em bitônica. Em cada nó quebramos o array em 2 e após retornar da recursão, é preciso usar o algoritmo anterior para ordenar cada metade, gastando O(n/2 log n/2 + n/2 log n/2) = O(n log n). É fácil ver que em cada nível gastamos O(n log n) e temos O(log n) níveis. Logo, a complexidade total do algoritmo é .

Esse algoritmo poderia ser melhorado, observando que é possível ordenar uma sequência bitônica em O(n) (exercício), o que resultaria na complexidade ótima de ordenação que é O(n log n). Porém, esse algoritmo na forma original é interessante para ser paralelizado. Porém, esse é um assunto que discutiremos em um futuro post.

Código

Eu ia implementar esse algoritmo em python, mas como na Wikipedia já existe essa implementação, decidi fazer uma em C++. Para simplificar, o código supõe que o tamanho do vetor é uma potência de 2. Se não for o caso, basta encontrar o maior elemento do vetor e inserir várias cópias dele no final até completar um tamanho que satisfaça essa propriedade. Depois de ordenado, é só jogar fora os últimos elementos.

#include <stdio.h>
#include <algorithm>

// Ordena sequência bitonica
void BitonicSplit(int *v, int n, bool inc){
    if (n <= 1) return;

    for(int i=0; i<n/2; i++)
        if ((inc && v[i] > v[i+n/2])||
            (!inc && v[i] < v[i+n/2]))
            std::swap(v[i], v[i+n/2]);

    BitonicSplit(v, n/2, inc);
    BitonicSplit(v + n/2, n/2, inc);
}
// Ordena sequência arbitrária
void BitonicSort(int *v, int n, bool inc){
    if (n <= 1) return;

    BitonicSort(v, n/2, inc);        // Ordena cresc.
    BitonicSort(v + n/2, n/2, !inc); // Ordena decresc.
    BitonicSplit(v, n, inc);
}

int main (){

    int v[ ] = {5, 1, 6, 9, 8, 7, 0, 3};
    int n = 8;

    BitonicSort(v, n, true);

    for(int i=0; i<n; i++)
        printf("%d ", v[i]);
    printf("\n");
}

Referência

[1] Parallel Programming with MPI – Peter S. Pacheco
[2] Wikipedia – Bitonic Sorter


Comunicação Não Bloqueante

Dezembro 10, 2010

A forma mais comum de comunicação entre dois processos no MPI é através de Sends e Receives, implementados pelas funções MPI_Send e MPI_Recv, respectivamente. Em teoria essas funções são bloqueantes, no sentido de que ao enviar uma mensagem com MPI_Send, o programa para sua execução até que o processador para o qual ele enviou a mensagem receba sua mensagem com um MPI_Recv.

Imagine um cenário simples com 2 processos que queiram trocar mensagens entre si. Localmente, ambos executam um MPI_Send seguido de um MPI_Recv. O diagrama abaixo ilustra esse caso:


Diagrama ilustrando potencial deadlock

No caso em que o send e o receive são bloqueantes, teremos o chamado deadlock (no diagrama de dependência, ele é caracterizado por um ciclo dirigido), ou seja, os processadores ficam esperando infinitamente.


Exemplo de deadlock no dia-a-dia (foto recebida por email).

Felizmente, a maior parte das implementações do padrão MPI, provê um buffer para que o send não seja bloqueante. Ao chamar MPI_Send, a mensagem é copiada em um buffer e a execução do programa continua. Aí quando o destinatário chama MPI_Recv, ele lê a mensagem do buffer. Em implementações onde não há o esse buffer, deve-se usar MPI_Bsend, onde o buffer deve ser explicitamente alocado.

Porém, a chamada MPI_Recv continua bloqueante. Dependendo da aplicação, essa característica pode ser custosa, pois enquanto espera uma mensagem, o processador fica ocioso. Recentemente me deparei com uma situação que sofria desse problema.

Suponha três processos p1, p2, p3, sendo que p1 é o processo que gerencia a execução do algoritmo (leitura de entrada, repassar tarefa para p2 e p3, além de processar os resultados de p2 e p3). Ao processo p1 é dado um certo número de iterações que deverão executadas por p1, p2 e p3. Como cada iteração executada leva um tempo diferente, usamos a estratégia de distribuição por demanda.

Assim, p1 inicialmente envia um bloco de iterações a p2 e p3 para que estes executem. Enquanto isso, ele trata de executar também algumas iterações. Ao final dessa execução, ele comunica com p2 e p3 para verificar se eles já terminaram suas iterações. Se sim, envia mais um bloco de iterações para que eles executem. Caso contrário, volta para executar mais iterações, fazendo a verificação novamente, até que o número especificado de iterações seja executado.

Para fazer a comunicação com p2 (ou p3), o processo p1 pode chamar MPI_Recv, esperando que p2 retorne seus resultados. Depois, ele decide se ainda há iterações para serem executadas. Então, envia com o MPI_Send um ‘ok’, em caso positivo, ou um ‘stop’, em caso negativo. Por outro lado, o processo p2, ao terminar de executar seu bloco de iterações, envia seus resultados com o MPI_Send e espera a resposta de p1 para saber se deve parar ou continuar, através do MPI_Recv.

É muito provável que algum dos processos fique esperando os outros terminarem suas tarefas, enquanto poderia estar executando mais iterações. Nesse caso, operações de send e receive não bloqueantes seriam mais adequadas. Felizmente, a biblioteca MPI oferece essa alternativa.

Sends e Receives não bloqueantes

No MPI, as funções que implementam send e receive não bloqueantes são denominadas MPI_Isend e MPI_Irecv, respectivamente. Elas não bloqueiam, mas também não efetuam de fato a operação de send/receive, apenas iniciam o processo.

Ao chamar uma dessas funções, é retornado um objeto do tipo ‘request’, que indica o status do send ou do receive. Esse ‘request’ pode ser verificado basicamente de duas maneiras: através da função MPI_Wait ou da função MPI_Test. A primeira bloqueia a execução até que o send ou receive se complete. A segunda retorna uma flag que é true se a operação completou, ou false caso contrário.

O exemplo apresentado anteriormente pode ser adaptado para usar comunicação não bloqueantes. Agora, o processador p1 distribui o bloco de iterações e começa a executar as suas. Ao final, ele chama o MPI_Irecv para indicar que está esperando uma mensagem de p2 e p3. Aí então ele verifica através do MPI_Test se a sua mensagem já chegou. Em caso positivo, ele executa o MPI_Isend dizendo se é para parar ou continuar a execução. Caso não tenha chegado a mensagem, ele simplesmente executa mais um bloco de iterações e volta para verificar novamente.

No outro lado, o processo p2 (ou p3), ao terminar suas iterações, envia uma mensagem para p1 com MPI_Isend e então invoca MPI_Irecv para indicar que está esperando a resposta de p1. Em seguida, chama MPI_Test para determinar se a mensagem já chegou. Em caso negativo, volta a executar mais um bloco de iterações. Em caso positivo, verifica se a mensagem é para que ele pare de executar.

Experimentos computacionais

Implementei as duas estratégias mencionadas acima, simulando a execução de iteração com um sleep de um tempo aleatório entre 1 e 5 segundos. Fixei 100 iterações e variei os tamanhos de bloco em 1, 5, 10 e 20. A tabela abaixo sumariza os tempos de execução obtidos e os tempos de espera.

O tempo de espera é a soma do tempo de chamada de cada função de send ou receive. Mais especificamente, eu meço o tempo com MPI_Wtime antes e depois de chamar cada uma dessas funções, e somo a diferença desses tempos.

Para medir o tempo total, foi medido apenas no processador mestre, mas para garantir que a medida corresponde ao tempo do processador que terminou por último, usei a função MPI_Barrier, que bloqueia todo mundo que a chama enquanto houver que ainda não a chamou.

Tabela: Comparação de tempo de execução total e tempo ocioso total entre a estratégia bloqueante e a não bloqueante para diversos tamanhos de blocos.

Verificamos, como era esperado, que o uso de chamadas não bloqueantes resulta em tempo ocioso nulo. O tempo de execução total tende a aumentar com o tamanho dos blocos.

Observe que para blocos pequenos, a estratégia não-bloqueante se deu melhor, devido aos tempos de processador ocioso da estratégia bloqueante. Porém, para blocos maiores, a estratégia bloqueante é mais rápida. Uma explicação para isso é que na estratégia não-bloqueante, o número de iterações realizadas pode superar a quantidade estabelecida de iterações, pois quando o MPI_Test retorna falso, o processador vai executar outro bloco de iterações, mesmo que nesse momento o número de iterações já tenha sido atingido.

Da forma como o tempo de processador ocioso é medido, está incluindo o tempo de envio e recebimento das mensagens. Note então que esse tempo é irrelevante perto do tempo de execução do algoritmo. Assim, usar blocos de tamanho pequeno, em detrimento do aumento de trocas de mensagem, e comunicação não-bloqueante parece uma boa ideia.


Generalized Upper Bound Branching

Dezembro 3, 2010

O generalized upper bound (GUB) branching é uma técnica de ramificação utilizada por algoritmos do tipo branch-and-bound.

Motivação

Imagine uma formulação contendo a seguinte desigualdade:

(1)

Suponha que o a relaxação linear foi resolvida e a variável possui valor fracionária e foi escolhida para ser ramificada. Assim, o algoritmo criará dois nós, um com e o outro com .

No nó com , a desigualdade (1) fica

(2)

Enquanto no nó com a desigualdade implicará que todas as outras variáveis terão valor 0.

Há uma diferença desproporcional em relação à redução do espaço de busca. No primeiro caso, a desigualdade (1) não permitiu fixar o valor de outra variável se não , enquanto no segundo, fixamos os valores de todas as variáveis envolvidas na desigualdade.

Uma das ramificações será resolvida rapidamente enquanto a outra continuará praticamente como o nó pai. Ou seja, é quase como se não tivéssemos efetuado a ramificação.

Esse tipo de degenerescência na árvore de busca é semelhante ao do algoritmo Quicksort, quando a escolha do pivô é tal que um dos subproblemas fica com quase todos os elementos e o outro com quase nenhum. Nesse caso a complexidade do algoritmo pode ficar .

Solução

Para contornar esse problema, existe uma estratégia chamada generalized upper bound, em que se tenta fixar não o valor de uma variável, mas o valor da soma de algumas delas. Para tentar manter a árvore de busca mais balanceada, vamos incluindo as primeiras variáveis em (1) até que a soma parcial deles ultrapasse 1/2. Matematicamente falando, sejam os valores das variáveis na relaxação linear. Então, seja

(3)

Criamos um nó adicionando a desigualdade

(4)

E outro com a desigualdade adicional

(5)

Xpress-Optmizer

O Xpress-Optimizer é um software proprietário que usamos no laboratório LOCo, capaz de resolver programas lineares inteiros mistos. Ele fornece esse tipo de estratégia, mas sob o nome de Special Ordered Set (SOS).

No Xpress, é preciso informar quais conjuntos de variáveis deverão sofrer ramificação da maneira apresentada acima. Além disso, para cada um desses conjuntos, é preciso passar o chamado “valor de referência” para cada variável. Segundo o manual do Xpress, esse valor é do tipo ponto flutuante e serve para ordenar as varáveis do conjunto. Se bem entendi, se é o valor de referência da variável i, ao invés de considerar ao calcular o somatório parcial, considera-se , onde representa uma permutação dos índices tal que , onde é o valor de referência de cada variável.

Citando o manual do Xpress, seção “Problem Types”:

Special ordered sets of type one (SOS1) — a set of non–negative decision variables ordered by a set of specified continuous values (or reference values) of which at most one can take a nonzero value. SOS1s are useful for modeling quantities that are taken from a specified discrete set of continuous values (e.g., choosing one of a set of transportation capacities);

Não está especificado no manual, mas os valores de referência devem ser distintos. A seção “Solution Methods”, ao explicar sobre o algoritmo de branch-and-bound também faz referência a SOS:

If the MIP problem contains SOS sets then the nodes of the Branch and Bound tree are separated by branching on the sets. Note that each member of the set has a double precision reference row entry and the sets are ordered by these reference row entries. Branching on the sets is done by choosing a position in the ordering of the set variables and setting all members of the set to 0 either above or below the chosen point. The optimizer used the reference row entries to decide on the branching position and so it is important to choose the reference row entries which reflect the cost of setting the set member to 0. In some cases it maybe better to model the problem with binary variables instead of sets. This is especially the case if the sets are small.

Note que a magnitude do valor de referência, além de determinar a ordem do somatório, influencia, de modo não especificado, na escolha do pivô (índice r em (3)) onde será feito a ramificação. Um chute seria que dentro do Xpress a escolha do pivô seja feita assim:

(6)

Na prática

Lembro-me de ter lido (vou ficar devendo a referência) que em casos onde a desigualdade (1) é usada para representar possíveis valores de uma variável, os valores de referência devem ser iguais a esses valores. Por exemplo:

(7)
(8)

Onde (8) serve para modelar que v pode valer 3, 5 ou 7. Então ao declarar que (8) deve sofrer GUB, é interessante usar como valor de referência .

Leitura complementar

[1] Special Ordered Sets (SOS) (Ver SOS1)