Cache Lines - Algorithmica

The basic units of data transfer in the CPU cache system are not individual bits and bytes, but cache lines. On most architectures, the size of a cache line is 64 bytes, meaning that all memory is divided in blocks of 64 bytes, and whenever you request (read or write) a single byte, you are also fetching all its 63 cache line neighbors whether your want them or not. To demonstrate this, we add a “step” parameter to our incrementing loop. Now we only touch every 𝐷 D-th element: If we run it with 𝐷 = 1 D=1 and 𝐷 = 16 D=16, we can observe something interesting: As the problem size grows, the graphs of the two loops meet, despite one doing 16 times less work than the other. This is because, in terms of cache lines, we are fetching the exact same memory in both loops, and the fact that the strided loop only needs one-sixteenth of it is irrelevant. When the array fits into the L1 cache, the strided version completes faster — although not 16 but just two times as fast. This is because i

saved by

• Tri Ho