"random" in task 3e of assignment 3

"random" in task 3e of assignment 3

by Stefan Bauer -

Hello,

I have a question concerning task 3e of assignment 3:

On slide 7 of "Comments for Assignment 3" it is stated that the worst case is a random access. I think this is not correct. With a random access CL-reuse would be possible in some cases just out of luck. Initialising the array with random values could even result in a best case scenario. One could quantify how often "random" results in a worst case access pattern (if we would have more information on the cache), but this was not part of the task. I even got only 10 out of 15 point, because I did not mention the word "random"...


Best,

Stefan

Re: "random" in task 3e of assignment 3

by Christie Louis Alappat -
Hi Stefan,

Worst case is when you use only one element within a fetched cache-line, and the rest of the elements in the cache line are not used. Typically with random numbers you get close to it. It need not be random numbers, it can also for example happen with codes having huge strides (remember the assignment with strided STREAM-triad).

For your assignment submission five points were deducted not because you didn't mention the word "random", but because your results for worst case was wrong. You considered the worst case to have only 8 bytes transfer for the indirectly accessed 'v' array. But in the worst case as mentioned above you would have a transfer corresponding to the entire cache line, i.e., L_c bytes. L_c is much bigger than 8 bytes, on Fritz for example it is 64 bytes.

Best,
Christie