Measure Locality in Time

Goal

Even when reading the same data the same number of times, you measure directly how the reading order alone changes the time by several times. After three experiments — stride, row-major versus column-major, and tiling — locality becomes not an abstract phrase but a number you can hold in your hand.

Why it matters

The memory hierarchy stands on the assumption that programs have locality. Code that violates that assumption gets none of the help the hardware has prepared. The cache fetches data in 64-byte line units, the prefetcher reads ahead for accesses that advance at a regular interval, and the TLB remembers the address translations of recently used pages. Increasing the stride defeats these three in turn.

What you measure here is not Python's speed. Python is slow, but that slowness is attached equally to every experiment, so if you fix the number of reads, the remaining difference is due to memory. You could say this design is the whole of this lab.

The absolute values of the numbers differ from machine to machine. The grader does not look at absolute values either, only which side is slower and by how much.

Steps

1. Check the cache line size and the cache hierarchy of the CPU this Pod runs on, and save them in /root/mem/01-cache.txt.
2. Create /root/mem/stride.py. It takes the stride as an argument and prints nanoseconds per read as a single line of digits only.
3. Measure strides 1, 16, and 65536 and save them in /root/mem/03-stride.txt as three lines.
4. To stride.py, add a rand branch, measure sequential and random, and save them in /root/mem/04-random.txt as two lines.
5. Create /root/mem/matrix.py. It takes N and the traversal direction as arguments and prints nanoseconds per element.
6. Set N to 2048, measure row-major and column-major, and save them in /root/mem/06-order.txt as two lines.
7. To matrix.py, add a block branch, measure column-major and tiling, and save them in /root/mem/07-block.txt as two lines.
8. Summarize the three experiments in one sentence each and save them in /root/mem/08-notes.md.

Notes

• Put all outputs under /root/mem/. Run mkdir -p /root/mem first.
• Measure time with time.perf_counter(). time.time() has too little resolution.
• Warm up by reading about 1,000 times before measuring. The first access includes the cost of building the array and page faults.
• Common mistake 1: making the array small. If it is a size that fits in the cache, changing the stride makes no difference however much you change it.
• Common mistake 2: writing the index expression differently for each branch. If you drop a multiplication on one side, that difference gets mixed into the measurement, and you can no longer tell whether you are measuring memory or arithmetic.
• The array is about 96MB. The Pod gets 2Gi of memory, so there is headroom, but do not run several programs at once.

Read this machine's cache hierarchy

Check the cache line size and cache hierarchy (L1/L2/L3) of the CPU this Pod runs on, and save them in /root/mem/01-cache.txt. Also calculate how many elements of int32 fit in one line and write it there.

The cache line size is in /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size, and reading level, type, and size in the same directory shows the hierarchy. int32 is 4 bytes, so dividing the line size by 4 gives how many fit in one line. This number becomes the reference for choosing strides in later steps.

Build a tool that measures with varying strides

Create /root/mem/stride.py. When called as python3 /root/mem/stride.py <보폭> (the placeholder is the stride), it must build an array of 24,000,001 int32 elements (about 96MB), read it 500,000 times, and print the nanoseconds taken per read to one decimal place as a single line of digits only.

The key is to fix the number of reads regardless of the stride. That way Python's own slowness cancels out equally on both sides and only the memory difference remains.

Build the indices as a list in advance, and in the timed section iterate only over that list. Advance to the next index with i = (i + 보폭) % 배열길이 (stride, array length). Because the array length is odd, even with a large stride you do not quickly step on the same spot again.

Warm up by reading about 1,000 times before measuring. The first run includes the cost of building the array.

Measure with strides 1, 16, and 65536

Using the tool from step 2, measure strides 1, 16, and 65536 and save three lines in /root/mem/03-stride.txt in the form 보폭 나노초 (stride, nanoseconds).

Running it like for s in 1 16 65536; do echo "$s $(python3 /root/mem/stride.py $s)"; done gives all three lines at once.

A stride of 16 is, for int32, a jump of exactly one cache line, and a stride of 65536 is 256KB, so it far exceeds both the page boundary and the range the prefetcher can follow. The prefetcher cannot cross a page boundary, so the value jumps high here.

Same size, only the order changed

Modify /root/mem/stride.py so that if it receives rand as an argument, it reads in random order. Then measure sequential (stride 1) and random, and save two lines in /root/mem/04-random.txt: seq 나노초 and rand 나노초 (nanoseconds).

The point of this step is to keep both the array size and the number of reads the same and change only the order of reading. Since the size is the same, you cannot blame capacity, and the only explanation left is spatial locality.

Build the random indices in advance, before measuring. If you fix the seed, as in random.Random(1), the same order comes out when you run it again.

Build a tool that sweeps a matrix in two directions

Create /root/mem/matrix.py. When called as python3 /root/mem/matrix.py <N> <row|col|block>, it must store an int32 N×N matrix in one flat array (a[i * N + j]), sweep all of it in the specified direction, and print nanoseconds per element to one decimal place as a single line of digits only.

For row, i is the outer loop and j the inner. col is the opposite. Keep the index expression identical in both branches as a[i * N + j]. If you drop the multiplication on only one side, the cost of Python arithmetic gets mixed into the measured difference and you can no longer tell what you are measuring.

block is used in step 7. For now, this step passes even with only row and col.

Measure the difference between row-major and column-major

Set N to 2048, measure row-major and column-major, and save two lines in /root/mem/06-order.txt: row 나노초 and col 나노초 (nanoseconds).

You read the same elements the same number of times, and only the order differs. Even so, column-major is several times slower. With N at 2048, one step in the column direction is 8KB, which is a distance beyond a single page (4KB).

If the difference does not show well, try increasing N. If the matrix fits in the cache, it becomes similar whichever direction you read.

Cut into tiles to reduce the column-major loss

To matrix.py, add a block branch. Keep the order column-major but make it loop only within 64×64 pieces. Then set N to 2048, measure column-major and tiling, and save two lines in /root/mem/07-block.txt: col 나노초 and block 나노초 (nanoseconds).

The outer two loops move the starting coordinates of the tile, and the inner two loops go around column-major within the tile. If a tile is 64 rows × 64 columns, the cache lines touched within it total about 16KB, which fits in L1.

The reason it gets faster even though you read the same elements the same number of times is that you use up a fetched line before discarding it. This is why tiling is used in matrix multiplication.

Summarize the three experiments in one sentence each

Write at least three lines in /root/mem/08-notes.md. In one sentence each, write why increasing the stride makes it slower, why column-major traversal is a loss, and what tiling recovers.

All three experiments tell the same story from different angles. Memory moves in line units, and if you discard a fetched line without using it, you lose that much.

The words 보폭, 열 우선, and 타일 (stride, column-major, and tile) must appear in the text.