Associativity is the number of lines per set. More ways hold more aliasing addresses at once, but every way adds a tag compare and widens the select mux.
The hit path slows as ways grow. That delay is paid on every access, while the miss saving only applies to conflict misses.
Ways | Tag compares per access | What improves | What worsens |
|---|---|---|---|
1 (direct-mapped) | 1 | Nothing to choose, fastest hit | Any alias pair thrashes |
4 to 8 | 4 to 8 | Most conflict misses gone | Hit delay and tag energy up |
16 and above | 16 and above | Little extra miss saving | Delay, power and timing closure pain |
Compulsory misses touch data for the first time. Capacity misses happen even in a fully associative cache of the same size. Conflict misses are the rest, and only associativity or mapping fixes remove them.
Multicore designs add a fourth class. Coherence misses come from invalidations by other cores, and they belong to the coherency topic, not to sizing.
Class | Removed by | Diagnosed with |
|---|---|---|
Compulsory | Larger lines or prefetch, never by ways | First-touch share of misses |
Capacity | Larger cache at fixed associativity | Fully associative shadow model |
Conflict | More ways, better mapping, victim buffer | Set-pressure heatmap |
Coherence | Less sharing or better layout | Invalidation counters per core |
The two models below share geometry: 4 sets and 1-byte lines, so index and tag decode match. Only the way count differs.
The trace writes two aliasing addresses, then reads them alternately twelve times. The direct-mapped cache misses every read, while the 2-way cache holds both lines.
Every miss fetches the line, for loads and stores alike. The two fill misses are compulsory, and the twelve alternating-read misses vanish in a fully associative cache of the same size, so they are conflict misses.
module cache_dm (
input logic clk,
input logic rst,
input logic req,
input logic wr,
input logic [7:0] addr, // tag[7:2] index[1:0], 1-byte lines
output logic hit,
output logic [31:0] hits,
output logic [31:0] misses
);
logic [5:0] tag_arr [4];
logic valid_arr [4];
logic [1:0] idx;
logic [5:0] tag;
logic match_line;
integer i;
assign idx = addr[1:0];
assign tag = addr[7:2];
assign match_line = valid_arr[idx] && (tag_arr[idx] == tag);
assign hit = req && match_line;
always_ff @(posedge clk) begin
if (rst) begin
hits <= 0; misses <= 0;
for (i = 0; i < 4; i = i + 1) begin valid_arr[i] <= 0; tag_arr[i] <= 0; end
end else if (req) begin
if (match_line) hits <= hits + 1;
else begin
misses <= misses + 1;
// every miss fetches the line: stores allocate, loads fill from memory
if (wr) begin tag_arr[idx] <= tag; valid_arr[idx] <= 1; end
else begin tag_arr[idx] <= tag; valid_arr[idx] <= 1; end
end
end
end
endmodule
module cache_tw (
input logic clk,
input logic rst,
input logic req,
input logic wr,
input logic [7:0] addr, // tag[7:2] index[1:0], 1-byte lines
output logic hit,
output logic [31:0] hits,
output logic [31:0] misses
);
logic [5:0] tag_arr [4][2];
logic valid_arr [4][2];
logic lru_arr [4];
logic [1:0] idx;
logic [5:0] tag;
logic m0;
logic m1;
logic vw;
integer i;
integer w;
assign idx = addr[1:0];
assign tag = addr[7:2];
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);
always_ff @(posedge clk) begin
if (rst) begin
hits <= 0; misses <= 0;
for (i = 0; i < 4; i = i + 1) begin
lru_arr[i] <= 0;
for (w = 0; w < 2; w = w + 1) begin valid_arr[i][w] <= 0; tag_arr[i][w] <= 0; end
end
end else if (req) begin
if (m0 || m1) begin
hits <= hits + 1;
lru_arr[idx] <= m0 ? 1'b1 : 1'b0;
end else begin
misses <= misses + 1;
// every miss fetches the line: stores allocate, loads fill from memory
if (wr) begin
tag_arr[idx][vw] <= tag;
valid_arr[idx][vw] <= 1;
lru_arr[idx] <= vw ? 1'b0 : 1'b1;
end else begin
tag_arr[idx][vw] <= tag;
valid_arr[idx][vw] <= 1;
lru_arr[idx] <= vw ? 1'b0 : 1'b1;
end
end
end
end
endmodule
Cache | Hits | Misses | Reading |
|---|---|---|---|
Direct-mapped | 0 | 14 | Every read evicts the other line |
2-way | 12 | 2 | Both aliasing lines stay resident |
Two bounded fixes avoid paying full associativity. A victim buffer catches freshly evicted lines, and way prediction probes the likely way first.
Compulsory and capacity only. Conflict misses cannot exist with no set restriction, so the survivors define the floor for this size.
Hit latency. AMAT in the next lesson prices the slower hit against the miss saving.