Skip to question

Q066FreeSystemVerilog

Represent a 64-entry window with one bitmap

Difficulty
Easy
Topic
Reliable RTL
Language
SV
Interview prompt

Question

Optimize a fixed 64-entry transaction window by replacing the associative received set with one 64-bit bitmap. Sequence inputs and the initial base are signed 32-bit integers and do not wrap. Internal arithmetic must preserve their full range; after retiring 2^31 - 1, the next base is 2^31 and no further input sequence can be accepted.

Sequence numbers B through B plus sixty-three mapped to offsets in a single receive bitmap
A sequence maps to one bitmap bit using its offset from the current window base.
Candidate starting point

Implementation scaffold

class BitmapWindowTracker;
  bit [63:0] seen = '0;
  longint base;

  function new(int base = 0);
    this.base = base;
  endfunction

  function bit accept(int seq);
    longint offset = longint'(seq) - base;
    // Implement here: accept.
  endfunction
endclass
Reviewed example

Trace one case

Input
base=254; accept sequence 256, then 254, then 255
Expected output
offset2 sets first; accepting 254 and 255 advances base to257; bitmap returns to zero

The fixed bitmap records offset two out of order, then right-shifts once for each contiguous bit-zero retirement across the numeric boundary.

What to cover

Requirements

  1. Map seq minus base to bit positions zero through 63.
  2. Reject negative, too-large, and already-set offsets.
  3. Set the accepted bit.
  4. Shift right and increment base while bit zero is set.
Continue practicing
Q573 · Verification UtilitiesTrack an out-of-order sequence windowMediumPQ244 · Reliable RTLHandle wrapping 8-bit sequence numbersMediumPQ770 · Reference ModelsUse a bitmap for a 64-entry reorder windowMediumPQ973 · Reference ModelsDebug a signed sliding-window peakMediumP