Cache misses
A square n × n matrix of s-byte numbers lies in memory row by row starting at address 0: element (i, j) occupies the bytes from (i·n + j)·s. It is traversed, reading each element once, by rows, by columns or in blocks. Count how many times the needed data will not be in the cache.
The cache works like this. Memory is divided into lines of L bytes: an element falls into line number ⌊address / L⌋, and its bytes do not cross a line boundary. The cache holds C bytes, that is, C/L slots for lines, split into sets of w slots. A line numbered x can lie only in set x mod (C/(L·w)). When an element is read, if its line is not in its set, that is a miss: the line is loaded, and if the set is full, the line least recently accessed is evicted from it. If the line is already there, it becomes the most recent in the set.
The traversal orders: row, by rows of the matrix, from left to right; col, by columns, from top to bottom; block B, the matrix is divided into B × B squares (smaller at the edges), the squares go by rows, and inside a square also by rows.
Input
The first line holds q (1 ≤ q ≤ 6). Each of the next q lines holds n, s, C, L, w and the traversal order (for block, also B). 1 ≤ n ≤ 512, s divides L, L·w divides C, and all sizes except n, w and B are powers of two.
Output
For each line, the number of misses.
Examples
Example 1
3 4 4 64 16 1 row 4 4 64 16 1 col 4 4 64 16 2 block 2
4 4 4
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
No clever algorithm is needed here, only an exact model. Keep for each set a list of lines in order of last access and repeat the rules of the statement carefully.
2The idea
For each read compute the address, the memory line number and the set number. A set is a short list of at most w lines: if the line is in it, move it to the end (most recent); if not, it is a miss: evict the first (least recent) if the set is full, and put the new one at the end.
3Walkthrough
A column-by-column traversal of a matrix whose row takes a power of two bytes is the worst case for such a cache: elements of one column are exactly one matrix row apart, their memory lines fall into the same set, and its w slots are not enough. Every read becomes a miss. A row-by-row traversal, on the contrary, reads a memory line whole: one miss per L/s reads.
Tiling is the technique used to speed up matrix multiplication and transposition (more in the article “Cache-friendly data”): if a block fits in the cache, each of its memory lines is loaded once, and there are almost as many misses as memory lines the matrix occupies at all. In the fifth test that is 11,250 with blocks of 4 and 8; as the block grows it stops fitting in the cache, and there are more misses, 11,804 with a block of 64.
Look at the fourth test too: a 500 × 500 matrix by columns gives 16,000 misses, while 512 × 512 gives all 262,144. A matrix row of 2000 bytes is not a power of two, and the elements of a column spread over different sets instead of crowding into one. That is why high-performance code sometimes lengthens the rows of large matrices by a few elements on purpose.
A speed-up for the simulation: if the line is the same as on the previous read, it is a hit, and it is already the most recent, so you can go straight to the next read.
3+Solution
4Complexity
O(n²·w) per traversal: n² reads, each a search in a set of w lines.
5Common mistakes
- A cache without sets. If a line can go anywhere, there are fewer misses than in a real cache: a column of 512 rows no longer evicts itself from the eight slots of a set.
- Evicting the wrong line. You need the one least recently accessed, not the one loaded earliest: a hit makes a line the most recent.
- Blocks at the edge. If n is not divisible by B, the edge blocks are smaller; the fifth test checks this.