1

Consider the following code, which sums the elements of a product of two matrices:

register int i, k; 
// i, k are in the processor registers 
register float sum, a[8][8], b[8][8];

for(i = 0; i < 8; i++) { /* 1 */
	for(k = 0; k < 8; k++) { /* 2 */
		sum += a[i][k] * b[k][i]; /* 3 */
	}
 }

Assume the following:

• There is a perfect instruction cache; i.e., do not worry about the time for any instruction accesses.
• Both int and float are of size 4 bytes.
• Assume that only the accesses to the arrays a and b generate accesses to the data cache. The rest of the variables are all allocated in registers.
• Assume a fully associative, LRU data cache with 8 lines, where each line is 32 bytes.
• Initially, the data cache is empty.
• The arrays a and b are stored in row order.
• To keep things simple, we will assume that statements in the above code are executed sequentially.
  Lines (1), and (2) take 10 cycles for each invocation. Line (3) takes 10 cycles plus an additional 20 cycles per data cache miss to wait for the data. That is, if both array accesses in line (3) miss, it takes a total of 50 cycles.
• Assume that the arrays a and b both start at cache line boundaries

--

먼저 볼 것: 한 행(row) = 캐시 한 줄
float 하나 = 4 B, 한 행 = 8개 × 4 B = 32 B = 캐시 한 줄
배열은 행 우선(row order)으로 저장되고 줄 경계에서 시작하므로:
a[i][0..7] → 줄 A_i 하나
b[k][0..7] → 줄 B_k 하나
a, b 각각 8줄씩 총 16줄인데, 캐시는 8줄뿐입니다.

접근 패턴
i를 하나 고정하고 k = 0..7을 돌면:

a[i][k] : a[i][0], a[i][1], ..., a[i][7]  → 전부 같은 줄 A_i (행 방향)
b[k][i] : b[0][i], b[1][i], ..., b[7][i]  → B0, B1, ..., B7 (열 방향 = 매번 다른 줄)

i 하나를 처리하는 데 필요한 줄은 A_i 1개 + B0~B7 8개 = 9줄인데, 캐시는 8줄입니다. 여기서 문제가 생깁니다.
-> 문제에서 cache line = 8 lines 이라고 했음

(a)

How many accesses to arrays a and b will result in cache misses? Explain your answer.

답은 (a) 72번 미스 (a 8번 + b 64번).

(a) 미스 횟수 = 72
i = 0

접근 순서: A0, B0, A0, B1, A0, B2, …, A0, B7

A0: 처음 1번 미스, 나머지 7번 hit
B0~B7: 처음이라 8번 모두 미스
B7이 들어올 때 캐시가 꽉 차 있으므로 LRU인 B0이 쫓겨남

i = 0이 끝난 뒤 캐시 (오래된 것 → 최근 것): B1 B2 B3 B4 B5 B6 A0 B7

B 줄들은 순서대로 돌아가며 쓰이는데, LRU는 ”가장 오래전에 쓴 줄"을 내보내고, 그게 바로 곧 다시 쓸 줄입니다. 9줄이 8칸 캐시를 순환하면 LRU에서는 b 접근이 전부 미스가 납니다. A_i는 매 반복 쓰이니 계속 남아 있습니다.

끝난 상태가 i = 0 뒤와 같은 모양이라, i = 2~7도 똑같이 반복됩니다

참고로 실행 시간은 10 × 8 (line 1) + 10 × 64 (line 2) + 10 × 64 (line 3) + 20 × 72 (미스) = 2800 cycles입니다.

(b)

Now assume there is a data prefetch instruction with the format prefetch (array[index1][index2]). This prefetches the entire block containing the word array[index1][index2] into the data cache.

It takes 1 cycle for the processor to execute this instruction and send it to the data cache. The processor can then go ahead and execute subsequent instructions. If the prefetched data is not in the cache, it takes 20 cycles for the data to get loaded into the cache.

Add prefetch instructions to minimize the execution time. Do not transform the code in any other way. How many cache misses for accessing a and b at line (3) in your modified code?

(Hint: since line 1, 2, and 3 each takes 10 cycles when there is no cache miss, you can consider using them to hide the 20-cycle latency for the data to get loaded into the cache when prefetching. If you insert the prefetch instructions appropriately, the cache misses can be totally eliminated.)

