Primeira Fase da Maratona de Programação 2010

Setembro 24, 2010

No último Sábado (18 de Setembro), aconteceu a primeira fase da maratona de programação. A regional de Campinas aconteceu na PUC-Camp, como no ano passado. Diferentemente do ano passado, o ITA não veio (foi para a sede de São Paulo) e o ICMC voltou (ano passado eles tinham ido pra São Paulo).

Saímos logo de manhã da frente do IC1-2 em uma van fretada pelo instituto. Chegamos lá na PUCC um pouco cedo, com os organizadores ainda preparando o ambiente.

Às 10h00 começou o aquecimento (warmup). O aquecimento é uma prova de 1h com dois problemas fáceis, com a finalidade de testar e se familiarizar com o sistema. Pelo terceiro ano consecutivo o problema “Dama” caiu no warmup. Nesse problema tem que dizer, dado um tabuleiro de xadrez, qual o menor número de movimentos para levar a rainha de uma posição inicial a uma posição final (esse problema está no SPOJ-Br). O outro problema era o seguinte: dadas N tábuas de comprimento variado e largura fixa, encontrar o menor número de tábuas necessárias para construir um retângulo n por m posicionando as tábulas lado a lado com mesma orientação (i.e. todas de “pé” ou todas “deitadas”). Não é possível serrar nenhuma tábua e só é possível juntar duas tábuas para aumentar seu comprimento. Esse problema é relativamente simples, mas nenhum time o resolveu! O pessoal do Unicamp Alpha argumentou que foi por causa da lenda de que quem ganha o warmup não ganha a competição.

Organizadores com dificuldade pra colocar a faixa

Depois disso fomos almoçar na praça de alimentação da PUCC (O organizador do evento também sugeriu que fôssemos andando até o Shopping D. Pedro!).

Às 14h começou a prova, contendo 11 problemas. Eu e o Alessandro, o reserva dos times, ficamos na sala dos coaches, de onde dava para ver os competidores. Rapidamente começaram a surgir balões para o problema A e o problema J. A partir daí o time Unicamp Alpha e o Dona Margarida do ICMC começaram a disputa pelo primeiro lugar. O time Unicamp Beta ficou embolado com três outros times do ICMC, além do time de Sorocaba. Ao congelar o placar (com 4h de prova), o Dona Margarida estancou em 6 problemas e o Unicamp Alpha continuou ganhando balões até chegar em 9. Logo atrás havia dois times do ICMC com 6 e o Unicamp Beta e o time de Sorocaba com 5. Nesse momento estávamos classificando 2 times para a final, devido à regra de só poderem ir dois times por faculdade. Porém, a qualquer momento o time de Sorocaba poderia passar um problema. Durante a última hora, muita coisa aconteceu. A equipe Dona Margarida passou 3 problemas e alcançou o Unicamp Alpha e até ficamos preocupados de perder o primeiro lugar. Além disso, o Unicamp Delta, passou dois problemas e acabou deixando pra trás o Unicamp Beta e o time de Sorocaba.

O placar na nossa regional ficou o seguinte:

1. Unicamp – Alpha, 9 problemas (Douglas Santos, Igor Assis, Paulo Costa)

2. ICMC – Dona Margarida, 9 problemas

3. ICMC – Capitão Ad Hoc, 7 problemas

4. ICMC – HEAP HEAP ARRAY, 6 problemas

5. Unicamp – Delta, 6 problemas (Alex Brandt, Igor Wolff, Patrícia Hongo)

6. Unicamp – Beta, 5 problemas (Bruno Crepaldi, Ruan Silva, Thiago Cavalcante)

7. Sorocaba – De última hora, 5 problemas

12. Unicamp – Gamma , 3 problemas (Charles Garcia, Felipe Fleming, Thiago Santos)

Ninguém fez os problemas G e K na nossa sede, mas em outras sedes no Brasil sim. Porém, ninguém chegou a gabaritar a prova. Um pessoal organizou o placar nacional nessa planilha.

