Your manager has given you the task of implementing the following pseudo code in an FPGA:
if is_odd(a + d) {
p = (a + d)*2 + ((b + c) - 1)/4;
} else {
p = (b + c)*2 + d;
}
Notes:
- You must use registers on all input and output ports.
- p, a, b, c and d are to be implemented as 8-bit signed signals.
- A 2-input 8-bit ALU that supports both addition and subtraction takes 1 clock cycle.
- A 2-input 8-bit multiplier or divider takes 4 clock cycles.
- A small amount of additional circuitry (for example a NOT gate, an AND gate or a MUX) can be squeezed into the same clock cycle(s) as an ALU operation, multiply or divide.
- You can require that the environment provides the inputs in any order and that it holds the input signals at the same value for multiple clock cycles.
Questions:
- What is the minimum number of clock cycles needed to implement the pseudo code with a circuit that has two input ports?
- What is the minimum number of ALUs, multipliers and dividers needed to achieve the minimum number of clock cycles that you just calculated?
- What is the minimum number of datapath storage registers (8, 6, 4 and 1 bit) and clock cycles needed to implement the pseudo code if the circuit can have at most one ALU, one multiplier and one divider?
Good luck!
How to approach it
This is a classic high-level synthesis question: turn an algorithm into a schedule of operations on shared hardware. The trick is to look at every operation before you count cycles, because several of them are much cheaper than they appear.
- Multiply by 2 and divide by 4 are not real multiplies or divides. They are shifts by a constant, which in hardware are just wiring. No multiplier or divider is needed at all.
- is_odd(a + d) does not need the sum. The least significant bit of a + d is a[0] XOR d[0]. One XOR gate gives the branch condition as soon as a and d are available.
- Only one branch needs to be computed. Since the condition is known early, the hardware can compute just the branch that is taken, or compute parts of both and select the result with a multiplexer.
- Two input ports means four inputs take two cycles to arrive. The order in which you ask for them matters.
After those observations the problem is a handful of additions, and the answers follow from drawing a dependency graph and scheduling it.
The short answers
Under the assumptions set out in the deep dive (inputs b and c first, an operation can start in the cycle after its operands are registered):
- Three cycles of computation after the first pair of inputs is registered.
- Two ALUs, no multipliers and no dividers.
- Four computation cycles with one ALU, using one 8-bit register and one 6-bit register for intermediate values, plus a 1-bit register for the branch condition if the a and d inputs are not held.
Course conventions differ on whether the input and output register cycles are counted, so state your convention clearly in an interview. The reasoning matters more than the number.
Deep dive: the schedule, the hardware and the bit widths
This part works through the dependency graph, the cycle-by-cycle schedule and the register sizing. Skip it if the short answers are all you need.
The operations
| Name | Operation | Hardware | Needs |
|---|---|---|---|
| s1 | a + d | ALU | a, d |
| s2 | b + c | ALU | b, c |
| t | s2 - 1 | ALU | s2 |
| odd | a[0] XOR d[0] | One gate | a, d |
| p1 | (s1 << 1) + (t >>> 2) | ALU, shifts are wiring | s1, t |
| p2 | (s2 << 1) + d | ALU | s2, d |
| p | odd ? p1 : p2 | MUX | odd, p1, p2 |
The odd branch has the longest chain: s2, then t, then p1, three ALU operations in series. The even branch is only two: s2, then p2.
Question 1: minimum cycles with two input ports
Read b and c first, because they sit at the start of the longest chain. Number the clock edges from 0, where edge 0 registers the first pair of inputs.
| Cycle (between edges) | Input registers hold | ALU 1 | ALU 2 |
|---|---|---|---|
| 1 (edge 0 to 1) | b, c | s2 = b + c | idle |
| 2 (edge 1 to 2) | a, d | t = s2 - 1 | s1 = a + d |
| 3 (edge 2 to 3) | a, d (held) | p1 = (s1 << 1) + (t >>> 2), or p2 = (s2 << 1) + d | idle |
The output register loads p at edge 3. A lower bound confirms this is the minimum: a and d cannot both be available before edge 1 if b and c come first, and the odd branch then needs two more ALU levels after a and d arrive (s1, then p1). Reading a and d first is worse, because the three-step chain through b + c would then start a cycle later. So the answer is three cycles of computation, or four if you also count the cycle that registers the first inputs.
Question 2: minimum hardware for that schedule
Cycle 2 needs two additions at once (t and s1), so at least two ALUs. No cycle needs more than two. The even branch p2 is computed in cycle 3 on the same ALU as p1, with a multiplexer on the ALU inputs selected by the odd bit, which is allowed as "small additional circuitry". Because the constant multiply and divide are shifts, the answer is zero multipliers and zero dividers. Using the 4-cycle multiplier and divider would only make the design slower.
Question 3: one ALU, minimum registers and cycles
The odd branch needs four ALU operations (s2, t, s1, p1), so with one ALU it needs at least four cycles. One schedule:
| Cycle | ALU operation | Result stored in |
|---|---|---|
| 1 | s2 = b + c | R8 (8-bit) |
| 2 | odd: t = s2 - 1, stored already shifted as t >>> 2. Even: p2 = (s2 << 1) + d | R6 (6-bit), or R8 for p2 |
| 3 | odd: s1 = a + d | R8 (s2 is no longer needed) |
| 4 | odd: p1 = (R8 << 1) + sign-extended R6 | Output register |
Why 6 bits: an 8-bit signed value shifted right by two has only 6 significant bits; the top two bits of the result are copies of the sign, so they can be regenerated by sign extension when R6 is read. Storing t pre-shifted saves two flip-flops. The single 8-bit register is reused for s2 and then s1, because s2 is dead once t has been computed.
Register count: one 8-bit and one 6-bit datapath register. If the environment holds a and d on the input registers (allowed by the notes), the branch condition can be recomputed from a[0] XOR d[0] whenever needed; otherwise add a 1-bit register for it. For a fixed-latency design the even branch simply waits until cycle 4 to write its result.
The signed-arithmetic detail interviewers like
- Divide by 4 and rounding. An arithmetic shift right (>>> 2) rounds toward minus infinity. Integer division in C and many HDL simulators rounds toward zero. For x = -5, x >>> 2 = -2, but -5 / 4 = -1. To match truncation, add 3 before shifting when x is negative, which costs another addition, or agree with your manager that floor rounding is acceptable.
- Overflow. With 8-bit signed values, a + d can range from -256 to 254, which does not fit in 8 bits, and (a + d) x 2 is larger still. The question specifies 8-bit signals, so results wrap. Mention it and ask whether wider internal signals are allowed.
- is_odd for negative numbers. In two's complement the least significant bit gives oddness for negative values too: -3 is 1111 1101, LSB 1.
Worked check with numbers
Take a = 3, d = 4, b = 10, c = 7. a + d = 7 is odd. s2 = 17, t = 16, t >>> 2 = 4, s1 = 7, s1 << 1 = 14, so p = 14 + 4 = 18. Software check: (3 + 4) x 2 + (17 - 1) / 4 = 14 + 4 = 18.
Now take a = 2 so that a + d = 6 is even: p = (b + c) x 2 + d = 34 + 4 = 38. The hardware computes p2 = (17 << 1) + 4 = 38.
Related practice
For another interview question that combines logic sizing with timing, see the FSM interview question on ROM size, state count and timing.


Your comments will be moderated before it appears here.