Crivo de Eratóstenes

UNIVERSIDADE CATÓLICA DE PETRÓPOLIS
CENTRO DE ENGENHARIA E COMPUTAÇÃO
ENGENHARIA DE COMPUTAÇÃO
PARADIGMAS DE LINGUAGENS DE PROGRAMAÇÃO

CRIVO DE ERATÓSTENES
Relatório de Testes

Petrópolis
2013

O Problema

O problema abordado consiste em verificar quais são os números primos em um intervalo que vai de zero até um valor limitante. Assim escolhendo como valor limite 16, temos [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16], a esses números que se aplica o teste de primalidade.

Teste de Primalidade

O teste de primalidade utilizado consiste na verificação do número escolhido, analisando se o mesmo é divisível por algum número de 2 até a sua raiz quadrada, assim, por exemplo, o número 9 é verificado se é divisível até o numero 3, identificando assim que o numero 9 não é um número primo. Com essa abordagem se reduz de forma significativa a quantidade de testes necessários.

Teste em GPU

O tratamento do problema consistiu em usar o posicionamento do número na matriz da textura, assim seria usada naturalmente a estrutura de GPU como em CUDA e seriam eliminados cálculos extras para a conversão char para float.
Na matriz de textura em shader um número é mapeado simplesmente pela soma dos índices dados pelo gl_FragCoord com mais alguns cálculos de dimensionamento, para testes com texturas diferentes do tamanho da viewport, em cada fragmento é colocado branco se o número correspondente e primo e preto caso contrário.
Em CPU o mapeamento é feito pelo uso de um vetor de dados correspondente a textura lida do framebuffer utilizando a técnica de render to texture, com alguns cálculos para o posicionamento no vetor é possível verificar a qual número o pixel corresponde, verificando dessa forma se o mesmo é um número primo.

Teste em OpenMP

Em CPU cada número é verificado executando o teste de forma sequencial e de forma paralela através de OpenMP com 8 threads, com