Hardware interview practice

Stably sort records in a local cache-line buffer

MediumRTL DesignSystemVerilog

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.

Reviewed example

Work through one case

Input

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

Expected output

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

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

What to cover

Requirements

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.