Mô phỏng một cache 2-way set associative dùng chính sách thay thế LRU. Cache có S set, mỗi set chứa 2 đường (way), kích thước block là B byte (lũy thừa của 2).
Với mỗi địa chỉ truy cập addr: block index = addr // B; set index = block_index % S; tag = block_index // S. Nếu tag có trong set → hit (cập nhật LRU); nếu không → miss, nạp block, thay thế đường ít dùng gần đây nhất (LRU) khi set đầy.
Hãy đếm số hit và số miss theo thứ tự truy cập.
S = 2, B = 4, các địa chỉ 0 4 8 0: ba truy cập đầu đều miss (cache rỗng), truy cập 0 cuối là hit. Kết quả: 1 hit, 3 miss.
Dòng 1: S B q (số set, kích thước block, số truy cập). Dòng 2: q địa chỉ không âm cách nhau bởi dấu cách.
1 ≤ S ≤ 1024, B lũy thừa của 2 (1 ≤ B ≤ 4096), 1 ≤ q ≤ 10^5, địa chỉ trong [0, 10^9].
Một dòng: hits misses cách nhau bởi dấu cách.
Ví dụ:
Đầu vào:
2 4 4
0 4 8 0
Đầu ra:
1 3
Giải thích:
Đang tải editor...