h1

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:

cyclic_combinational1.png

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.

cyclic_combinational2.png

cyclic_combinational3.png

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

cyclic_combinational4.png

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



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: