**Unformatted text preview:**

Main PageDAC'03Front MatterTable of ContentsAuthor IndexMaking Cyclic Circuits AcyclicStephen A. Edwards∗Columbia University, Department of Computer ScienceNew York, NY [email protected] circuits that do not hold state or oscillate are often the mostconvenient representation for certain functions, such as arbiters,and can easily be produced inadvertently in high-level synthesis,yet are troublesome for most circuit analysis tools.This paper presents an algorithm that generates an acyclic circuitthat computes the same function as a given cyclic circuit for thoseinputs where the cyclic circuit does not oscillate or hold state. Thealgorithm identifies all patterns on inputs and internal nodes thatlead to acyclic evaluation orders for the cyclic circuit, which arerepresented as acyclic circuit fragments, then combines these toproduce an acyclic circuit that can exhibit all of these behaviors.Experimental results suggest this potentially exponential algo-rithm is practical for small circuits and may be improved to han-dle larger circuits. This algorithm should make dealing with cycliccombinational circuits nearly as easy as dealing with their acycliccounterparts.Categories and Subject DescriptorsB.6.3 [Logic Design]: Design AidsGeneral TermsCyclic Circuits, Resynthesis, Acyclic circuits, Constructiveness1. INTRODUCTIONThe algorithm presented in this paper takes a cyclic circuit thatneither oscillates nor holds state for certain inputs and builds asmall acyclic circuit that computes the same function for these in-puts. Cyclic circuits are minimal representations for certain func-tions [5, 7, 8] and can be produced by high-level synthesis tools [1,13]. Yet many circuit analysis tools simply prohibit cyclic circuits.This paper uses a definition due to Malik [6]: a circuit is com-binational for a particular input vector if three-valued simulationof the circuit starting with all internal nodes set to X resolves the∗The author is supported by the NSF under CCR–0133348, theSRC, Ne w York’s MDC, and Intel Corporation.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.DAC 2003, June 2–6, 2003, Anaheim, California, USA.Copyright 2003 ACM 1-58113-688-9/03/0006 ...$5.00.output of ev ery gate in the circuit to either 0 or 1. For example, theoutput of every gate in circuit in Fig. 1a resolves to 0 or 1 wheninput x is 0 or when input z is 0, as suggested by the truth table inFig. 1b. Otherwise, some of the gates output an X.This definition is attractive because it is mathematically strong(0, 1, and X comprise a Scott domain and three-valued simulationcomputes the unique least fixed point of the circuit) and abstractsa physical model: Shiple et al. [9, 12] show that a circuit is stableunder Malik’s definition if and only if it stabilizes in a unique wayunder every delay assignment in Brzozowski and Seger’s [4] up-bounded inertial delay model. For these reasons, Berry adopted itas the semantics for his synchronous language Esterel [2].The two-stage algorithm in this paper builds an acyclic circuitthat reproduces a cyclic circuit’s combinational behavior. The al-gorithm first looks for a small collection of sets of assignmentsto inputs and internal nodes that produce all combinational be-havior. The main insight (Theorem 1) is that it only necessary toconsider applying controlling values to the inputs of each strongly-connected group of gates in the circuit. In the second stage, theacyclic circuit fragments implied by each set of assignments aremerged using a heuristic to produce an equivalent acyclic circuitwith a minimal number of gates. Identifying all patterns can be ex-ponential in the size of the circuit, but the number of patterns isoften quite small. Determining how to merge the acyclic fragmentsto produce the smallest circuit appears to be NP-complete, so aquadratic heuristic is used.Below is a simple example. The contrived cyclic circuit on theleft behaves combinationally unless both inputs are 1, as illustratedby the truth table. The algorithm generates the acyclic circuit on theright, which reproduces only the non-oscillatory behavior.arqbabqr00110101101011XXbqarThe algorithm only reproduces the behavior of combinational in-put patterns and implicitly assumes that all others are not of inter-est. Determining whether a circuit with state-holding elements canever reach a state with non-combinational behavior can be diffi-cult. Shiple et al. [10, 11] use BDDs to calculate the reachable statespace of a cyclic circuit containing flip-flops to determine whetherany state produces non-combinational behavior. Toma [14] imple-mented this algorithm in the Esterel V5 compiler to check whetheran apparently cyclic program could ever deadlock. If not, Toma’salgorithm builds an equivalent acyclic circuit from the BDDs.The remaining sections of this paper present how the algorithmworks on the example in Fig. 1, describe the algorithm in detail,present some experimental results, and come to some conclusions.15910.4a bcdexyzxyz ab c d e0 −− 01¬yz¬y ∧ z−− 001¬y 00101XX 1 X X111XXXX X(a) (b)a bcdex = 0yz01a bcdexy = 0z1a bcdexyz = 00100(c) (d) (e)a bcdeabcxyza bcdedeyxz(f) (g)ceyzea0b1cd(h)Figure 1: An example. (a) A cyclic circuit and (b) its truth ta-ble generated by three-valued simulation. The algorithm firstplaces controlling values on inputs x, y,andz, producing twoacyclic fragments (c,e), and a cyclic one (d) that does not leadto any new fragments. Fragments (c) and (e) can be merged intwo ways (f,g). (g) is smaller, and can be further reduced bysetting the (unlabeled) don’t-care inputs to 0, producing (h).By construction, this much smaller circuit computes the samefunction as the circuit in (a) when the gate outputs are not X.2. AN EXAMPLEFig. 1 shows how the algorithm works on a simple circuit. It firstdetermines when (i.e., under what input conditions) the circuit iscombinational, which amounts to asking which input v alues pro-duce completely-defined gate outputs or equiv alently, which breakthe strong connectivity. The following theorem is the key to an-swering this efficiently.THEOREM 1. For