(b) Prefetch로 미스 0번 만들기
핵심: 데이터가 필요한 시점보다 20 cycles 이상 먼저 prefetch

prefetch는 발행에 1 cycle, 데이터 도착에 20 cycles가 걸립니다. 힌트대로 line 1, 2, 3이 각각 10 cycles이므로 두 줄(20 cycles)만큼 앞서 prefetch하면 지연이 다 숨겨집니다

prefetch(a[0][0]);                   /* A0: 첫 a 줄 */
prefetch(b[0][0]);                   /* B0: 첫 b 줄 */
for (i = 0; i < 8; i++) {            /* 1 */
    for (k = 0; k < 8; k++) {        /* 2 */
        prefetch(b[k+1][i]);         /* 다음 반복에 쓸 b 줄 B_(k+1) */
        sum += a[i][k] * b[k][i];    /* 3 */
    }
    prefetch(a[i+1][0]);             /* 다음 i의 a 줄 A_(i+1) */
    prefetch(b[0][i+1]);             /* 다음 i의 첫 b 줄 = B0 */
}

각 prefetch가 왜 그 위치인가

① 루프 전 prefetch 2개
prefetch 두 개(2 cycles)를 낸 뒤 line 1(10) + line 2(10) = 20 cycles가 지나고 첫 line 3이 실행되므로, 딱 맞게 도착합니다.

② 안쪽 루프의 prefetch(b[k+1][i])
반복 k에서 발행하면, 그 뒤 line 3(10) + 다음 반복의 line 2(10) = 20 cycles 후에 b[k+1][i]를 씁니다. 한 반복 앞서 가져오면 충분합니다.

③ 바깥 루프 끝의 prefetch 2개
k = 7의 line 3이 끝나고 다음 i의 첫 line 3까지 line 1(10) + line 2(10) = 20 cycles입니다.

a[i+1][0]: 다음 행의 a 줄
b[0][i+1]: 줄 B0. b[0][어떤 열]이든 같은 줄이라, 다음 i의 첫 b 접근 b[0][i+1]이 미리 들어옵니다.
a는 왜 한 행에 한 번만 prefetch하나

a[i][0..7]이 전부 한 줄(A_i)이라, 첫 접근만 미스입니다. 그 뒤로는 매 반복 쓰이니 LRU에서 쫓겨나지 않습니다. 그래서 행마다 한 번만 가져오면 됩니다.

주의: 너무 일찍 prefetch하면 안 됨

prefetch(a[i+1][0])을 바깥 루프 처음(안쪽 루프 전)에 두면, 실제로 쓰기 전까지 Ai와 B0~B7, 9개 줄이 쓰입니다. A(i+1)은 그동안 한 번도 안 쓰여서 LRU가 내보냅니다. 그러면 다시 미스가 나므로, 쓰기 직전 20 cycles 시점에 가져와야 합니다.

(b) 답: line 3에서 a, b 접근 미스 0번

참고: 쓸모없는 prefetch 몇 개
k = 7일 때 b[8][i]는 배열 b 바깥 주소이고, 다음에 필요한 B0는 ③에서 이미 가져옵니다.
i = 7일 때 a[8][0], b[0][8]도 더 이상 필요 없는 데이터입니다.

---

2

공통
① page offset = log₂(페이지 크기)
② 캐시: block offset = log₂(블록 크기)
         index = log₂(캐시 크기 ÷ 블록 크기 ÷ way 수)
③ 비교: index + block offset  vs  page offset

예제 1 유형 (비트를 묻는 문제)
④ VPN = 가상 주소 − page offset,  PPN = 물리 주소 − page offset
⑤ TLB: index = log₂(TLB set 수), tag = VPN − index  (fully associative면 index 0)
⑥ 캐시 tag = 물리 주소 − index − block offset
⑦ 비트 번호로 겹쳐 보고 분류
   - page offset 안 → 가상 주소에서 바로 사용
   - page offset 밖 → TLB 번역 후 사용
   
예제 2 유형 (시간을 묻는 문제)
④ ③에서 index + offset ≤ page offset 이면
     병렬: max( max(TLB, tag index) + 비교, data index ) + mux
   아니면
     직렬: TLB + max( tag index + 비교, data index ) + mux
