Map Generator

Assignment 2 – September 10, 2006

Due: 8.00 a.m. September 17, 2006

Language: Use the same language you used last time.

Objectives:

• Implement some simple optimizing techniques in C (by hand)
• Compare the result of your optimizations with the compiler’s optimization

For this week, you will use the optimizations that Mike will talk about in class on Wednesday. Also, you will be responsible for incorporating the suggestions made in discussion section to improve the readability of your code. This might include breaking large functions into smaller ones, more comments, or a better layout.

Keep a copy of your code from last week (we are interested in part I only). Make the code improvements that we suggested last week first before continuing.

We are going to use a very rough method of timing. Last semester, we tried using gprof but the data file that we had was too small to provide anything useful. So, this time around, we will be using time (or something similar if you are using Visual C++). To use time, do something like this time myprogram input.txt and time will report how long it takes to run. Even better, make your program run a few times and take the average.

Here is what you need to do this week:

1. Create a sample input files of size 8×8, 16×16, 32×32, 64×64, 128×128, 256×256. You can just use a simple script to generate them randomly.
2. Compile your program (modified to incorporate the suggestions for readability) from last week. Run time for each of the input files above and jot down the times.
3. Compile your program with the -O1 flag and run time for each of the data sets. Jot these results down.
4. Compile your program with the—O3 flag and run time for each of the data sets. Jot these results down also.
5. Do your optimizations. Mike will probably mention two kinds of optimization: 1) partitioning the input file into regions and 2) using symmetry. Please do step 1) first then run time with the data sets above. Do NOT turn on the compiler optimizations.
6. Implement the symmetry trick and then run time again for each of the data sets. Again, do NOT turn on compiler optimizations.
7. Plot a simple graph of the times. An easy way would be to use Excel or something similar. See if there are really any significant differences.

Also, do make sure that after your optimizations, your program still works properly! There is no point optimizing and getting a broken program. You can test it with the data from last week since you know how the map looks for that data set.

If you find that you do not get a good graph, you can increase the size of the input file so that are running your program against input files with sizes of 512×512 and above.

Interpret the results of the graph. Compare the final result of our hand optimizations with the original program compiled with -O3 flag. So, do you think that our hand optimizations are worth it?

Update:

I was a bit too presumptuous about familiarity with gcc. This has been addressed on the newsgroup, but I am going to include it here for reference.

			
				gcc -o <program_name> -O1 <input file(s)>
				gcc -o <program_name> -O3 <input file(s)>
				 
			
		

Replace gcc above with g++ if you are using C++. Concrete example (It's just an example. Don't name your files like this! )

					
				gcc -o MapGenerator -O1 raster.c
			
		

Feel free to use the method suggested in class to get a better time estimate. Or use whatever tool that you have built-in to your IDE. Someone showed me Visual Studio that day and it was capable of profiling at the function level without much user intervention. I don't have Visual Studio with me so I cannot tell you the exact steps. Someone who is familiar with Visual Studio can post this on the newsgroup. Also, if you were using Visual Studio for the first assignment, you can just stick with it. It has its own flags that roughly correspond to gcc's -O1 and -O3.

Optional:

In class, Mike mentioned that he has a better map terrain. For those who wish to play with it, the files are provided. You need the input file, which is now in binary format and you read it as follows. This is in little-endian format, so if you are working on a PowerPC architecture, you need to do more work to read the binary data in (for the header only). The real data is in bytes so it does not matter.

What you need is to read the header length that tells you how many bytes the header of the file will be. The header is the part before the data. In the file header, there are the rows and columns (also in binary). You can ignore all other data in the header.

You also need the text file that tells you how to interpret that data. This data is much more comprehensive than the one we have been using. So, you will find that we don't really have enough picture tiles for those data. You should use one tile for several types of terrain as you see fit.

Grading:

• Technical:
  • Did you follow the advice from last week to improve code readability? [5]
  • Did you do the optimizations (step 1 and step 2)? [10]

• Style:
  • Were comments adequate? [3]
  • Were meaningful names used for variables, constants and function? [3]
  • Was the naming convention consistent? [3]

• Participation:
  • Did you ask questions in discussion section? [5]
  • Did you turn in your assignment on time? [5]
  • Did you read your partner’s code before class? [3]