Projeto de Programação 1
Crivo de Erastótenes Paralelo usando MPI
Universidade Federal do ABC
MCZA020-13 - Programação Paralela
2018.Q3
Professor: Emilio Francesquini
E-mail: e.francesquini@ufabc.edu.br
Data limite: 28/10/2018 \(\rightarrow\) 04/11/2018 \(\rightarrow\) 11/11/2018 Hard Deadline!
Índice
1 Introdução
O Crivo de Erastótenes é um algoritmo supreendentemente eficiente para encontrar números primos até um valor limite pré-definido. Tal algoritmo teria sido criado pelo matemático grego Erastótenes (285-194 a.C.) que, entre outras proezas, foi o terceiro bibliotecário chefe da Biblioteca de Alexandria e o primeiro a calcular a circunferência da Terra.
Figura 1: Erastótenes (Fonte: Wikipedia)
Um número primo é um número natural que tem exatamente \(2\) divisores distintos: \(1\) e ele mesmo.
O crivo de Erastótenes é um método para encontrar todos os números primos até um número limite \(n\). O método pode ser descrito pelos seguintes passos1:
- Crie uma lista de inteiros consecutivos de \(2\) até \(n\): (\(2, 3, 4, \ldots, n\)).
- Seja \(p = 2\), o primeiro número primo.
- Enumere todos os múltiplos de \(p\) até \(n\) e marque-os como não primos na lista criada no primeiro passo. Esses números serão da forma \(2p, 3p, 4p,\ldots\) Note que \(p\) deve continuar na lista (pois é primo).
- Encontre o primeiro número na lista que seja maior do que \(p\) e que não esteja marcado como não primo. Caso não exista tal número, pare. Caso contrário, seja \(p\) igual a este número (que é o próximo primo já que caso não fosse primo ele teria sido marcado no passo 3), repita a partir do passo 3.
- Quando o algoritmo terminar, os números não marcados presentes na lista serão todos os números primos entre \(1\) e \(n\).
Figura 2: Animação do Crivo de Erastótenes (Fonte: Wikipedia)
Note que algoritmo pode marcar alguns números mais do que uma vez, por exemplo, 15 vai ser marcado tanto pelo 3 quanto pelo 5.
1.1 Possíveis otimizações
Alguns aprimoramentos podem ser feitos ao crivo para aumentar a eficiência da sua implementação, como por exemplo (lista não completa):
- Só precisamos marcar os números da lista (passo 3) a partir de \(p^2\) (Por quê?)
- A lista inicial só precisa conter, além de 2, os números ímpares.
- Na verdade, a lista só precisaria conter, além de \(2\) e \(3\), os números da forma \(6k \pm 1\). (Por quê?)
2 O projeto
Este projeto2 tem dois objetivos. O primeiro objetivo é implementar uma versão paralela do Crivo de Erastótenes utilizando MPI e a linguagem de programação C. O segundo objetivo é analizar o desempenho das implementações apresentadas. Observe como o speedup e a eficiência variam com a adição de processadores e com o tamanho do problema.
O seu programa deverá receber como entrada \(N\) (o limite superior até o qual todos os números primos deverão ser gerados) e ter como saída a quantidade de números primos encontrados no intervalo \([1, n]\).
As execuções de teste serão feitas em máquinas paralelas com até 16 processadores (\(1 \le P \le 16\)) e com \(N\) variando desde \(10^6\) até \(10^{11}\).
Seu programa deve ser capaz de funcionar no mínimo com \(N = 10^6\).
3 Entregas e avaliação
Todos as entregas descritas abaixo devem ser enviadas em um único arquivo compactado a ser enviado pelo TIDIA em uma tarefa criada para este fim.
Link para entrega da atividade: http://tidia4.ufabc.edu.br/x/xAQZXC
3.1 Código (4 pontos)
- 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 OpenMPI e GCC. Você deve entregar uma versão sequencial do seu código além da versão paralelizada com MPI. Lembre-se: a versão sequencial deve ser a versão mais eficiente possível!
- 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.
3.2 Relatório (3 pontos)
Juntamente com o seu código você deverá entregar um relatório (máximo de 5 páginas) que contenha:
- Quantidade de números primos entre 1 e 1.000.000.000
- Os 20 últimos números primos do intervalo 1 e 1.000.000.000
- Uma explicação detalhada de como o particionamento das tarefas foi feito entre os processos na sua implementação.
- Tabelas e gráficos do speedup e da eficiência para os seguintes
valores de \(N\) e \(P\) (não esqueça de incluir a especificação da
máquina utilizada para a execução):
- \(N = 10^3, 10^4, 10^5, 10^6, 10^7, 10^8, 10^9, 10^{10}\)
- \(P = 1, 2, 4, 8, 16\).
- Interpretação dos valores mostrados na tabela anterior. Descreva e interprete a variação do speedup e da eficiência em relação à \(N\) e \(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 balanceamento de carga. Todos os processos recebem a mesma quantidade de trabalho? Todos acabam a execução aproximadamente ao mesmo tempo?
Dica: Utilize como referência 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.
3.3 Desempenho (3 pontos)
- É 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.
- Os desempenhos tanto da versão sequencial (10%) quanto da versão paralela (20%) do seu algoritmo serão avaliados.
3.4 Bônus 1 (+1 ponto)
O programa que tiver o melhor tempo de execução (wall-clock time) para \(P = 16\) e \(N = 10^{10}\) dentre os entregues receberá 1 ponto adicional na avaliação.
3.5 Bônus 2 (+1 ponto)
Caso o seu código execute mais rapidamente que o código do professor ou caso ele seja o mais rápido da turma.
3.6 Política de atrasos
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 |
Notas de Rodapé:
Este projeto foi inspirado naquele proposto pelo Prof. Fikret Ercal, para o seu curso de Introduction to Parallel Programming and Algorithms na Missouri University Of Science And Technology.