Convert combinational loops into latches

Question

Can you recommend an algorithm that convert any cyclic combinational logic into an acyclic combinational logic plus latches? Thank you

Answer 1

This is a rather open-ended question and can be a very hard problem in its general form. This is more of a CAD problem and has little to do with Verilog. Just creating an acyclic combinational logic graph from a cyclic combinational logic graph is easy: find a cycle and break it by inserting a latch. Continue until there is no cycles left.

However, you should also define some sort of functional correctness and equivalence and preserve it after the conversion. By adding latches to the circuit you are changing the relative timing of signals (aka synchronous distance) and the resulting graph may be functionally different than the original graph.

A classic algorithm called retiming tries to move latches that already exist to satisfy/minimize the clock cycle time.

A sketch of algorithm that I can think which preserve the synchronous distance is the following: add n latches at primary inputs and run an enhanced retiming algorithm in which you add extra constraints to preserve the synchronous distance of equal-distance nodes from the primary inputs. These nodes are the inputs of combinational gates and primary outputs. For example, the sequential distance of two inputs a and b of an AND gate should always remain the same from all primary inputs, i.e. in the path from each input i to a you should see the same number of latches that you would see from i to b.

With these added constraints retiming would tell you if it can move the latches to satisfy the clock-cycle time (which in this case can be a very large number, i.e. bigger than your longest cycle). If n is enough, retiming algorithm should be able to put the latches to break all the cycles. You can iterate the algorithm on different values of n to get an answer.