TDEB Top Bar

Trending
Semiconductor Industry News — The Digital Electronics Blog
Follow Us

TDEB Masthead

The Semiconductor Hub

Semiconductors.  Chips and Systems.  Innovation.

Indexed by leading Search Engines, AI and referenced by Engineers worldwide 500+ Articles 10M+ Pageviews 30+ Reports 50+ Citations

NVIDIA Interview Question: Pipelining Two Operations

Murugavel Ganesan
by
14
Share Facebook X LinkedIn WhatsApp Email

You are designing a circuit that implements two operations, A and B, as shown below. Operation A passes through three modules, f, g and h; operation B passes through two, k and l. Where you put registers decides the clock period, and the clock period decides how many cycles each operation takes. This NVIDIA interview question asks you to find the best balance.

Module delays from the figure: operation A: f = 40 ns, g = 20 ns, h = 50 ns. Operation B: k = 30 ns, l = 25 ns.

Notes:

  1. At any point in time the circuit is doing either A or B.
  2. Delays through modules of each operation are given in the figure.
  3. The circuit must have registers on all inputs. No registers are needed on the outputs.
  4. The delay through a register is 5 ns.
  5. Operation A occurs 70% of the time while operation B occurs 30% of the time.

What is the clock period that will result in the highest overall performance? And questions increasing in difficulty follow below.

What the question is really testing

It is a trade-off between a short clock and a small number of cycles. With no registers inside the logic, every operation finishes in one long cycle that must fit the slowest operation, so the fast operation B wastes most of its cycle. With registers between modules, the clock gets shorter, but A then needs several cycles, and every extra register adds its own 5 ns. Because A happens 70% of the time, the best answer is the one that makes the average operation fastest, not the one with the highest clock frequency.

This is the same reasoning a processor architect uses to choose between a single-cycle and a multi-cycle datapath, and it is why interviewers like it: it checks whether you measure performance as time per operation rather than as megahertz.

The short answer

Use a 65 ns clock. Put a register between g and h, so A runs as f plus g (40 + 20 + 5 = 65 ns) followed by h (50 + 5 = 55 ns), taking 2 cycles, and B runs as k plus l (30 + 25 + 5 = 60 ns) in 1 cycle. The average time per operation is 0.7 × 130 + 0.3 × 65 = 110.5 ns, against 115 ns for the unpipelined circuit and 144 ns or more for any faster clock.

How to attack questions like this

  1. Add up the delay of each operation and note the slowest single module: no clock can be shorter than that module plus one register.
  2. List the clock periods that are worth trying. Only the delays of possible stage groupings matter, so there are only a handful.
  3. For each period, count the cycles each operation needs, multiply by the period, and weight by how often the operation happens.
  4. Pick the smallest weighted average, then sanity-check the answer against the unpipelined design.

Deep dive: the numbers and details

This part holds the full table of clock periods, the general formula, variants with different register delays and operation mixes, and the overlapped (pipelined) case. Skip it if the short answer is all you need.

Stage delays

Each stage costs its logic delay plus the 5 ns register in front of it. Registers are required on the inputs, so every stage, including the first, pays the 5 ns.

Possible stageLogicStage delay with register
f g h (A unpipelined)110 ns115 ns
f g60 ns65 ns
g h70 ns75 ns
f40 ns45 ns
g20 ns25 ns
h50 ns55 ns
k l (B unpipelined)55 ns60 ns
k30 ns35 ns
l25 ns30 ns

Module h alone needs 55 ns, so no clock below 55 ns can work. Above that, only the periods 55, 60, 65, 75 and 115 ns change how many cycles an operation takes.

Every candidate clock period

The average time per operation is Tavg = Tclk × (0.7 × NA + 0.3 × NB), where NA and NB are the cycles each operation needs at that clock.

Clock periodA stagesNAB stagesNBA timeB timeAverage
55 nsf | g | h3k | l2165 ns110 ns148.5 ns
60 nsf | g | h3k l1180 ns60 ns144.0 ns
65 nsf g | h2k l1130 ns65 ns110.5 ns
75 nsf g | h or f | g h2k l1150 ns75 ns127.5 ns
115 nsf g h1k l1115 ns115 ns115.0 ns

