Algumas coisas serão muito importantes nesta disciplina e, principalmente, na sua carreira em computação. Você deve saber compilar bem um programa, executá-lo de forma prática e automatizada, depurá-lo, saber qual parte dele é mais lenta e ter noções de paralelização.
Este laboratório está baseado em ferramentas GNU que já estão instaladas em Linux mas que podem ser instaladas em Windows e Macs também.
Você deve responder estas perguntas:
Ao final, você deve ser capaz de utilizar estas ferramentas e também diferenciar alternativas de ganho de desempenho obtidas por algoritmos e também por ferramentas.
Comece com o programa primo.c abaixo. Ele é uma versão nada otimizada para calcular se um número é primo (esta versão foi feita de propósito para gastar tempo e ser simples):
#include <stdio.h>
int primo(int n)
{
int i;
for(i = 2; i < n; i ++)
if (n % i == 0)
return 0;
return 1;
}
main()
{
int n = 104395301;
if (primo(n))
printf("%d é primo.\n", n);
else
printf("%d não é primo.\n", n);
}
Agora siga as atividades abaixo, anotando as informações e decisões que você precisará tomar para fazer seu relatório ao final.
Compile o programa sem nenhuma opção de compilação extra. Quanto tempo ele gasta? Veja se o valor muda utilizando, separadamente, cada uma das otimizações -O0, -O1, -O2 -O3 (letra O maiúscula seguida de um número). Qual delas deu o melhor tempo? Existem outras otimizações que você pode aplicar no processador atual, consulte o manual do gcc por otimizações da categoria -mtune e veja quais se aplicam ao seu processador. Para que elas servem? O tempo melhorou?
Quebre o programa em dois arquivos separados: main.c com a função main e calc_primo.c com a função primo. Faça as alterações necessárias nos dois arquivos para que eles compilem. Como compilá-los? Você consegue montar um script que compile estes dois programas? E um Makefile? (procure por "Makefile tutorial" no Google). Rode novamente o programa e veja se ele gasta o mesmo tempo com a melhor otimização utilizada anteriormente. O resultado foi o esperado? Comente.
Modifique seu programa para calcular quantos números primos existem entre 1 e n, seguindo o mesmo algoritmo utilizado, modificando apenas a função main e fazendo com que n seja um parâmetro passado por linha de comando. Novamente, este não é o melhor algoritmo mas serve como exemplo para mostrar o efeito das otimizações. Meça o tempo com um arquivo fonte e com dois. O resultado foi o esperado? Comente.
Agora é hora de tentar melhorar um pouco o programa (mas não muito ainda). Edite o laço da função primo para varrer apenas os números ímpares, dividindo o conjunto de números a testar por dois. Lembre-se que o resultado deve ser o mesmo para a mesma entrada! Caso encontre algum problema, utilize o GDB para depurar seu programa. Muitas vezes, a interface em modo texto do GDB dificulta a depuração, recomendo que vocês utilizem um visualizador gráfico para o GDB. Um bom visualizador é o DDD (basta executar ddd na linha de comando). Alguns comandos interessantes do GDB que você deve saber utilizar: breakpoint, watchpoint, print, display, run, set args e help.
Em qual parte seu programa gasta mais tempo? use o gprof para descobrir (veja o manual do gprof ou os tutoriais 1 e/ou 2).
Se você tiver que paralelizar alguma parte do código, qual parte você escolheria? Como paralelizar de forma escalável o código? Eu sugiro utilizar OpenMP, veja uma breve apresentação, um tutorial, o site oficial, uso pelo GCC e implementação GNU do for. Meça o tempo do programa paralelizado. O resultado foi o esperado? Comente.
Como melhorar ainda mais o desempenho deste programa?