Quase ao mesmo tempo em que ocorreu a prova, houve um contest com os mesmos problemas no site de Valladolid aberto ao público. Lá, 6 pessoas fecharam a prova >.<

No geral achei que fomos bem. Esse ano tivemos uma renovação considerável nos times. Prova disso é que excetuando-se o Paulo e o Igor do primeiro time, todos os outros competidores são primeiro ou segundo-anistas. No Unicamp Delta o Igor e a Patrícia são bixos da Engenharia.

Competidores, reserva e coach reunidos.

Depois da prova fomos ao Shopping D. Pedro jantar e, lógico, discutir sobre a prova :)

Agora é treinar até a final, em Joinville!

Anúncios

Biblioteca MPI

Setembro 17, 2010

Introdução

Recentemente resolvi aprender um pouco sobre a biblioteca MPI (Message Passing Interface). Ela é uma das principais bibliotecas para fazer a paralelização de código. Existe uma outra chamada OpenMP. Pelo que andei pesquisando, OpenMP é feita para sistemas com memória compartilhada, como por exemplo uma máquina multicore. Nela temos vários processadores compartilhando uma mesma memória. Já o MPI é voltado para memória distribuída, como é o caso de clusters, que são basicamente um conjunto de máquinas rodando um sistema operacional distribuído. A vantagem do MPI é que ele é escalável para as diversas máquinas do cluster, enquanto o OpenMP fica restrito a uma só. Apesar de o MPI também rodar em uma máquina multicore só, podemos ter um desempenho menor em relação ao OpenMP, já que o primeiro não aproveita o fato da memória ser compartilhada. Uma abordagem híbrida pode ser uma boa solução. A nível de cluster, utilizamos o MPI e em cada nó (máquina) do cluster, usamos o OpenMP.

Super-computador Cray Jaguar, o computador mais rápido do mundo. Muitos dos super-computadores (top500) são clusters.

A paralelização de código consiste em quebrá-lo em pedaços que podem ser executados independentemente e distribuir para vários processadores. Assim, por exemplo, um programa que recebe um vetor de inteiros e soma seus elementos, provavelmente o fará através de um laço, parecido com o programa abaixo

int s = 0, v[ ] = {1,2,3,4};

for (int i=0; i<4; i++)
    s += v[i];

Se a máquina for multicore, podemos quebrar o laço em várias partes de forma que cada processador execute aquele pedaço do laço. Se o vetor tivesse 15.000 entradas e a máquina tiver quatro cores, usaríamos uma para gerenciar a distribuição de trabalho e as outras três para fazer os cálculos. O primeiro processador somaria os elementos de 0 a 4.999, o segundo de 5.000 a 9.999 e o terceiro de 10.000 a 14.999. Depois de computar a soma dos elementos, cada processador devolveria o resultado para o processador principal e este trataria de somar os resultados parciais. Uma propriedade importante que o programa acima tem é que cada iteração do laço é independente das outras. Assim, o resultado não ia ser diferente se eu resolvesse somar o vetor começando pelo último elemento. Isso não é verdade por exemplo, para o cálculo da recorrência de fibonacci. Nesse caso temos

Um loop para calcular o n-ésimo número de fibonacci não pode ser paralelizado. Programas como o da soma são exemplos fáceis de paralelizar, sendo apenas necessário distribuir pedaços das iterações para os processadores. Tais programas são ditos vergonhosamente (:P) paralelizáveis (do inglês embarrassingly parallel).

Para compilar um programa C++ utilizando MPI no linux, fazemos:

mpic++ programa.cpp -o programa

Em seguida, é preciso editar um arquivo de texto chamado ‘hostfile’ contendo o endereço dos nós do cluster (no caso de uma máquina, basta colocar localhost). Após isso é preciso inicializar o LAM (Local Area Multicomputer)

lamboot -v hostfile

Para executar o programa, basta fazer

mpirun -np <numero de threads> ./programa <argumentos do programa>

O programa iniciará com o número especificado de threads. Como queremos paralelizar o código, esse número pode ser a quantidade de processadores disponíveis. O laboratório IC3 da Unicamp possui um cluster com atualmente 6 nós, cada qual uma máquina com 4 processadores. Dessa forma, temos 24 processadores para paralelizar o código.

