Lab 1: Software Optimization

Due: Friday, January 20 by 10:00 PM
Assignment ID: lab1

Lab description

For this lab, write C++ source code (lab1RowMajor.cpp and lab1ColMajor.cpp) for two programs that explore the difference in terms of execution time that it takes to write to a two dimensional array by rows (and then columns) versus by columns (and then rows). To see the difference in timing, you'll need to allocate each array on the heap (with new, malloc or calloc). Allocate the arrays the same way for both programs (i.e., by rows). Make the arrays square (i.e., the same number of rows and columns). Choose a size of array that exhibits a discrepancy in the timing. The Unix time command will be used to measure the timings. Increase the size of the arrays if the real time is 0.00 for either program (or the time is the same or nearly the same).
Report in a flat text file (lab1Report.txt) whether iterating by rows then columns (row-major) or columns then rows (column-major) takes less time. Do more than just capture the output of the time command.

Example Execution

$ time -p ./lab1RowMajor && time -p ./lab1ColMajor
real X.XX
user Y.YY
sys Z.ZZ
real X.XX
user Y.YY
sys Z.ZZ

Submission

Save the source code for each program as lab1RowMajor.cpp and lab1ColMajor.cpp. Compile the code and verify that execution times are different. Submit the source code files using the handin program. For example, for this lab, type the following in a terminal exactly as it appears:

  handin  lab1  lab1RowMajor.cpp  lab1ColMajor.cpp   lab1Report.txt

Alternatively, you can submit the assignment from any computer via PeerSpace. After successfully logging into PeerSpace, go to Tools, then Assignments. Click on the Submit link.

Rubric:

Points          Item
----------      --------------------------------------------------------------
                Program (80 points)
_____ / 50	Program compiled properly
_____ / 15	Dynamically allocated memory on the heap (using new, malloc or calloc)
_____ / 15      Large enough array dimensions for non-"0.00" timing

                Report (20 points)
_____ / 10	Reported timings
_____ / 10      Reported if C++ is row- or column-major


_____ / 100

Hints

There is a strong convention in the community that the indicies for two dimensional arrays are row then column (i.e., myArray[row][column]).
For row-major, the array should be assigned values in the following order:

      myArray[0][0]
      myArray[0][1]
      ...
      myArray[0][size - 1]
      myArray[1][0]
      myArray[1][1]
      ...
      myArray[1][size - 1]
      ...
      myArray[size - 1][size - 1]

For column-major, the array should be assigned values in the following order:

      myArray[0][0]
      myArray[1][0]
      ...
      myArray[size - 1][0]
      myArray[0][1]
      myArray[1][1]
      ...
      myArray[size - 1][1]
      ...
      myArray[size - 1][size - 1]

Run the timing multiple times because ranger is a shared system and you can not control what else is being run on it.
The larger the arrays, the more likely you are to see a timing difference.