Matrix multiplication: Small difference in matrix size, large difference in timings

by

Here’s my wild guess: cache

It could be that you can fit 2 rows of 2000 doubles into the cache. Which is slighly less than the 32kb L1 cache. (while leaving room other necessary things)

But when you bump it up to 2048, it uses the entire cache (and you spill some because you need room for other things)

Assuming the cache policy is LRU, spilling the cache just a tiny bit will cause the entire row to be repeatedly flushed and reloaded into the L1 cache.

The other possibility is cache associativity due to the power-of-two. Though I think that processor is 2-way L1 associative so I don’t think it matters in this case. (but I’ll throw the idea out there anyway)

Possible Explanation 2: Conflict cache misses due to super-alignment on the L2 cache.

Your B array is being iterated on the column. So the access is strided. Your total data size is 2k x 2k which is about 32 MB per matrix. That’s much larger than your L2 cache.

When the data is not aligned perfectly, you will have decent spatial locality on B. Although you are hopping rows and only using one element per cacheline, the cacheline stays in the L2 cache to be reused by the next iteration of the middle loop.

However, when the data is aligned perfectly (2048), these hops will all land on the same “cache way” and will far exceed your L2 cache associativity. Therefore, the accessed cache lines of B will not stay in cache for the next iteration. Instead, they will need to be pulled in all the way from ram.

More Related Contents:

  1. how to show time performance for merge sort? [closed]
  2. How to do unsigned saturating addition in C?
  3. Efficient 4×4 matrix vector multiplication with SSE: horizontal add and dot product – what’s the point?
  4. read line by line in the most efficient way *platform specific*
  5. Algorithm to find all the exact divisors of a given integer
  6. Which is better way to calculate nCr
  7. Pattern Programmings
  8. the problem is from a algorithm problem I do recently,but I can't gain the right answer [duplicate]
  9. Improve INSERT-per-second performance of SQLite
  10. hash function for string
  11. What is the efficient way to count set bits at a position or lower?
  12. Generating permutations of a set (most efficiently)
  13. Building a logarithm function in C without using float type
  14. How can I simplify this working Binary Search code in C?
  15. Is it faster to count down than it is to count up?
  16. What is the fastest way to swap values in C?
  17. How do you print the EXACT value of a floating point number?
  18. Time complexity of a recursive algorithm
  19. How to find largest triangle in convex hull aside from brute force search
  20. Why prefer start + (end – start) / 2 over (start + end) / 2 when calculating the middle of an array?
  21. Generating a uniform distribution of INTEGERS in C
  22. AVX/SSE version of xorshift128+
  23. Rolling median algorithm in C
  24. why does GCC __builtin_prefetch not improve performance?
  25. faster alternative to memcpy?
  26. Floating point linear interpolation
  27. Finding the intersecting node from two intersecting linked lists
  28. Finding out the duplicate element in an array
  29. Does C have any tools for doing string addition?
  30. Performance: memset

Leave a Comment