Testes

Para aprender um pouco sobre a biblioteca e testar suas capacidades, resolvi implementar o seguinte algoritmo: dado um vetor de n inteiros, execute uma função com complexidade para cada elemento do vetor. A ideia então é paralelizar esse código que é vergonhosamente paralelizável.

Testei duas abordagens: uma em que o número de iterações para cada processador é igual, ou seja, n dividido pelo número de processadores. A outra divide as iterações em pequenos blocos (e.g. blocos de tamanho 10) e distribui-se um bloco para cada processador. Conforme este termine de computar, retorna a resposta para o processador principal que se encarrega de mandar um novo bloco para aquele, até que todos os blocos tenham sido processados. Chamei a primeira estratégia de uniform-share e a outra de demand-share. Os processadores podem levar tempos diferentes para computar sua parte e por isso aqueles que terminarem primeiro vão ficar ociosos até que o último processo termine. Com o demand-share esse efeito é minimizado, pois quem terminar suas iterações mais rápido, acaba processando mais blocos. A desvantagem é que há um maior número de troca de mensagens nessa abordagem.

Fiz dois tipos de instâncias: a primeira consiste de 50.000 números aleatórios entre 10 e 20, enquanto a segunda consiste de 50.000 números indo de 10 a 20 em ordem crescente (os 5.000 primeiros números são 10, os próximos 5.000 são 11 e assim por diante). Chamei a primeira de random e a segunda de sequential.

Tempos (em segundos) para a instância random.

Aqui os tempos foram praticamente os mesmos. Eu imaginava que o overhead causado pelo número maior de mensagens pudesse aumentar o tempo do algoritmo por demanda, mas não foi o que se verificou.

Tempo (em segundos) para a instância sequential.

Para a instância sequential, aconteceu o que eu esperava: a divisão uniforme fez com que os últimos processadores ficassem com a parte mais demorada (só com elementos 20), o que prejudicou o tempo total de execução.

Próximos Passos

Pretendo fazer testes com problemas não tão vergonhosamente paralelizáveis e também aprender como integrar MPI e OpenMP. O prof. Rodolfo, especialista em arquitetura multicore, sugeriu também que eu tentasse otimizações em nível mais baixo, através das instruções SSE. Lembro vagamente o que são e por isso vou ter que dar uma revisada.


Galeria de Arte

Setembro 10, 2010

O Marcelo Couto é ex-membro no Laboratório de Otimização e Combinatória que defendeu sua tese de mestrado recentemente. Orientado pelo Cid Souza e Pedro Rezende, ele pesquisou durante seu mestrado o problema da Galeria de Arte. Vou tentar explicar resumidamente seu trabalho, me baseando em sua apresentação na defesa e alguns slides na página do prof. Rezende, de onde também peguei as figuras desse post.

Introdução

Dado um polígono simples, sem buracos, queremos determinar o menor número de vértices que enxergam todo o interior do polígono. Há várias versões desse problema, mas a que eu vou apresentar aqui é a versão em que os guardas são fixos em vértices e têm visão de 360 graus. Uma aplicação prática que pode ser modelada como esse problema é minimizar o número de câmeras no interior de um museu que cubram toda a sua extensão.

Inicialmente os polígonos considerados eram ortogonais, ou seja, todos os seus lados são paralelos a algum dos eixos. Lee e Lin [1] provaram que, mesmo para polígonos ortogonais, o problema da galeria de arte é NP-difícil.

Em sua tese de mestrado, o Marcelo ataca o problema com Programação Linear Inteira. O problema da galeria de arte pode ser reduzido para o problema da cobertura de conjuntos: O universo de elementos são todos os infinitos pontos internos do polígono. Cada vértice do polígono representa o subconjunto de pontos que um guarda cobre estando naquele vértice. Queremos encontrar o menor número de subconjuntos (guardas) que cobrem todo o conjunto de pontos. O problema dessa abordagem é que há infinitos elementos, o que torna impossível explicitá-los no modelo.

