G4.6.2 A 16-Bit Adder on a Delay Budget

HardOptimizeIcarus · browser samples / server checksReview the topic

Build a 16-bit adder from unit-delay cells whose outputs settle within 8 gate delays of any input change.

Hardware context: A 4-bit adder for a timer block, built from unit-delay cells. Look ahead twice, over bits and over blocks, to fit a 16-bit adder in eight gate delays.

A signal processor adds two 16-bit samples in every cycle. The cycle leaves room for 8 gate delays. The ripple-carry adder in the starter is correct, but its worst carry needs 33.

This is an Optimize problem. Rewrite add16 as a netlist of cells from the read-only library. After any input change, every output must stop changing within 8 gate delays. The cell count must be from 60 to 180.

Lesson G4.6 shows lookahead for the block carries, which reaches 15. Look ahead one more level.

Signals in the Timeline

SignalWidthRole
gate_delays32stimulus, the same for every design
longest_path32stimulus, the same for every design
Full specification
The module (keep the name and the ports)
module add16 (
  input  logic [15:0] a,
  input  logic [15:0] b,
  input  logic        ci,
  output wire  [15:0] s,
  output wire         co
);
  // your netlist
endmodule
cells.sv: the cell library (read-only). Ports are (y, inputs...): the output comes first
// cells.sv: the unit-delay cell library (read-only), with a path mode for the bench.
// 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.
// In path mode (tb.trace_paths = 1) the output is x until every input is known, then 1, one unit later.
module INV (output wire y, input wire a);
  wire f, k;
  not #1 (f, a);
  assign #1 k = (^{a} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module AND2 (output wire y, input wire a, b);
  wire f, k;
  and #1 (f, a, b);
  assign #1 k = (^{a, b} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module AND3 (output wire y, input wire a, b, c);
  wire f, k;
  and #1 (f, a, b, c);
  assign #1 k = (^{a, b, c} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module AND4 (output wire y, input wire a, b, c, d);
  wire f, k;
  and #1 (f, a, b, c, d);
  assign #1 k = (^{a, b, c, d} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module AND5 (output wire y, input wire a, b, c, d, e);
  wire f, k;
  and #1 (f, a, b, c, d, e);
  assign #1 k = (^{a, b, c, d, e} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module OR2 (output wire y, input wire a, b);
  wire f, k;
  or #1 (f, a, b);
  assign #1 k = (^{a, b} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module OR3 (output wire y, input wire a, b, c);
  wire f, k;
  or #1 (f, a, b, c);
  assign #1 k = (^{a, b, c} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module OR4 (output wire y, input wire a, b, c, d);
  wire f, k;
  or #1 (f, a, b, c, d);
  assign #1 k = (^{a, b, c, d} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module OR5 (output wire y, input wire a, b, c, d, e);
  wire f, k;
  or #1 (f, a, b, c, d, e);
  assign #1 k = (^{a, b, c, d, e} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module NAND2 (output wire y, input wire a, b);
  wire f, k;
  nand #1 (f, a, b);
  assign #1 k = (^{a, b} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module NOR2 (output wire y, input wire a, b);
  wire f, k;
  nor #1 (f, a, b);
  assign #1 k = (^{a, b} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module XOR2 (output wire y, input wire a, b);
  wire f, k;
  xor #1 (f, a, b);
  assign #1 k = (^{a, b} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule
module XNOR2 (output wire y, input wire a, b);
  wire f, k;
  xnor #1 (f, a, b);
  assign #1 k = (^{a, b} === 1'bx) ? 1'bx : 1'b1;
  assign y = tb.trace_paths ? k : f;
  initial tb.cells++;
endmodule

RuleDetail
Function{co, s} = a + b + ci for every input.
Delay budgetThe longest path of cells from any input to any output is at most 8 cells. So after any input change, s and co settle within 8 gate delays.
Gate delayOne cell, of any size, takes one time unit. The widest cells have five inputs.
CellsOnly instances of the library cells, from 60 to 180 of them. Constants 1'b0 and 1'b1 may drive an input.

Each case sets a starting input and makes four input changes. The result shows {co, s} after each change, in hex. It shows how far the slowest change was over the budget, and whether the cell count is out of range.

Last, the bench switches the library to path mode and measures the longest path. A slow path that only rare inputs use still counts.

Examples

Example 1

The Carry in Crosses All Sixteen Bits
Input
start at ffff + 0000 + 0; then ffff + 0000 + 1, ffff + 0000 + 0, ffff + 0000 + 1, ffff + 0000 + 0
Output
sum_change1 = 0x10000, sum_change2 = 0xffff, sum_change3 = 0x10000, sum_change4 = 0xffff, gate_delays_over_budget = 0, cell_count_out_of_range = no, longest_path_over_budget = 0

With a = ffff, each change of ci flips every sum bit and the carry out. The ripple starter needs 32 gate delays here.

Example 2

Bit 0 Starts a Carry That Crosses Every Bit
Input
start at fffe + 0000 + 1; then ffff + 0000 + 1, fffe + 0000 + 1, ffff + 0001 + 0, ffff + 0000 + 0
Output
sum_change1 = 0x10000, sum_change2 = 0xffff, sum_change3 = 0x10000, sum_change4 = 0xffff, gate_delays_over_budget = 0, cell_count_out_of_range = no, longest_path_over_budget = 0

A change of a0 adds one more level: p0 has to change before any carry can. This is the slowest change for most designs.

Example 3

A Carry Born in Each Block
Input
start at 00f0 + 0010 + 0; then 0ff0 + 0010 + 0, ff00 + 0100 + 0, f000 + 1000 + 0, fff0 + 0010 + 0
Output
sum_change1 = 0x1000, sum_change2 = 0x10000, sum_change3 = 0x10000, sum_change4 = 0x10000, gate_delays_over_budget = 0, cell_count_out_of_range = no, longest_path_over_budget = 0

Each change makes a new carry in a different block, which must reach the top bits.

Constraints and Contract

  • Inputs are known 0/1 values. Each input change is held for 40 ns before the outputs are read.
  • Keep the module name and the ports. Use single bits or constant part-selects in cell ports; no operators.

Hints

Hint 1

Split the adder into four 4-bit blocks. For each block, compute the block propagate P (an AND of four p) and the block generate G.

Hint 2

Treat each block as one wide bit. The block carries c4, c8, c12 and co follow the 4-bit lookahead equations, with P and G for p and g.

Hint 3

Inside each block, write the three inner carries from p, g and the block's carry in, not from each other. Count the levels: p and g, G, block carry, inner carry, sum.

What the grader checks: Seven directed and twelve seeded scripts each make four input changes. The sum is compared with a + b + ci computed in JavaScript. The time of the last output change is compared with the budget of 8 gate delays. The directed changes start carries at bit 0 and in every block. Then the path mode of the library measures the longest input-to-output path, which bounds every possible change, not only these. The model ignores fan-out and wires.

19 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 2 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

The Carry in Crosses All Sixteen Bits

Input
start at ffff + 0000 + 0; then ffff + 0000 + 1, ffff + 0000 + 0, ffff + 0000 + 1, ffff + 0000 + 0
Expected output
sum_change1 = 0x10000, sum_change2 = 0xffff, sum_change3 = 0x10000, sum_change4 = 0xffff, gate_delays_over_budget = 0, cell_count_out_of_range = no, longest_path_over_budget = 0

With a = ffff, each change of ci flips every sum bit and the carry out. The ripple starter needs 32 gate delays here.

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

Icarus · browser samples / server checks