Task 3.2 - Delta Sum

Data Access and Performance

Task 3.1 showed that the order in which data is access in memory also has an influence on performance. For this task we use the follow algorithm (in pseudocode) to explore the issue further: Given an array X of n integer values, compute the sum of X[(k * delta) mod n] for k from 0 to count-1. The run-time behaviour of this algorithm depends on n and delta and you should test these separately (e.g. fix delta and measure times for different n).

sum = 0
k = 0
for l = 0 to count-1
   sum = sum + X[k]
   k = k + delta
   if k > n then k = k - n

Measure the execution time of the data access algorithm:

  • Implement the above algorithm.
  • Time your code over increasing sizes n for a fixed delta and fixed count (larger than n).
  • Then repeat this for larger values of delta (sy 1, 5, 10, 11, 15, 20).
  • Compare the theoretical expectation of the timings from the pseudocode with your actual timing values. Briefly state what your conclusions on the actual timing of the algorithm vs. the theoretical expectation are.
Upload a single graph containing the time vs. array size curves for different deltas and briefly discuss your conclusions.