Skip to question

Q013FreeSystemVerilog

Find the densest 4 KiB page

Difficulty
Easy
Topic
Memory Systems
Language
SV
Interview prompt

Question

Given an associative array keyed by written addresses, return the 4 KiB-aligned page base containing the most keys and its density.

Six addresses grouped into three aligned four-kibibyte page bins with counts
Clear the low twelve address bits to form each page base, then compare the resulting densities.
Candidate starting point

Implementation scaffold

function automatic void densest_page_4kb(
  input bit [31:0] mem[longint unsigned],
  output longint unsigned densest_page,
  output int unsigned density
);
  int unsigned counts[longint unsigned];
  // Implement here: densest_page_4kb.
endfunction
Reviewed example

Trace one case

Input
written addresses=[0x1004,0x1010,0x1FFC,0x2000]
Expected output
page_base=0x1000; density=3

The first three keys share page number 1 after shifting by 12; the fourth belongs to page 0x2000.

What to cover

Requirements

  1. Count keys by shifting each address right by 12.
  2. Return the page base, not the page number.
  3. Return zero outputs for an empty input.
  4. Break equal-density ties in favor of the lower page base.
Continue practicing
Q157 · Memory SystemsReturn every page at the kth density rankMediumQ223 · Memory SystemsEstimate the densest page in a bounded streamHardPQ266 · Memory SystemsReturn the top K densest pagesMediumPQ243 · Memory SystemsConstrain eight aligned nonoverlapping memory regionsHardPQ094 · Data StructuresImplement a simple least-recently-used cacheMedium