FIFOs and Arbitration Interview Questions

Requester 0 wins every cycle it asks, so it gets 50 grants. Requester 3 wins only in the cycles where requester 0 is quiet, which is the other 50. The if-else chain is a priority encoder: each later branch is reached only when all earlier requests are low. If requester 0 asked every cycle, requester 3 would get nothing.

Both pick the lowest-numbered active input. In two's complement, req & -req keeps only the lowest set bit, which is exactly the grant. Synthesis gives about the same gates for either form, so choose the one the team reads most easily.

Fixed priority is tiny, has no state, and gives a guaranteed fast response to the top requester. But it can starve the rest. Round robin needs a little state and gives each active requester a turn within N grants. Use fixed priority for rare urgent requests and round robin for peers that share a resource.

Use two levels. The urgent requester has fixed priority over a round robin of the eight. To stop it from starving everyone, limit it. Use a maximum request rate, or let one normal grant through after a few urgent ones. Then you can state a worst-case wait for both classes.

Register the grant, so it is valid one cycle after the request. The requester must then hold its request until it sees the grant. The arbiter must not grant a requester that has already dropped its request. Latency grows by a cycle, which matters for short transfers.

Keep a mask of the requesters above the last winner. First look for the lowest requester inside the mask. If there is none, wrap around and take the lowest requester overall. After each grant, set the mask to the bits above the winner. The pointer moves only on a grant, so an idle cycle changes nothing.

Round robin promises that the winner goes to the back of the queue. Suppose the pointer moves on cycles with no grant, or past idle requesters. Then some requester ends up first more often than the others. Tying the update to the winner keeps the promise for any request pattern.

Lock the grant until the transfer ends, for example on a last signal. Update the mask only when the lock is released. Otherwise the arbiter may switch owners in the middle of a burst. The lock also means the worst-case wait now depends on the longest transfer.

Both give the same grants. The rotate form needs two barrel shifters, which grow with N times log N and add depth. The mask form uses two fixed-priority searches and a mux, which map well to fast carry-style logic. For small N either is fine; for large N the mask form is usually smaller and faster.

The lowest-bit search across 64 bits becomes the critical path. One option is a tree of small arbiters: eight groups of eight, with a round robin over the groups. Another is a pipelined arbiter that grants one cycle later. The tree changes fairness slightly, because each group gets an equal share regardless of how many requesters it has.

Fair in grants, not in bandwidth. Round robin gives each master one packet per turn, so the 8-beat master gets 8 of every 9 beats. If the goal is equal bandwidth, the arbiter must count beats, for example with deficit round robin or weights. Start by asking what "fair" means in the spec: grants, bandwidth, or a bounded latency.

Weighted round robin gives each master a fixed number of grants per round. It suits equal-size transfers, but long packets still skew the bandwidth. Deficit round robin gives each master a budget of beats per turn and carries any unused budget to the next turn. So bandwidth follows the weights even with mixed packet sizes, at the cost of a counter per master.

A waiting master is served before any other master gets a second turn. So it waits at most one turn for each of the other N - 1 masters. The bound in cycles is the sum of their longest transfers. That is why long bursts hurt everyone's worst-case latency, and why buses limit burst length.

Round robin cannot meet that, because one turn of the long master already lasts 256 cycles. Split long bursts into shorter ones at the master or the interconnect, or give the urgent master priority with a rate limit. Splitting costs some efficiency, because each burst pays its own address overhead.

Turn each goal into a measurable check. For starvation, assert that every request is granted within a bound. For bandwidth, measure each master's share over a window under saturating traffic. For latency, record the worst wait per master. Then cover the hard patterns: all masters busy, one master idle then sudden, and mixed burst sizes.

With only address bits, equal pointers mean either empty or full, and you cannot tell which. The extra bit tells whether the pointer has wrapped an odd or even number of times. Equal pointers, extra bit included, mean empty. Equal address bits with different extra bits mean the writer is one whole lap ahead: full. So all 8 entries are usable with no counter.

A level counter gives full, empty and the fill level directly, and it works for any depth. It costs a counter and an adder that updates on reads and writes. The extra bit costs one flop per pointer, but it needs a power-of-two depth. Only the extra-bit style carries over to an asynchronous FIFO, where no single counter can see both clocks.

