G5.1.1 Find the Critical Path

EasyImplementIcarus · browser samples / server checksReview the topic

Add gate delays along every path of a seven-gate circuit and find the slowest path. It is not the one with the most gates.

Hardware context: A status flag and a two-output control block made of timed gates in a motor controller. Find the critical path of a seven-gate circuit and its delay.

A status flag in a motor controller is made of seven gates. The team wants to know how long the flag takes to settle after any input changes, so they can pick the clock. One engineer added up all seven delays. Another counted the gates on the longest path. Both got it wrong.

This is an Implement problem with no logic to write. Work out each answer by hand and write it into the answer module as a constant. The first three constants are worked examples and are already correct.

The check compares every constant with the right value and names the first one that is wrong.

Signals in the Timeline

SignalWidthRole
question8input of each check
Full specification
The circuit. Each gate lists its output first, then its inputs
// Seven gates, each with its own delay in ns (#2 is 2 ns).
module crit (input wire a, b, c, d, e, output wire y);
  wire n1, n2, n3, n4, n5, n6;
  nand #2 g1 (n1, a, b);
  not  #1 g2 (n2, c);
  nor  #3 g3 (n3, n1, n2);
  xor  #6 g4 (n4, d, e);
  nand #2 g5 (n5, n3, b);
  and  #3 g6 (n6, n4, c);
  or   #2 g7 (y, n5, n6);
endmodule
ConstantWhat to write
PATH_B_G5_G7The delay of the path b, g5, g7 in ns (2 + 2).
PATH_C_G6_G7The delay of the path c, g6, g7 in ns (3 + 2).
PATHS_FROM_BHow many different paths lead from b to y (through g1 and through g5).
TPD_YThe propagation delay of the circuit: the delay of its critical path, in ns.
CRIT_GATESHow many gates the critical path passes through.
LONGEST_FROM_AThe longest delay from a change on a to y, in ns.
LONGEST_FROM_CThe longest delay from a change on c to y, in ns.
MISS_BYY must settle within 10 ns of any input change: by how many ns does the circuit miss that.

A path starts at an input and follows wires through gates to y. Its delay is the sum of the delays of the gates on it. Wires take no time here.

Write each answer as a whole number in place of the 0. Keep the module name and the constant names.

Examples

Example 1

Worked Example: One Path
Input
the delay of the path b, g5, g7 in ns (2 + 2)
Output
path_b_g5_g7 = 4

The path from b through g5 to g7 passes two gates. Add their delays: 2 ns and 2 ns make 4 ns. This constant is already filled in.

Example 2

Worked Example: Another Path
Input
the delay of the path c, g6, g7 in ns (3 + 2)
Output
path_c_g6_g7 = 5

From c, one branch goes straight into g6 and then g7: 3 ns and 2 ns make 5 ns. This constant is already filled in.

Example 3

Worked Example: Count the Paths
Input
how many different paths lead from b to y (through g1 and through g5)
Output
paths_from_b = 2

The input b feeds two gates, g1 and g5, so two paths leave it. This constant is already filled in.

Constraints and Contract

  • Keep the module name answer and the names of the constants.
  • Every answer is a whole number of nanoseconds or a count.

Hints

Hint 1

Draw the circuit first: inputs on the left, y on the right. Then list every path from each input to y.

Hint 2

An input that feeds two gates starts two paths. Follow both. A gate with a large delay can make a short path slow.

Hint 3

The critical path is the path with the largest total delay, whatever its number of gates. Compare the totals, not the gate counts.

What the grader checks: The check reads eight constants and compares each with a value computed from the netlist. It cannot see how a value was found. Gate delays here are fixed numbers; real gate delays depend on load and input slope.

8 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

Worked Example: One Path

Input
the delay of the path b, g5, g7 in ns (2 + 2)
Expected output
path_b_g5_g7 = 4

The path from b through g5 to g7 passes two gates. Add their delays: 2 ns and 2 ns make 4 ns. This constant is already filled in.

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

Icarus · browser samples / server checks