⑤ 숫자 대입

Consider a virtual memory system where a TLB access takes 6ns and there is a single level of 32KB, a 4-way set associative, 16-byte block, write-back data cache with the following parameters:

• Indexing the cache to access the data portion takes 12ns = data index
• Indexing the tag array of the data cache takes 8ns = tag index
• Tag comparisons take 3ns = tag comparison
• Multiplexing the output data takes 1ns = mux

Assume these are the only parts that affect the cache access time. Assume the page size is 8KB. Calculate the amount of time it takes to get data from the cache on a hit, including any needed TLB access time. Please explain your answers in detail to get the full credits.

---

답은 13 ns입니다. 이번 문제는 Exercise 2와 달리 TLB와 캐시를 동시에 접근할 수 있는 경우예요. 같은 순서로 풀어 볼게요.

① 캐시 index + block offset

block offset = log₂(16 B) = 4비트
set 수       = 32 KB ÷ (4-way × 16 B) = 32768 ÷ 64 = 512
index        = log₂(512) = 9비트
합계         = 9 + 4 = 13비트

② page offset

페이지 8 KB = 2¹³ → page offset = 13비트

③ 비교: 병렬 가능한가?

index + block offset = 13  ≤  page offset = 13  ✅

캐시 index와 block offset이 전부 page offset 안에 들어갑니다. 이 비트들은 번역해도 바뀌지 않으므로, TLB 번역을 기다리지 않고 가상 주소로 바로 캐시를 index할 수 있습니다. 그래서 TLB 접근과 캐시 접근을 동시에 시작합니다. (way 하나 = 32 KB ÷ 4 = 8 KB = 페이지 크기라서 딱 맞습니다.)

④ 병렬 공식에 대입

hit time = max( max(TLB, tag index) + tag 비교, data index ) + mux
         = max( max(6, 8) + 3, 12 ) + 1
         = max( 8 + 3, 12 ) + 1
         = max( 11, 12 ) + 1
         = 12 + 1
         = 13 ns

각 단계 설명:

0 ns: TLB, tag 배열, data 배열이 동시에 시작합니다. 캐시는 가상 주소의 하위 13비트로 set을 고릅니다.
tag 비교는 8 ns에 시작: 비교하려면 TLB의 물리 페이지 번호(6 ns에 나옴)와 캐시의 tag(8 ns에 나옴)가 둘 다 있어야 합니다. 늦은 쪽인 8 ns부터 3 ns 동안 비교해서 11 ns에 hit 신호가 나옵니다.
data는 12 ns에 준비: data 배열 읽기가 12 ns로 가장 오래 걸립니다.
mux는 12 ns에 시작: hit 신호(11 ns)와 data(12 ns)가 둘 다 준비돼야 hit한 way를 고를 수 있으므로, 늦은 쪽인 12 ns부터 1 ns → 13 ns.

이 문제에서는 data 배열 읽기(12 ns)가 가장 느린 경로(critical path)입니다. TLB(6 ns)는 tag 읽기(8 ns) 뒤에 완전히 숨겨집니다.

Step 1. Cache index and offset bits. Block offset = log₂(16) = 4 bits. Number of sets = 32 KB / (4 × 16 B) = 512, so index = log₂(512) = 9 bits. Index + block offset = 13 bits.

Step 2. Page offset. Page size 8 KB = 2¹³, so the page offset is 13 bits.

Step 3. Can the TLB and cache be accessed in parallel? Since index + block offset (13 bits) ≤ page offset (13 bits), all bits needed to index the cache come from the page offset, which is not changed by translation. Therefore the cache can be indexed with the virtual address while the TLB translates the page number in parallel (virtually indexed, physically tagged).

Step 4. Timing. The TLB (6 ns), tag array (8 ns), and data array (12 ns) all start at time 0. The tag comparison needs both the physical page number from the TLB and the stored tag, so it starts at max(6, 8) = 8 ns and finishes at 8 + 3 = 11 ns. The data array output is ready at 12 ns. The mux needs both the hit signal and the data, so it starts at max(11, 12) = 12 ns and finishes at 13 ns.

Hit time = max(max(6, 8) + 3, 12) + 1 = 13 ns.