Cyclic Combinational Circuits: Analysis for Synthesis
Marc D. Riedel and Jehoshua Bruck

Proceedings of the International Workshop on Logic and Synthesis, Laguna Beach, CA, 2003


Digital circuits are called combinational if they are memoryless: they have outputs that depend only on the current values of the inputs. Combinational circuits are generally thought f as acyclic (i.e., feed-forward) structures. And yet, cyclic circuits can be combinational. In previous work, we showed that introducing cycles permits optimizations of area. We proposed a general methodology for the synthesis of multilevel networks with cyclic topologies and incorporated it in a logic synthesis environment. In trials, benchmark circuits were optimized significantly, with improvements of up to 30% in the area.

In this paper, we discuss the role of combinationality analysis in the context of synthesis. We present a symbolic framework for analysis based on a first-cut strategy. Unlike previous approaches, our method does not require ternary-valued simulation. It is formulated recursively, and thus it permits us to cache analysis results for common sub-networks through iterations of the synthesis process. We also discuss timing analysis of cyclic combinational circuits.

View Paper (PDF)

View Presentation (PowerPoint)