Efficient state reduction methods for PLA-based sequential circuits

Efficient state reduction methods for PLA-based sequential circuits 1 /- PI ’ - M.J. Avedillo J.M. Quintana J.L. Huertas /- combinational /PO logic - Indexing terms: Finite sequential machines, Programmable logic arrays, Stare minimisation / Abstract: Experiences with heuristics for the state reduction of finite-state machines are presented and two new heuristic algorithms described in detail. Results on machines from the literature and from the MCNC benchmark set are shown. The area of the PLA implemention of the combinational component and the design time are used as figures of merit. The comparison of such parameters, when the state reduction step is included in the design process and when it is not, suggests that fast state-reduction heuristics should be implemented within FSM automatic synthesis systems. / / / ~ register 1 Introduction Nowadays, technological advances lead to more and more sophisticated digital system. It is impracticable to realise them without the help of CAD tools [l-31. Systems for the design of finite state machines (FSM) have been implemented since the early 1960s but, few of them included state minimisation because the inherent complexity of this process. In particular, it was shown that the reduction of completely specified finite automata can be achieved in O(n log n) steps [4]. The minimisation of incompletely specified finite automata is a NP- complete problem [SI. Nevertheless, FSM designers have recently pointed out the need for efficient algorithms for the minimisation of large machines [lS, 161. The minimisation of the number of states is an important task in the optimal design of sequential circuits. Reducing the number of states corresponds to decreasing the number of transitions of the sequencing functions and eventually to reducing the number of implicants in a twolevel logic realisation or reducing the number of literals in a multilevel one. Moreover, a reduction of the number of states may correspond to a reduction of the number of bits that is needed for the state encoding [6]. Another area where state minimisation applies is the test generation for sequential machines. Many of the reported approximations are ineffective when the number of states in the circuit is large and the test demands long input sequences. In this paper we deal with the state minimisation problem as a part of an automatic synthesis system. After giving some basic concepts to make the paper self contained, we review existing methods for state minimisation of a FSM. Emphasis is placed on heuristic approaches, establishing a distinction between constructive heuristics and iterative improvement techniques. Two new methods for solving this problem are described, each from one of the two categories above. Experimental results are given and a detailed comparison is carried out mainly in terms of silicon area and computer time. I state reduction 1 state assignment t 1 logic minimisation I Paper 9098E (C2, ElO), first received 16th July 1991 and in revised form 18th June 1992 The authors are with the Departamento de Disefio Analogico, Centro Nacional de Microelectronica, Edif. CICA, Avda. Reina Mercedes s/n, 41012-Sevilla, Spain IEE PROCEEDINGS-E, Vol. 139, No. 6, NOVEMBER I992 minimised next state and output functions Fig. 2 Designflow 49 1 Symbolic descriptions consist of a set of symbolic implicants [7]. Each symbolic implicant has four components : i s 6(i, s) L(i, s) and represents the state transition and outputs produced when input i is applied to the FSM being in state s. The present state s and the next state 6(i, s) are symbolic representations (labels) which will be coded in the state assignment phase. Input and output functions can be both symbolic, in which case they will also be optimally encoded, or binary-valued due to the constraints imposed by other components of the system being designed. If the next state or outputs are not specified for all (input, present state)-pairs the FSM is said to be incompletely specified. State tables (tabular symbolic descriptions) are the starting point of classical state reduction theory [SI. The problem can be stated as: ‘given a state table, find another one which specifies the same external behaviour with a minimum number of states’. We briefly review for the sake of completeness some basic concepts in state reduction [8-1 11. Internal states s, and sj are compatible if: (a) for any input i, E I such that both I(i,, si) and >.(i,, s,) are specified A(&, si) = sJ) (b) for any input i, E 1 such that both 6(ik, si) and 6(ik, s,) are specified 6(i,, si) is compatible to 6(i,, s,) A compatibility class or compatible C, is a set of states such that members of the set are pairwise compatible. A compatible which is not a proper subset of any other compatibility class is called a maximal compatible (MC). If there is an input such that sk is the next state of si and sf is the next state of s, and (s,, sf) # (sir sJ) then we say that (sk, sf) is implied by (si, sj). The class set Pi implied by the compatible C, is the set of all compatibles Cij implied by Ci for all inputs ij, such that (i) Cij has more than one element (ii) Ci, @ Ci (iii) C, @ C, if C, E P, The closure class set Ei of a compatible Ci is a set of all compatibles implied by Ci obtained by repeated use of transitivity of implication, such that the compatibles which are subsets of either Ci or any other member of Ei are removed from the set. A compatible Ci dominates a compatible CJ if C, 2 C, and Pi L P,. A compatible that is not dominated by any other compatible is called a prime compatibility class W). A collection of compatibles covers all states of a state table if every state is contained in at least one compatible in the collection. A collection of compatibles is closed if for each compatibility class in it, Ci = isil, si2, . . . , si,,,} and any input i,, the set of states {6(ik, sil), 6(ik, si2), ..., &k, si,,,)} is contained in at least one compatible of the collection. 3 Exact minimisation approaches A fundamental theorem [lo] states that, given an incomplete state table, another state table specifying the same external behaviour corresponds to each closed set of 492 compatibility classes which covers all internal states of the given table. Classical approaches to the state reduction problem are structured in two well differentiated steps: (a) generation of the complete set of some kind of compatibility classes (prime compatibles [9], prime closed sets [12], etc.) The allowed compatibility classes are those for which there is assurance a minimum cardinality closed cover exits which is composed uniquely of them. There are drawbacks related to both steps. Concerning the first one, the number of those compatibility entities might be too large precluding an efiicient generation. The second step implies the solution of a minimum closed covering problem, which is known to belong to the class of NP- complete problems for incompletely specified finite state machines. Then, the very nature of this problem has precluded the inclusion of a state minimisation step in many FSM design systems during the 1970s and early 1980s. However, advances both in computing power and heuristic algorithms have convinced researchers that revising state minimisation concepts is worthwhile [13-161. But nowadays FSM designers are no more interested in symbolic descriptions with a minimum number of states; instead they focus the FSM synthesis process as a global optimisation task aimed at obtaining minimal cost implementations both in terms of silicon area and design time. It is well known that a symbolic description with a minimal number of states is not necessarily the appropriate starting point when minimal area implementations are looked for; however, usually a reduction in the number of states leads to a reduction in the complexity of the resulting FSM. Then, there is a need for developing efficient algorithms which are able to produce FSMs optimised in terms of silicon area, speed, testability, etc. (b) extraction of a minimum closed cover. 4 Heuristic minimisation approaches: previous There are several styles of heuristic strategies for solving combinatorial optimisation problems. We classify these strategies into two categories: constructive approaches, and iterative improvement methods. In constructive heuristics, a good solution to the problem being solved is built up piece by piece. This kind of approach to the state-reduction problem follows the structure of classical methods but, instead of attempting to determine minimum solutions, near-minimum (minimal) ones are heuristically selected through (a) generation of a set (usually, a complete set) of some kind of compatibles (b) heuristic selection of minimal closed cover. Heuristic algorithms were developed as early as 1972 by Bennets 1181. In this pioneering work it was pointed out that the type of initial compatibles on which they are based is not so critical. Bennets proposed a reduction algorithm based on the maximal compatible sets, MCs. Using this subset of the prime compatible set reduces (in some cases drastically) the number of candidate compatibles. The procedure consists of selecting one of the essential (or quasi-essential) MCs and attempting to satisfy its closure requirements (generating one of the smallest set of MCs that satisfies the violated closure requirements for the MC selected). The result will be a closed set of MCs that may or may not provide full covering on the work IEE PROCEEDINGS-E, Vol. 139, No. 6, NOVEMBER 1992 initial set of states. The procedure is repeated until a full cover is achieved. Very recently, several heuristic algorithms for FSM minimisation have been proposed. Kannan and Sarma [lS] begin by generating the set of all the maximal compatibles. Then a minimal set of maximal compatibles which covers all the states is built up. Finally, if the FSM is incompletely specified and the minimal cover is not the complete set of maximal compatibles, this minimal cover is expanded to obtain an optimal closed cover. Two different heuristic algorithms are proposed for the last step. In the ‘large set’ approach, each compatible in the minimal cover is checked for closure and appropriate compatibles are added to fulfill closure requirements. At every step, extra states are tried to be added to compatibles in the cover. New sets are created only if absolutely necessary. In the ‘lean set’ approach, all the states that occur more than once in the set of maximal compatibles in the minimal cover are removed. Then closure requirements are satisfied adding states to the existing compatibles or adding new compatibles. Hachtel et al. [16] stated that exact state minimisation is feasible for a large class of practical examples but have also pointed out the interest of heuristic techniques for the state minimisation of FSM generated by sequential synthesis systems. Two heuristic approaches are presented to solve the problem. In both of them they attempt to reduce the time and memory requirements by generating only a subset of the prime class set for the subsequent closed covering problem. First, a closed cover composed of maximal compatibles uniquely is found. Then, only the prime classes contained in the maximal compatibles of the previous solution are computed and used to formulate a binate covering problem [9, 101 which is then solved exactly. There are two different heuristics reported to find a closed cover of maximal compatibles. One of them is suitable for machines with a high number of maximal compatibles and is based on the concept of isomorphic states so that not all the maximal compatibles are taken into account in the process of building up a closed cover. The other one is for machines with a large number of prime classes. In this case, the complete set of maximal compatibles is generated and a minimum closed cover is found. Although these recent references appear as very interesting, the field is worth exploring further. In iterative improvement strategies an existing solution is perturbed in the direction of a lower cost one. These strategies have been only applied to the final steps of some methods and thus they may be considered as refinements [13, 161 of solutions obtained by constructive approaches. But in our opinion, iterative improvement strategies have not been explored in depth. There seems to be a parallelism between the history of logic minimisation and that of state reduction. Approaches to logic minimisation exist which simultaneously identify and select implicants for a cover. This is the case of the well known logic minimiser Espresso [19]. No similar approach exists for state reduction. So an interesting objective is developing state-reduction algorithms which simultaneously identify and select compatibles for the closed cover, and comparing them with existing approaches. REDUCES(T) /* state reduction algorithm based on maximal compatibles (MCs) *,’ { CCSS = Get-MC(T); Q = GetLconstraints(CCSS. T), cc = {a}; while(CC! =closed cover) { if (CC ! = closed) CC = +Select-CC(violated closure constraints) : else {CC = +SelecttCC(violated covering constraints), } 1 I ; = Get-Table(CC); Select-CC(violated type constraints) { Cand = Mosttrestrictive(vio1ated type constraints), for (each CC in (2nd) Compute-CO; return (M, maximises C); > 5 A new constructive heuristic We have developed a state-reduction algorithm, Reduces [20], using a constructive heuristic based on maximal IEE PROCEEDINGS-E, Vol. 139, NO. 6, NOVEMBER I992 compatibles. The state reduction is achieved by processing the state table T, from which the set of maximal compatibles CCSS is obtained. The global process is described using Pidgin-C in Fig. 3. Then, a table Q with the covering and closure constraints is derived by Getconstraints() in Fig. 3. Covering and closure constraints member of a closed cover set and c, = 0 if M, is not selected. These covering and closure constraints are shown in Fig. S. Initially, CC = 0 and the procedure Select-CC() is called with the set of covering constraints (1-9 in Fig. 5) as argument. Expr. 4 in Fig. S is the most restrictive violated one, as it is satisfied only by the selection of MI or M, (these MCs are the only ones that cover state s,). Fig. 4 Table 1 : FSM example 121 I to clarify how new algorithm works ABCD Maximal compatibles for FSM in Table I s2.- sa.- - s3, - Ss,- sg,- - - s,,- s,, - sz,- SI,- Sg,- s5,- se* - s,. 0 - sq. - -, 1 s5, 1 s2,- - - s5,-- - s,. 0 s5,- S), - - - -- _-- (1) (2) (3) (4) (5) (6) (7) (8) (9) (1 0) (11) (1 2) (1 3) -1 +c, +cs +cg +c,o > 0 -1 +c2 +C) + c5 + ce + c, + c, +cg +c,o -1 +c3 + C6 +c, +c,o > 0 -1 +c1 +ca 2 0 -1 +c, +c2+c4+c5+c, +cg b 0 -1 +c.+c5 +c6+c9+c,o > 0 -1 +c1 +C,+C,>O -1 +c,+c2+c,+c,+c,>o -1 +c, +c2 +c3 +c, +c5 +C6 2 0 -c, + c2 + c5 +c, +cg > 0 -c, +C, +c,o > 0 -c, +cg > 0 -c* +c4 +c5+cg > 0 -c,+c,+C,bo -c2 + cg + CIO b 0 (16) -c3 +c4 +c5 +cg > 0 -c4 +c, +cg > 0 (1 8) (1 9) -cq +cg +c,o 2 0 (20) -c, +c5 +C6+C9 +c,o 2 0 (21 ) -c5 +cg > 0 (22) -c5 +cg +C6 2 0 -c,+c,>O (23) -c,+c,+c,>O (26) -c, +c, +c4 > 0 -c, +c,o > 0 -c, +C5 +cg > 0 (28) -c, + c, +c4 > 0 (30) -c9+c, +c,>o (31) -c,+c,+c,,>O (32) -c,o+c, +c,>o (33) -c,,+c,+c,bo -c,,+c,+c,>o (34) Covering and closure constraints for FSM in Table I 0 (14) (1 5) (1 7) -c3 +c, +c, b 0 -ce +c2 +c, > 0 (241 (25) (27) (29) ~i~. 5 494 It is clear that M, and/or M, will be members of any closed cover set, including that of minimum cardinality. Then, Cand = {M,, M,}, and C is computed for both MCs: b for M, PC(M,) = S because MI = (s,, s5, s, , s,, sg) covers five uncovered states of the original table. That is, the selection of this MC satisfies five violated inequalities: expr. 4, 5, 7, 8 and 9. NC(M,) = 3 because the consequence of selecting M, is the violation of inequalities 10, 11, 12 which express the closure requirements of MI. That is, if M, is selected as a member of a closed cover, MCs containing compatibles (s,, s2, sJ, (s2, s5) and (s,, s5, s,) will have to be included too. C(M,) = PC(M,) - 2NC(M,) = - 1 b for M, PC(M,) = 4 NC(M,) = 3 C(M,) = PC(M,) - 2NC(M,) = -2 M, is selected (CC = {M,}) because it maximises the parameter C. Now there are some closure constraints violated (expr. 10, 11, 12) and the algorithm tries to satisfy them firstly, so procedure Selec-CC() is called for these constraints. Among this set, expr. 12 is the most restrictive one and Cand = {M,}. In this case, as there is only one candidate MC, we do not need to compute C. M, becomes a member of CC. Now, the set of violated closure constraints is {(ll), (31)) and Cand={M,,M,,Mlo) C(M,) = 0 C(M,) = 2 C(M,,) = -1 M, is selected. The only inequality not satisfied is expr. 31 and the algorithm evaluates C for each of the MCs whose selection satisfies that constraint, i.e. : Cand = {M6. Mlo} C(M,) = -1 C(M,,) = -1 Arbitrarily, M, is selected. As a consequence of adding this MC to CC, expr. 24 is violated: Cand = { M2, M3} C(M,) = 1 C(M3) = 1 M, is added to CC (CC = {MI, M,, M,, M,, M?)) which now is a closed cover of the original table descnbing the FSM. 6 Iterative improvement heuristic 6.1 Motivations The strategy we propose herein is similar to that in Espresso [19] for the heuristic minimisation of combinational functions. That is, a set of basic operations is defined which transforms a symbolic description of the FSM in another one with a smaller number of states. Our algorithm Arnes [22, 231 may be described, from a high level point of view, as a sequence of transformations (functions) which, starting with the initial description of the FSM, results in a sequence of intermediate descriptions of such a machine with a decreasing number of states. The process finishes when the application of the functions implemented by the algorithm does no longer reduce the number of states. The main advantage of this IEE PROCEEDINGS-E, Vol. 139, No. 6, NOVEMBER 1992 approach is the avoidance of generating any complete set of compatibles, as in classical state reduction algorithms. 6.2 The new algorithm Primary objective in Arnes is reducing the number of states in the symbolic description of a FSM being used as an input to other phases of the design process of sequential circuits. Moreover, once it obtains a solution with a reduced number of states, Arnes operates on it to maximise the number of 'don't cares' in excitation functions. This aims at simplifying the task of state assignment programs and logic minimisers [13, 161, so better solutions are obtained. In Fig. 6 the algorithm control block is described using Pidgin-C, where T is a symbolic description of a FSM using state tables, C is a closed cover for table T, that is, a closed set of compatibles which covers all internal states in T, and (€J is the number of compatibles in C (number of internal states in the description of the FSM). Procedure init(T) initialises C to the set of internal states ARNES(T) { C=" init(T), @* = 9 = cost(C). (@, C) = expand(C. T), (@, C) = reduction(C, 77. T' = table(C. 77. If(@ < @*) { ARNES(T'). > } Fig. 6 Pidgin-C description of control block oJthe algorithm expand(C. T) /*given a closed cover of T, returns a closed cover composed by larger compatibles (eventually prime compatibles) without having generated them previously*l { @* = @ = cost(C). for (I = 1, i G IC1 , I++) { expandl (C,), @ = cost(C). } If (@ i @*) {expand(C. 77. > Fig. 7 Pidgin-C description ofprocedure expand in the initial description T which is a closed cover of the FSM. Function cost(C) evaluates the cost of a solution, C. There are two main functions in Arnes: expand and reduction which we describe in detail. Once C has been transformed by the application of basic previous functions, procedure table(C, T) builds a symbolic description T for the FSM defining an internal state for each compatible in C. If the cost of this new description is smaller than that of the initial one, the whole process is repeated for T. Now, we explain the main procedures of Arnes. Procedure expand adds states to each compatible Ci in C, includes those compatibles needed to fulfill closure requirements of C,? (expanded compatible) and eliminates those in C that are now covered. Given Ci to be expanded, an optimum expanded compatible Cppt is defined such that a = card (W(Cpp')) - card (DIMP(CPpi)) is maximum (1) (2) where DIMP(CP") is the closure set 4"' of CYp eliminating those compatibles which are members of C, W,{Cppt) is the set of compatibles which can be eliminated from C, when substituting Ci by Cpp' because they are included in C:p', and W,(CPpr) is the set of compatibles which can be eliminated from C, when substituting Ci by Cppi because they are included in one compatible in DIMP(CYp'). If all compatibles C 3 Ci could be enumerated, we would select one satisfying eqn. 1. Instead, since this operation is computationally too expensive, the basic operation expandl obtains C: that is a good approximation to eqn. 1. In Fig. 7 and 8 procedures expand and expandl are described using Pidgin-C. Procedure expandl begins by computing the set of states that are compatible to all states in Ci and storing them in set comp. Then, for each potential expanded compatible C+j = Ci U sj, where sj is a state in set comp, a is evaluated. One of the expanded compatibles which maximises 1 is selected to be Ci and procedure expandl is repeated for this new Ci. The expansion of one compatible finishes when there are not compatible states to the current expanded compatible or a is negative for all potential expanded compatibles. After expanding a compatible, Cis still a closed cover for T. Moreover, expand- W(CPP') = W,(Cy) U W,(cppr) expandl (C,) /*given C, , compatible in C. returns C,' which is a good approximation to (1 ) * { flag = 1 , while(flag= = 1 ) { comp = compatibles(C,) if(comp1 ={a}) { for(each s, E comp) *stores in comp those states which are compatible to all states in C,*/ CT' = c. v s,, select C:' which maximises 2. and store in C' C= (C U C: U DIMP(C:)) ~ C, - W(C:) /*C: is a compatible which contains C,* /*DIMP(C,*) is the closure set €7 of C: minus those compatibles in C* l*W is the set of ComDatibleS in C contained in C' or in any compatible in DIMP'I if(a < 0 for all C:') flag = 0, /*C, expansion is not continued because expanding means increasing the number of compatibles in C'/ &se flag = 0. /*C, expansion is not continued because there are not compatible states to C,*/ Fig. 8 Pidgin-C description of procedure expandl IEE PROCEEDINGS-E, Vol. 139, No. 6, NOVEMBER 1992 49s ing is only allowed if it does not mean an increment in the cardinality of C. Procedure reduction transforms C in a new C* where each Ci is sequentially substituted by a reduced compatible C; c Ci, such that {C - C,} U C; is a closed cover For reducing each Ci, first the set of states in C, covered by unless another compatible in C, H, is derived. All states in H could be removed from Ci and C still would be a cover of T but may be not a closed set of compatibles, Procedure MCEE selects the largest subset of H that can be eliminated from Ci, such that C is still a closed cover of T. Procedure reduction allows to move away from one solution to another of less cost, as the application of the whole procedure to state table T, might lead to less costly solutions. Moreover, reduction eliminates states that are covered by more than one compatible. The minimisation of such number of states leads to the maximisation of ‘don’t cares’ in excitation functions [13]. In Fig. 9 we describe the procedure. Fig. 10 contains a description of the basic function in reduction (procedure MCEE). MCEE complexity increases exponentially with the number of states in the set H. From our experience we conclude this is not a problem, even for large machines. We use again the machine described in Table 1 to show how the algorithm works. As seen from the foregoing description there are three main blocks in the algorithm: initialisation, expansion and reduction. 6.3 Example Initialisation: We initialise C to the set of internal states in the original state table and evaluate the cost of such Expansion: Procedure expand1 is called for the first compatible in C. That is, C, = (s,). States which are compatible to all states in C, are stored in comp: comp = isz, s3, ss, s6, sa} (x is evaluated for each C:J = C, U sj, where sj is an element from comp. for sz: c:’ = (SI, s2) DIMP(C:’) = {(SZs6)? (s4s9), (sIs6), (sIs3), (szssb (S3%)> (s1sa)l W,(c:? = ((s2)J W,(C:’) = {(s,), (s4), (s9b (Sd (SSL (sa)} It can be eliminated from C because it is covered by C:2; They can be eliminated from C because they are covered by compatibles in DIMP. card(W(C:’)) = 7 card(DIMP(CT2)) = 7 a=7-7=0 This means, expanding s1 with sz leads to a closed cover with the same number of compatibles. reduction(C T) /*returns C* where each compatible C is substituted sequentially by C minimum Compatible which when substituting C,, verifies that C* is still a closed cover of T* for(;= 1; i < ICI; i++) { { H={0>; for(/ = 1 ;I < IC1 :I++) { If(i1 =/) {H = H U (C, n C,), > I j*H is the set of states in C, covered by at least another compatible in C’ If(HI = 0) Fig. 9 Pidgin-C description of procedure reduciion MCEE(H) /‘given H, a set of states in C, covered by at least another comparible in C returns the largest subset of H that can be eliminated from C, { if (all states in H can be eliminated) { return (H) else { s, = select-state(H) H- = MCEE(H, ), Hi = MCEE(H;) H‘ = merge(H H’) return (H‘), such that (C - (C,)) U (C, - MCEE(H)) isstilla closedcover of T* > ‘selects the first stare in H still not selected’ /*tries a solution without eliminating s, from C,* ‘tries a solution eliminating s, from C *selects the set with the largest cardinality* > } Fig 10 496 Pidgin-C description of procedure MCEE IEE PROCEEDINGS-t, Vol 139, No 6, NOVEMBER 1992 Summarising the results of the evaluation of z for each state sj from comp: C:” s3 is selected to expand C,. C is updated. New closed cover and cost are = {(sIs3), (s3 (s1s8)? (sZsS)3 (s4)3 (s6), (s7)> (s9)} @=8 New compatible C, in Cis expanded Cl = {(s1s3)} camp = {SZ > s6 > sa} Again, a is evaluated for each C;’. C:’* As a is positive, state s2 is added to C,. New closed cover and cost are = {(s1sZs3s8), (sZs5s6), (s1s6), (s4sY), (ST)} @=S There are not compatible states to C, = {(s,szsJs8)}, and so the expansion of this compatible is not continued. Now the algorithm tries to expand compatible C, in C. The expansion of C, is not continued because z is negative for all states in comp. The number of states in closed cover C would increase if we used s, or s9 to expand C, = {(s2s5s6)}. The algorithm goes on with C3 I(sls6sZ)<o I (sls6s3)<0 1 (sIs6sS)<oI a is negative for each C: and C3 is not expanded. IEE PROCEEDINGS-E, Vol. 139, No. 6, NOVEMBER 1992 C is updated by expanding C, with s, . = {(slsZ s3 (s2 s5 s6)3 (Sls6), (s4 s7 s9)} @=4 Now C, = {(s4s7 sg)} comp = {ss, sE) C: ’a j(s,s7s9s5)<O I (s4s7s,s8)<o~ C, is not expanded because a is negative for all potential expanded compatible Caj. Reduction ; Procedure reduction sequentially removes from the compatibles in C, those states which are not necessary to fulfill covering constraints nor closure ones. In this example no state is eliminated. As @ = 4 is less than @* = 9 the whole procedure is repeated for the new state table derived from the final closed cover. No improvement is achieved in this case. 7 Experimental results Experiments have been carried out on a large set of FSMs to test the algorithms previously described. Both of them have been coded in C. The program implementing the constructive one is called Reduces and the iterative improvement one, Arnes. Results both for machines from the literature and for machines in the MCNC benchmark set [24] are shown. 7.1 Figures of merit We focus on three figures of merit: the final number of states in the FSM representation, the area occupied by the combinational component in a PLA-based implementation of the FSM, and the time which is required for design. We introduce them in more detail: (a) the number of states in the symbolic description after state reduction. This is an important parameter to evaluate how well the state reduction algorithms work. It is the main concern of all the algorithms described in classic papers on the subject. If state assignment programs which use minimum length codes are employed, the number of states determines the number of memory elements. (h) the area of the combinational component. We use a PLA to implement the combinational component of the FSM. The area in this case is area = Kp(2ni + 3n, + ne) (3) where ni is the number of input variables, n, is the number of state variables, and no is the number of output variables. (c) design time. This parameter reports the time needed for passing from the initial symbolic description to the minimised Boolean representation of next state and output functions. It is composed of three partial times: t, time for state reduction phase (if implemented) 491 tz time for state assignment phase t, time for final logic minimisation time = t, + t, + t3 7.2 Results on machines from the literature We have tried many examples of machines from switching circuit textbooks and journal papers about minimisation [26]. In many of them the gains were significant. Table 2 shows the number of states (ns), the number of product terms (tp) and the size of the PLAs implementing the combinational part of the machines after state assignment and logic minimisation for four different initial descriptions: state tables as they appear in the literature, state tables reduced by the application of an implementation of a classic state reduction algorithm (Bennets algorithm [18]), state tables reduced by the application of Reduces, and state tables obtained by Arnes. This parameter size has been obtained with a K, = 1 in eqn. 3. Reported times in the last three include the time invested in the state reduction step. In all cases, the optimal state assignment algorithm we used was the 'i-hybrid complement' algorithm in Nova [25]. From Table 2 Arnes obtains minimum cardinality solutions in 14 of 15 cases, including the well known (and difficult) 22-state machine (FSM6) in Reference 17. Also, from this table, it should be clear that the size of the final circuit when Arnes is applied is lower than the size when starting with original FSMs except for FSMlO (equal size). In ten machines Arnes gave less area realisations than solutions supplied by the well-known Bennets algorithm. Only for FSMl and FSM10 did the implementation of Bennets algorithm achieve better size results than Arnes. Summarising the comparison between Reduces and Arnes, in nine machines Arnes gave area savings while Reduces obtained better results for three machines. For each of the machines in Table 2 two ratios have been calculated 0 1- (4) size, time, A=- and T=v sizeo time, FSM12r FSM9r -FSM15 I This is the area occupied by the PLA, obtained using Arnes, divided by the area resulting when the original description is used for state assignment. In the same way, the design time with state reduction using Arnes is divided by the design time without state reduction step. We represent the pair (A, T) for each machine in a design space whose Y-axis represents the time ratio and the X-axis the area ratio. There are two significant lines in this space, defined as A = 1 and T = 1, respectively. For any machine FSMi with coordinates (Ai, 7J below the line defined by T = I, the design time decreases when state reduction is included in the synthesis process. For any machine FSMi with coordinates (Ai, TJ on the left of the line defined by A = 1, the state-reduction step is advantageous in terms of silicon area. Advantages in both area and time correspond with machines inside the region limited by those lines. Also its borders represent favourable situations. That is, they represent cases where state reduction achieves a decreasing in one of the design coordinates without changing the other one. In Fig. 11, pairs (A, T) for the machines in Table 2 have been drawn. The point labelled [FSM] (0.45, 0.22) represents the average for the machines in Table 2. n 0 41 PI I FSM4r I I FSM3r B I Table 2: Minimisation results for machines from literature Original FSM Bennets FSM n, no ns tp size, time, ns, tp size time Reduces FSM nsR tp size time ns, Arnes FSM ns,,, tp size, time, FSMl FSM2 FSM3 FSM4 FSM5 FSM6 FSM7 FSM8 FSMS FSMlO FSMll FSMl2 FSM13 FSM14 FSMl5 2 1 5 7 98 27 4 4 44 14 2 1 9 10 170 121 6 10 140 37 2 1 7 9 126 48 4 7 77 15 2 1 6 7 98 31 4 4 44 10 2 1 6 8 112 43 4 6 66 12 2 1 22 25 500 261 2 12 16 272 1803 2 1 9 14 238 165 5 10 140 26 2 1 6 8 112 50 4 6 66 14 3 1 9 15 285 352 4 9 117 30 3 1 8 14 224 164 5 13 208 48 2 1 6 9 126 61 5 9 126 35 2 1 9 11 187 153 4 7 77 17 3 1 611 176 66 3 5 65 13 21 6798 282 324 06 3 1 10 10 190 236 4 7 91 19 4 4 44 1.2 3 5 10 140 31 4 4 7 77 1.2 4 3 4 44 0.8 3 4 6 66 1.2 3 11 12 204 23.9 9 6 10 140 2.7 4 4 6 66 1.3 3 4 11 143 2.7 3 5 13 208 4.7 5 5 9 126 3.2 4 4 7 77 1.4 3 3 5 65 1.4 3 2 3 24 0.6 2 4 6 78 1.9 4 5 55 0.8 3 7 77 1.8 4 5 55 1.8 4 4 44 1.2 3 5 55 1.2 3 13 231 55.9 9 8 88 1.8 4 6 66 1.2 3 5 65 1.7 3 14 224 7.5 4 7 77 1.5 4 6 66 1.3 3 4 52 1.2 3 3 24 0.4 2 5 65 1.5 4 n,. number of input variables; no. number of output functions; ns. nsg. nsR, ns,. states in descriptions obtained from papers. Bennets algorithm. Reduces and Arnes. respectively; ns,,,, minimum number of states; tp, number of product terms; size. PLA size evaluated by Nova: time, time in seconds on a Sun 3/260 workstation 498 IEE PROCEEDINGS-E, Vol. 139, No. 6, NOVEMBER 1992 Table 3: Minimisation results for machines in MCNC benchmark Original FSM Reduces FSM Arnes FSM n, no ns tp size, timeo ns; tp size time ns; tp size, time, t. t, +t, t. r,+t, 0 B 0 0- m b -o 06- z" 04- bbara bbsse beecount ex1 ex2 ex3 ex5 ex7 lion9 markl opus scf se. bbsse tbk train1 1 I I .bbora I A- tmcnc,- beecount ~ ex3r I I 4 2 10 25 34 710 9 19 20 50 2 2 19 36 2 2 10 18 22 918 2 2 10 17 21 9 9 5 16 15 17 5 6 10 16 7 7 16 29 6 3 32 170 2 1 11 12 7 7 16 29 27 56 121 146 1 550 957 1 90 2600 756 324 324 306 153 646 448 91 26 957 51 00 204 17.1 47.0 78 350.3 95.0 14.5 11.6 17.3 8.7 51.5 11.6 9676.6 49.4 7840.0 14.5 7 20 13 29 49 18 43 10 19 6 10 48 47 47 12 17 9 16 97 128 13 29 16 52 46 380 957 144 2236 342 150 96 84 77 646 448 16768 957 1404 66 08 41 03 32 3 36 09 08 09 05 41 11 50 39 5 05 137 8.1 7 435.2 13 3.4 4 281.5 18 13.8 7 3.5 5 2.3 3 2.3 4 2.4 4 225.6 12 10.0 9 7234.0 97 459.2 13 1426.9 16 2.6 4 20 29 9 43 13 9 6 9 7 16 16 128 29 52 6 380 957 144 2236 195 135 72 108 77 608 448 16768 957 1404 66 0.2 3.5 0.2 24.3 4.3 0.9 0.3 0.4 0.1 4.2 0.4 3.5 30.8 0.1 112 8.8 39.8 3.7 281.5 6.9 5.1 2.3 3.1 2.6 44.1 9.8 7234.0 40.0 1425.3 3.4 shown in the column labelled t, for each of our algorithms. The columns labelled t, + t3 give the time invested in state assignment and logic minimisation with the 'i-greedy complement' option in Nova. From the Table for almost half of the machines area savings of more than 50% are achieved when the reduced machine obtained with Arnes or Reduces is used as input for the state assignment phase. The time to obtain such solutions with Arnes (tl + t, + t, in time, column) is less than that resulting from applying Nova to the original machine (time, column) for all of them. Concerning the state assignment and minimisation steps, there are three machines (bbsse, sse, markl) for which the Nova time when using Reduces (t2 + t, in Reduces column) is higher than the Nova time when the original description is used. It is due to the symbolic descriptions generated by the state minimisers which are then used as input to the state assignment phase. In some cases, they are descriptions with a large number of symbolic implicants and the logic minimisation step slows down. However, this is a feature of the algorithm's implementation which can be corrected. In Fig. 12, pairs (A, T) for the machines in Table 3 have been drawn. t-- l0C-- -__-_-___________- A bbsse,sse .ex1 )opus 1 rscf , A I MC NCI 0 02 04 06 08 10 A~rnes.~cva'Aorlg. N~~~ Fig. 12 mark Experimental results when Arnes IS applied fa MCNC bench- Nevertheless, the discussion of results would be incomplete if we did not consider what happens with machines for which state reduction does not achieve any reduction. When provided with a description of a machine to be implemented, we do not know beforehand whether there are compatible states or not. This means the state reducer IEE PROCEEDINGS-E, Vol. 139, No. 6, NOVEMBER 1992 will be invoked and a certain amount of time invested in checking if there are compatible states. If so, a description with less states will be tried, but the state reducer can fail in finding such one. Thus, the result of this processing being the same initial description and coordinates for this machine (A = l, T > l). It is difficult to carry out an estimation of how this increasing in the computer time may affect. To give a rough idea, we have evaluated coordinates (A, T) for the whole MCNC set (about the half of the machines do not have compatible states), the average result leading to the point (0.76, 0.83), point [MCNC] in the Figure, which is inside the striped region in Fig. 12. Of course, the average value for those MCNC machines admitting minimisation is much better (point [mcnc] with coordinates (0.63,0.53) in the Figure). From the set of machines from the literature, the superiority of Arnes against Reduces in area is evident. They are similar in time. The superior performance of Arnes is not so clear for the machines in the MCNC benchmark. The key point to understand the differences is whether the selection of maximal compatibles as variables to formulate the LP integer problem (Reduces) implies a limitation to the quality of the solutions it can obtain. This is the case for the literature machines but, obviously, it is not for the MCNC benchmark. Since there have been two other approaches recently [IS, 161, it is convenient to compare our results with them. From the published results, we have elaborated Table 4 where the minimisation achieved on MCNC Table 4: Comparison of minimisation results achieved on MCNC machines Kannan Hachtel Reduces Arnes er a/ 1151 er a/ 1161 ns * ns* ns* ns* bbara 7 7 7 7 bbsse - 13 13 13 beecount 4 4 4 4 ex1 - 18 18 18 ex2 10 5 10 7 ex3 4 6 5 ex5 4 3 4 3 ex7 4 3 4 4 lion9 - 4 4 4 markl 12 12 12 12 opus 9 9 9 9 scf 97 97 97 97 sse 13 13 13 13 tbk 16 16 16 16 train11 4 4 4 4 ns', number of states in reduced descriptions ~ 499