Project 1

Serial Performance

The question

Two programs can do the same amount of arithmetic and still take different amounts of time. In this project, you will investigate that idea by computing the sums of the columns of a matrix.

Write the code, check its answers, and measure what happens when you change the order in which it visits the data. Then explain what your measurements tell you.

This project builds on Module 1: C and Performance Basics. Use serial C throughout; we have not started parallel programming yet.

1. Compute column sums

Create a program named column_sums.c. Use a square array with N rows and N columns. Initialize each entry with:

a[i][j] = i + j;

Use double for the matrix entries and the sums. The answer should be an array of N column sums, with one result for each column.

Write two versions of the calculation in the same program:

  • Across rows: Visit all the entries in row 0, then row 1, and so on. Add each entry to the total for its column.
  • Down columns: Visit all the entries in column 0, then column 1, and so on. Again, add each entry to the total for its column.

Both versions must compute the same N column totals. This is different from the example in Module 1, which computes one total for the entire matrix.

Use a separate result array for each version. Set both result arrays to zero before the timed calculations. You may use the same matrix for both versions. Declaring the large matrix outside main, as we did in the module, keeps it off the stack.

You may reuse the timer pattern and array setup from Module 1. Write the column-sum calculations yourself. Functions and command-line arguments are optional; a single main and a fixed #define N are fine.

2. Check a small case

Start with N = 4. Your matrix should be:

0  1  2  3
1  2  3  4
2  3  4  5
3  4  5  6

The column sums are:

6  10  14  18

Print all four results from each version and check them before using larger arrays.

For larger sizes, the expected sum for column j is:

\[ \text{column sum}_j = \frac{N(N-1)}{2} + Nj. \]

The first term adds the row indices; the second adds j once for every row. Use floating-point arithmetic when calculating this expected value in C—for example, start with N * (N - 1) / 2.0.

Check every column from both versions against this formula after the timers stop. For these input values and the sizes below, the totals are integers that can be represented exactly by our double type, so direct equality is appropriate. This would not be a general rule for arbitrary fractional data.

For a large array, print a short message saying whether the checks passed, plus the first and last column sums from each version. Do not print the full matrix or thousands of column sums. If a check fails, stop and fix the calculation before collecting timings.

Using the results in these checks and printed output also helps keep the compiler from discarding an unused calculation.

3. Time the calculations

Use clock_gettime(CLOCK_MONOTONIC, ...) as in Module 1. Time each traversal separately.

The timed region should include the loops that compute the column sums. Keep matrix initialization, resetting result arrays, checking answers, and printing outside that region. Every time you repeat a calculation, reset its result array first.

Label the two timings clearly, such as:

Across rows:  ... seconds
Down columns: ... seconds

Use seconds for all measurements and print enough decimal places to distinguish the runs. Keep the same timed boundaries in every comparison.

4. Run the experiments

Use the same assigned compute node for all comparisons. Record hostname and gcc --version. If others are using the same node, take turns running the experiments when possible.

Array size and access order

Build with optimization:

gcc -g -Wall -O2 -o columns_O2 column_sums.c
./columns_O2

Collect results for N = 1024 and N = 4096. Change N in the source and rebuild when switching sizes.

For each size, run the program once as a warm-up, then five more times. Each run should report both traversal times. Alternate which traversal runs first; you can move the two timed blocks in the source and rebuild to do this. Record the order used for each run.

The matrices use approximately 8 MiB and 128 MiB, respectively, with eight-byte doubles. The two result arrays add very little. These are reasonable starting sizes on our 8 GB boards, but other users still share those resources.

Compiler optimization

Keep N = 4096 and also build an unoptimized version:

gcc -g -Wall -O0 -o columns_O0 column_sums.c
./columns_O0

Run it once as a warm-up, then five measured times, again recording both traversal times. Compare these with the -O2 results you already collected for the same size. Both executables must use the same input and produce correct results.

You now have three experiment conditions, five measured program runs per condition, and two timings per run. Keep all 30 timings. You do not need to rerun the 4096/-O2 condition unless you change the calculation or the measurement conditions.

5. Explain the results

Write a short report, about 1–2 pages, with your summary table and answers to the questions below. Put the raw measurements in a separate table or appendix; they do not count toward the page suggestion.

Use this summary format:

N Compiler setting Minimum across rows (s) Minimum down columns (s) Column time / row time
1024 -O2
4096 -O2
4096 -O0

Use the minima from the same row of the table to calculate its ratio. A ratio greater than 1 means the column traversal took longer. Also report the smallest and largest observed times for each traversal so the variation is visible.

  1. Correctness: How did you check your answers? Include the N = 4 results.
  2. Access order: Which traversal was faster? Was the pattern consistent? Explain how the way C stores arrays could contribute to the difference.
  3. Problem size: Moving from 1024 to 4096 gives four times as many rows and four times as many columns. How many times as many entries is that? How did the timings change?
  4. Optimization: What changed between -O0 and -O2? Compare the same traversal and array size. Does your evidence support a clear improvement?
  5. Variability: How much did times vary? Did traversal order or other activity appear to matter? What would you check next?

Separate what you observed from what you think explains it. A timing difference alone does not measure cache misses. If the results do not match your prediction, report them honestly.

The minimum is the fastest run you observed. If one unusually low result drives the conclusion, discuss it and also compare medians—the middle values after sorting. Use the same statistic on both sides of a comparison.

What to submit

Submit through Moodle:

  • column_sums.c — Your source, with the final N set to 4096 and a short comment explaining how to change it.
  • Your report — Include your node, compiler version, exact compilation commands, correctness results, summary table, and discussion.
  • Raw timings — Label each measurement with array size, compiler setting, run number, traversal order, and elapsed time. Clearly separate the warm-up from the five measured runs.

Do not submit compiled executables. Make sure your program compiles without warnings using the commands above.

Back to top