## Cyclic Combinational Circuits

March 7, 2008

As one of my strange hobbies, I sometimes try to search the web for interesting PHD thesis works. I came across this one a while back and thought it would be interesting to share.

We always hear how bad combinational cyclic loops are. Design Compiler even generates a reports to help us detect them. In the normal ASIC flow combinational loops are very dangerous, hard to analyze and characterize for timing. But here comes this Dissertation work by Marc Riedel and highlights a special set of cyclic combinational circuits which offer several important advantages.

I will try to explain the basic principle by going through an example, but make sure to read his PHD thesis, it is well written and easily understood.

As an example we will look at the very simple case depicted below:

Notice that it has 5 inputs: X, Y0, Y1, Y2, Y3 and has 6 outputs f0..f5. Notice also the symmetry or duality between the AND/OR gates which have the X input connected into them. The basic principle being, that if X = “0” the cycle will be broken at the top AND gate and if X = “1”, the cycle would be broken in the middle OR gate. This in turn will “create” two “different” circuits depending on the value of X. In essence we have physically a combinational loop BUT we guarantee that whatever value X has, this loop will be logically broken!

Both cases are shown below.

If we factor in X into the equations we get the following dependencies for all the outputs on all the inputs.

The above example is one of the simplest of all and was just presented to show the principle. In this specific circuit you could also short Y0 and Y2, Y1 and Y3 and get a 3 input circuit where each of the inputs has the same behavior as X in the example (shown in page 12 in the PDF file of the thesis).

The thesis goes on to show how such circuits can be used with different advantages. The thesis is bears the date May 2004 – I hope that significant advances have been made in this area in the last 4 years. This idea is too beautiful to just let it accumulate dust or being discarded by the CAD industry…

Advertisements

### 2 comments

1. Hi,
I am also a sufferer of the same cause since last 2 years. We have designed a CPU which 2 combinational loops which are physically present but not functionally. Now, since Design Compiler(C) doesn’t support such loops, it has given lot of nightmares to us.
The problems which we faced were how to optimize such timing paths as DC is going to break these loops at its will, and can deteriorate some valid paths.
We tried to break these loops manually by declaring ‘set_disable_timing’ and then tried to put ‘set_max_delay’ on both side of timing arcs.

It would be useful for me to share other peoples experiences.

-Deepak
(deepak.baranwal@gmail.com)

2. Hi,
i think that this work got the best paper award at DAC’03.
http://www2.dac.com/40th/pbest.html
However, i haven’t seen any tool support since then…

Pavlos