Technology mapping for speed-independent circuits: Decomposition and resynthesis

Technology Mapping for Speed-Independent Circuits: Decomposition and Resynthesis Alex Kondratyev, The University of Aizu, Japan Jordi Cortadella, Univ. Politecnica de Catalunya, Barcelona, Spain* Michael Kishinevsky, The University of Aizu, Japan Lucian0 Lavagno, Politecnico di Torino, Italy t Alex Yakovlev, University of Newcastle upon Tyne, United Kingdom ! Abstract This paper presents theory and practical implementation of a method for multi-level logic synthesis of speedindependent circuits. An initial circuit implementation is assumed to satisfy the monotonous cover conditions but is technology independent. The proposed method pedorms both combinational {inserting new gates) and sequential {inserting new memory elements) decomposition of complex gates in a given standard cell library, while preserving original behaviour and speed-independence. The algorithm applies known eficient algebraic factorization techniques from combinational multi-level logic synthesis, but achieves also boolean simplification and sequential decomposition. The method allows sharing of decomposed logic. 1 Introduction Speed-independent circuits, originating from D.E. Muller’s work [ 111, are hazard-free under the unbounded gate delay model. With recent progress in developing efficient analysis and synthesis techniques, supported by CAD tools, this sub-class has moved closer to practice, bearing in mind the advantages of speed-independent designs, such as their greater temporal robustness and self-checking properties. Existing methods of logic synthesis for speedindependent circuits either assume that the implementation library contains and gates with unbounded fanin and “free” input inversions ([1,5,9]) or they use non-standard ‘‘hazard absorbing” flip-flops whose effectiveness inpractice still needs to be evaluated ([ 141). Other results on the implementability of semi-modular circuits without inputs using two-input/two-output and and or gates ([HI) are only interesting from a theoretical standpoint, due to their extremely high implementation cost. In attempts to map speed-independent circuits into a more realistic, standard cell-like, library, other sort of re- ‘This work has been partly supported by the Ministry of Education of Spain (CICYT TIC 95-0419), ACD-WG (ESPRIT21949) and integrated action UK -1995-0203. his work has been partly supported by MURST research project “VLSI architectures”. Work supported by UK EPSRC GRn24038, ACiD-WG (ESPRIT 21949) and British Council integratedaction Spain (MDR/1996/97/1159) strictions have been exercised. For example, the approach described in [16] works only under thefundamental mode assumption, which is overly restrictive and does not fit well theoretically with the unbounded delay assumption. The same authors describe in [15] a method to perform technology mapping for speed-independent circuits that only decomposes existing gates (e.g., a 3-input AND into two 2-inputANDs), without any further search of the implementation space. They do not explore complex decompositions, that could use multi-cube divisors, or decompose several gates simultaneously. The same limitations also affect the work of [l, 21. The idea of complete resynthesis of a circuit every time a new signal is inserted is exploited in [12] for the technology mapping of timed asynchronous circuits. However the search space for decomposition is again limited by a single signal network. In [13] a method for technology mapping of speedindependent circuits using complex gates was presented. This method however only identifies when a set of simple logic gates can be implemented as a complex gate, but cannot perform a speed-independent decomposition of a signal function in case it does not fit into a single gate. In fact, this method can be used as a post-optimization step after our proposed decomposition technique. Finally, Bums analyzes [4] the correctness conditions for a decomposition of a sequential element that is part of a speed-independent circuit into two sequential elements (or a sequential and a combinational element). Notably, these conditions are analyzed using the original (unexpanded) behavioural model, thus helping the efficiency of the method. This work is, in our opinion, a big step in the right direction, but addresses mainly correctness issues. It does not describe how to use the efficient correctness checks in an optimization loop, and does not allow the sharing of a decomposed gate by different signal networks. The idea of combinational logic decomposition with resynthesis has been proposed in [8,7]. The approach combines together efficient algebraic factorization techniques used in multi-level combinational logic synthesis (finding candidates for decomposition), and speed-independence preserving signal insertion (the latter idea originated in [ 171 and was implemented efficiently in [6]). The main contribution of this paper is a generalisation and extension of the above basic idea so as to cover both combinational and sequential decomposition. We have 0-8186-7922-0/97 $10.00 0 1997 IEEE 240 developed a body of theory that allows us to prune the search space when looking for solutions. We continue to use classical logic synthesis techniques available for combinational multi-level logic in order to fiid good candidate functions for the decomposition. In the case of combinational decomposition the newly inserted signal is a library gate. The insertion of a combinational gate is based primarily on one of the two transitions of the gate's output (e.g., its rising transition). The other transition of the combinational gate is fully determined by the insertion place of the first transition. A sequential decomposition, based on a new memory element, can improve the progress of mapping by rendering the opposite transition a more effective role, since the set and reset logic are inserted independently. In particular, two boolean functions can be decomposed at the same time with one new signal. Thus, in comparison with [4], this method: e targets the search of the solution towards a given e allows logic sharing based on multiple acknowledg0 performs global optimization via resynthesis (rather Throughout the paper we use the following notation: library; ments; than sequential decomposition). A stands for the original State Graph, A' -- for a new State Graph obtained by signal insertion. a, b, c, . . . (lower case Latin letters) are used for signal names and, corresponding to them, literals in Boolean functions. 2 - always denotes a new signal, which is inserted in State Graph A to decompose a non-implementable function. B, C, F, P, Q, R, . . . (upper case Latin letters, except A) stand for the names of Boolean functions. 2 Theoretical background In this section we introduce theoretical concepts required for our decomposition method: (1) circuit specification and its logic implementability; (2) conditions for speedindependent decomposition of complex gates; and (3) transformations of state graphs to ensure those conditions. 2.1 State Graphs and Logic Implementability A State Graph (SG) is a labeled directed graph whose nodes arc called states. Each arc of an SG is labeled with an event, that is a rising (a+) or falling (a-) transition of a signal a in the specified circuit. We also allow notation a* if we are not specific about the direction of the signal transition. Each state is labeled with a vector of signal values. An SG is consistent if its state labeling v : S --f (0, is such that: in every transition sequence from the initial state, rising and falling transitions altemate for each signal. Figure 1,b shows the SG for the Signal Transition Graph in Figure l,a, which is consistent, We write s Z (s 5 s') if there is an arc from state s (to state s') labeled with a. a+ Za,d - inputs acdz r--l o001Figure 1: An example of State Transition Graph (a) and State Graph (b) (benchmark hazard.g) The set of all signals whose transitions label SG arcs are partitioned into a (possibly empty) set of inputs, which come from the environment, and a set of outputs or state signals that must be implemented. In addition to consistency, the following two properties of a SG are needed for their implementability in a speed-independent logic circuit. The first property is speedindependence. It consists of three constituents: determinism, commutativity and outputpersistency. A SG is called deterministic if for each state s and each label a there can be at most one state s' such that s ---f s'. A SG is called commutative if whenever two transitions can be executed from some state in any order, then their execution always leads to the same state, regardless of the order. An event U* is called persistent in state s if it is enabled at s and remains enabled in any other state reachable from s by firing another event b*. A SG is called output-persistent if its output signal events are persistent in all states. Any transformation (e.g., insertion of new signals for decomposition), if performed at the SG level, may affect all three properties. The second property, Complete State Coding (CSC), becomes necessary and sufficient for the existence of a logic circuit implementation. A consistent SG satisfies the CSC property if for every pair of states s,s' such that v(s) = v(s'), the set of output events enabled in both states is the same. (The SG in Figure 1 ,b is output-persistent and has CSC.) CSC does not however restrict the type of logic function implementing each signal. It requires that each signal is cast into a single atomic gate. The complexity of such a gate can however go beyond that provided in a concrete library or technology. 2.2 Gate-level implementability without hazards Necessary and sufficient conditions for speedindependent implementation using unbounded fanin and gates (with unlimited input inversions), bounded fanin or gates and C elements were given in [ 1,9]. In this work we are considering a similar basic implementation architecture, called the standard-C architecture, which is described in Figure 2. The difference from previous work is that 24 1 instead of unbounded fanin gates for the set and reset logic of C-elements, we will allow only implementable gates, that is the gates which exist in the chosen library. Figure 2: The standard-C architecture extended for complex gates The concepts of excitation and quiescent regions are essential for that. A set of states is called an excitation region (ER) for event a* (denoted by ERj(a*)) if it is a maximal connected set of states such that Vs E E Rj (a*) : s 5. Since any event a* can have several separated ERs, an index j is used for the distinction between different connected occurrences of a* in the SG. The quiescent region (QR) (denoted by QRj(a*)) of a transition a*, with excitation region ERj(a*), is a maximal set of states s reachable from ERj(a*) such that a is stable in s and s is not reachable from any other ERk(a*) such that k # j without going through ERj (a*) '. Examples of ER and QR are shown in Figure 1,b. Let Cj(a*) denote one of the first-level AND-OR gates in the standard-C architecture. Cj(a*) is a correct monotonous poly-term cove? for the excitation region ERj(a*) if the following three conditions are satisfied: 1. Cover condition: Cj(a*) covers all states of ERj(a*) (i.e., Cj(a*) evaluates to 1 in all states of ERj(a*)). 2, One-hot condition: Cj(a*) does not cover any state outside ERj(a*) U QRj(u*). 3. Monotonicity condition: Cj(a*) changes at most once The conditions above are called the Monotonous Cover conditions or shortly the MC-conditions. Since under these conditions the outputs of the first-level gates are one-hot along any state sequence within QRj(a*). 'Note that contrary to [9, 11 in this paper we use only the so-called restricted quiescent regions which do not include states reachable directly from two different excitationregions of the same signal. *Here for simplicity we consider the definition of Monotonous Cover without the extension by the so-called backward quiescent regions and without considering covering of multiple regions by the same cover. However all the results can be easily generalized for this extension as well. encoded any valid Boolean decomposition of the secondlevel or gates is speed-independent. The standard-C architecture permits a combinational implementation of a signal. If the set and reset networks are the complements of each other, then a C-element with identical inputs can be simplified to a wire (see Figure 2,b,c). In such case we say that the signal has a complete cover, 2.3 Property-preserving event insertion Our decomposition method is essentially behavioural -- the extraction of new signals at the structural (logic) level must be matched by an insertion of their transitions at the behavioural (SG) level. Event insertion is an operation on a SG which selects a subset of states, splits each of them into two states and creates, on the basis of these new states, an excitation region for a new event. Figure 3 shows the chosen insertion scheme, analogous to that used by most authors in the area [17]. Figure 3: Event insertion scheme: (a) before insertion, (b) after insertion State signal insertion must preserve the speedindependence of the original specification. An inserted signal is denoted by x in this paper. The corresponding to it events are denoted x*, x+, x-, or, if no confusion occurs, simply by 2. Let A be a SG and A' is a state graph obtained by insertion of event x. We say that an insertion state set ER(x), in a SG A is a speed-independence preserving set (SIP-set) iff: (1) for each event a in A, if a is persistent in A, then it remains persistent in A', and (2) A' is deterministic and commutative. The formal conditions for the set of states r to be a SIP-set can be given in terms of intersections of r with the so-called state diamonds of SG [6]. These conditions are illustrated by Figure 4, where all possible cases of the illegal intersections of r with state diamonds are shown. It was shown in [6] that the insertion of a signal by means of a SIP-set is a necessary and sufficient condition to preserve the speed-independence of a corresponding SG. This requirement is the most general one in the synthesis of speed-independent circuits and it does not restrict the solution space unless we go beyond the speed-independent class. An efficient method for finding SIP-sets, which is based on regions, has been proposed in [6]. The first method for finding SIP-sets based on reduction to satisfiability problem was proposed in [ 171. Assume that the set of states S in a SG is partitioned into two subsets which are to be encoded by means of an additional signal. This new signal can be added either in order to satisfy the CSC condition, or to break up a complex gate into a set of smaller gates. In the latter case, a new signal represents the output of the intermediate gate added to the circuit. Let r and 7 = S - r denote the blocks of such a partition. For implementing such a partition we 242 Figure 4: Possible violations of SIP conditions need to insert transitions of the new signals in the border states between T and V. In this paper we shall consider the so-called input border of a partition block T, denoted by IB(T), which is informally a subset of states of T by which T is entered. We call IB(r) wellformed if there are no arcs leading from states in T - IB(T) to states in IB(T). If a new signal is inserted using an input border, which is not well-formed, then the consistency property is violated. Therefore, if an input border is not well-formed, its well-formed speedindependent preserving closure is constructed, as described by Algorithm 4.1 in Section 4. The insertion of a new signal can be formalized with the notion of I-partition ([17] used a similar defmition). Given a SG, A, with a set of states S, an I-partition is a partition of S into four blocks: {S+, S', S-, So}. So(S') defines the states in which z will have the stable value 0 (1). S+(S-) defines ER(z+) (ER(%-)) in the new SG A'. Therefore, abusing notation we will often refer to S+(S-) as to ER(s+) (ER(z-)) when talking about states of the original SG A or, if confusion may arise, we write ERA(z+) (ERA(z-)). If the insertion of z preserves consistency and persistency, then the only transitions crossing boundaries of the blocks are the following: so --+ s+ -+ s' t st so. 3 Decomposition techniques We assume here familiarity with multi-level logic synthesis (see [3] for more details). As described in the previous section, any deterministic, commutative, output-persistent SG satisfying the CSC and the Monotonous Cover conditions can be implemented using the standard-C architecture. We assume that Celements are present in the library '. OR-gates combining cover functions C( a*) can be decomposed by any standard technique since their inputs are one-hot encoded. Hence the bottleneck for technology mapping is the implementation of cover functions C(a*) using gates available in the library. As traditionally done in multi-level combinational synthesis, we have chosen algebraic division as the main operation for logic decomposition. Thus, for each cover function C( a*) we seek algebraic divisors, aiming at decompositions of the following ty C(a*) = F * G + R where G is the quotient C(a*)F! AND-decomposition 31n fact our technique works and is implemented also for RSand Dlatches. However, this generalization of the method is omitted due to the lack of space. i complex gate! I Figure 5: Cover function C(a*) (a) and its combinational (b) and sequential (c) decompositions is done when R = 0, whereas OR decomposition occurs when G = 1. However, contrary to the classical combinational decomposition we use divisor F not for immediate extraction, but as a first approximation of the function to be extracted. More specifically, function F defies one (sequential decomposition) or two (combinational decomposition) blocks of a partition of the state space, which is later used for new signal insertion (see Sections 4 and 5 for more details). Two ways of decomposing C(a*) are possible: 0 combinational decomposition: a divisor F is implemented by a combinational gate, z, as shown in Figure 5,b and 0 sequential decomposition: an additional latch (e.g., C-element) implements signal z; divisor F is used as one of the input functions for the latch as shown in Figure 5,c. Another function (denoted by P in the figure) must be extracted from some other cover function. Functions F and P form the set and reset functions for the new sequential signal z. In our decomposition technique transitions of z are acknowledged by several cover functions. This is more general and powerful than [lS, 41 where transitions of s must be acknowledged locally, only by the cover function C(a*) from which z is extracted. Multiple acknowledgment offers two advantages: (1) the same signal z can be shared by several cover functions (this corresponds to the extraction of common sub-dividers in classical multi-level decomposition) and (2) correct speed-independent decomposition can be found even if it does not exist for solutions with single acknowledgments (see the experimental results). Note that we do not specifically search for multiple acknowledgments. They appear automatically due to the signal insertion technique based on SIP-sets. Hence our solution is correct by construction and contrary to [2] never requires iterations with verification procedures. To find good divisors F for C(a*) the following functions are considered: 0 Kernels and co-kernels of C(a*). 243 0 If C(a*) is a poly-term cover, any subset of terms of the sum-of-product expression (OR-decomposition). 0 If C(a*) is one cube, any subset of literals of the cube (AND-decomposition). 0 Recursive decomposition of the previous candidates, e.g. sub-kemels and AND/OR-decomposition of kernels. This generation of divisors is heuristically pruned to avoid an explosion of candidates for functions with many terms or cubes with many literals. Experimental results (Section 6) have shown this type of decomposition to be very effective. In particular, only those decompositions are considered that: (1) preserve speed-independence and (2) guarantee progress in mapping the circuit to the given library. The first condition is satisfied by finding an I-partition for signal IC. Many candidates for decomposition are filtered out at this step, since for many divisors there are no valid I-partitions. To clarify the second condition assume that function F is extracted from a cover function C( a*) for combinational decomposition (see Figure 5,b). If there is a valid I-partition for a new signal 2, then there is a speed-independent implementation for the circuit with signal IC. However, in general, there is no guarantee that function C(a*) is simplified in the new circuit. The substitution of 5 for F in C(a*) does not always preserve s ed-independence and hence new fan-in signals for CG) can appear in the implementation. Thus, the progress condition checks whether a substitution of IC instead of F in C( a*) is valid. Since multiple acknowledgment of 5 can appear, the requirement for “good decomposition” is following: the complexity of all (other than C(a*)) functions in 5’s fan-out has to remain the same or to increase very moderately. In Section 4.3 we present a computationally efficient method for the estimation of effective decompositions. The overall algorithm for logic decomposition is sketched below. The next sections describe each step in more detail. Algorithm 3.1 (Speed-independent decomposition) while circuit is not mapped to the libmy do Calculate monotonous covers for all events; Let a* be the event with the most complex cover; Let D, be a set of divisors for C(a*); /* Kemels, co-kernels, AND/OR decomposition */ Let &be a set of divisors for the most complex cover functions other than C(a*); for each F E D, do Decomposition(F, F) ; /* Check combinational decomposition for F */ for each P E &do Decomposition(F, P) /* Check sequential decomposition for the pair { F, P} */ end for end for if All decompositions fail then else return; /* Cover C(a*) cannot be decomposed */ Choose the best decomposition ({F, F} or {F, P}); Insert a new signal /* by an I-partition defined by the best decomposition */ end if end while Decomposition(F, P); Find I-partition for the pair { F, P}; if not exists then return failure; Evaluate progress for decomposition of C(a*); /*(proposition 4.1) */ if no progress then return failure; Estimate progress for all other covers; /* (property 4.5) */ if implementability is disturbed then return failure Note that after each cycle, when a successful decomposition is found, the implementation of every signal in the circuit is recomputed for the best candidate. Since at the recomputation step the new don’t care sets are used for all signals, this practically implements sequential decomposition and boolean division (i.e., it is far beyond the capabilities of algebraic factorization). a a z z Figure 6: Circuits for a hazard.g example before (a) and after (b) decomposition Example hazardg. This example (from the set of asynchronous benchmarks) is used for illustrating our algorithm. Its Signal Transition Graph and SG are shown in Figure l,a and b. Signals a and d are inputs, signals c and z -- outputs. A speed-independent implementation of the output signals c and z is presented in Figure 6,a. Our target is the decomposition of function S, into two-input gates, because it is a standard worst case against which the performance of a decomposition algorithm can be measured. Function S, consists of a single 3-literal cube iidc. It can be decomposed in three ways: by extracting functions iid, Ec and dc. Example 2. For the cover C(y*) = ab+ac+de f the following divisors are generated (trivial 1-literal divisors are not considered): the kernel b + c, the OR-decompositions ab, ac, def, ab + ac, ab + def and ac + def and the AND-decompositions de, df and ef. 4 Combinational d~co~~osition 4.1 State partitioning In this section we apply the theory of SIP-insertion, reviewed in Section 2.3, to a divisor F of a given cover C(a*). 244 Definition 4.1 (Transition sets) Let A =< V, E > be a SG with a set of states V and a set of events E. Let S C V be a subset of states and e E E be an event. The following sets of states are defined for S and e (see Figure 7): before(e, S) = { s : s # S A 3s'( s 5 s' A s' E S)} entry(e, S) = {s : s E s A W(s' -5 s A SI # s)} Zeave(e, S) = {s : s E S A W(s -5 s' A s' # s)} after(e, S) = {s : s s A 3s'(s' s A s' E s)} eave(e,S) after(e,S) Figure 7: Illustration of transition sets Pred(S) and Succ(S) give the sets of states outside S reachable in one step in backward or forward direction, respectively. Input, IB(S), and exit, EB(S), borders of S give the sets of states inside S from which the states not included in S are reachable in one step in backward or forward direction, respectively. Our technique operates with input borders. Set IB(F) defined by Definition 4.1 can be computed as follows (IB(F) is computed similarly): IB(F) = U entry(e, {s : ~(s) = 01) = = {S : F(s) = 0 A 391 : SI + s A F(s~) = 1). eEE An event b* is said to be a trigger event for event a* if entry(b*,ER(a*)) # 8. Informally, by firing trigger events it is possible to enter the excitation region for a*. We also say that signal b is a trigger signal for signal a and for event a*. All trigger signals for signal a must be included in the support of the logic function implementing a and hence each trigger signal will be in the fan-in of a. Triggers can be easily derived by observing ERs of a in the SG. We can also show another property of trigger signals, that will be used to estimate the complexity of the logic after decomposition. Property 4.1 Event x* is a trigger for event b* in SG A' iffZeave(b*, ER(%*)) # 8. The proof follows directly from the rules for event insertion (cf. Figure 3), because if Zeave(b*, ER(x*)) # 8 then the firing of b* will be delayed until x* has fired. Any boolean function F defines a bipartition { S F, SF} of the set of states of a SG: SF = {s : F(s) = 1) and S" = {s : F(s) = 0). As discussed in Section 2.3, for insertmg a new signal x it is necessary to find an I-partition, {S+,S1,S-,So}, based on bipartition {SF,SF}. The four blocks of I-partition are constructed as follows: S- = ER(x-) g SF and S+ = ER(s+) g S", corresponding to the excitation regions of 5 in the new SG, are obtained by the well-formed closure of the input border sets, IB(F) C SB and IB(F) C SF, respectively [6]. - - S' = SF - S+ and So = SF - S-. The following property states that, if there is a well-formed SIP closure of the IB, then there is a minimal closure that has strictly less states than any other. Property 4.2 [8] Let {b,6} be a bipartition of the SG states. Let I1 C b and let I2 be a minimal well-formed SIP set such that I1 C I2 C b. Then I2 either does not exist or unique. In particular (the practically useful case), this property holds for I1 = IB(b). The proof (see [SI) provides a constructive procedure for selecting the minimal wellformed SIP closure of the input border without backtracking and thus is computationally efficient. This procedure can be summarized as follows. (We further illustrate it by deriving ER(x-) for F = dc in S, for the hazard.g example, as shown in Figure 8). 8) Figure 8: Derivation of ER(x-) for a decomposition dc of a hazard.g example Algorithm 4.1 Generation of ERs for a new signal, by example of S- = ER($-) 1. Let ER(z-) = IB(F) 245 2. Find well-formed closure by recursive application of the following rule: ifs E Pred(ER(x-)) n SF, then let ER(x-) = ER(x-) U s. 3. Preserve (if required) the input-output interface by checking that no input signals can be delayed by x. For this do the following: for any input si nal b: i s E after(b*,ER(x-)), then let ER(x-7 = ERi-) U s. 4. Force SIP properties (make any intersection of state diamonds with ER(x-) legal by inserting in ER(x-) the corresponding states of the diamond). Goto Step 9 d Calculation of ER(x-) stops either if at some step intersects with SF (then there is no legal ) or a fixed point is reached. Calculation of is done similarly based on IB(F). Example ha2ard.g continued. In the example (see Figure 8,a) ER(x-) = (1011) (step 1). It is well-formed (step 2). At step 3 we will find that state 0011 E after(a-,ER(x-)) and state 1001 E ). Therefore, {0011,1001} are inFigure 8,b). State diamond illegally intersects ER(x-) (step 4). To le alize this, the intersection state OOO1 is included in ERtx-) as shown in Figure8,c. Figure 9 shows the results of ER(x*) generation for the decomposition of S, = Ecd with divisors Ed, Ec and dc, respectively. The choice F = Ed is not valid (see Figure 9,a), because F intersects illegally with state diamond { 101 1,001 1,1001,0001). This illegal intersection cannot be corrected by expanding IB(F) without hitting states where F = 0. The divisors Ec and dc are valid and the corresponding ERs of signal x are shown in Figure 9,b,c. acdz Figure 9: Three attempts to decompose S, = Zcd in huzurdg example 4.2 Progress Analysis If ER(x+) and ER(x-) are derived, then there is a speed-independent implementation of the SG with a new signal x. However, to ensure progress in the technology mapping for the target cover function C(m) = P * G + R, we would like to have the following implementation in the new circuit: C(a*) = x * G + R (function F is substituted in this expression by one literal z)~. This is not always possible, since to preserve speed-independence, C( a*) may require more fan-in signals. We will formulate progress conditions which will defiie when the implementation above is valid. State images. The progress conditions are easily formulated in terms of the new SG A' . However, constructing the new SG is computationally hard and hence it is better to use the original SG A (cf. the approach in [4]). For this we need to compare the states of A and their images in A'. The insertion scheme (Figure 3) determines a binary relation (we call it an image relation) between the states of A and the states of A'. A state s' from SG A' is said to be an image of a state s from A if values of all signals, except x, are the same in s and in s'. Then, state s is called the inverse image of s'. The inverse image for any state from A' is unique. The opposite is not true. Each state s E ER(x*) from SG A has two images s', s" in A' such that s' 2 s". All other states in A have one image. The image relation is expanded to the sets of states. If S is a set of states in A', then its inverse image is denoted by S-'. To avoid confusion, we will add subscript A or A' to address the objects in SGs A and A' if necessary. Inverse images for excitation and quiescent regions. The validity of substituting a new signal z in a cover function C(a*) is checked by considering the inverse images of ER(u*)At and QR(u*)A~. By construction, only states from ER(u*)A have images in which a* is enabled, hence ER(u*)A is the inverse image of ER(u*)A~. For quiescent regions the image relation is more complicated. Consider, for example, signal transition a+. For every state s E QR(u+)A there is an image in which signal a is equal to 1, and therefore QR(u+)A C QR(a+),f. However, QR(a+)p! can include additional states because some original signal transitions are delayed by x. Figure 10: Inverse image for quiescent regions This case is illustrated in Figure 10. In SG A state s E ER(a-). However, in one of its images, s', signal a is equal to 1 and is stable, and therefore s' E QR(u+)A~. Hence, state s is in the inverse image of QR(u+)AI. The following procedure computes the inverse image for a quiescent region (by example of QR(ai+)A!). 4Algorithm 4.1 does not modify the borders of SF or SB, so the combinational solution z = F is always valid. However the technique described in this section may also find a sequential decomposition with this combinational "seed". 246 Algorithm 4.2 Computing inverse image for quiescent regions QR( ai+);! = QR( ai +)A; for each a, - that succeeds a;+ do ifs E ER(%*) n ER(a,-) A after(a,-, s) n ER(%*) = 0 then QR(ai+)Af = QR(ai+),! U s end for Before formulating progress conditions we present a useful property that captures conditions for signal x to have a constant value inside the excitation region of the original signal a in the new SG even if the excitation region for x* in the original SG contains states from the ER(a*) (2, as before, denotes the signal which is inserted for decomposition). Property 4.3 [8] Let SG A' be obtained from SG A by insertion of signal x. Let a* be an event. Let ER(x+) be a welllformed SIP closure of the input border for a block of a state partition for SG A, obtained with Algorithm 4.1, such that ER(x+) fl ER(a*) # 8. Ifthe following two conditions are satisfied for SG A then x is equal to 1 in any state of ER(u*)At. A symmetrical property holds for ER(x-). The next proposition states the progress condition by presenting conditions for preserving monotonous cover conditions for substituting function F with one literal x in the cover function C(a*). Proposition4.1 [7] Let CA(U*) = F * G + R be a monotonous cover of ER(a*) in SG A. Let ER(x+) and ER(x-) be the S+and S-sets for inserting a signal x obtained by Algorithm 4.1. Thefunction CAI (U*) = x*G+ R satisfies the three conditions for the monotonous cover in the new SG A', iff: .. 1. Covercondition: after(a*, (ER(a*)nF*G*fi-))n ER(x+) = 8 2. One-hot condition: Vs : s $2 ER(a*) U QR(a*),! + s $2 ER(x-) n G 3. Monotonicity conditions: (a) Vs : s E (QR(a*) n F * G * x) + s $2 ER(x+), and (b) VS : s E 'QR(a*),! n ER(x1) n G + Pre;(s) E G+R The proof is given in [8]. The conditions in the above proposition can be informally explained as follows. Condition 1 ensures the cover condition for CAI (U*) in the new SG A', by detailing Property 4.3. Set ER(a*) n F * G * contains those states of ER(a*) in SG A that are covered by F * G, but not by R. Therefore, to satisfy the cover condition in SG A', the image of this set in A' must be covered by the function x * G. If after(a*, (ER(a*) n F * G * x)) n ER(x+) # 0, then there is a transition SI 2 s2 internal to ER(x+) such that F(sl) = G(sl) = 1 and R(sl) = 0. Hence, state ~ 247 SI has two images si and sy in A' such that si 2 sy, which implies that signal x has value 0 in si and value 1 in sy. Therefore, state si E ERA~(x+) is not covered by CAI(U*) = x * G + R since both 2 * G and R have value 0 in si. The cover condition is violated. Condition 2 ensures the one-hot condition for CA' (U*) in the new SG A'. Lets be outside ER(a*) U QR-'(a*). If s E ER(x-) n G in SG A, then in the new SG A', function x * G evaluates to 1 in the first image s' of s (s' "J s"). Hence, for A', function x * G is evaluates to 1 outside ERA,(U*)UQRA~(U*), which violates the one-hot condition for the cover function CA' (U*) = x * G + R. Condition 3 ensures the monotonicity condition for CAI (U*) in SG A'. Condition 3(a) guarantees that CAI (U*) cannot make a non-monotonous transition of the ty e "10-1" along any path inside ERA~(u*) U QRA'(a*y Set QR(a*) n F * G * contains the states of QR(a*) that are covered by F * G, but not by R, in SG A. Let some state s from this set belong to ER(x+). Then there are two images for state s in SG, A': s' and s" such that s' 2 s". Function x * G evaluates to 0 in s' and to 1 in SI'. Neither image is covered by R. Moreover since states of ER a*) are covered by CA,(,*) the cover function CA' (a* \ performs a non-monotonic transition 1-0-1 along a path within ERAI(u*) U QRA,(u*) (this path starts in ER(a*) and contains states s' and s"). Condition 3(b) ensures that CA' (U*) cannot make a nonmonotonous transition of the other type "0-1-0 along any path inside ERA, (a*) U QRA,(u*). Assume that there is at least one state, s, such that s E QR(u*)~! n ER(x-) fl G and let its predecessor, SI, be covered neither by G nor by R. Then function CA,(,*) has value 0 in the image, si, of s1 (if s1 has two images, then CAI (U*) has value 0 in both). State s has two images in A' (s' "s s"). Function x * G evaluates to 1 in the first one, s', and to 0 in the second one, s". Hence, function CAI (a*) performs a non-monotonous 0-1-0 transition along the path si -+ s' -+ s" in A'. Example hazard.g continued. All the conditions of Proposition 4.1 are satisfied for F = Ec and F = de and for both of them S, can be safely decomposed into two AND gates. 4.3 Cost estimation The progress condition (if satisfied) guarantees that the implementation of a target cover function C(a*) will be simplified as a result of a decomposition. However, to accept a decomposition we need to check that it will not increase the complexity of logic for other events. We use a conservative estimate of logic complexity, in which trigger signals play a key role, in order to select candidates for decomposition. All events (besides the target event a*) can be divided e Events x* of signal x in 3 groups: It can be shown, by analyzing the MC conditions that x = F is a correct complete cover for a signal x. The preconditions for these events are not modified by the insertion of x, and hence we can (in the e Events for which x* is not a trigger worst case) use the same implementation as before the decomposition. It is possible, though, that x can be used to further simplify the implementation of those signals as well, since the don't care set is increased. e Events for which x* is a trigger, denoted by TT(x). For estimating complexity of such events the following procedure is used. Algorithm 4.3 Estimating complexity of signals for which x is a trigger 1. for each b* E TT(I) do 2. if I* replaces trigger event d* in ER(b*) then I* property 4.4 */ 3. if I substitutes d in a cover function C(b*) then I* proposition 4.2 *I 4. The complexity of C( b*) is not increased /* property 4.5 *I 6. The complexity of C(b*) is increased moderately 8. Decomposition fails 5. else if I can be added as one additional literal to C(b*) then 7. else 9. end if 10. end if 1 1. end for Further we consider the main steps of Algorithm 4.3. Replacement of other trigger events by x (line 2 of Algorithm 4.3). Property 4. l helps to find the set of events Tr(z) for which signal x becomes a trigger. Conditions for replacing a trigger event by a new signal transition x* are stated by the following property. Property4.4 [8] An event x* replaces d* as a trigger event for b* in SG A' iff in SG A the following conditions are satisj?ed: (1) entry(d*,ER(b*)) c ER(x*) (2) before(d*,ER(b*))n ER x*) = 0 (3) after(&, entry(d*, ER@* 0 )) n ER(x*) = 0 Example ha2ard.g continued. Let us consider a combinational decomposition of S, using function F = dc. ER(x+) satisfies all the conditions of Property 4.4 and hence x+ becomes a new trigger event for t+ instead of d+. On the other hand, for ER(x-) for both events aand dcondition 2 of Property 4.4 is violated. Therefore, events aand dare concurrent with 5and none of them is replaced by the new trigger event x-. After inserting signal x event twill have three trigger events x-, a-, d-. For the decomposition based on function F = Ec, the new signal x replaces old trigger signals for Validating substitution of signal x into a cover function other than C(a*) (line 3 of Algorithm 4.3). If a trigger event x* replaces another trigger event d* for some ER(b*), then the next step is to check that signal d can be replaced by signal x in the logic implementation of C(b*). Assume that CA@*) = d * M + N. We want to check validity of substitution CAI (b*) = x * M + N. Conditions for validity of such substitution are almost identical to those of Proposition 4.1. both Z+ and t - . Proposition 4.2 Let C( b*) = d * M + N be a monotonous cover of ER( b*) in SG A. Let { S+ = ER( x+) , S' , S- = ER(x-), So} be the I-partition for inserting signal x. The implementation CA, (b*) = x * M + N satisfies the three conditions for monotonous cover in the new SG A' iff: I. Cover condition: (after( a*, (ER(a*) nd* M*N)) n 2. One-hot condition: Vs : s $ ER(a*) U QR(a*)A! =$ s # (ER(z-) U S') n M 3. Monotonicity conditions: (a) Vs : s E (QR(a*) n d * M * Pred(s) E M + N Let us clarify the difference between Propositions 4.1 and 4.2. In Proposition 4.1 signal x is the output of the gate implementing function F and is substituted into C(a*) = F * G + R instead of F. In Proposition 4.2 x substitutes signal d, which is implemented by a gate different from the gate implementing x. Therefore, Conditions 1-3 have a more general form in Proposition 4.2. Indeed, to ensure the cover condition (according to Property 4.3) condition ER(a*) n F * G *R n ER(z-) = 0 is required. This condition is automatically satisfied if z = F and x substitutes F in C(a*), whereas it is not if x substitutes signal d. If signal z substitutes function F, z is equal to 1 in the same states as F with the exception of ER(x*). Hence, in the one-hot and the monotonicity conditions, we should only consider states from ER(x-). If x substitutes signal d, then states from S should be considered as well. Note that Property 4.2 can also be used when signal z replaces several trigger signals dl , . . . , dk. In this case the cover function for b* can be represented as C( a*) = dt * . . . * dk * M + N. After substituting x a new cover function is C(b*), = z * M + N. When the replacement fails (line 5 of Algorithm 4.3). In this case the complexity of a cover function for ER( b*) can in general increase (unless the expanded don't care set induced by x* implies further simplification of C(b*)). If the conditions of the following property are satisfied, then no more than one literal is added to the fan-in of C(b*). We restrict our method with such a moderate increase in complexity only to bound the search space. Property 4.5 [7, 81 Let CA(b*) be a monotonous cover for event b* in SG A. If in the SG A' obtained from A by inserting a new signal x the following conditions are satisfied: ER(X+) = 0) A (ER(u*) n d * M * F n ER(X-) = 0) + s $ ER(z+), and (b) VS : s E QR(U*)A! n (ER(x-) U SI) n M 3 1. event x+ is a trigger for b*; 2. ER(x+) rl after@*, ER@*)) = 0 and then the cover function CAI (b*) = CA&) * z for 3. C(b*) n ER(x-) = 0, event b* in A' satisfies the monotonous cover conditions. This property is used as a heuristic filter to select candidate divisors that are guaranteed not to increase excessively the complexity of the implementation of other signals. 248