DescriptionQ402
Q402DesignASIC interview problem
Coalesce a frame of DMA ranges
TechniquesIntervalsBounded sortStreaming output
DifficultyMedium
TopicRTL Design
LanguageSystemVerilog
Requirements4 checkpoints
01
Problem
Buffer one frame of up to eight half-open direct-memory-access (DMA) ranges, sort them by start then end, and emit the smallest sorted set covering the same addresses. Merge overlap and exact adjacency.
Example input and output
Use this case to check your interpretationInput
input half-open ranges=[10,20),[5,8),[8,10),[15,25)Output
one output range=[5,25) with out_last=1Explanation
Sorting places [5,8) first; exact adjacency at 8 and 10 plus overlap at 15 coalesce every range into one cover.
02
Requirements (4)
- Accept 1 through 8 valid ranges satisfying start < end before producing output.
- Interpret ranges as [start, end) and merge whenever next_start <= current_end.
- Handle arbitrary order, duplicate starts, contained ranges, and adjacent ranges deterministically.
- Assert out_last only with the final coalesced token and hold every output field stable while stalled.