Projeto de Programação 2
Sokoban - 倉庫番

A entrada do seu programa será dada por um arquivo contendo a fase a ser resolvida e o número de threads a utilizar (além do main thread). Você pode baixar aqui um conjunto com as 90+2 fases (que serão utilizadas durante a correção). As fases 01 a 90 são as fases clássicas do jogo e as fases -1 e 00 são fases artificialmente simples que são úteis para testar o seu código.

Os arquivos utilizam a seguinte notação (cada caractere é uma casa do tabuleiro):

• Casas vazias são representadas por espaços
• # (sustenido) representa uma parede
• $ (sifrão) indica a presença de uma caixa
• . (ponto) é uma casa-alvo
• * (asterisco) é caixa sobre uma casa-alvo
• @ (arroba) é o Sokoban
• + (sinal de adição) é o Sokoban em uma casa-alvo

Veja o do arquivo de entrada level01 abaixo:

    #####
    #   #
    #$  #
  ###  $##
  #  $ $ #
### # ## #   ######
#   # ## #####  ..#
# $  $          ..#
##### ### #@##  ..#
    #     #########
    #######

E uma versão gráfica gerada pelo XSok da fase acima:

As fases 01-90 disponibilizadas no arquivo acima são as mesmas disponíveis no XSok utilizando o Level Subset → Sokoban. Para instalar o XSok basta fazer:

sudo apt-get install xsok

ou o equivalente da sua distribuição Linux.

A saída do seu programa deve consistir na sequência de movimentos feitos pelo Sokoban para resolver a fase dada como entrada. O formato da saída é o seguinte (formato LURD):

• u - Cima (up)
• d - Baixo (down)
• l - Esquerda (left)
• r - Direita (right)
• U - Cima com movimentação de caixa (up)
• D - Baixo com movimentação de caixa (down)
• L - Esquerda com movimentação de caixa (left)
• R - Direita com movimentação de caixa (right)

Arquivo level_00:

#######
#     #
#     #
#. #  #
#. $$ #
#.$$  #
#.#  @#
#######

Exemplo de execução ($ indica o prompt do terminal):

$ ./meu_sokoban level00 4
ulULLulDDurrrddlULrruLLrrUruLLLulD
$

ATENÇÃO Seu programa deve ser capaz de resolver pelo menos os níveis -1, 00 e 01 (seu programa será executado em uma máquina com pelo menos 16GB de RAM). Programas que não forem capazes de resolver o nível 01 sofrerão uma redução significativa na nota.

As execuções de teste serão feitas em máquinas paralelas com até 16 processadores (\(1 \le P \le 16\)).

---

• Você deve entregar todo o código fonte do seu programa juntamente com instruções claras sobre sua compilação e execução.
• Programas com erros de compilação receberão nota 0.
• O ambiente de testes será Linux com GCC. Você deve entregar uma versão sequencial do seu código além da versão paralelizada com Pthreads e OpenMP. Lembre-se: aqui estamos interessados na versão força bruta do problema, e não em uma solução que envolva a aplicação de conceitos avançados de IA.
• Programas que não cumprirem os requisitos (resultados incorretos, erros durante a execução, …) descritos na seção anterior receberão nota 0.
• Programas sem boa documentação no código terão a sua nota reduzida.
• Programas desorganizados (nomes de variáveis/funções ruins, falta de identação, …) terão a sua nota reduzida.

Juntamente com o seu código você deverá entregar um relatório (máximo de 4 páginas) que contenha:

• Fases resolvidas: Solução, tempo para resolver, máquina utilizada e número de threads utilizado.
• Uma explicação detalhada de como o particionamento das tarefas que foi feito entre os threads na sua implementação.
• Tabelas e gráficos do speedup e da eficiência para pelo menos as fases 00 e 01 com \(1 \le P \le 16\) (não esqueça de incluir a especificação da máquina utilizada para a execução
• Interpretação dos valores mostrados na tabela anterior. Descreva e interprete a variação do speedup e da eficiência em relação à \(P\). Explique os resultados obtidos levando em consideração as características da máquina utilizada.
• Análise da escalabilidade da sua implementação. Ela é escalável? Apresenta escalabilidade forte ou fraca?
• Análise do consumo de memória da sua implementação.
• Análise do balanceamento de carga. Todos os threads recebem a mesma quantidade de trabalho? Todos acabam a execução aproximadamente ao mesmo tempo?

Dica: Utilize como modelo para a sua análise as seções 3.6.2, 3.6.3 e 3.6.4 do livro [PP].

Obs.: Certifique-se de executar o seu programa pelo menos 3 vezes e relate o tempo da execução mais rápida (wall-clock time). Veja a motivação para fazê-lo nas notas de aula e/ou no livro [PP]-Cap. 3.

• É esperado que você consiga speedup > 1 na versão paralela.
• O teste de desempenho será efetuado em uma máquina Intel Xeon E5 com 16 cores (32 threads) com 64 GB de RAM.

O programa que tiver o melhor speedup dentre os entregues receberá 1 ponto adicional na avaliação.

Caso o seu código execute mais rapidamente que o código do professor ou caso ele seja o mais rápido da turma.

Projetos entregues com atraso sofrerão uma redução da nota conforme a tabela abaixo:

Dias em Atraso	Nota Máxima
0	10
1	7
2	6
3	5
>3	0

---