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

Última alteração: July 12, 2004

Professor: Nivio Ziviani
Monitor: Fabiano C. Botelho
4 $^{\underline{o}}$ Trabalho Prático - 03/06/04 - 10 pontos
Data de Entrega: 25/06/04
Penalização por Atrazo: 1 ponto até 01/07/04 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).

Problema: Quicksort Paralelo

Implemente o algoritmo Parallel Sorting by Regular Sampling (PSRS) descrito na seção 10.5.3 do livro do Quinn (1994), utilizando uma máquina paralela MIMD. A máquina paralela MIMD deverá ser do tipo rede de estações de trabalho (NOW - Network Of Workstations) (Anderson, Culler e Patterson, 1995), utilizando os mecanismos de comunicação e sincronização descritos nesta apresentação. Vários exemplos podem ser encontrados aqui.

O que deve ser entregue:

• Listagem do programa.
• Listagem dos testes executados: execução passo-a-passo da massa de dados da figura 10-29 do livro do Quinn (1994).
• Speedup obtido pela sua implementação. Utilize 2, 4 e 8 máquinas. Gere massas de teste usando um gerador de números aleatórios. Discuta os resultados obtidos.
• Faça um estudo comparativo do algoritmo implementado com a versão tradicional de Quicksort paralelo da seção 10.5.1.
• Discuta a implementação do Quicksort paralelo sob o ponto de vista dos modelos de paralelismo de dados e de controle.

Obs.: 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 do DCC.

Referências

[Q] M. J. Quinn, Parallel Computing Theory and Practice, McGraw-Hill, 1994, cap. 10.

T. Anderson and D. Culler and D. Patterson ``A Case for NOW (Network of Workstations)'', IEEE Micro, vol. 15, no. 1, 1995, pp. 54-64.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 pa04tp4

The translation was initiated by Nivio Ziviani on 2004-07-12