Para resolver esse problema, foi usada uma técnica muito interessante de discretização: Escolha apenas alguns pontos interiores do polígono. Com isso é possível construir o modelo PLI e calcular a cobertura de conjuntos mínima. Algumas regiões vão ficar descobertas. Adicione mais pontos das regiões não cobertas ao modelo e re-execute o algoritmo até que não restem mais dessas regiões. É possível mostrar que esse algoritmo converge em tempo finito.

Modelo de PLI

Seja U o conjunto universo de pontos e S um conjunto de subconjuntos de U, de forma que a união dos subconjuntos em S é igual a U. Em geral, existe um custo associado a cada subconjunto i de S. O objetivo é escolher alguns subconjuntos em S que cubram U e tenham custo mínimo.

Definimos a variável binária que é igual a 1 se o subconjunto i está na solução e 0 caso contrário. Ficamos com o seguinte modelo:

Sujeito a:

(1) Para todo elemento u em U,

O lado direito da restrição (1) consiste da soma das variáveis de todos os subconjuntos que contém um dado elemento u. Assim, essa restrição garante que cada elemento é coberto por pelo menos um subconjunto. No problema da galeria de arte padrão não há custo associado à colocação dos guardas de forma que no modelo do Marcelo os custos são unitários.

Estratégias de discretização

A primeira ideia para discretizar esses pontos foi considerar apenas pontos que pertencessem a um grid imaginário, conforme a figura abaixo:

Discretização em Grid: pontos vermelhos são os elementos a serem cobertos.

Dependendo do espaçamento do grid, podem haver muitos pontos no modelo e a maioria deles podem ser irrelevantes. Então, porque não começar com poucos pontos e deixar o algoritmo encontrar as regiões não cobertas? Surgiu então a ideia de colocar apenas os vértices do polígono como pontos iniciais do modelo.

Uma outra opção para não depender do espaçamento do grid, foi considerar um grid induzido pelos lados do polígono. Para isso, basta estender para uma reta, cada segmento de reta que forma o lado do polígono. As interseções dessas retas que estiverem dentro do polígono são colocadas no modelo inicialmente. A ordem de pontos aqui é O(n^2).

Discretização com grid induzido

Depois foi provado que é possível determinar um número finito de pontos de forma que nenhuma região fique descoberta após a resolução do modelo. A ideia é que as regiões de visibilidade dos vértices particionam o polígono em regiões. Para entender melhor, considere a região de visibilidade do vértice 12 da figura abaixo.

Regiao de Visibilidade do vértice 12

Considere os segmentos de reta que formam as fronteiras entre as regiões cinza e branca. A união desses segmentos induzidos pela região de visibilidade particiona o polígono em um conjunto de regiões, chamadas AVP’s (Atomic Visibility Polygons). Colocar um ponto no centróide de cada uma dessas regiões é suficiente para que todas as regiões sejam cobertas com apenas uma iteração do algoritmo.

Partição induzida pelas regiões de visibilidade dos vértices

Foi provado que o número dessas regiões é O(n^3), o que representa um número bem grande de pontos. Além disso, a construção dessas regiões leva um tempo considerável. Assim, tem-se um tradeoff entre tempo de pré-processamento e número de iterações. No final das contas, a maior parcela do tempo total do algoritmo com discretização em AVP’s foi devido a pré-processamento, como pode ser visto no gráfico abaixo. Surpreendentemente, começar com apenas os vértices apresentou o melhor desempenho, mesmo na fase de processamento.

Resultados Computacionais

Conclusão

Depois o trabalho também passou a resolver polígonos não-ortogonais e com buracos. Além disso, foi muito eficiente na prática, resolvendo instâncias muito maiores do que se tinha conhecimento até então. Com isso, foram possíveis diversas publicações internacionais.

Referências:

[1] Computational complexity of art gallery problems, D Lee, A Lin – IEEE Transactions on Information Theory, 1986 – ieeexplore.ieee.org


GRASP

Setembro 3, 2010

