Skip to question
ASIC.FYI

Q242FreeSystemVerilog

Estimate the densest page in a bounded stream

Difficulty
Hard
Topic
Memory Systems
Language
SV
Interview prompt

Question

Process address observations online while storing at most MAX_ENTRIES page counters. Return an approximate densest page and its estimated density.

Starting point

Question code

class StreamingPageCounter #(int MAX_ENTRIES = 64);
  function void observe(longint unsigned addr);
  function void get_densest(
    output longint unsigned page_base,
    output int unsigned estimated_density
  );
endclass
Reviewed example

Trace one case

Input
MAX_ENTRIES=2; observed pages=[0x1000,0x2000,0x3000,0x3000,0x3000]
Expected output
approximate densest page=0x3000; estimated density=4 (true density=3)

Space-Saving replaces one minimum counter and inherits its error, so the bounded estimate may overcount but still identifies the heavy page.

What to cover

Requirements

  1. Increment exact counters for pages already tracked.
  2. Add unseen pages while capacity remains.
  3. When full, replace a minimum counter using the Space-Saving estimate.
  4. Document that bounded storage produces an approximation.
Continue practicing
Q283 · Memory SystemsFind the densest 4 KiB pageQ256 · Memory SystemsReturn every page at the kth density rankQ032 · Streaming AlgorithmsVerify a dictionary-order permutation streamer