NVIDIA Pipeline Interview Question: Total Time for 100 Parcels

This NVIDIA pipeline interview question asks how long 100 input parcels take to pass through a two-stage pipeline whose first stage runs operation A or B (with different delays) and whose second stage runs operation C in two clock cycles. With the 60 ns clock period from the earlier question, stage 2 is the bottleneck at one parcel every two cycles, so 100 parcels take 201 or 202 cycles: about 12.1 microseconds. Re-choosing the clock period for the pipeline as a whole cuts this to about 10.4 microseconds, and both calculations are worked below.

Key takeaways

• Total time = time for the first parcel to fill the pipeline + (number of parcels minus 1) x the interval between results.
• With registers only at stage inputs, a stage that needs two cycles can accept a new parcel only every two cycles; it becomes the bottleneck.
• At T = 60 ns: 100 parcels take L1 + 200 cycles, where L1 is 1 or 2 cycles for the first parcel, so 12,060 ns or 12,120 ns.
• At T = 115/3 = 38.3 ns (still a two-cycle operation C), exactly 70 A and 30 B parcels take 272 cycles, about 10,427 ns.
• The best clock period for one stage on its own is not always the best for the whole pipeline.

The question

Circuit below, which implements operation C, has been designed such that it has two modules i and j, with the delays shown in the given figure below. The latency for circuit b is 2 and the delay through a register is 5ns. Assume that circuits a and b are stages of a pipeline as shown in the figure below.

NOTES:

1. The pipeline has 2 stages where the first stage of the pipeline contains circuit a (executing operation A or B) and the second stage of the pipeline contains circuit b (executing operation C).
2. Stage 2 reads the output of stage 1 as soon as it is available even if the two operations of stage 1 (i.e. A and B) have imbalanced latencies.
3. The pipeline has registers only on the inputs of the stages.
4. The performance and cost overhead due to control circuitry (e.g. Mux) is not considered in this preliminary analysis.

Based on your analysis in the earlier post, what is the total time required to execute 100 input parcels sent through the pipeline?

What the earlier question established

The earlier NVIDIA clock period question defined circuit a: operation A is modules f (40 ns), g (20 ns) and h (50 ns) in series; operation B is k (30 ns) and l (25 ns). Registers sit only on the inputs and cost 5 ns. A occurs 70% of the time and B 30%. So:

Operation	Logic delay	+ register	Total
A (stage 1)	40 + 20 + 50 = 110 ns	5 ns	115 ns
B (stage 1)	30 + 25 = 55 ns	5 ns	60 ns
C (stage 2)	30 + 40 = 70 ns	5 ns	75 ns

Each operation is a multi-cycle path: it takes ceil(total / T) cycles. For circuit a alone, the average time per operation is 0.7 x (cycles for A) x T + 0.3 x (cycles for B) x T. Among clock periods that keep both operations to one or two cycles, the best is T = 60 ns: A takes 2 cycles (120 ns), B takes 1 cycle (60 ns), and the average is 0.7 x 120 + 0.3 x 60 = 102 ns, compared with 115 ns for a 115 ns clock. At T = 60 ns, operation C (75 ns) takes 2 cycles, which matches "the latency for circuit b is 2".

Worked answer at T = 60 ns

Step 1: cycles per stage

• Stage 1: 2 cycles for A, 1 cycle for B.
• Stage 2: 2 cycles for every parcel.

Step 2: find the bottleneck

Because there are registers only on stage inputs, stage 2 holds one parcel for its full 2 cycles before it can take the next. Stage 1 never needs more than 2 cycles, so it always has the next result ready in time. One result therefore leaves the pipeline every 2 cycles (120 ns). When stage 1 finishes a B in one cycle, it simply waits for stage 2.

Step 3: trace the first few parcels

Example order A, B, A, A (cycle numbers are clock edges, starting at 0):

Parcel	Op	Stage 1 starts	Stage 1 result ready	Stage 2 starts	Result out
1	A	0	2	2	4
2	B	2	3	4 (waits for stage 2)	6
3	A	4	6	6	8
4	A	6	8	8	10

