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:
- At any point in time the circuit is doing either A or B.
- Delays through modules of each operation are given in the figure.
- The circuit must have registers on all inputs. No registers are needed on the outputs.
- The delay through a register is 5 ns.
- 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
- Add up the delay of each operation and note the slowest single module: no clock can be shorter than that module plus one register.
- List the clock periods that are worth trying. Only the delays of possible stage groupings matter, so there are only a handful.
- For each period, count the cycles each operation needs, multiply by the period, and weight by how often the operation happens.
- 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 stage | Logic | Stage delay with register |
|---|---|---|
| f g h (A unpipelined) | 110 ns | 115 ns |
| f g | 60 ns | 65 ns |
| g h | 70 ns | 75 ns |
| f | 40 ns | 45 ns |
| g | 20 ns | 25 ns |
| h | 50 ns | 55 ns |
| k l (B unpipelined) | 55 ns | 60 ns |
| k | 30 ns | 35 ns |
| l | 25 ns | 30 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 period | A stages | NA | B stages | NB | A time | B time | Average |
|---|---|---|---|---|---|---|---|
| 55 ns | f | g | h | 3 | k | l | 2 | 165 ns | 110 ns | 148.5 ns |
| 60 ns | f | g | h | 3 | k l | 1 | 180 ns | 60 ns | 144.0 ns |
| 65 ns | f g | h | 2 | k l | 1 | 130 ns | 65 ns | 110.5 ns |
| 75 ns | f g | h or f | g h | 2 | k l | 1 | 150 ns | 75 ns | 127.5 ns |
| 115 ns | f g h | 1 | k l | 1 | 115 ns | 115 ns | 115.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 same trade-off in a processor
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
- A. Roth and M. Martin, CIS 371 Unit 4: Performance and Multicycle (University of Pennsylvania, Spring 2009): the single-cycle versus multi-cycle example and the CPU performance equation.
- David Harris, CMOS VLSI Design lecture 10: Sequential Circuits (Harvey Mudd College, 2004): sequencing overhead of flip-flops and latches.


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.
ReplyDeleteI don't see the relevance of the 70-30 division, as we have to take the critical path into account. What am I missing?
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.
ReplyDeleteAs 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.
ReplyDeleteAlso, 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.
I think it should be 50ns, not 55.
ReplyDeleteAnswer wud be 35 ns
ReplyDeletefor detail solution mail me
mr.saurabh.srivastava@gmail.com
It should be 55ns ( 50+5)
ReplyDeleteOk Ok
ReplyDeleteGuys 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
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.
ReplyDeleteanswer is 45
ReplyDeleteGreat!
ReplyDeleteAs #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".
ReplyDeleteThe answer is either:
ReplyDelete45 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 ;-)
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.
ReplyDeleteThe answer will be 55ns. The minimum clock period for correct functioning of the circuit is given by:
ReplyDeletetclk >= 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