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.

erastotenes.png

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:


  1. Crie uma lista de inteiros consecutivos de \(2\) até \(n\): (\(2, 3, 4, \ldots, n\)).
  2. Seja \(p = 2\), o primeiro número primo.
  3. 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).
  4. 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.
  5. Quando o algoritmo terminar, os números não marcados presentes na lista serão todos os números primos entre \(1\) e \(n\).


New_Animation_Sieve_of_Eratosthenes.gif

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):

  1. Só precisamos marcar os números da lista (passo 3) a partir de \(p^2\) (Por quê?)
  2. 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é:

1
Descrição do algortimo retirada da Wikipedia.
2

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.

Autor: Emilio Francesquini

Created: 2018-11-08 Thu 20:44