The pattern is: first result after L1 + 2 cycles, then one result every 2 cycles.

Step 4: total for 100 parcels

Total cycles = L1 (first parcel) + 2 x 100.

• First parcel is A: 2 + 200 = 202 cycles = 202 x 60 = 12,120 ns
• First parcel is B: 1 + 200 = 201 cycles = 201 x 60 = 12,060 ns
• Expected value with a 70/30 mix: 201.7 cycles, about 12,102 ns (12.1 microseconds)

For comparison, without pipelining (each parcel goes through A or B and then C before the next starts), the average is 1.7 + 2 = 3.7 cycles per parcel, or 370 cycles (22,200 ns) for 100 parcels. Pipelining gives about 1.8 times the throughput.

Can a different clock period do better?

Yes. At 60 ns, stage 2 wastes 45 ns of every 120 ns window (it needs 75 ns). The general rule for this pipeline is that the interval between results is max(L1, L2) cycles for each parcel, so the total is the first parcel's L1 + the sum of max(L1, 2) over the remaining 99 parcels + 2. Trying every period that keeps operation C at 2 cycles (37.5 ns to 75 ns) and assuming exactly 70 A and 30 B parcels:

Clock period	Cycles A / B / C	Average interval	Total for 100 parcels
60 ns	2 / 1 / 2	120 ns	12,060 to 12,120 ns
57.5 ns	2 / 2 / 2	115 ns	11,615 ns
40 ns	3 / 2 / 2	108 ns	10,880 ns
38.33 ns (115/3)	3 / 2 / 2	103.5 ns	10,427 ns
37.5 ns	4 / 2 / 2	127.5 ns	12,825 ns

At 38.33 ns stage 1 becomes the bottleneck (3 cycles for A), and the total is 70 x 3 + 30 x 2 + 2 = 272 cycles, about 10.4 microseconds, roughly 14% faster than at 60 ns. The lesson for the interview: the period that is best for circuit a alone (60 ns) is not the best once circuit b shares the clock.

How interviewers extend this question

• "Add a register between modules i and j." At 60 ns, i (35 ns with its register) and j (45 ns) each fit in one cycle, so stage 2 can accept a parcel every cycle and stage 1 becomes the bottleneck.
• "What is the latency of a single parcel?" At 60 ns: 4 cycles (240 ns) for A and 3 cycles (180 ns) for B.
• "Now cut the power." That is the NVIDIA power reduction question for a two-stage image pipeline and its four-stage branching extension.
• "What did you ignore?" Mux delay, clock skew, setup time and control logic, all excluded by note 4.

Mistakes to avoid

• Multiplying 100 by the stage 1 average (102 ns). The pipeline rate is set by the slower stage, not by stage 1 alone.
• Assuming stage 2 can accept a parcel every cycle. With registers only on stage inputs, a two-cycle stage is busy for both cycles.
• Forgetting the fill time of the first parcel.
• Forgetting the 5 ns register delay when counting cycles.

For a related retiming example with numbers, see the pipelining interview question on latency and throughput. Short definitions are in the Semiconductor Hub glossary entry on pipelining.

Related NVIDIA interview questions

• NVIDIA true or false questions on simulation, timing, power and test
• NVIDIA clock period question for two operations with different delays
• NVIDIA power question extended to a branching four-stage pipeline

Frequently asked questions

How do you calculate the total time for N items through a pipeline?

Total time = latency of the first item + (N minus 1) x the interval between results. The interval is set by the slowest stage, measured in whole clock cycles.

What limits throughput when stages have different latencies?

The stage that holds each item longest. If it is not internally pipelined, it accepts a new item only when it has finished the previous one.

Why does a faster clock not always help?

Operations take a whole number of cycles. A period that is slightly too short for an operation adds a full extra cycle, as at 37.5 ns where A jumps from 3 to 4 cycles.

What is a multi-cycle path?

A register-to-register path allowed more than one clock period, here because each operation runs for several cycles between input registers. Timing tools need a multicycle path constraint for it.