1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ242

Page ↗

Q242ArchFollow-up to Q283ASIC interview problem

Estimate the densest page in a bounded stream

TechniquesStreamingHeavy hittersSpace Saving

DifficultyHard

TopicMemory Systems

LanguageSystemVerilog

Requirements4 checkpoints

Problem

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

Class declarationSystemVerilog

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

Example input and output

Use this case to check your interpretation

Input

MAX_ENTRIES=2; observed pages=[0x1000,0x2000,0x3000,0x3000,0x3000]

Output

approximate densest page=0x3000; estimated density=4 (true density=3)

Explanation

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

Requirements (4)

Increment exact counters for pages already tracked.
Add unseen pages while capacity remains.
When full, replace a minimum counter using the Space-Saving estimate.
Document that bounded storage produces an approximation.