Some things will be very important in this discipline and especially in your career in computing. You must know how to compile bem a program, to execute it in a practical and automated way, to debug it, to know which part of it is slower and to have notions of parallelization.
This lab is based on GNU tools which are already installed on Linux but which can be installed on Windows and Macs as well.
You must answer these questions:
In the end, you should be able to use these tools and also differentiate performance gain alternatives obtained by algorithms and also by tools.
Start with the program cousin.c below. It is a version nothing optimized to calculate if a number is prime (this version was made for the purpose of spending time and being simple):
#include
int cousin (int n)
{
int i;
for (i = 2; i <n; i ++)
if (n% i == 0)
0 return;
1 return;
}
Main()
{
int n = 104395301;
if (prime (n))
printf ("% d is prime. \ n", n);
else
printf ("% d is not prime. \ n", n);
}
Now follow the activities below, writing down the information and decisions you will need to make to make your report at the end.
Compile the program without any extra compilation options. How much time does he spend? See if the value changes using, separately, each of the optimizations -O0, -O1, -O2 -O3 (capital letter O followed by a number). Which one gave the best time? There are other optimizations that you can apply to the current processor, see the gcc by category optimizations -mtune and see which ones apply to your processor. What are they for? Has the weather improved?
Break the program into two separate files: main.c with the main function and calc_primo.c with the primo function. Make the necessary changes to the two files for them to compile. How to compile them? Can you build a script that compiles these two programs? And a Makefile? (search for "Makefile tutorial" on Google). Run the program again and see if it spends the same time with the best optimization previously used. Was the result expected? Comment.
Modify your program to calculate how many prime numbers there are between 1 and n, following the same algorithm used, modifying only the main function and making n a parameter passed through the command line. Again, this is not the best algorithm but it serves as an example to show the effect of the optimizations.. Measure time with one source file and two. Was the result expected? Comment.
Now it's time to try to improve the program a little (but not much yet). Edit the loop of the primo function to scan only the odd numbers, dividing the set of numbers to be tested by two. Remember that the result must be the same for the same entry! If you encounter any problems, use GDB to debug your program. Often, the GDB text mode interface makes debugging difficult, I recommend that you use a graphical viewer for GDB. A good viewer is DDD (just run ddd on the command line). Some interesting GDB commands that you should know how to use: breakpoint, watchpoint, print, display, run, set args and help.
Where does your program spend the most time? use gprof to find out (see the gprof manual or tutorials 1 and / or 2).
If you have to parallelize some part of the code, which part would you choose? How to scale parallelize the code? I suggest using OpenMP, see a brief presentation, a tutorial, the official website, use by GCC e GNU implementation of for. About the time of the parallel program. Was the result expected? Comment.
How to further improve the performance of this program?