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

Algoritmos e Estruturas de Dados III

1^o semestre de 2008

Trabalho prático 4

Data de entrega: 01 de Julho de 2008 (nenhum atraso será permitido, ou seja, trabalhos atrasados - qualquer atraso, valerão ZERO
O Trabalho pode ser feito em grupos de dois alunos, no maximo.

Este trabalho tem por objetivo exercitar questões ligadas a paralelização de algoritmos. Nele, você deverá paralelizar, utilizando primitivas da biblioteca pthreads, um algoritmo de criação de uma árvore B a partir de uma lista de registros. Você deverá avaliar a eficiência da sua paralelização.

Mais especificamente, o seu programa deverá:

• Criar uma árvore B de ordem m vazia.
• Ler de um arquivo uma lista com N registros (apenas as chaves representadas por inteiros), inserindo um a um na árvore criada.

De forma a tentar melhorar a eficiência do algoritmo, múltiplas threads trabalhadoras, cada uma responsável pela inserção de um registro, deverão executar paralelamente. Estas threads deverão ser criadas e iniciadas por uma thread mestre, responsável pela inicialização e gerenciamento do programa. A sua estratégia de criação de threads pode ser estática ou dinâmica. Seja qual for, o seu programa deve manter múltiplas threads de execução simultâneas, garantindo, entretanto, exclusão mútua entre elas sempre que necessário.

Para facilitar, assuma que:

• os nós da árvore B estão todos sempre em memória principal.
• os nós são pre-alocados (via malloc ) pela thread mestre, antes da criação das threads trabalhadoras, e são mantidos em um buffer compartilhado.

Apresente em seu relatório uma descrição da sua estratégia de paralelização, uma justificativa da escolha e uma avaliação da sua eficiência, comparando seu tempo de execução com o da versão sequencial, para diferentes tamanhos de entrada N e m. Para todos os casos, faça sempre N >> 2m (isto é escolha valores de N muito maiores que 2m ).