CMSC216 HW10: Timing Reversals

Homeworks are optional practice with no submission and no credit

CODE DISTRIBUTION: hw10-code.zip

Download the code distribution every HW
See further setup instructions below

CHANGELOG: Empty

1. Rationale
- 1.1. Associated Reading / Preparation
- 1.2. Grading Policy
2. Codepack
3. Questions

1 Rationale

When studying the performance of code, it is important to time using functions like clock() and gettimeofday() so that suspicions about memory and cache behavior are backed by empirical data. Automating benchmarks of code is best handled using build systems like make. This HW focusing on evaluating a few functions to reverse and array for their speed, timing those run and automating the process.

1.1 Associated Reading / Preparation

Bryant and O'Hallaron: Ch 6 on The Memory Hierarchy. Ch 6.5 and 6.6 may be particularly helpful to understanding cache effects.

Tutorials on Makefiles abound with some coverage in a recent lab. Those wanting a more complete account should consult the GNU Make Manual as it is the most widely deployed implementation of make and its manual is thorough.

1.2 Grading Policy

Homework provides optional extra practice for students looking for it. No submission is collected and the HW is not worth any course credit. Solutions will be posted some time after the HW is posted. Students approaching course staff for additional practice problems will be asked to explain their own written answers to the QUESTIONS.txt documents in HWs before any additional problems will be constructed.

2 Codepack

The codepack for the HW contains the following files:

File	State	Description
`QUESTIONS.txt`	Edit	Answer questions in the file to complete the HW
`reverse_benchmark.c`	Edit	Problem 1 source file to analyze/edit
`Makefile`	Create	Problem 1 build file to create according to instructions

3 Questions

                           _________________

                            HW 10 QUESTIONS
                           _________________


HWs are optional practice and there is no submission.


PROBLEM 1: Timing Benchmarks
============================

  The code in `reverse_benchmark.c' implements two functions which
  reverse the elements of an array. They take different approaches.
  ,----
  | void reverse_arr1(int *arr, long size){
  |   int *tmp = malloc(sizeof(int)*size);
  |   for(long i=0; i<size; i++){
  |     tmp[i] = arr[size-i-1];
  |   }
  |   for(long i=0; i<size; i++){
  |     arr[i] = tmp[i];
  |   }
  |   free(tmp);
  | }
  | 
  | void reverse_arr2(int *arr, long size){
  |   for(long i=0; i<size/2; i++){
  |     int tmp = arr[i];
  |     arr[i] = arr[size-i-1];
  |     arr[size-i-1] = tmp;
  |   }
  | }
  `----


(A) Predictions
~~~~~~~~~~~~~~~

  Predict which of these two functions will run faster based on their
  code characteristics. Justify your answer by contrasting the features
  of the two reversal functions.


(B) Timing
~~~~~~~~~~

  Complete the provided `reverse_benchmark.c' file by filling in code
  that will repeatedly run the two functions above and print times for
  them. The runs will be on increasing sizes of arrays. When the code is
  complete, manually compile and run the benchmark to investigate some
  times and either confirm or support your suspicions on speed. Measure
  elapsed CPU time, not than real/wall time.


(C) Makefile
~~~~~~~~~~~~

  Write a small Makefile to automate building and evaluating the
  system. The Makefile should have the following targets.
  - `all' the default target, builds `reverse_benchmark' and then prints
    to the screen `Ready to reverse'
  - `reverse_benchmark' which depends on `reverse_benchmark.c' and
    compiles it using the following GCC options: `-g -Og'
  - `run' depends on `reverse_benchmark' and does two runs of the
    benchmark:
    1. Echoes "Running large with 1 repetition" then runs
       `./reverse_benchmark 22 26 1'
    2. Echoes "Running small with 100 repetitions" then runs
       `./reverse_benchmark 20 24 100'
  - Clean which removes `reverse_benchmark' and any `.o' files that are
    around

  Test out the Makefile to ensure it performs correctly: such as what is
  shown in the following session.

  ,----
  | >> make clean
  | rm -f reverse_benchmark *.o
  | 
  | >> make run
  | gcc -g -Og -o reverse_benchmark reverse_benchmark.c
  | Running large with 1 repetition
  | ./reverse_benchmark 22 26 1
  |       SIZE     rev1     rev2 
  |    4194304  0.01025  0.00693 
  |    8388608  ...
  |    ...
  | Running small with 100 repetitions
  | ./reverse_benchmark 20 24 100
  |       SIZE     rev1     rev2 
  |    1048576  0.14696  0.05640 
  |    2097152  ...
  |    ...
  | 
  | >> make clean
  | rm -f reverse_benchmark *.o
  | 
  | >> make
  | gcc -g -Og -o reverse_benchmark reverse_benchmark.c
  | Ready to benchmark
  | 
  | >> make run
  | Running large with 1 repetition
  | ./reverse_benchmark 22 26 1
  |       SIZE     rev1     rev2 
  |    4194304  0.01108  0.00359 
  |    8388608  ...
  |    ...
  | Running small with 100 repetitions
  | ./reverse_benchmark 20 24 100
  |       SIZE     rev1     rev2 
  |    1048576  0.14349  0.05626 
  |    2097152  ...
  |    ...
  | >> make
  | Ready to benchmark
  `----


(D) Analysis
~~~~~~~~~~~~

  Clean the code, build it, and do a `make run' on Zaratan. Examine the
  timing information to see if the timing results support your
  suspicions from earlier. Paste your completed timing results below.