The 65 ns design is about 4% faster than the unpipelined 115 ns design (110.5 against 115 ns per operation). The 60 ns clock looks attractive because it is the shortest that lets B finish in one cycle, but at 60 ns neither f plus g (65 ns) nor g plus h (75 ns) fits, so A needs three cycles and the average gets worse.

Harder question 1: when does the 60 ns clock win?

Let p be the fraction of operations that are A. Then Tavg(60) = 60 + 120p and Tavg(65) = 65 + 65p. The 60 ns clock is better when 60 + 120p < 65 + 65p, that is when p < 5/55, or about 9%. So the answer holds for almost any mix in which A is common; if A were rare (under about 9% of operations), the designer should optimize for B instead. A good candidate states this sensitivity without being asked.

Harder question 2: a faster register

With a 1 ns register instead of 5 ns, the candidate periods become 51, 56, 61, 71 and 111 ns. The averages are 137.7, 134.4, 103.7, 120.7 and 111 ns, so the same partition wins at 61 ns. Register overhead shifts the numbers but not the structure here. It would change the answer if it became large compared with the module delays, because each extra stage then costs more than it saves.

Harder question 3: what if operations can overlap?

Note 1 says the circuit does either A or B at any time, so the analysis above assumes one operation finishes before the next starts. If the design is allowed to start a new operation every cycle (a true pipeline), throughput becomes one operation per clock, and the shortest legal clock, 55 ns, gives the most operations per second: one every 55 ns instead of one every 110.5 ns. Latency then rises to 165 ns for A and 110 ns for B. The catch, and the follow-up interviewers ask, is that A takes 3 cycles and B takes 2, so an A started in one cycle and a B started in the next would both finish together. If they share an output, the control logic must stall one of them. Expect to be asked how you would detect and avoid that conflict.

The University of Pennsylvania course notes CIS 371 Unit 4: Performance and Multicycle (Roth and Martin, Spring 2009) work the processor version. Most instructions need 10 ns and multiplies need 40 ns, and multiplies are 10% of instructions. A single-cycle datapath needs a 40 ns clock, so every instruction takes 40 ns. A multi-cycle datapath with a 10 ns clock has an average CPI of 0.9 × 1 + 0.1 × 4 = 1.3, or 13 ns per instruction, about three times faster. The NVIDIA question is the same calculation with register overhead added and fewer candidate clocks.

Common mistakes

  • Maximizing frequency. The 55 ns clock is the fastest, and it gives the worst average of all.
  • Forgetting the input register. Every stage, including the first, pays the 5 ns.
  • Ignoring the mix. An unweighted average of A and B gives a different and wrong comparison.
  • Splitting modules. The figure treats f, g, h, k and l as indivisible; registers can only go between them.
  • Assuming overlap. Read note 1 carefully: unless the question allows overlapping operations, throughput equals one divided by the time per operation.

For the timing equations behind "logic plus register overhead must fit the clock", see David Harris's CMOS VLSI Design lecture 10: Sequential Circuits (Harvey Mudd College, 2004), where the overhead is setup time plus clock-to-Q delay.

Further reading

Murugavel Ganesan
About the Author
Murugavel Ganesan
Product Director | SerDes · IVN · Edge AI · Compute | Ex Intel · Infineon

A semiconductor product leader working across product architecture, definition, strategy, and silicon and software execution, from concept through volume production. He has worked with teams across Asia, Europe and the USA, including at Intel, Infineon and ArrayComm.

His work covers ASICs, SoCs, FPGAs and chiplets for wireless, wireline, automotive, IoT and AI, including PCIe, CXL and DDR interfaces alongside RF and mixed-signal design.

Share Facebook X LinkedIn WhatsApp Email

Post a Comment

14 Comments

