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

DescriptionQ045

Page ↗

Q045DesignArchASIC interview problem

Stably sort records in a local cache-line buffer

TechniquesStable sortSingle-port memoryMulticycle FSM

DifficultyMedium

TopicRTL Design

LanguageSystemVerilog

Requirements4 checkpoints

Problem

Load up to 16 key/payload records into one local synchronous storage array, stably sort them by nondecreasing key, and stream the sorted records with backpressure.

Multicycle stable-sort architecture with one single-port record memory, adjacent-pair control phases, and a backpressured output register. — The phase flow makes the one-port and one-cycle read-latency constraints explicit while preserving equal-key order.

Example input and output

Use this case to check your interpretation

Input

records in arrival order=[(key2,A),(key1,B),(key2,C),(key1,D)]

Output

streamed order=[(1,B),(1,D),(2,A),(2,C)]

Explanation

Stable sorting retains B before D and A before C for equal keys while each payload stays attached to its record.

Requirements (4)

Preserve each payload with its key and retain arrival order among equal keys.
Use a single read-or-write memory operation per cycle and honor one-cycle read latency.
Handle one record, duplicate keys, sorted input, and reverse-sorted input.
Hold the output record and out_last stable until accepted, and finish within a bounded number of internal cycles.