Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
PROJETO E ANÁLISE DE ALGORITMOS

Última alteração: 17. Julho 2003

Horario : Terça: 14:55 - 16:35, Quinta: 14:55 - 16:35, Sala: 2029
Professor: Nivio Ziviani
Monitor: Bruno Pôssas
4 $^{\underline{o}}$ Trabalho Prático - 15/07/03 - 10 pontos
Data de Entrega: 01/08/03
Penalização por Atrazo: 1 ponto até 06/08/03 mais 1 ponto por dia útil a seguir
Observação: Toda a documentação deverá ser apresentada como uma página acessível via Web (apresente o link para acesso à documentação).

Computação Paralela

O objetivo deste trabalho é projetar um algoritmo paralelo para ser executado em uma rede de estações de trabalho. A implementação deve ser feita usando sockets para comunicação entre o processo mestre e os processos escravos.

O processo mestre envia uma requisição para os processos escravos e espera pelas respostas. Para ler as respostas dos diferentes processos escravos enviadas assincronamente, o processo mestre pode adotar uma das seguintes opções:

• Criação de diferentes threads (processos leves) para ler os dados provenientes de cada um dos sockets associados aos diferentes processos escravos;
• Uso da função select para checar por dados disponíveis para leitura no conjunto de sockets relativos aos processos escravos. Essa opção é mais eficiente, pois elimina o overhead associado ao gerenciamento das threads.

Veja demonstração de comunicação entre processos usando select em mastersel.c e slavesel.c e usando threads em master.c e slave.c.

Algoritmo Paralelo para Casamento de Padrão

Implemente um algoritmo paralelo para recuperar ocorrências de padrões em arquivos constituídos de documentos e distribuídos através de uma rede de estações de trabalho.

O programa recebe como parâmetros de entrada uma cadeia de caracteres e a opção de busca exata ($k=0$) ou aproximada ($0 < k < m$), e imprime como saída todas as ocorrências do padrão no texto. Para a busca sequencial nos documentos de texto, você deverá utilizar o algoritmo Shift-And para casamento aproximado de padrões.

Análise de Desempenho

Para analisar o desempenho do sistema, compare o algoritmo sequencial com o algoritmo paralelo utilizando 2 e 4 máquinas. Discuta os resultados do algoritmo de casamento de padrão aproximado, tanto na busca sequencial quanto na busca paralela nos documentos de texto distribuídos. Use como métrica de avaliação o speedup do algoritmo paralelo.

A coleção de texto será constituída por um conjunto de $1$ gigabyte de arquivos da TREC, que serão distribuídos igualmente por tamanho entre 2 e 4 máquinas, e por um conjunto de $10$ consultas. As máquinas, arquivos textuais, conjunto de consultas e respectivos diretórios para os testes serão divulgados oportunamente.

Observações:

1. Crie uma interface de uso do seu sistema parecida com a do sistema agrep disponível na rede do DCC.

2. A saída do programa deve mostrar a linha do documento que contêm o padrão.

3. Toda a fase de depuração deverá ser executada em uma única estação de trabalho, até que seu programa esteja inteiramente depurado. Apenas a fase de estudos do speedup deverá ser realizada utilizando a rede a ser disponibilizada para os experimentos.

O que deve ser entregue:

• Explicação suscinta dos algoritmos e estruturas de dados utilizados para resolver o problema. (2 pontos)

• Listagem dos programas implementados. O código deve ser bem comentado e organizado. (4 pontos)

• Resultados dos experimentos usando os arquivos e consultas disponibilizadas para os testes: (i) listagem da saída do programa; (ii) avaliação empírica do desempenho do sistema, reportando o speedup obtido para o algoritmo paralelo. (4 pontos)

Referências

M. J. Quinn, Parallel Computing Theory and Practice, McGraw-Hill, 1994, cap. 12.

Stevens, W. Richard, ``Unix Network Programming'', Prentice-Hall, 2nd Edition, 1998.

Ziviani, N. Projeto de Algoritmos com Implementações em Pascal e C, Thomson, segunda edição, 2004.