Your comments will be moderated before it appears here.

  1. Assuming the internal modules cannot be further pipelined, the clock would have to be greater than 50 + 5 = 55 ns. This is assuming registers are put in between all the internal modules.
    I don't see the relevance of the 70-30 division, as we have to take the critical path into account. What am I missing?

    ReplyDelete
  2. Higher the frequency, higher will be the performance. But we need to check what is the minimum delay being taken by any unit in the design. All "input registers" are taking a delay for "5 ns". So the system clock should be designed taking this into consideration. Other informations are irrelevant.

    ReplyDelete
  3. As there is no delay needed at output so 5ns register delay will not come in picture. Because within the 20ns+5ns period the processing unit "G" can put the correct data into the unit "h" so the clock period will be 50ns and not 50ns + 5ns.
    Also, looking from other angle. if 50ns is the period all the internal pipeline units (f,g,k) can put the data properly in next unit (g,h,l respectively) for the pipeline to function perfectly. If there is a output delay requirement from our critical path unit (i.e. h) then that delay will add up into the clock period.

    ReplyDelete
  4. I think it should be 50ns, not 55.

    ReplyDelete
  5. Answer wud be 35 ns
    for detail solution mail me
    mr.saurabh.srivastava@gmail.com

    ReplyDelete
  6. It should be 55ns ( 50+5)

    ReplyDelete
  7. Ok Ok
    Guys lets cross check
    By 55 clock period (denoted by C5)
    scheduling would be
    Stages - 45(40+5) 25(20+5) 55(50+5)
    C5 will take 3 cycle ok
    Stage 35 , 25 (for operation B)
    C5 will take 2 clock cycle
    Total average time
    55*(0.7*3+0.3*2)= 148.5

    Now C3 clock with 35 period
    Operation A 5 clock
    Operation B 2 clock
    Total average time
    35*(0.7*5+0.3*2)= 143.5

    Clear now

    ReplyDelete
  8. Yes, but with 35ns clock, the register at g input will never receive the output from f before the next clock tick. The clock period has to be sufficient to accommodate for the maximum combinational path delay in the pipe stages and the setup/hold time of the register. The delays in each module are a clear indication that they are combinational and cannot be split further. I agree with Mk's answer. the register setup time will be added to the previous stage's delay. Also, nothing has been said about the output of h. So if we assume the output to be left as a combinational one (not connected to any FF), then the clock period will be 45ns. Although this will cause a warning during par.

    ReplyDelete
  9. As #8 said, the clock period can't be < 45 or else you'll lose the value at g. The latency is shortest per operation if tclk >= 115 ns, but the throughput suffers. The throughput is best if you use the shortest allowable clock, which in this case is 45 since you don't have to register the outputs. If you want to optimize for the best latency/throughput compromise, you'd need to know what the questioner means by "overall performance".

    ReplyDelete
  10. The answer is either:
    45 ns, due to f()+reg
    or:
    5 ns, the gcd of all times present, where we have to use additional logic to decide when to sample and when not.

    If we are allowed 35 ns, for k()+reg, using 2 cycles at f() and h(), the percentages will be interesting, else not, but then again, 5 ns is even better, like perfect ;-)

    ReplyDelete
  11. SaurabhS, I agree with your argument, but the correct answer is 30ns. If you go by the same logic, 30ns gives you 30*(6*0.7+4*0.3)=132ns per instruction on an average.

    ReplyDelete
  12. The answer will be 55ns. The minimum clock period for correct functioning of the circuit is given by:
    tclk >= t(clk-Q) + tlogic(max) + tsetup
    here t(clk-Q) is the delay of the output to appear at the output (Q) of the pipeline register, tlogic(max) is the maximum delay in the circuit implementing the logic (remember it is not the minimum time because we have to consider the worst case logic delay in order to guarantee correct functionality) and tsetup is the time before the next clock edge that the data to be latched has to be stable. Here as there is no output register in the last module of operation A, the optimum tclk = 5ns(t(clk-Q)) + 50ns(tlogic(max)) = 55ns

    ReplyDelete
Post a Comment

#buttons=(Ok, Go it!) #days=(20)

Our website uses cookies to enhance your experience. Learn more
Ok, Go it!