A cache divides each address into three fields. The index picks the set, the tag is compared against the stored tags, and the offset picks bytes inside the line.
Widths follow from geometry. With S sets and B-byte lines, the index needs log2 S bits and the offset needs log2 B bits. The tag takes the rest.
32-KB cache, 8-way associative, 64-byte lines, 32-bit addresses
lines = 32768 / 64 = 512
sets = 512 / 8 = 64, so index = log2(64) = 6 bits
offset = log2(64) = 6 bits
tag = 32 - 6 - 6 = 20 bits
address 0x12345678:
offset = bits[5:0] = 0x38
index = bits[11:6] = 25
tag = bits[31:12] = 0x12345Field | Width in the example | Role |
|---|---|---|
Offset | 6 bits | Selects 1 of 64 bytes in the line |
Index | 6 bits | Selects 1 of 64 sets |
Tag | 20 bits | Compared against each way of the set |
A hit needs a valid line whose tag matches. The line data is then returned with no lower-level traffic.
A miss allocates or fetches instead. The table below lists the steps in order.
Step | Hit | Miss |
|---|---|---|
Set select | Index picks one set | Same |
Tag compare | One way matches and is valid | No way matches |
Data | Offset picks bytes from the line | Victim evicted, line fetched or allocated |
State update | LRU ages refreshed | Valid set, dirty set on a write |
Set 25. Bits [11:6] of the address read 0x19, which is 25.
Nothing. The miss is counted and reported, and the array keeps its contents until a fill source exists.
The model below is a 4-set 2-way cache with LRU. Writes allocate, read misses leave the array alone, and a dirty eviction is counted.
module cache_2way (
input logic clk,
input logic rst,
input logic req,
input logic wr,
input logic [7:0] addr, // tag[7:4] index[3:2] offset[1:0]
input logic [7:0] wdata,
output logic hit,
output logic [7:0] rdata,
output logic [31:0] hits,
output logic [31:0] misses,
output logic [31:0] dirty_evicts
);
logic [3:0] tag_arr [4][2];
logic valid_arr [4][2];
logic dirty_arr [4][2];
logic [7:0] data_arr [4][2][4];
logic lru_arr [4]; // 0: way0 is LRU, 1: way1 is LRU
logic [3:0] tag;
logic [1:0] idx;
logic [1:0] off;
logic m0;
logic m1;
logic vw; // victim way for a write miss
integer s;
integer w;
integer b;
assign tag = addr[7:4];
assign idx = addr[3:2];
assign off = addr[1:0];
assign m0 = valid_arr[idx][0] && (tag_arr[idx][0] == tag);
assign m1 = valid_arr[idx][1] && (tag_arr[idx][1] == tag);
assign vw = !valid_arr[idx][0] ? 1'b0 : (!valid_arr[idx][1] ? 1'b1 : lru_arr[idx]);
assign hit = req && (m0 || m1);
assign rdata = m0 ? data_arr[idx][0][off] : data_arr[idx][1][off];
always_ff @(posedge clk) begin
if (rst) begin
hits <= 0; misses <= 0; dirty_evicts <= 0;
for (s = 0; s < 4; s = s + 1) begin
lru_arr[s] <= 0;
for (w = 0; w < 2; w = w + 1) begin
valid_arr[s][w] <= 0;
dirty_arr[s][w] <= 0;
tag_arr[s][w] <= 0;
for (b = 0; b < 4; b = b + 1) data_arr[s][w][b] <= 0;
end
end
end else if (req) begin
if (m0 || m1) begin
hits <= hits + 1;
if (wr) begin
if (m0) begin data_arr[idx][0][off] <= wdata; dirty_arr[idx][0] <= 1; end
else begin data_arr[idx][1][off] <= wdata; dirty_arr[idx][1] <= 1; end
end
lru_arr[idx] <= m0 ? 1'b1 : 1'b0;
end else begin
misses <= misses + 1;
if (wr) begin
if (valid_arr[idx][vw] && dirty_arr[idx][vw]) dirty_evicts <= dirty_evicts + 1;
tag_arr[idx][vw] <= tag;
valid_arr[idx][vw] <= 1;
dirty_arr[idx][vw] <= 1;
for (b = 0; b < 4; b = b + 1) data_arr[idx][vw][b] <= 0;
data_arr[idx][vw][off] <= wdata;
lru_arr[idx] <= vw ? 1'b0 : 1'b1;
end
end
end
end
endmodule