Ailton Cardoso Junior AN LISE COMPARATIVA CPU E GPU

UNIVERSIDADE DO VALE DO ITAJAÍ CENTRO DE CIÊNCIAS
TECNOLÓGICAS DA TERRA E DO MAR CURSO DE CIÊNCIA DA
COMPUTAÇÃO

ANÁLISE COMPARATIVA DE ALGORITMOS PARA DESCOBERTA DE
NUMEROS PRIMOS EXECUTADOS EM CPU E GPU UTILIZANDO CUDA

Por
Ailton Cardoso Junior

Itajaí (SC), novembro de 2014.

Algoritmo Número Primo
Objetivo: Algoritmo para encontrar o maior número primo em 1 minuto, em CPU e
GPU.

Parâmetros de Saída: ultimoPrimo tempoInicial = clock;
Enquanto tempo percorrido for menor que 1 minuto faça div = num*0,5;
Para i de 3 até div faça
Se num%1 = 0 então
++cont;
Pare;
Fim se
Fim para
Se cont = 0 então ultimoPrimo = num;
Fim se
Cont=0;
Num+=2;
Fim enquanto
Escreva: ultimoPrimo;
Fim algoritmo

Implementação na CPU usando C++

Na implementação para a CPU foi utilizado alguns conhecimentos para a descoberta de números primo mais rápido, tais como: começar a verificar os números após o 3, considerando que o 2 já é um número primo, ignorar os números pares para não se dar ao trabalho de verificar se são ou não primos, tendo em vista que nunca serão, a partir do momento que encontra um divisor no laço interno já considero que o número não faz parte do conjunto dos números primo, uma outra maneira de deixar o algoritmo mais rápido foi dividir o número que a ser descoberto por dois e o laço ir de
3 até o número dividido por dois, pois se não encontrar nenhum divisor metade do número é sinal que é um número primo e não precisa perder tempo e verificar até o fim. O algoritmo na CPU fica em torno de 4,33x mais rápido, após as melhorias no algoritmo listadas acima. É possível usar outras melhorias e artimanhas para encontrar um número primo mais rapidamente, porem após alguns experimentos vi que nem todas as melhorias acarretam em aumento de performance, como o exemplo de uma propriedade dos números primos que diz que ao pegar o número no qual se deseja

descobrir e tirar a raiz quadrada, pode iniciar o laço a partir do resultado da raiz e ir somente até a metade do número, mas