GRASP (Greedy Randomized Adaptive Search Procedures) é uma meta-heurística para problemas de otimização combinatória. Meta-heurística basicamente é uma heurística que resolve problemas genéricos, com algumas pequenas adaptações. Esse método foi originalmente desenvolvido pelo brasileiro Maurício Resende, que hoje é pesquisador no AT&T.

De maneira geral, o algoritmo consiste de duas fases: construção e busca local. Na fase de construção tenta-se construir uma solução viável com um método que é um pouco guloso e um pouco aleatório. A busca local consiste em explorar vizinhos de uma solução até encontrar uma solução ótima local. Essas duas fases são repetidas por um certo número de iterações. Intuitivamente, o algoritmo sorteia pontos no espaço de soluções, quase que aleatoriamente (não é totalmente aleatório devido ao fator guloso, que tende a sortear soluções de melhor custo). Aí a busca local faz o trabalho de achar o ótimo local a partir de cada um desses pontos. Observe que as iterações são independentes entre si.

Construção da solução inicial

Para ficar mais claro, vamos considerar o problema de encontrar o caminho Hamiltoniano de custo mínimo, ou seja, dado um conjunto de cidades, encontrar a ordem em que se deve visitá-las de forma a minimizar o custo total de se viajar de uma cidade para outra. Podemos enxergar esse problema como o problema de encontrar a permutação de menor custo de elementos. O custo de uma permutação é a soma das distâncias entre dois elementos adjacentes nela.

O algoritmo é basicamente o seguinte: fazemos n iterações. Na i-ésima iteração, decidimos qual elemento ocupará a i-ésima posição do vetor representando a permutação. Para cada i,

  1. Construímos uma lista restrita de candidatos (Restricted Candidate List RCL)
  2. Selecionamos um elemento ‘s’ da RLC aleatoriamente e inserimos ele na posição i
  3. Remova ‘s’ da lista de candidatos

A construção da RCL é a parte principal dessa fase. Primeiramente calculamos o aumento no custo que cada elemento da lista de candidatos causará se for inserido na i-ésima posição. No nosso caso isso é basicamente sua distância para o elemento (i-1). Salvamos qual foi o maior e o menor custo desses elementos, cmin e cmax, respectivamente. Aí inserimos na RCL apenas os elementos cujo custo c(e) satisfizerem

Onde é um parâmetro de controle. Se , só o elemento de menor custo será inserido na RCL enquanto que se , todos os elementos o serão. Observe que como o elemento da RCL é escolhido aleatoriamente, se só houver um elemento, não há espaço para aleatoriedade e o algoritmo fica puramente guloso. Por outro lado, se todos os elementos estão na RCL, qualquer elemento é igualmente possível de ser escolhido, o que torna o algoritmo puramente aleatorio. Assim, fornece um controle sobre o quão guloso ou aleatorio é essa construção.

Busca Local

Após construída a solução inicial, realizamos a busca local que consiste em andar por soluções adjacentes que melhorem o custo da solução. A escolha da vizinhança é crucial para a eficácia do algoritmo. No nosso problema, uma possível vizinhaça seria as soluções obtidas trocando-se dois elementos de posição.

Há duas estratégias para “caminhar” em uma busca local: o First Improving e o Best Improving. Na primeira, logo que encontramos uma solução vizinha que seja melhor do que a solução atual, damos o passo. Já na segunda, exploramos todos os possíveis vizinhos e damos o passo na direção daquele de melhor custo.

Busca local termina em ótimos locais.

Path Relinking

Uma técnica para complementar o algoritmo GRASP é chamada de Path Relinking. Ela consiste em guardar um conjunto limitado de soluções — de baixo custo e suficientemente diferentes entre si — encontradas no decorrer do GRASP, e é chamado de soluções de elite. Ao chegar no ótimo local após a busca, consideramos os caminhos para sair dessa solução e chegar até cada uma das soluções de elite. A esperança é de que existam boas soluções no meio desses caminhos.

Bibliografia

[1] Greedy Randomized Adaptive Search Procedures: Advances and Applications – Resende, Mauricio e Ribeiro, Celso. Handbook of Metaheuristics 2008.