Build an eight-entry ternary CAM with care masks, valid bits and deletes, whose search returns the lowest matching entry.
Hardware context: The address table of a small network switch, eight learned keys in a CAM. Build a CAM whose search returns the lowest valid entry that holds the key.
A network switch keeps the addresses it has learned in a small CAM. A search must say in one cycle whether a key is stored, and where. Old entries are deleted when they age out.
This is an Implement problem. Write cam8: eight entries, each with an 8-bit key, a care mask and a valid bit. A write stores the key and the mask and makes the entry valid. A delete makes it empty.
A search compares the key with every valid entry at once. A bit whose care bit is 0 matches anything, so one entry can cover a range. When several entries match, the lowest one wins. Empty entries still hold their old keys, and must never match.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
keys | 192 | input of each check |
Full specification
module cam8 (
input logic clk,
input logic rst, // synchronous, active high: every entry becomes empty
input logic we, // 1: store wkey in entry waddr at the next rising edge
input logic [2:0] waddr,
input logic [7:0] wkey,
input logic [7:0] wcare, // with we: 1 = this key bit must match, 0 = don't care
input logic del, // 1: delete entry daddr at the next rising edge
input logic [2:0] daddr,
input logic [7:0] key, // the search key
output logic hit, // 1: some valid entry matches key on all its care bits
output logic [2:0] index // the lowest such entry; 0 when there is no hit
);
// your design
endmodule
| Rule | Definition |
|---|---|
| Search | Combinational: hit and index follow key and the entries in the same cycle. |
| Match | An entry matches when it is valid and its key equals key on every bit whose care bit is 1. |
| Write | At the rising edge, entry waddr takes wkey and wcare and becomes valid. |
| Delete | At the rising edge, entry daddr becomes empty. Its old key stays in the array. |
| Both | A write and a delete of the same entry in one cycle: the write wins. |
| Priority | index is the lowest matching entry. |
| Reset | At a rising edge with rst = 1 every entry becomes empty. |
Each test resets the CAM and runs 24 cycles. Some cycles write or delete, and every cycle searches. hit and index are checked before each edge. index is only checked when hit is 1.
| Field | Meaning |
|---|---|
| wrong_hits | How many cycles had the wrong hit. |
| wrong_index | How many cycles with a hit had the wrong index. |
Examples
Example 1
Write Three Keys, Then Search Them- Input
write 11 in 0 search 11; write 22 in 1 search 11; write 33 in 5 search 22; search 33; search 11; search 22; search 44; search 00; search 35; search 6a; search 9f; search d4; search 09; search 3e; search 73; search a8; search dd; search 12; search 47; search 7c; search b1; search e6; search 1b; search 50
- Output
wrong_hits = 0, wrong_index = 0, cycles = 24
Each key is found at the entry it was written to. A key that was never written gives hit = 0. A search in the cycle of a write still sees the old contents.
Example 2
The Same Key in Two Entries- Input
write 5a in 6 search 5a; search 5a; write 5a in 2 search 5a; search 5a; write 5a in 4 search 5a; search 5a; delete 2 search 5a; search 5a; search 00; search 35; search 6a; search 9f; search d4; search 09; search 3e; search 73; search a8; search dd; search 12; search 47; search 7c; search b1; search e6; search 1b
- Output
wrong_hits = 0, wrong_index = 0, cycles = 24
When entries 2 and 6 both hold 5a, the search returns 2. After entry 2 is deleted, the next match up is found.
Example 3
Delete, Then Search- Input
write 77 in 3 search 77; search 77; delete 3 search 77; search 77; search 00; write 00 in 3 search 00; search 00; search 00; search 35; search 6a; search 9f; search d4; search 09; search 3e; search 73; search a8; search dd; search 12; search 47; search 7c; search b1; search e6; search 1b; search 50
- Output
wrong_hits = 0, wrong_index = 0, cycles = 24
After the delete, a search for the old key misses. A search for 00 must miss too, until a key 00 is really written.
Constraints and Contract
- The inputs are known 0/1 values. They change while the clock is low.
- Keep the module name, the ports and the array
keys. The test leaves old keys in it before the reset.
Hints
Hint 1
Give each entry a match line: valid, and (key XOR stored key) AND care equal to zero. Eight lines, all computed at once.
Hint 2
hit is the OR of the match lines. For the index, scan from entry 7 down to entry 0 and keep the last match you see.
Hint 3
In the clocked block, do the delete first and the write after it. The later assignment wins, so a write beats a delete of the same entry.
What the grader checks: Nine directed and eight seeded scripts of 24 cycles use exact and ternary entries. They are compared with a JavaScript model before every edge. Old keys are left in the array before reset, so a CAM that ignores the valid bits fails. Multi-cycle searches are outside this problem.
The submitted design must synthesize with 0 latches and no combinational loop. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.
17 checks on Icarus Verilog + Yosys · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 1 steps and the final capstone