Associative Arrays

Arbitrary key types, exists(), delete(), iteration, sparse memory, scoreboard lookup.

Module 3 · Page 3.3

When Sequential Indices Make No Sense

You are modeling a 4GB address space. The DUT only touches a few dozen locations during any given test. A static array of 4 billion entries wastes memory. A dynamic array forces you to manage a mapping from address to array index manually. An associative array gives you exactly what you need: use the actual 32-bit address as the key, store only the addresses you actually write to, and let the simulator handle the hash table underneath.

Associative arrays are also the right tool for scoreboards that track transactions by ID, coverage models that track which opcodes have been seen, and any lookup table where the key space is sparse, string-based, or simply not known in advance. The syntax is clean: mem[32'hFFFF_0000] = 8'hAB writes a byte to an address. mem.exists(32'hFFFF_0000) checks if it was ever written. mem.delete(32'hFFFF_0000) removes it.

The behavior that catches engineers off guard: reading a non-existent key with val = mem[key] does not throw an error. For most key types it returns the default value (0 for int, X for logic) and — critically — it may or may not insert the key depending on the simulator and context. Always use exists() before reading if the key's presence is uncertain.

How Associative Arrays Work — Key Concepts

Think of an associative array as a hash map. Under the hood, most simulators implement it as a balanced tree or hash table indexed by the key type. The key can be any integral type, a string, or the wildcard [*] which accepts any integral key regardless of width. Elements are stored only for keys that have been written — the "size" of the array grows as you add entries.

Iteration order matters: for integer keys, foreach visits entries in ascending key order. For string keys, iteration is lexicographic. This sorted iteration is something dynamic and static arrays do not offer, and it makes associative arrays useful for ordered reporting and deterministic test reproduction.

Auto-allocation on write — Writing to any key instantly creates the entry. No new[] needed. The array grows on demand, one key at a time.
exists() — safe read guard — Returns 1 if the key has an entry, 0 if not. Always call before reading when the key might be absent. Reading missing keys returns default but may silently create the entry.
num() — entry count — Returns the current number of occupied entries. Unlike $size() for other arrays, associative arrays use the num() method.
Sorted iteration — foreach visits integer keys in ascending order, string keys lexicographically. first(), next(), last(), prev() for manual traversal.

Syntax — Every Method You'll Use

SystemVerilog — Associative Array Syntax

// ── Declaration ──────────────────────────────────────────────────
logic [7:0]  mem   [int];          // int key, 8-bit value
int            score [string];      // string key, int value
logic [31:0] regs  [logic[7:0]]; // 8-bit address key, 32-bit value
int            wild  [*];             // wildcard key — any integral type
 
// ── Write (auto-creates entry) ────────────────────────────────────
mem[32'hA000] = 8'hFF;
score["write"] = 10;
regs[8'h05]  = 32'hCAFE_BABE;
 
// ── Read ──────────────────────────────────────────────────────────
logic [7:0] val = mem[32'hA000];   // OK: key exists
int           s   = score["write"];  // OK: key exists
 
// ── exists() — ALWAYS check before reading unknown keys ──────────
if (mem.exists(32'hA000))
val = mem[32'hA000];
else
$display("Key not found");
 
// ── num() — count of active entries ──────────────────────────────
$display("Entries: %0d", mem.num());  // how many keys are populated
 
// ── delete() — remove one key or all keys ────────────────────────
mem.delete(32'hA000);              // remove one entry
mem.delete();                      // remove ALL entries (clear the array)
 
// ── foreach — sorted iteration ────────────────────────────────────
foreach (mem[addr])
$display("mem[0x%0h] = 0x%02h", addr, mem[addr]); // ascending key order
 
// ── first() / next() / last() / prev() ───────────────────────────
int k;
if (mem.first(k))
do $display("0x%0h", k);
while (mem.next(k));              // walks all keys in order

Method	Signature	Returns	Notes
`exists(key)`	`int exists(key_t key)`	1 if key present, 0 if not	Must call before reading uncertain keys
`num()`	`int num()`	Count of current entries	Use instead of `$size()`
`delete(key)`	`void delete(key_t key)`	void	Removes one entry; safe if key absent
`delete()`	`void delete()`	void	Removes all entries — clears the array
`first(key)`	`int first(ref key_t key)`	1 if array non-empty	Sets key to smallest/first entry
`last(key)`	`int last(ref key_t key)`	1 if array non-empty	Sets key to largest/last entry
`next(key)`	`int next(ref key_t key)`	1 if successor exists	Advances key to next entry in order
`prev(key)`	`int prev(ref key_t key)`	1 if predecessor exists	Retreats key to previous entry

Visual — Sparse Storage and Iteration Order

Sparse Memory Model — Only Occupied Entries Stored

Address space: 32-bit (4 billion possible addresses). Only 5 locations written. An associative array stores exactly 5 entries:

Key (Address)	Value	exists()?	foreach visit order
`32'h0000_0100`	`8'hAA`	1	1st
`32'h0000_0200`	`8'hBB`	1	2nd
`32'hA000_0000`	`8'hCC`	1	3rd
`32'hF000_0000`	`8'hDD`	1	4th
`32'hFFFF_FFFC`	`8'hEE`	1	5th
All other addresses	Not stored	0	Never visited

Total memory used: proportional to 5 entries, not 4 billion. mem.num() = 5.

String Key Iteration — Lexicographic Order

Write order	Key	Value	foreach visit order
3rd write	`"write"`	10	4th (lexicographic: w > r > n > i)
1st write	`"read"`	5	3rd
4th write	`"nop"`	0	2nd
2nd write	`"idle"`	3	1st (i comes first)

Write order does not determine iteration order. foreach always visits in sorted key order — this makes reports deterministic regardless of the order transactions arrived.

exists() vs Direct Read — The Behavior Difference

Operation	Key exists?	Result	Side effect
`mem.exists(key)`	Yes	1	None
`mem.exists(key)`	No	0	None — pure check, no entry created
`val = mem[key]`	Yes	Stored value	None
`val = mem[key]`	No	Default value (0/X)	May create entry with default value (tool-dependent)
`mem[key] = val`	No	void	Creates entry — intended behavior

Code Examples — Sparse Maps to Protocol Scoreboards

Example 1 — Beginner: Basic Integer and String Keys

Example 1 — Associative Array Basics

module tb_aa_basics;
 
int    addr_map [int];        // int key, int value
string op_name  [int];        // int opcode → string name
int    counters [string];     // string key → counter
 
initial begin
 
// ── Integer key ───────────────────────────────────────────────
addr_map[32'h1000] = 100;
addr_map[32'h2000] = 200;
addr_map[32'hF000] = 999;
$display("num = %0d", addr_map.num());         // 3
$display("[0x1000] = %0d", addr_map[32'h1000]); // 100
 
// ── Exists check ──────────────────────────────────────────────
$display("exists(0x1000) = %0b", addr_map.exists(32'h1000)); // 1
$display("exists(0x5000) = %0b", addr_map.exists(32'h5000)); // 0
 
// ── Delete ────────────────────────────────────────────────────
addr_map.delete(32'h2000);
$display("After delete: num = %0d", addr_map.num());   // 2
 
// ── String key ────────────────────────────────────────────────
counters["read"]  = 0;
counters["write"] = 0;
counters["idle"]  = 0;
counters["read"]++;
counters["read"]++;
counters["write"]++;
 
// ── foreach: lexicographic order ─────────────────────────────
$display("Operation counts (sorted):");
foreach (counters[op])
$display("  %-8s: %0d", op, counters[op]);
// Prints: idle:0, read:2, write:1  (lexicographic)
 
// ── Opcode → name lookup ─────────────────────────────────────
op_name[8'h10] = "ADD";
op_name[8'h11] = "SUB";
op_name[8'h20] = "LOAD";
logic [7:0] recv_op = 8'h11;
if (op_name.exists(recv_op))
$display("opcode 0x%02h = %s", recv_op, op_name[recv_op]); // SUB
 
$finish;
end
 
endmodule

Expected output:

Simulation Output

num = 3
[0x1000] = 100
exists(0x1000) = 1
exists(0x5000) = 0
After delete: num = 2
Operation counts (sorted):
idle    : 0
read    : 2
write   : 1
opcode 0x11 = SUB

Example 2 — Intermediate: Sparse 32-bit Memory Model

Example 2 — Byte-Addressable Sparse Memory

module tb_sparse_mem;
 
// Sparse byte-addressable memory — 4GB address space, only used bytes stored
logic [7:0] mem [logic[31:0]];
 
// Write a word (4 bytes) to the memory model
task automatic write_word(input logic [31:0] addr, input logic [31:0] data);
mem[addr]   = data[7:0];
mem[addr+1] = data[15:8];
mem[addr+2] = data[23:16];
mem[addr+3] = data[31:24];
endtask
 
// Read a word — returns X if any byte is missing
function automatic logic [31:0] read_word(input logic [31:0] addr);
if (!mem.exists(addr)   || !mem.exists(addr+1) ||
!mem.exists(addr+2) || !mem.exists(addr+3))
return 32'hXXXX_XXXX;
return {mem[addr+3], mem[addr+2], mem[addr+1], mem[addr]};
endfunction
 
initial begin
write_word(32'h0000_1000, 32'hAABB_CCDD);
write_word(32'hF000_0000, 32'h1234_5678);
 
$display("Bytes used: %0d", mem.num());                   // 8
$display("[0x1000] = 0x%08h", read_word(32'h0000_1000));  // AABBCCDD
$display("[0x2000] = 0x%08h", read_word(32'h0000_2000));  // xxxxxxxx
 
// Dump all occupied addresses in order
logic [31:0] k;
if (mem.first(k)) do
$display("  mem[0x%08h] = 0x%02h", k, mem[k]);
while (mem.next(k));
 
$finish;
end
 
endmodule

Example 3 — Verification: Transaction Scoreboard by ID

Example 3 — Out-of-Order Scoreboard Using Associative Array

module tb_scoreboard;
 
typedef struct {
logic [31:0] addr;
logic [31:0] data;
bit           is_write;
} txn_t;
 
txn_t   sent_txns [int];    // tid → sent transaction
txn_t   rcvd_txns [int];    // tid → received response
int     mismatch_cnt = 0;
 
// Called when driver sends a transaction
task automatic record_sent(int tid, txn_t t);
sent_txns[tid] = t;
endtask
 
// Called when monitor captures a response
task automatic record_rcvd(int tid, txn_t t);
rcvd_txns[tid] = t;
// Check immediately if sent was already recorded
if (sent_txns.exists(tid)) compare(tid);
endtask
 
// Compare a single transaction pair
task automatic compare(int tid);
if (sent_txns[tid].addr !== rcvd_txns[tid].addr ||
sent_txns[tid].data !== rcvd_txns[tid].data) begin
$error("TID=%0d MISMATCH: sent addr=0x%h data=0x%h  got addr=0x%h data=0x%h",
tid,
sent_txns[tid].addr, sent_txns[tid].data,
rcvd_txns[tid].addr, rcvd_txns[tid].data);
mismatch_cnt++;
end else
$display("TID=%0d PASS", tid);
sent_txns.delete(tid);   // clean up matched pair
rcvd_txns.delete(tid);
endtask
 
initial begin
txn_t t;
 
// Simulate out-of-order: responses arrive in different order from sends
t = '{32'h1000, 32'hAABB, 1}; record_sent(0, t);
t = '{32'h2000, 32'hCCDD, 0}; record_sent(1, t);
 
// Response for TID=1 arrives before TID=0
t = '{32'h2000, 32'hCCDD, 0}; record_rcvd(1, t);
t = '{32'h1000, 32'hAABB, 1}; record_rcvd(0, t);
 
$display("Mismatches: %0d", mismatch_cnt);
$finish;
end
 
endmodule

Expected output:

Simulation Output

TID=1 PASS
TID=0 PASS
Mismatches: 0

Example 4 — Corner Case: first()/next() Traversal and Empty Array Guard

Example 4 — Manual Traversal and Edge Cases

module tb_aa_traverse;
 
int scores [string];
string k;
 
initial begin
 
// ── Empty array: first() returns 0 ────────────────────────────
if (!scores.first(k))
$display("Array is empty — first() returns 0");   // prints
 
// ── Populate ──────────────────────────────────────────────────
scores["charlie"] = 85;
scores["alice"]   = 92;
scores["bob"]     = 78;
 
// ── first() / next() — full forward walk ──────────────────────
$display("Forward (lexicographic):");
if (scores.first(k)) do
$display("  %s = %0d", k, scores[k]);
while (scores.next(k));
 
// ── last() / prev() — backward walk ──────────────────────────
$display("Backward:");
if (scores.last(k)) do
$display("  %s = %0d", k, scores[k]);
while (scores.prev(k));
 
// ── Delete during iteration is UNSAFE — collect keys first ───
string keys_to_delete [$];   // queue to collect
foreach (scores[s])
if (scores[s] < 90) keys_to_delete.push_back(s);
foreach (keys_to_delete[i])
scores.delete(keys_to_delete[i]);        // safe: delete after iteration
 
$display("After removing <90: num = %0d", scores.num());  // 1 (alice)
 
$finish;
end
 
endmodule

Expected output:

Simulation Output

Array is empty — first() returns 0
Forward (lexicographic):
alice = 92
bob = 78
charlie = 85
Backward:
charlie = 85
bob = 78
alice = 92
After removing <90: num = 1

Simulation Behavior — Internals and Edge Cases

Memory and Performance Characteristics

Simulators implement associative arrays as balanced binary trees or hash maps. Lookup, insertion, and deletion are all O(log N) for tree-based implementations or average O(1) for hash-based. For large associative arrays (hundreds of thousands of entries), this is significantly more efficient than searching a dynamic array for a matching element. However, for small arrays (dozens of entries), the overhead of hashing or tree traversal can make a dynamic array faster — profile if performance matters.

What Happens When You Read a Missing Key

The LRM says reading a non-existent associative array entry returns the default value for the element type — 0 for two-state types, X for four-state. Whether the act of reading also creates the entry is tool-dependent. Aldec Riviera and Synopsys VCS handle this differently. The safe contract: always call exists() first. Never rely on "read returns 0 if missing" as a correctness guarantee in portable code.

Scenario	Behavior	Safe practice
Read existing key	Returns stored value	Always safe
Read missing key	Returns default; may or may not create entry (tool-dependent)	Call `exists()` first
Write to new key	Creates entry, stores value	Always safe — this is the normal write operation
Delete existing key	Entry removed, `num()` decremented	Always safe
Delete non-existent key	No-op, no error	Safe — no guard needed
foreach during delete	Undefined — iterator may be invalidated	Collect keys first, delete after loop

Where Associative Arrays Belong in Real Verification

Verification Patterns Using Associative Arrays

// ── 1. SPARSE MEMORY MODEL — most common use ──────────────────────
logic [7:0] mem [longint unsigned];  // 64-bit address space, byte-granule
// mem[addr] = data;  — writes any address instantly
// if (mem.exists(addr)) ...  — checks before read
 
// ── 2. OUT-OF-ORDER SCOREBOARD — transactions arrive in any order ──
typedef struct { logic[31:0] data; int time_sent; } pending_t;
pending_t pending [int];           // TID → pending transaction
// Driver: pending[tid] = txn;
// Monitor: if (pending.exists(tid)) { compare; pending.delete(tid); }
 
// ── 3. OPCODE/REGISTER NAME TABLE ─────────────────────────────────
string reg_name [logic[11:0]];      // 12-bit reg addr → human name
reg_name[12'h000] = "STATUS";
reg_name[12'h004] = "CONTROL";
reg_name[12'hFFF] = "VERSION";
// In monitor: $display("Write to %s", reg_name.exists(addr) ? reg_name[addr] : "UNKNOWN");
 
// ── 4. COVERAGE TRACKING — which opcodes were exercised ───────────
int opcode_hits [logic[7:0]];
// In monitor: opcode_hits[op]++;  (creates entry if first occurrence)
// End-of-test report:
// foreach (opcode_hits[op])
//   $display("op=0x%02h hit %0d times", op, opcode_hits[op]);
 
// ── 5. CONFIGURATION DATABASE (UVM resource-like) ─────────────────
int    cfg_int    [string];
string cfg_string [string];
cfg_int["timeout_cycles"]    = 1000;
cfg_string["interface_name"] = "axi_if";
 
// ── 6. PROTOCOL COVERAGE: seen address ranges ─────────────────────
int region_hits [string];
function automatic void classify_addr(logic [31:0] a);
string region = (a inside {[32'h0:32'hFFF]})     ? "BOOT"   :
(a inside {[32'h1000:32'hFFFF]}) ? "SRAM"   : "PERIPH";
region_hits[region]++;
endfunction

Bugs Engineers Hit With Associative Arrays

Bug 1 — Reading a Missing Key: Silent Default Value

Bug 1 — Missing exists() Check Before Read

int hit_count [logic[7:0]];     // tracks how many times each opcode seen
 
// BUGGY: reading an unseen opcode returns 0, which looks correct
// But on some tools it also silently CREATES the entry with value 0
// Now the coverage report shows the opcode was "seen" when it wasn't
logic [7:0] op = 8'hAB;
if (hit_count[op] == 0)             // reads a missing key — may create it!
$display("opcode 0xAB never seen"); // correct by luck, but entry now exists
 
// End-of-test: hit_count.num() = 1, but opcode was never actually driven!
 
// CORRECT: always use exists() to check presence
if (!hit_count.exists(op))
$display("opcode 0xAB never seen");   // purely checks, no side effect
else if (hit_count[op] == 0)
$display("seen but count is 0 — shouldn't happen");

Bug 2 — Deleting During Iteration: Undefined Behavior

Bug 2 — Modifying Array During foreach

int data [string];
data["a"]=1; data["b"]=2; data["c"]=3;
 
// BUGGY: deleting inside foreach — undefined/tool-dependent behavior
foreach (data[k])
if (data[k] < 2) data.delete(k);    // may skip entries or crash
 
// CORRECT: collect keys to delete, then delete after loop
string to_del [$];
foreach (data[k])
if (data[k] < 2) to_del.push_back(k);
foreach (to_del[i])
data.delete(to_del[i]);               // safe: delete after iteration complete

Bug 3 — Increment of a Never-Seen Key: Unintentional Creation

Bug 3 — op++ on Missing Key Starts From Default

int hit [logic[7:0]];
 
// This is actually FINE for int keys — default is 0, so 0++ = 1 ✓
// hit[op]++ works correctly for int-valued AA with integer keys
hit[8'hAB]++;   // creates entry with value 1 if key was absent
hit[8'hAB]++;   // now 2 — correct
 
// PROBLEM: logic-type values start as X, not 0
logic [7:0] count [int];
count[5]++;    // X + 1 = X — the counter is stuck at X forever!
$display("count[5] = %0d", count[5]);   // X
 
// CORRECT: use int or bit for counters, not logic
int safe_count [int];
safe_count[5]++;   // int default is 0, so 0+1 = 1 ✓

Bug 4 — Pending Entries Left in Scoreboard at End-of-Test

Bug 4 — Unmatched Sent Transactions at End-of-Test

// Scoreboard: sent_txns is populated by driver, deleted when response matches
// At end-of-test, any remaining entries = DUT never responded
 
function void check_drain();
if (sent_txns.num() != 0) begin
$error("%0d transactions sent but never received response:", sent_txns.num());
foreach (sent_txns[tid])
$error("  TID=%0d addr=0x%08h", tid, sent_txns[tid].addr);
end else
$display("All transactions matched");
endfunction
 
// BEST PRACTICE: call check_drain() at end-of-test before $finish
// A non-zero num() here means DUT dropped some transactions

Interview Questions

Beginner Level

Q1: What key types can be used with associative arrays in SystemVerilog? Any integral type (int, logic [N:0], bit, etc.), string, or the wildcard [*] which accepts any integral key. The key type determines iteration order: integer keys are visited in ascending numeric order, string keys lexicographically. Q2: How do you safely read from an associative array without accidentally creating entries? Always call exists(key) before reading when the key's presence is uncertain. Reading a missing key directly with arr[key] returns the default value but may silently create the entry — behavior is tool-dependent. exists() is a pure read-only check with no side effects.

Intermediate Level

Q3: Why are associative arrays better than dynamic arrays for modeling a 4GB byte-addressable memory in simulation? A dynamic array for 4GB would require 4 billion elements — far exceeding available simulator memory. An associative array only allocates storage for addresses that are actually written, making it O(writes) in size rather than O(address space). A typical test exercises hundreds or thousands of unique addresses, not billions. Access time is O(log N) for a tree-based implementation, which is acceptable for simulation. A dynamic array lookup by address would also require linear search or a manual hash — both inferior to the built-in associative array implementation. Q4: In what order does foreach iterate an associative array with integer keys? Ascending numeric order, regardless of the order in which keys were written. If you write keys 5, 1, 3, foreach visits them as 1, 3, 5. This is sorted iteration — something static and dynamic arrays do not provide. It makes end-of-test reporting deterministic: two simulations with the same transactions always produce the same output order, even if transactions arrived in different sequences.

Experienced Engineer Level

Q5: A scoreboard uses an associative array indexed by transaction ID to hold sent transactions. At end-of-test, sent.num() returns a non-zero value even though the test ran to completion. What does this indicate and how do you diagnose it? Non-zero sent.num() means those transaction IDs were never matched by a received response — the scoreboard never called sent.delete(tid) for them. Possible causes: (1) DUT dropped the transactions and never sent a response, (2) the monitor missed responses because of incorrect clock edge or signal sampling, (3) the response uses a different transaction ID than the one in the sent record (ID remapping bug in DUT), or (4) the test ended before all responses arrived — insufficient drain time. Diagnosis: dump the remaining entries via foreach (sent[tid]) at end-of-test to see which specific TIDs are unmatched. Cross-reference with the waveform to determine if the DUT issued a response for those TIDs. This end-of-test drain check is a mandatory scoreboard completion criterion — a test that ends with pending transactions is not a passing test.

Best Practices & Coding Guidelines

Always exists() before read — Reading a missing key returns default value and may create an entry. Use exists(key) for uncertain reads. Direct read is fine only when you know the key was previously written.
Use int/bit for counters — logic-valued AA entries default to X. Incrementing X gives X — the counter is permanently broken. Use int for any counter-style associative array value.
Never delete during foreach — Modifying the key set while iterating is undefined. Collect keys to delete into a temporary queue or dynamic array, then delete them after the loop completes.
Drain check at end-of-test — Any scoreboard associative array that holds pending transactions should be checked at end-of-test. Non-zero num() means the DUT missed transactions — this is a test failure, not just a warning.

Use case	Best array type	Reason
Full address space memory model	Associative `[int]` or `[longint]`	Sparse — only stores written addresses
Out-of-order transaction scoreboard	Associative `[int]` (TID key)	O(log N) lookup by ID, any-order matching
Named configuration table	Associative `[string]`	Human-readable keys, lexicographic iteration
Small fixed lookup table	Static array or `case` statement	Simpler, faster for small known sets
Coverage: which opcodes seen	Associative `[opcode_type]`	Auto-creates on first occurrence; num() = unique count

Summary

Associative arrays are the right tool whenever the key space is sparse, irregular, or string-based. The auto-allocation on write, sorted iteration, and O(log N) lookup make them ideal for memory models, out-of-order scoreboards, and coverage databases. The three behavioral rules that matter in practice: always guard uncertain reads with exists(), use int for counter-style values rather than logic, and never delete keys during a foreach loop.

Auto-allocation on write — no new[] needed. Any key you write to is created instantly.
exists(key) is the safe read guard. Reading a missing key returns default but may create the entry — tool-dependent behavior you cannot rely on.
num() returns the entry count — not $size(). A non-zero num() at end-of-test in a scoreboard means dropped transactions.
Iteration is sorted. Integer keys ascending, string keys lexicographic — independent of write order. Deterministic reporting without extra sorting.
Verification-only. Cannot be synthesized. Keep them in testbench packages.