is too small, the accessed array elements in one loop iteration (for example, i = 1, j = 1 to n) may cross cache lines, causing cache misses. Tiling size It is not always easy to decide what value of tiling size is optimal for one loop because it demands an accurate estimate of accessed array regions in the loop and the cache size of the target machine. The order of loop nests (loop interchange) also plays an important role in achieving better cache performance. Explicit blocking requires choosing a tile size based on these factors. By contrast, cache-oblivious algorithms are designed to make efficient use of cache without explicit blocking. Example: matrix multiplication Many large mathematical operations on computers end up spending much of their time doing matrix multiplication. The operation is: C = A×B where A, B, and C are N×N arrays. Subscripts, for the following description, are in form C[row][column]. The basic loop is: int i, j, k; for (i = 0; i < N; ++i) { for (j = 0; j < N; ++j) { C[i][j] = 0; for (k = 0; k < N; ++k) C[i][j] += A[i][k] * B[k][j]; } } There are three problems to solve: Floating point additions take some number of cycles to complete. In order to keep an adder with multiple cycle latency busy, the code must update multiple accumulators in parallel. Machines can typically do just one memory operation per multiply-add, so values loaded must be reused at least twice. Typical PC memory systems can only sustain one 8-byte doubleword per 10–30 double-precision multiply–adds, so values loaded into the cache must be reused many times. The original loop calculates the result for one entry in the result matrix at a time. By calculating a small block of entries simultaneously, the following loop reuses each loaded value twice, so that the inner loop has four loads and four multiply–adds, thus solving problem #2. By carrying four accumulators simultaneously, this code can keep a single floating point adder with a latency of 4 busy nearly all the time (problem #1). However, the code does not address the third problem. (Nor does it address the cleanup work necessary when N is odd. Such details will be left out of the following discussion.) for (i = 0; i < N; i += 2) { for (j = 0; j < N; j +=