Skip to question
ASIC.FYI

Q276FreeDesign Verification

Randomize free-range allocation

Difficulty
Medium
Topic
Memory Systems
Language
SV
Interview prompt

Question

Allocate from a randomly selected sufficient free range, then choose a valid random start within that range.

Starting point

Question code

function bit alloc_random(
  int unsigned size,
  output int unsigned addr
);
Reviewed example

Trace one case

Input
free=[[0x1000,0x10FF],[0x2000,0x20FF]]; request size=0x40
Expected output
One valid randomized result: base=0x2040; remaining selected-range fragments=[[0x2000,0x203F],[0x2080,0x20FF]]

Either free range and several starts are legal. This result demonstrates preservation of both prefix and suffix, so it is not the only valid random outcome.

What to cover

Requirements

  1. Choose uniformly among eligible ranges.
  2. Choose a valid start in the selected range.
  3. Preserve both unused prefix and suffix fragments.
  4. Return 0 without mutating state when no range is sufficient.
Continue practicing
Q212 · Memory SystemsBuild a first-fit range allocatorQ262 · Memory SystemsAllocate on a power-of-two boundaryQ290 · Memory SystemsImplement best-fit allocation