G3.8.2 Factor to Save Gates, Keep the Delay

MediumOptimizeIcarus · browser samples / server checksReview the topic

Factor a request chain of two-input cells to at most seven cells. Every output change must still arrive within four gate delays.

Hardware context: A lamp function built from two-input unit-delay cells, flat and factored. Factor a bus request chain to seven cells within four gate delays.

Four requesters share a bus. Requester 3 wins outright. Each lower requester k is passed on only when the enables of every stage above it are 1. So the bus is busy when y = r3 + e3 r2 + e3 e2 r1 + e3 e2 e1 r0.

The cell library has two-input cells only, each with one gate delay. The starter is the flat sum of products. It is correct and meets the delay, but it uses eight cells.

This is an Optimize problem. Use at most seven cells, and keep every output change within four gate delays of any input change. Factoring saves cells, but factoring too far makes a slow chain.

Signals in the Timeline

SignalWidthRole
block8input of each check
Full specification
The module (keep the name and the ports)
module chain (input wire r3, e3, r2, e2, r1, e1, r0, output wire y);
  // your netlist
endmodule
cells.sv: the cell library (read-only). Ports are (y, inputs...): output first
// cells.sv: the unit-delay cell library (read-only).
// Every cell takes 1 time unit, whatever its fan-in. Ports are (y, inputs...): output first.
// Each cell adds 1 to the bench's cell counter when the simulation starts.
module INV   (output wire y, input wire a);                 not #1 (y, a);               initial tb.cells++; endmodule
module AND2  (output wire y, input wire a, b);              and #1 (y, a, b);            initial tb.cells++; endmodule
module OR2   (output wire y, input wire a, b);              or #1 (y, a, b);             initial tb.cells++; endmodule
module NAND2 (output wire y, input wire a, b);              nand #1 (y, a, b);           initial tb.cells++; endmodule
module NOR2  (output wire y, input wire a, b);              nor #1 (y, a, b);            initial tb.cells++; endmodule

RuleDetail
Functiony = r3 + e3 r2 + e3 e2 r1 + e3 e2 e1 r0 on all 128 input rows.
CellsFrom 6 to 7 instances of the library cells. Fewer than 6 cannot read all seven inputs.
DelayAfter any single input change, y stops changing within 4 gate delays.
Gate delayEvery cell takes one gate delay.
NetsDeclare each internal net as a wire. Connect by position, output first.

Each case applies a block of eight input rows and reads y on each. From each row it changes every input alone and times y. The result shows the eight values of y and the gate delays over the budget. A last check counts the cells.

Examples

Example 1

Rows 120 to 127
Input
rows 1111000 to 1111111 (order r3 e3 r2 e2 r1 e1 r0)
Output
y_row0 = 1, y_row1 = 1, y_row2 = 1, y_row3 = 1, y_row4 = 1, y_row5 = 1, y_row6 = 1, y_row7 = 1, gate_delays_over_budget = 0

Here r3 = e3 = r2 = e2 = 1, and only r1, e1 and r0 vary. y is 1 on all eight rows.

Example 2

Rows 16 to 23
Input
rows 0010000 to 0010111 (order r3 e3 r2 e2 r1 e1 r0)
Output
y_row0 = 0, y_row1 = 0, y_row2 = 0, y_row3 = 0, y_row4 = 0, y_row5 = 0, y_row6 = 0, y_row7 = 0, gate_delays_over_budget = 0

Here r3 = 0, e3 = 0 and r2 = 1. Without e3, nothing below requester 3 reaches y.

Example 3

Rows 72 to 79
Input
rows 1001000 to 1001111 (order r3 e3 r2 e2 r1 e1 r0)
Output
y_row0 = 1, y_row1 = 1, y_row2 = 1, y_row3 = 1, y_row4 = 1, y_row5 = 1, y_row6 = 1, y_row7 = 1, gate_delays_over_budget = 0

Here r3 = 1 again; every row of the block gives y = 1.

Constraints and Contract

  • Inputs are known 0/1 values. Each input change is held for 10 ns before y is read or timed.
  • Keep the module name and the ports. Use only cell instances.

Hints

Hint 1

Count the starter: five AND cells and three OR cells. Every AND that only feeds the OR tree is a place to factor.

Hint 2

Factoring everything gives r3 + e3(r2 + e2(r1 + e1 r0)): six cells, but each level waits for the one below. Count its levels.

Hint 3

Split the chain in two halves and join them once. The high half is r3 + e3 r2, the low half is r1 + e1 r0, and e3 e2 joins them.

What the grader checks: Sixteen blocks of eight rows cover all 128 input rows. From every row, every input is changed alone and the last change of y is timed. The worst time is compared with 4 gate delays. Every cell takes one time unit, so this measures the structure, not a real delay. The cell count must be 6 or 7. The judge accepts only library cell instances connected by plain nets.

17 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 3 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Rows 120 to 127

Input
rows 1111000 to 1111111 (order r3 e3 r2 e2 r1 e1 r0)
Expected output
y_row0 = 1, y_row1 = 1, y_row2 = 1, y_row3 = 1, y_row4 = 1, y_row5 = 1, y_row6 = 1, y_row7 = 1, gate_delays_over_budget = 0

Here r3 = e3 = r2 = e2 = 1, and only r1, e1 and r0 vary. y is 1 on all eight rows.

Run samples executes all 3 public checks. Check all tests runs 17 checks on the server.

Icarus · browser samples / server checks