Cyclic Combinational Circuits [pdf](mriedel.ece.umn.edu)
mriedel.ece.umn.edu
Cyclic Combinational Circuits [pdf]
http://www.mriedel.ece.umn.edu/wiki/images/7/7a/Riedel_Cyclic_Combinational_Circuits.pdf
7 comments
I’ve implemented these types of circuits on a few designs many years ago (after reading one of Marc's first papers on the subject) and did get a noticeable resource reduction. The hard part was getting this through design review; I remember being mildly amused watching colleagues (unsuccessfully) attempt to prove that the circuits wouldn’t work.
Real world designs uses feedback ostensibly for things like registers, latches, flip-flop variations... the most simple maybe the SR-flip-flop in [1]. Making gates with transistors leads to real bi-stable circuits. A good design has a division between a state maintaining parts (say a register banks) and a purely combinatorial parts. I think Krohn-Rhodes Theory analyzes this situation. An automaton is seen as an open discrete dynamic (a state set acted by a semigroup of possible inputs), so "... an automaton A is emulated by a feed-forward cascade of a) automata whose transformation semigroups are finite simple groups and [generating all combinatorial stuff] b) automata that are banks of flip-flops running in parallel" [2]
[1] https://www.electronicshub.org/sr-flip-flop-design-with-nor-... [2] https://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory#De...
[1] https://www.electronicshub.org/sr-flip-flop-design-with-nor-... [2] https://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory#De...
These are called sequential circuits. The author describes the construction of cyclic purely combinational circuits. Afaik, they are interesting from a theoretical standpoint but not from an engineering one since most digital design is built on top of standard cells.
The first paragraph of the acknowledgements starts with this amusing one:
"It has been said that the better people are at understanding mathematics the worse they are at understanding human behavior. If so, then perhaps it was a compliment when I declared that my father – Prof. Ivo Rosenberg, a mathematician – would make the worst psychologist in the universe."
"It has been said that the better people are at understanding mathematics the worse they are at understanding human behavior. If so, then perhaps it was a compliment when I declared that my father – Prof. Ivo Rosenberg, a mathematician – would make the worst psychologist in the universe."
From the abstract:
> The accepted wisdom is that combinational circuits must have acyclic (i.e., loop-free or feed-forward) topologies. ... In this dissertation, we advocate the design of cyclic combinational circuits (i.e., circuits with loops or feedback paths). We demonstrate that circuits can be optimized effectively for area and for delay by introducing cycles.
> On the theoretical front, we discuss lower bounds and we show that certain cyclic circuits are one-half the size of the best possible equivalent acyclic implementations. On the practical front, we describe an efficient approach for analyzing cyclic circuits, and we provide a general framework for synthesizing such circuits. On trials with industry-accepted benchmark circuits, we obtained significant improvements in area and delay in nearly all cases.
Also: This was published in 2004.
> The accepted wisdom is that combinational circuits must have acyclic (i.e., loop-free or feed-forward) topologies. ... In this dissertation, we advocate the design of cyclic combinational circuits (i.e., circuits with loops or feedback paths). We demonstrate that circuits can be optimized effectively for area and for delay by introducing cycles.
> On the theoretical front, we discuss lower bounds and we show that certain cyclic circuits are one-half the size of the best possible equivalent acyclic implementations. On the practical front, we describe an efficient approach for analyzing cyclic circuits, and we provide a general framework for synthesizing such circuits. On trials with industry-accepted benchmark circuits, we obtained significant improvements in area and delay in nearly all cases.
Also: This was published in 2004.
[deleted]
I had the absolute privilege to study Circuit computation and biology course under Prof Marc Riedel at UMN and reading this brings back those memories.