I've been reading about implementing dense matrix multiplication when the matrix doesn't fit in cache. One of the graphs I've seen (slide 9 from these slides) shows sudden drops in performance using the naive algorithm. This drops are to around 50% of the speed, occur while the matrix still fits in cache, and only occur for one or two sizes. I'm not planning on using the naive algorithm, but I would like to know where the sudden drops in performance come from. (The drops also occur with blocked algorithms, but are much smaller.)
Tell me more
×
Computational Science Stack Exchange is a question and answer site for
scientists using computers to solve scientific problems. It's 100% free, no registration required.
|
That is a classic example of cache associativity. The stride associated with that problem size is filling up certain sets causing cache eviction despite there being lots of space in other sets.
Figure from Gustavo Duarte's excellent blog post on the topic See also Drepper's What every programmer should know about memory. |
|||
|
|
