A. Žemva, B. Zaje Faculty of Electrical Engineering, Ljubljana, Slovenia Keywords- digital circuits digital circuits optimization, logical perturbations, logic synthesis, test pattern generation, fault simulation, multi-level digital circuits, wave synthesis method, single-output circuits, multi-output circuits, experimental results, optimization algorithms Abstract- In this paper we introduce the concept of permissible logic perturbations as a method for logic optimization of multi-level digital circuits. The presented approach, denoted as a wave synthesis, refers to a seguence of procedures performed in order of logic levels that transform a perturbation region of multi-input, multi-output wires into a multi-input, multi-output logic subcircuit. Primal^ goal of the wave synthesis whic:h in contrast to the other methods for logic optimization relies on fault simulation and test pattern generation algorithms, is the area optimization of the initial technology-independent multi-level circuit. We have verified the wave synthesis concept for several multi-input, muiti-output combinational circuits and the experimental results obtained with the prototype software WASP confirmed the presented approach. Ključne besede: vezja digitalna, optimizacija vezij digitalnih, perlurbacije logične, generiranje vzorcev testnih, simulacija napak, vezja digitalna večnivojska, metoda valovne sinteze, vezja enoizhodna, vezja večizhodna, rezultati eksperimentalni, algoritmi optimizacijski Povzetek- V članku je predstavljena metoda za optimizacijo večnivojskih logičnih vezij na osnovi dovoljenih perturbacij. Predlagana metoda, Imenovana valovna s nteza, temelji na zaporedju procedur s katerimi večvhodno, večizhodno perturbacijsko področje pretvorimo v vecvhodno v^ztoTno rriutaciisko podvezje. Osnovni cilj valovne sinteze, ki v nasprotju z ostalimi metodami za log,eno optimizacijo temelj, na a gontmih za gen J^ct testi'h vzorL ter simulacijo napak, je optimizacija vezij s stališča površine. Metodo smo preverili na mnozici testnih vezi, m eksperimentalni rezultati so potrdili kvaliteto predlaganega pristopa. 1 Introduction The increasing complexity of the modern VLSI circuitry is only feasible through the advanced CAD systems which as one of the important components include logic optimization tools. Automatic logic synthesis and optimization tools transform a high-level logic description into a multi-level network of realizable logic gates /1/. The concept of logic perturbations has already been proven for optimizing multi-level logic combinational Boolean networks. It was first demonstrated in a transduction method, acronym for transformation and reduction, presented in /2/. Circuit transformations and reductions based on the permissible functions were repeatedly applied until a network of the sufficient lower cost was obtained. In this sense, the transduction method was significantly different from the known design methods. Optimization by logic perturbations has been further investigated in /3/. In particular, the replacement of a gate in a synchronous Boolean network was modeled by a perturbation of the gate functionality. Perturbations presented in /4,5,6/ are based on redundancy addition and removal which can be efficiently computed using ATPG techniques. The heuristics for adding one redundant wire at a time and removing redundant wires caused by such perturbation was proposed in /4,5/. In /6/, the improved heuristics for identifying gates which are good candidates for a local functionality change, was described. In this paper, logic optimization based on the concept of undetectable perturbations is discussed. The following discussion begins with the basic notations and definitions, followed by the description of the optimization method, Experimental results on the benchmark circuits confirmed the proposed method. 2 Notations and Definitions We consider a synchronous multi-level Boolean network as shown in Figure 1; all flip-flops (FFs) are implicitly synchronized with a single clock. All combinational logic nodes of the direct acyclic graph (DAG) between primary/pseudo-primary inputs (PI/PPl) and primary/pseudo-primary outputs (PO/PPO) are assigned into two basic partitions: a synthesized permissible mutation subcircuit Mi(10} " /o/fi^O 0 ^ab {0 i} = fJ^O^, ; ^{0 1} = fafbOf, ; ^{01} '{10} = fJtOfl,; ah '^{10} = UbOfo; ^{10} = fafbOfo '^{1 1} -= fafbOf, ; ^ ab ^{11} = fafbOf, ; „ab ^{11} fafbOf, (1) where for example, perturbation observability function Oii®'^ is defined as = IZ,(x,a* = f^,b* - f,) e Z,(x,a^' = f,,b* = f,) (2) where Ir designates OR~ing the respective functions for all outputs. Given that Pj consists of m wires, a total of 12 X m X (m-1)/2 perturbations are considered. Permissible perturbation in Pj is defined for any pair of wires in Pj whose detectability, as per equations in (1), is identical to 0. Basic properties of perturbation region Pj: 1. Pj is perturbable if there is at least one permissible perturbation in Pj; 2. Pj is non-perturbable if there is no permissible perturbation in Pj. Permissible mutation function set {(fa*, fb*)i} is synthesized from the pairwise permissible perturbations in Pj. We will also refer to this set as permissible pairwise mutations or simply permissible mutations. Suppose that we have the following number of permissible perturbations for a wire pair (a, b): l^b = {i I i = J4 ® + k4 -f 14 ^ -h m4 °} V(j, k, I, m) e P3, (5) and Pab is a 4~tuple of permissible perturbation indices. For example, for (a=0, b=0) we have: j=0: no perturbation is permissible for {0 0}ab; j=1: perturbation {0 0}ab is permissible; j=2: perturbation {_Q 0}ab is permissible; j=3: perturbation {Oüjab is permissible; and k, I and m are defined similarly for (a=0, b = 1), (a=1, b=0) and (a=1, b = 1). Permissible Mutation Subcircuit Mj is formed with the permissible mutations from {(fa*, fb*)i} as a maximum cover at the minimum cost. A greedy heuristics for this cover is given in the next section. Illustrative Example. We have already discussed the target perturbation region such as Pj in Figure 2a. Given that any of the three perturbations illustrated in Figure 2b are permissible (noo=0, noi = 1, nio=1 and nii = 1), we can synthesize up to 2-2'2-1=7 permissible mutations as shown in Figure 2c. In Figure 2d, we have tabulated permissible mutations in terms of their respective perturbation and mutation indices, along with yet to be defined mutation cost of each function, $i. For example, the first permissible mutation fa*= fafb, fb*=fb in Figure 2d is synthesized by considering perturbation {1.0} permissible (1=2). Associated perturbation index Pab=0.0.2.0 and the corresponding mutation index lab=0-l-0-f2-4l-f0 = 8. If all 12 perturbations were permissible, we would have a choice of 4-4-4'4 - 1 = 255 permissible mutations for the wire pair (a, b). Freeand Bound Wire. Wire a is referred as free if fa*=fa, fa*=fa, fa*=fb or fa*=fb; otherwise it is referred as bound or covered. The same applies for wire b. (a) Target perturbation region Pi (b) Permissible perturbations within Pj Type {OJl a* ^-^ J--^ Lb* Type (10) iT^Df' > Type an (c) Choices of permissible mutation subcircuits Mj (based on synthesis of permissible pairwise perturbations above) (d) Relating perturbation and mutation indices to permissible mutations and mutation costs Pert, index Mut. index Pennissible mutations Mutation cost 0.0.2.0 8 fa' = fafb fb* ~ fb $i=6 0.3.2.0 56 fa* - fb fb' = fafb $i=6 0.0.0.3 3 fa- = fafb fb' = fafb $i=4 0.3.0.0 48 fa' = fa + fb fb' = fafb 0.0.2.3 11 fa' =0 fb'= Ijb $i=-l 0.3.0.3 51 fa'=fa®fb fb'=0 $i=-l 0.3.2.3 59 fa' = lafb fb' = 0 Fig. 2 Permissible perturbation and synthesized mutation functions Cost Classes of Permissible Mutations. For each wire pair (a, b) and each permissible mutation i, we define a cost $i as follows: $i = $(a) + $(a*) + $(b) + $(b*) where $(a) = -4 if the input pin is floating = 0 otherwise (6) $(a*) =4 if the output pin is driven by a free wire = 2 if the output pin is driven by a bound wire = 1 if the output pin is driven by a bound wire and is logically equivalent to the other output pin = 1 if the output pin is driven by a free wire and is logically equivalent to the other output pin = -3 if the output pin is driven by a constant. V ^^ /—^ Na^/FÖ/II-W : ',/•. ' —r Class Mutation Cost size cost $i $(a) m $(a*) 7 $i=8 0 0 4 4 80 $i=6 0 0 2 4 80 0 0 2 2 20 $i=2 0 0 1 1 40 $i=-l 0 0 2 -3 8 $i=-2 -4 0 1 1 16 $i=-3 -4 0 4 -3 4 $i=-14 -4 -4 -3 -3 Fig. 3 Partitioning of 255 mutation functions into 8 cost equivaience classes and where $(b) and $(b*) are calculated similarly. For the set of permissible perturbations in Figure 2b, the costs of permissible mutations range from 6 to -1 as shown in Figure 2c-d. The cost assignment to I/O nodes of the permissible mutations as shown in (6) induces a partition of all 255 permissible mutations into 8 cost equivalence classes (CEC). Generic topology of 2-input, 2-output permissible mutations into the 8 CECs is shown in Figure 3, along with the table that depicts the size of each class, associated with the mutation cost $i. Shaded nodes represent fanout nodes, unshaded nodes represent logic nodes that can implement all irredundant functions of 2-inputs. The square node with 0/1 represents a constant 0/1 signal that can prune logic nodes in the forward path. The wire terminated with ~ represents a floating wire that can prune logic nodes driving this wire. Wires show no inverters, although inverters may be presented without affecting the cost function. The cost of the permissible mutation in each class ranges from 8 to -14. The lower the cost of the mutation, the more pruning potential we associate with the mutation. Since we can precompute and store all possible perturbation indices that map into the 255 mutation indices ranked by its cost, we can determine the minimum cost mutation by simple table look-up, given the 4-tuple of permissible perturbation indices. 3 Optimization Algorithm Consider a sample circuit shown in Figure 4, consisting of 20 2-input gates on 6 levels with a maximum fanout of 4, generated with SIS/8/for a given minimal two-level specification. Starting at the primary inputs, we introduce a perturbation region Pi as a set of directed wires that connect primary inputs to the inputs of the original circuit, designated as a remainder Ri, as shown in Figure 4. Given the perturbation region Pi, we assign to each wire pair a set of 2-in-2 perturbations introduced in /7/, and determine which, if any, of these perturbations are permissible. Permissible mutation subcircuit Mj is formed by inserting permissible pairwise mutations from {(fa*, fb*)i} for each pair. b—> TV- 11>1 ll>f I> Z2 Fig. 4 Sample multi-output circuit Cost of permissible mutation subcircuit Mj. Cost of permissible mutation subcircuit IVIj, denoted as $Mj, is defined as: $ =i($(a),$(a*)) (7) where $(a) and $(a*) are the cost of input and output pins as defined in the previous section. Heuristics for Mj synthesis. We are formulating the problem of iVij synthesis as the problem of a maximal covering at the minimum cost. Assigning initially atuple of (0,4) to all wires in Mj, the synthesis problem is related to the problem of finding a minimum cost $Mj for a given set of permissible mutations {(fa*, fb*)i}- Given a set of | lab I permissible mutations per pair (a,b), the upper bound of the syntheses on m-output Mj is: m{m-1)/2 (8) Greedy heuristics is used for the synthesis of permissible mutation subcircuit Mj. Permissible mutations, starting with the lowest cost, are assigned one after another to the free wires until all wires are bound or there are no more permissible mutations. The approach is illustrated in F"igure 5 for Mi of the sample circuit in Figure 4. For M1, fxi*=fxifx2, fx2* ==0 and kr =0, fx8* =fx7+fx8 are selected first from the set of 36 pairs. The number of free lines is reduced by 4 and fx3* =fx3, fx4* = fx3 + fx4 and fx5* = fx5-ffx6, fx6* =fx6 are selected from the set of the remaining 10 pairs. The number of free lines is reduced to 1 (xg) and the procedure is terminated. Complexity of the greedy heuristics used is 0(m2), where m is the number of wires in Pj. Using the proposed greedy approach, one of the cost equivalent mutation subcircuit is constructed. In order to construct Mj with different {(faS fb*)i}, a backtracking capability is embedded into the algorithm for Mj synthesis. As shown in Figure 5, new perturbation region P2 consists of directed wires driven by the synthesized permissible mutation subcircuit Mi. Remainder R2 is the remaining circuit driven by the output wires of P2. Applying the same procedure on P2, mutation subcircuit M2 is synthesized as shown in Figure 6. The steps illustrated in Figures 5 and 6, denoted as the wave synthesis, are repeated until either the size of the perturbation region has been reduced to the two wires and the remainder itself becomes the last permissible mutation subcircuit or the perturbation region is found unperturbable. Fig. 5 Synthesis of Mi for the sample circuit X3 X7 xg xg M2 P3 3>-I> =I> XI X4 X8 xg Rc Fig. 6 Case of unpertutbable perturbation region in multi-output circuit Case of Unperturbable Perturbation Region. The problem arises when we reach the perturbation region such as P3 in Figure 6, which is unperturbable. In this case, we have to consider a partitioning strategy for the remainder such as R3 in Figure 6. Remainder Rj is partitioned into two parts: one with a single output and the other with the remaining outputs. Our decision to select the 'best single output candidate partition' is based on the notion of the extraction potential. Our definition of the extraction potential expands the notation of replication potential introduced in /9/. Let Azi = [1 1 1 of, Az2=Az3 = [0 1 1 if denote the adjacency vectors of the remainder R3. The purpose of the adjacency vector is to show the dependency of the primary outputs of the circuit to the wires in the perturbation region. A value of 1 for the l<-th wire in the adjacency vector denotes that there is at least one path from the k-th wire to the PO Zi, while a value of 0 denotes that there is no path from the k-th wire to the PO Zi. The extraction potential yzi for each PO Zi of the remainder is then Azi ® n (9) All operations performed in (9) are defined as follows: ® Logical XOR. For example, given Azi = [1 1 1 Oj'^and Az2=[0 1 1 1]"^, AZ1 ©Az2 = [10 0 1]'^. ® Logical AND. For example, given Azi =[1 1 1 0]^ and Az2=[0 111]"^, n>i Azj=Azi ■Az2 - [0 1 1 0]"^. ® Norm. For example, given Azi = [1 1 1 0]^, ||Azi|| = 3. *3 -1> 3> X4 ► > r R3 • ► Z2 Zc, Fig. 7 Partitioning perturbation regions Single-output partition with the highest extraction potential \|fzi is selected. The higher is the extraction potential for Zi, the lower is the number of common wires of Pj driving Zi and the rernaining POs. Similarly, \|/zi=0 denotes that all wires of Pj drive Zi and the remaining POs. For the adjacency vectors of the remainder R3 in Figure 6, Azi = [1 1 1 Of, Az2=Az3 = [0 1 1 if, we find yzi = II ([1 1 1 Of e[0 1 1 1 ]T) II = 2 and \)/z2 = ws == II [0 1 1 1]T e[0 1 1 OJT) 11 = 1. Primary output Zi is extracted and the remainder R3 is partitioned into R3e= {Zi} and R3''={Z2,Z3} as illustrated in Figure 7. Perturbation region P3® consists of wires {X1*,X4*,X8*} and perturbation region Ps'' of wires {X4*,X8*,X9*}. Applying the same concept on remainder R3'', the final circuit is shown in Figure 8. It is composed of 13 2-input gates on 4 levels with a maximum fanout of 3. By inserting Mj, redundancy may be introduced in the previously synthesized permissible mutation subcir-cuits Mi (1 < i < j) as well as in the remainder Rj. We postpone redundancy removal until the optimization procedure terminates. Fig. 8 Final synthesized muiti-output circuit In Table 1, we compare WASP results to the results obtained with SIS, using the commands from script algebraic. The initial benchmark circuits exist in the multi-level form or in the minimum two-level representation (circuits market with p). Since the final, technology-independent circuits generated by WASP consist of 2-input nodes, we used command xl_split-n2 for the SIS generated circuits to split any logic nodes with more than 2 inputs into 2-input gates. For all circuits, we then report the number of 2-input nodes, logic levels and the maximum fanout. The results are summarized in Table 1. We have improved the number of 2-input nodes for 15.64%, number of logic levels for 5.08% and the maximum fanouts for 23.01 %. This confirms that the presented algorithm for logic optimization optimizes the area and the maximum fanout by in general any additional increase of the delay. 4 Experimental Results We have implemented the wave synthesis algorithm as a program WASP in Programming Language C and run it on Sun SPARC 10 workstation. In this section, we report our experimental results obtained with the circuits from the Benchmark set from /10/. 5 Conclusions In this paper, we have introduced the concept of wave synthesis for optimization of digital circuits. The premise of the proposed concept is exploiting permissible perturbations evaluated for wire pairs within the perturbation regions. Given a set of permissible functions associated to any pair with permissible perturbations, permissible mutation subcircuit of the lowest cost is synthesized and inserted into the nominal circuit. The Table 1: Comparison of technology-independent circuit Circuit Inp. Out. 1 SIS WASP 1 Name Nmb Nmb Gates Levels Fanout Gates Levels Fanout cm82a ! 5 3 13 5 3 12 5 IllIIl rd53P 5 3 34 6 8 22 7 cm138a 6 8 20 4 8 20 4 8 rd73P 7 3 59 10 8 44 9 4 z4ml 7 4 i 18 9 3 18 8 3 1 incP 7 9 100 9 19 94 10 13 i 5xplP 7 10 94 10 15 75 9 12 1 rd84P 8 4 1 61 14 6 49 10 3 1 misexl^ 8 7 49 7 7 50 7 clipP 9 5 99 10 14 i 88 11 13 1 sao2P 10 4 128 12 17 108 13 14 1 !i x2 j! 10 7 42 7 9 37 7 8 [ i cmBSa 11 3 36 6 5 26 8 3 [ t481 16 1 i 27 9 4 15 4 1 Total 780 118 126 658 112 97 Improvement [%] Gates: 15.64 Levels i: 5.08 Fanout: 23.01 proposed approach is feasible for single and multi-out-put circuits. Experimental results on the benchmark circuits demonstrated the proposed method by optimizing circuits in terms of area and wiring. References /1/ G. De Micheli. Synthesis and Optimization of Digital Circuits. McGraw Hill, New York, 1994. /2/ S. Muroga, Y. Kambayashi, H. G. Lai, and J. N. Culliney. The Transduction Method - Design of Logic Networks Based on Permissible Functions. IEEE Transaction on Computer Aided Design, 38{10):1404-1424, October 1989. /3/ M. Damiani and G. De Micheli. Don't Care Set Specifications in Combinational and Synchronous Logic Circuits. IEEE Trans, on Computer-Aided Design, CAD-12(3):365-388, March 1993. /4/ K.-T. Cheng and L. A. Entrena. Multi-Level Logic Optimization By Redundancy Addition and Removal. In European Conference on Design Automation, pages 373-377, 1993. /5/ L. A. Entrena and K.-T. Cheng. Sequential Logic Optimization By Redundancy Addition and Removal. In International Conference on Computer Aided Design, pages 271 -276, 1993. /6/ S.-C. Chang and M. Marek-Sadowska. Perturb and Simplify: Multi-level Boolean Network Optimizer, In International Conference on Computer Aided Design, pages 2-5, 1994, /7/ A, Zemva and F, Brglez, Detectable Perturbations: A Paradigm for Technology Specific Multi-Fault Test Generation. In VLSI Test Symposium, pages 350-357, April 1995. /8/ SIS-Release 1.2. UC Berkeley Soft. Distr., July 1994, /9/ R, Kužnar, F. Brglez, and B, Zajc, Multi-way Netlist Partitioning into Heterogeneous FPGAs and Minimization of Total Device Cost and Interconnect, In ACM/IEEE 31st DAC, pages 238-243, June 1994, /10/ Logic Synthesis Benchmarks, 1994 Available under Benchmarks at http://www,cbl,ncsu,edu/www/. For autoreply about benchmarks, send e-mail to benchmarks@cbl.ncsu.edu. Dr. Andrej Žemva, dipl.ing. Prof. Dr Baidomir Zajc, dipi.ing. Faculty of Electrical Engineering Tržaška 25, 1000 Ljubljana, Slovenia Tel.: +386 61 176 83 46 Fax: +386 61 126 46 30 E-mail: andrej.zemva@fe.uni-lj.si Prispelo (Arrived): 24.4.1997 Sprejeto (Accepted): 6.5.1997