First, make a copy of the small C program knights-tour.c. Read the program, and make sure you understand how it works. Observe the commenting and indenting styles.

Compile it and run it to make sure it is working correctly on your machine. Compilation can be done with the command

    cc -o knights-tour knights-tour.c

    knights-tour

Since this is a course on using computer resources efficiently, we need to be able to measure how long our programs take to run. Perhaps the simplest (and crudest) tool is the Unix "time" command. Instead of running the program by itself, run it with the command

    time knights-tour

1.410u 0.000s 0:01.41 100.0%    0+0k 0+0io 79pf+0w

Depending on what system you are running on, you may be able to get other information from the "time" command. On the Linux system that provided the line above, the 0+0k refers to the memory used for text space and for unshared data space (in kbytes). The 0+0io refer to input and output file system requests, the 79pf indicates that 79 page faults occurred, and the 0w says that the process was never swapped out of main memory. Mac OS X uses essentially the same format, since both use the "gnu" version of the "time" command.

For more information on the time command, give the UNIX command

    man time

Now that you know one way to measure the time a program takes, let's see what effect various compiler options have on the running time. There are two options worth looking at for this experiment: the "-O" setting for level of optimization, and the "-pg" setting for profiling. Try each of the following settings: "-O0", "-O1", "-O2", "-O3", "-O4", "-pg -O0", "-pg -O1", "-pg -O2", "-pg -O3", and "-pg -O4".

Measurement and analysis

Record the user time for each setting and make a neat table of them. Be sure to run all tests on the same machine, and report what the machine is. On Mac OS X system, the "about this mac" menu item reports the processor type and speed and memory size. Also report what version of the compiler you are use, which you can find out with

    cc --version

You should have noticed that the "-pg" flag slowed down the program a lot, but we'll be using this flag quite a bit this quarter. It adds some extra instrumentation to a program so that we can see where it is spending its time. When you run a program compiled with "-pg", it creates an extra file called "gmon.out". This file can be read, together with the program code, to create a profile of the use of CPU time in the program. Compile your code with "-pg -O4" and run it, then run

    gprof knights-tour > knights-tour.prof

TURN IN: use the "submit" program on the CATS Unix machines to submit a file called "timing" that has your table timings and your analysis of the program. Note: this file should be a PLAIN TEXT file, as I do not accept Microsoft Word files.

Program modification

1. trivial mod: change NumRows from 8 to 9. Do not leave emacs to do the compile and execution of the program, but use control-x, control-e (written as ^x^e) to start a compile command such as

       cc -O4 -o knights-tour knights-tour.c; time knights-tour
   

   If there are any bugs in the compilation, ^x^n in the *compilation* window will move you to the place in your source code where the error was detected, so that you can see it in context and make appropriate corrections.

   Time the modified program. Note that increasing the number of rows by 1 slows down the program a lot. Increasing both the rows and the columns slows things down so much that it is not clear whether or not the program is working!

2. Slightly more advanced modification. It is rather ugly that NumRows and NumCols are constant macros, and that changing them requires recompilation. Modify the program so that there are constants MaxNumRows and MaxNumCols to determine the size of the arrays, but NumRows and NumCols are integer variables. Initialize them to 8, but use the "argc", "argv" mechanism in the main procedure to get values from the argument line, so that

   	knights-tour
   

   does an 8x8 tour,

   	knights-tour 7
   

   does a 7x7 tour, and

   	knights-tour 6 9
   

   does a 6x9 tour. Be sure to include some tests that the ensure that the arguments are legal values (positive and no larger than MaxNumRows or MaxNumCols). You may need to learn more about "atoi()" or "strtol()". In emacs, you can get at the man pages by giving the emacs command "esc-x man".

   If you need to do some debugging, try using gdb under emacs (give the emacs command "esc-x gdb", then run gdb with "gdb knights-tour". Note that for debugging to work well, you probably want to compile using "-g" rather than "-O4". The parts of the debugger you'll probably use most are the breakpoints (look up the emacs command "gud-break") and the print statements.

   Add comments (in a similar style to the existing ones) as needed. Be sure that your name and date are prominent near the beginning of the program.

   Use your program to get times for 3x3,4x4,...,8x8 knight's tours. Again, record the compiler and processor information. You are not exploring compiler settings this time, so pick one (say, -O4) and stick with it.

3. Another measuring tool: clock(). Read "man clock" to find out one way to get the cpu time used in a program. Use the clock() procedure to time just the main call to the CompleteTour procedure and its descendants, without including initialization and output time. This will require two calls to clock(), one before the call to CompleteTour and one after---the difference is the time we're interested in. Print the search time in seconds (with 3 digits after the decimal point) after printing out the solution. (You may need to learn more about "printf".)

   Since you have so little I/O in your program, the timing for just CompleteTour should be almost identical to the timing for the whole program. Are they?

TURN IN: add the timing information for your modified program to the "timing" file. Make sure that the file makes sense as English text---uncommented numbers are just garbage. Also turn in the modified program, still called "knights-tour.c". I may want to compile it and run it myself.

Things learned on grading assignment

There was not much room in this assignment for bonus points. Perhaps I could have offered points for particularly clean makefiles to run the experiment, or gnuplot plots of time versus board size.

One of my grad students pointed out to me an obvious small change that speeds the program up by about a factor of 2. Perhaps I should add the demand for that to next year's assignment---I'll probably have to give hints, though, as the change was only obvious after I'd been told about. (Hit my head and say "Doh!")

SoE home

Questions about page content should be directed to