Differences

This shows you the differences between two versions of the page.

--- asic:timing:forks [2024/02/02 11:34] – [Theory] rajit
+++ asic:timing:forks [2024/09/03 14:06] (current) – [Relative timing] rajit
@@ Line 8: / Line 8: @@
 A timing fork, then, relates three //nodes//: a root node ''R'', and two other nodes that we refer to as the fast node ''F'' and the slow node ''S'' for convenience, where there is a sequence of signal transitions that go from ''R'' to ''F'' and ''R'' to ''S'' (see the referenced paper for details).
+A particular node may or may not appear in a computation due to data-dependent behavior. So a timing fork only makes sense when all three nodes referred to in the fork in fact appear in a computation.
 When a circuit is operating, these nodes occur at certain times that are determined by gate delays. We know that the delay from ''R'' to ''F'' has some upper bound ''ub'' (from gate delays), and the delay from ''R'' to ''S'' has a lower bound ''lb'' (again from gate delays). So we can bound the time difference between ''F'' and ''S'' using ''lb-ub'', because they share a common timing reference point ''R''. In other words, we can write ''time(S) - time (F) >= (lb-ub)'', or equivalently ''time(S) >= time(F) + (lb-ub)''.
@@ Line 17: / Line 19: @@
 The key technical result about timing forks says that if two nodes are ordered in all possible computations and without errors occurring, then a sequence of such timing forks **must exist**, and the reason the nodes are ordered is through a combination of inequalities of the form shown above that together ensure that the nodes are ordered. (This is called a timing //zig-zag//.) In other words, the intuitive notion of a common timing reference point that is the basis for ordering signal transitions is in fact a requirement.
+===== Timing forks in ACT =====
+ACT provides syntax to refer to these nodes in a limited fashion. Instead of being able to specify nodes using all the information needed, we simply refer to nodes at the point when a signal changes. Furthermore, we always consider all possible occurrences of the signal change, rather than a specific one (e.g. the seventh occurrence of a signal change). As common timing forks can relate difference occurrence indices, we provide [[language:langs:spec#timing_constraints|syntax]] to refer to common scenarios in circuit design.
+===== Related concepts =====
+There are many closely related but slightly different notions that are used in the literature to
+describe timing constraints in a variety of circuit contexts.  Here we try and provide a simplified view of the differences and similarities between some common notions and timing forks.
+==== Setup and hold time ====
+In clocked design, a setup and hold time constraint for a state-holding element is used to ensure
+correct operation. We use positive edge-triggered flip-flops as the running example.
+The setup time constraint states that the data input to the flip-flop is stable for a certain time (the setup time) before the clock pin makes a zero-to-one transition. To see why this is also a timing fork constraint, we make the following observations:
+   * The only way to ensure that the setup time constraint is met is to //know// something about when the input to the flip-flop can change //with respect to// the clock pin of the same flip-flop.
+   * In synchronous logic, the built-in assumption is that this is possible because the input to the flip-flop is in the same clock domain as the flip-flop itself---in other words, comes from another set of flip-flops that share a common clock.
+   * The timing fork can be determined as follows. The common timing reference point is the common clock tree root that feeds the source flip-flops and the target flip-flop. The path from the clock root through the source flip-flop clock pins out through their data pins and combinational logic to the target flip-flop has a delay constraint relative to the path from the clock root to the clock pin of the target flip-flop.
+A similar argument can be made for hold time.
+==== Point-of-divergence constraint ====
+The delay from a common timing reference point via all possible circuit paths to two different signal transitions is sometimes referred to as a point-of-divergence constraint. Checking all possible paths through the circuit of this form is one possible way a timing fork constraint can be checked.
+However, note that an asynchronous circuit has cycles in the timing graph, so technically a point-of-divergence check would require checking an infinite number of paths.  So a point-of-divergence timing constraint makes much more sense when the timing graph is acyclic (as is the case in standard clocked circuits). Sometimes point-of-divergence constraints are used to check timing in an asynchronous circuit by explicitly cutting the cycles in the timing graph.
+Timing forks can be applied even when there are cycles in the timing graph because the nodes in the fork refer to specific occurrence indices of signal transitions. Hence, even though the timing graph is cyclic, the paths to be checked for a timing fork are bounded.
+==== Relative timing ====
+Relative timing is a methodology for designing asynchronous circuits where you can assume that
+two signal transitions are ordered due to timing. When you assume that ''a+'' occurs before ''b-'' for example,
+there is an implicit assumption that ''a+'' and ''b-'' occur, and the methodology is most commonly used to reason about control logic where this is a common scenario.
+Timing fork theory states that if the two transitions are guaranteed to be ordered, then a timing fork/zig-zag that is the basis for the ordering must exist.  In other words, a design that uses relative timing constraints can only be correct if a timing fork/zig-zag exists that ensures that the constraint is satisfied.
+It is worth noting that a timing fork doesn't //require// that all the transitions occur. This is useful when we have data-dependent timing constraints, i.e., where a signal change occurs only in certain cases based data values being computed by the circuit.