The memory is written in the write domain and read in the read domain. Only the two pointers cross, each Gray-coded and through two flops. The write side compares its pointer with the synchronized read pointer to compute full. The read side compares the other way to compute empty. Each side sees the other pointer late, so a flag can stay on too long, but it is never wrongly off.

A late read pointer looks like fewer reads than really happened. So the write side thinks the FIFO is fuller than it is, and full may stay high a little too long. It never thinks there is space that is not there. The same reasoning makes empty late but safe on the read side.

Raise almost-full when the free space drops to the number of words the source can still send after the warning. Here that is 3, plus any cycles the flag itself takes to reach the source. In an asynchronous FIFO, the flag is already pessimistic, which adds a little margin at no extra cost.

Gray code changes one bit per step, so a value caught mid-change is either the old or the new one. It suits counters that move by one, such as FIFO pointers. A handshake holds any data stable while a synchronized request crosses and an acknowledge comes back. It carries any value, but takes several cycles per transfer. Choose Gray for streaming pointers, and a handshake or FIFO for occasional wide data.

Gray code assumes the bits arrive close together. If the wires of one pointer differ by more than about a clock period, two steps can mix. Logic between the Gray register and the synchronizer can glitch. And a Gray pointer that is computed but not registered can show several bits changing.

Start with structural analysis: define the clocks and their relationships. Then let the tool find every crossing and check that each has the right synchronizer for its type. Next comes protocol checking: each scheme's rules, such as hold times and Gray steps, become assertions in formal and simulation. Add reconvergence checks and reviewed waivers. Use metastability injection in simulation to expose designs that assume exact timing.

Combinational flags sit after a pointer compare, and the other block uses them in its own logic in the same cycle. That makes a long path across two blocks. Registered flags start that path at a flop. The cost is that you compute next-cycle flags from the next pointer values, which is easy to get wrong at the boundaries.

The address bits no longer wrap by themselves at the end of the memory. Each pointer must wrap by compare: back to 0 after 5. Then track full with a lap bit that flips on each wrap, or keep a level counter. Many teams just round up to 8 when the area allows.

The FIFO must hold the highest level reached during the burst. Count words written minus words read, cycle by cycle, and take the peak. Here 32 words go in and 14 come out during the burst, so the depth is 18. The run writes that count as a function, then simulates the traffic and sees a peak of 18 with no overflow.

A FIFO stores the difference between what came in and what went out. If the writer is faster on average, that difference grows without limit. A FIFO only absorbs bursts: periods of faster writing followed by idle time. For a steady rate mismatch you need backpressure, not depth.

Work in time, not cycles. The burst lasts 120 / 200 MHz = 600 ns. In that time the reader takes about 150 MHz x 600 ns = 90 words, so about 30 must be stored. In an asynchronous FIFO, add the synchronizer delay on the pointers. That is a few cycles in which the reader cannot see new data yet.

A FIFO sized for the worst burst never stalls the source, which matters when the source cannot wait, such as a sensor. Backpressure keeps the FIFO small, but the source must be able to pause, and throughput drops while it waits. Many designs use both: enough depth for normal bursts, and a ready or credit signal for the rest.

Start with the spec: depth and why, widths, and what happens on a write at full and a read at empty. Then name the corners: write at full, read at empty, both at the same edge, wrap-around, and reset with data inside. For each, say what the design does and which test or assertion proves it. Finish with what you would add next, such as formal checks on the flags.

It is a design choice, and the spec must state it. The simple rule refuses the write, because full was high before the edge. A more efficient rule accepts it, because the read frees a slot in the same cycle. The second rule makes full depend on rd_en, which can create a long path back into the reader.

With the usual rule, the read is refused, because empty was high before the edge, and the write goes in. The word comes out one cycle later. A first-word-fall-through design shows the new word on the output soon after. It still counts as read only when rd_en is high and the FIFO is not empty.

Assertions in the RTL check local rules every cycle: never full and empty together, and no pointer move on a refused write. They also go to formal tools. A scoreboard checks the data end to end: every word out equals the word in, in order. The two catch different bugs, so a solid FIFO has both.

In one clock domain, resetting both pointers empties the FIFO. The RAM contents can stay, because nothing reads them. In an asynchronous FIFO, each side resets in its own domain. For a few cycles, one side may see the other's old pointer. Hold both sides in reset together, or block traffic until both resets have released.