Paralelizando o problema da Mochila binária com OpenMP

Revisão do algoritmo Knapsack

O problema da mochila é um dos mais populares problemas de otimização combinatória. Seu nome vem do problema enfrentado por alguém que está limitado pelo tamanho de uma mochila e deve carregar a mochila com os objetos mais úteis ou valiosos.

O objetivo do algoritmo é conseguir a otimização do carregamento da mochila com um conjunto de itens, nesse caso livros, maximizando o valor total e minimizando o peso total dos itens que estão sendo carregados.

No problema da Mochila, temos N itens, de 1 a  N.  Cada item i ten um valor v_i  e um peso w_i. Todos os valores e os pesos são positivos e inteiros. O peso máximo que podemos levar na bolsa e W. A finalidade é carregar a mochila com um conjunto de itens de forma que o seu peso total não exceda a capacidade W e seu valor total seja o maior possível.

Formalmente definida:

Suponhamos que W  = 15, N = 6, e temos o seguinte conjunto de objetos:

A solução ótima seria escolher os itens: 1, 2, 5 e 6. O valor total de esta solução e de 330 e o peso de 15.

O problema knapsack pode ser resolvido por vários métodos entre eles estão o algoritmo de enumeração exaustiva, o método guloso e atraves da função recursiva.

Neste trabalho analisamos o código do programa seqüencial knapsack.tar.gz. Observamos que o programa tem três opções para geração de pesos e valores dos objetos (neste caso livros): podem ser gerados de forma aleatória, de forma estática ou atraves de um arquivo. Optamos pela forma estatica, de modo que os valores vam se repetindo a cada execução, ou seja os sorteio dos livros com seus valores e pesos são sempre os mesmo, o que nos permite melhor a valiar o desempenho entre os diferentes formas de paralelizar

O pacote alem de conter o programa knap.c; traz um timer para a medição dos tempos de execução; knap_defaults.h que contem os valores por default dos números de objetos, a capacidade da mochila, e as cotas dos pesos e dos valores dos objetos e outros arquivos que não nos interessam (knap.upc, knap.pbs e knap.ll). Os valores por padrão foram alterados conforme o codigo abaixo para todas as execuções

O timer.c contem funções que permitem a visualização dos tempos de execução em  pontos  do programa. Neste caso o knap.c as funções solve() e backtrack().Permitindo a visualização da parte mais critica do programa que é a função solve() que corresponde a maior fatia do tempo de execução.

Durante a execução do programa a função solve() leva em media 9.295762 segundos de processamento, e a a função backtrack() leva em media 0.006205 segundos, no programa original seqüencial.

Depois de ter refletido sobre o algoritmo se chegou à conclusão de que a opção mais razoável é paralelizar a função solve().

A função solve() possui três for's, sendo os dois ultimos aninhados , inicialmente tentamos paralelizar os três porem, problemas de sincronização e autalizações perdidas resultaram em falhas de segmentação, o que nos obrigou a testar as diretivas #pragma omp critica e #pragma omp

Logo varias tentativas de paralelização do algoritmo deduzimos que a o particionamento deve-se fazer com o cuidado de não irrumpir a comunicação entre os processos. Já que nas primeiras tentativas de paralelização os resultados foram alterados com relação a execução em seqüencial.

Propostas de paralelização

Para paralelizar o algoritmo de knapsack utilizamos o particionamento de dados. Adicionando a o programa as diretivas OpenMP  parallel e for.

Neste primeiro programa paralelizamos todas as estruturas for, e o rendimento obtido foi abaixo do sequencial, o tempo desempenho na execução desta versão paralelizada foi maior em relação a versão sequencial.

Na segunda proposta de paralelização, unicamente particionamos o primeiro for. Assim como na primeira tentativa o tempo de desempenho em vez de melhorar aumentou.

A seguinte alternativa de paralelização do algoritmo de knapsack foi a mais efetiva nos tempos de desempenho. Com este codigo o tempo de execução foi reduzido a quase a metade em relação a execução em sequencial, mantendo a precisão dos resultados.

Análise de desempenho e resultados

A maquina utilizada para os testes de execução linux03. Os resultados da execução paralela com 100000 objetos e capacidade máxima de 5000:

Fator de aceleração (speedup)

Eficiência

Conclusões

Após a análise do funcionamento do algoritmo do programa seqüencial procedemos na busca de uma alternativa válida para a paralelização do problema da mochila binária. Encontramos que a solução proposta não é a ideal para n processadores, pois ao analisar o speedup descobrimos que esta longe do  speedup linear como podemos observar no gráfico. Assim como era esperado ao acrescentar mais threads nas execuções, o tempo de processamento foi aumentando. Mesmo assim acreditamos que o programa fruto deste trabalho é uma boa alternativa para a paralelização do problema da mochila binária, devido a que com um número de dois threads o tempo de execução do programa paralelo caiu pela metade em comparação com o programa sequencial.


Lizzi Villalba
Sandro Oliveria