Boolean decomposition in multilevel logic optimization

IEEE JOUKNAI. OF SOLID-STATECIRCUITS, VOL.

24,

NO.

2, APKIL 1989

399

Boolean Decomposition in Multilevel Logic Optimization SRINIVAS DEVADAS, ALBERT R. WANG, A. RICHARD NEWTON, FELLOW, ALBERT0 SANGIOVANNI-VINCENTELLI, FELLOW, IEEE

Ahtruct -Work in the area of multilevel logic optimization has been concentrated primarily in the development of algebraic techniques for factoring and decomposing logic equations. In this paper, we present algorithms for Boolean decomposition based on multiple - uulued Booleun minimirution. These algorithms can decompose a PLA into a cascade of s n i d e r PLA’s or identify good Boolean factors that can be used as strong dicis0r.s so as to minimize the literal count and the area of a multilevel logic network. Given a two-level logic function, a subset of inputs to the function is .;elected, using new selection algorithms, such that the number of good Boolean factors contained in this subset of inputs is large. If the targeted implementation is a set of interconnected PLA’s, the different cube combinations given by this subset of inputs are re-encoded to reduce the number of product terms in the logic function. The re-encoding process incorporates a new encoding algorithm, superior to previous techniques, which minimizes the number of product terms in the re-encoded logic function given a constraint on the number of bits to be used. When targeting a general multilevel network, we are concerned with minimizing the literal count of the network. We have developed new algorithms to identify a set of factors that maximally decrease the literal count of the logic network when used as strong divisors. We present results obtained on several benchmark examples that illustrate the efficacy of our techniques.

IEEE, A N D

=gJ PLA-1

Onginal PLA

PLA-2

Fig. 1. PLA architecture.

The factoring algorithms proposed in [2] and [3] are primarily based on algebraic techniques. Boolean factoring/division techniques can achieve superior results. However, techniques proposed so far for Boolean factoring and multilevel Boolean minimization (e.g., [5], [9]) require very large amounts of CPU time. Multilevel logic networks can be realized by standard cell or gate array implementations. For small to medium (less than 50 product terms) sized two-level representations, the PLA is a very compact structure whose size is I. INTRODUCTION comparable (if not smaller) than a corresponding multiPTIMAL multilevel logic synthesis is a known diffi- level implementation. Topological optimization techniques cult problem which has been studied since the 1950’s. like folding [15] can further reduce PLA area. A set of In recent years, it has been the subject of a great deal of interconnected PLA’s can thus exploit both the layout compactness of PLA’s without being constrained by the at ten tion (e.g., [11, [21, [71, [81, [lo]). For multilevel design, two basic methodologies have relative inflexibility of two-level logic structures. A PLA can be decomposed into a set of interconnected evolved: 1) global restructuring, where the logic functions PLA’s which feed into one another. To perform this deare “factored” into an optimal multilevel form with little consideration of the form of the original description (e.g., composition, factoring algorithms are required. In this [2], [lo]); and 2) peephole optimization, where local trans- paper, we present algorithms for Boolean decomposition formations are applied to the user-specified (or globally based on multiple-valued Boolean minimization, which decompose a PLA into a cascade of two smaller PLA’s such optimized) logic function (e.g., [7], [ll]). Global restructuring procedures have been shown to be that the overall area of the resulting logic network, deemed crucially necessary in producing optimal designs. Factor- to be the sum of the areas of the constituent PLA’s, is ing algorithms have been proposed [2], [3] which are effec- minimized. The problem was first addressed in [14]. The architective in partitioning complex logic functions. ture of the decomposed PLA pair is shown in Fig. 1. The same architecture is used here. However, the decomposiManuscript received July 22, 1988; revised November 23, 1988. tion algorithms presented here are quite different from S. Devadas is with the Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, those in [14]. MA 02139. We also present algorithms, based on multiple-valued A. R. Wang, A. R. Newton, and A. Sangiovanni-Vincentelli are with the Department of Electrical Engineering and Computer Sciences. Uni- minimization, for identifying and extracting good Boolean versity of California. Berkeley, CA 94720. factors in multilevel logic optimization. Factors that miniIEEE Log Number 8826131.

0

0018-9200/89/0400-0399$01.00 01989 IEEE

400

mize the number of literals (transistors) in the network are identified. These factors are then used as strong divisors to minimize the area of the multilevel logic network. Given a two-level logic function, a subset of inputs to the function is selected. T h s selection step incorporates a new algorithm which selects a set of inputs such that the cardinality of the multiple-valued cover, produced by representing all combinations of these inputs as different values of a single multiple-valued variable, is much smaller than the original binary cover cardinality. A relatively small size for the multiple-valued cover implies that the number of good Boolean factors contained in this subset of inputs is large. Selecting different sets of inputs in the given logic function results in different multiple-valued cover cardinalities. Given a constraint on the number of inputs to be selected, the algorithm identifies a subset of inputs, which when represented by a single multiple-valued variable, results in a maximal reduction of cover cardinality. Given a selected subset of inputs, different decomposition algorithms are employed depending on the targeted implementation style. If the original description is decomposed into a set of interconnected PLA's, the different cube combinations given by this subset of inputs are re-encoded to satisfy all or a subset of the constraints given by the multiple-valued cover, producing a binary cover for the original PLA with smaller cardinality. The number of distinct constraints specified by the multiple-valued cover affects the number of bits required to satisfy these constraints, which in turn affects the areas of the resulting PLA's. This problem of optimal constrained encoding, i.e., satisfying a set of constraints by a minimum code length, is a complex combinatorial optimization problem. We have formulated optimal constrained encoding as a constraint ordering problem and developed a new encoding algorithm, based on the notion of partial satisfaction of constraints, which finds an encoding that maximally reduces the cardinality of the origmal PLA, given a bound on the number of encoding bits available. When targeting a general multilevel network, rather than re-encoding the different input combinations, good Boolean factors are identified based on the constraints specified by the multiple-valued cover. Algorithms have been developed which heuristically select the best set of factors, i.e., factors that maximally reduce the literal count of the network when used as strong divisors. We present experimental results for both kinds of decomposition algorithms. Total delays and areas of decomposed PLA's after Boolean decomposition are, in general, smaller than those for the original PLA's. Large PLA's have been reduced by factors of 2-3 in size and delay. Strong division using the Boolean factors identified via this approach produces smaller literal counts during multilevel logic optimization as compared to algebraic factorization. In Section 11, basic definitions and notations used are given. The input selection algorithm is described in Section 111. The encoding algorithm used to re-encode the different input combinations so as to minimize PLA cardinality is

IEEE JOURNAL OF SOLID-STATECIRCUITS,VOL.

24, NO. 2 , APRIL 1989

described in Section 1V. An algorithm for selecting Boolean factors so as to reduce literal counts via strong division is described in Section V. Results obtained on several benchmark examples are given in Section VI.

11. PRELIMINARIES A multiple-valued variable mP can take on values 0,l; . -,p - 1. In particular, a binary-valued variable m2 can take on values of 0 or 1. If the subscript p is omitted, it is assumed to be 2. Let p , for i = 1,.. ., n be positive integers representing the number of values for each of n variables. Define the set P I ={ O ; . . , p , - l } for i = l . . . n whchrepresents the p , values that variable m' may assume, and define BJ {O,l, * } which represent the value of the function. A multiple-valued input, binary-valued output function with k outputs, P n x k (hereafter known as a multiple-valued function), is a mapping

P n x k :P 1 x P 2 . . .X P , , - + B , X . . . X B , . The function is said to have n multiple-valued inputs mpi, k binary-valued outputs, and variable i takes on p ,

possible values. The cover of a multiple-valued function P n x kis a collection of cubes or implicants { c,, 1< i < IPI} where c, = ( C 1 1 4 , 2 , .. . c l n ,b'l

. . . b,k).

IPI is the number of cubes in the cover. The first n entries represent the input part of the cube, and the next k entries represent the output part of the cube. (In the sequel, when no confusion can arise, we will only list the input part of a cube). cJJc PJ is a collection of values of rn? that appear in cube c,. We will use a bit-vector representation of length pJ for C I J = [C,,(O),. . * , C J J ( P '-111, where

c , , ( k ) =1 if

~ E c elseO. , ~

A logic function g is a Boolean divisor or strong divisor of f if f = gh r , where h and r are logic functions and gh # 0. The inputs to a binary-valued logic function will be denoted x,. The area of a binary-valued logic function Pnxk is ~ defined to be ( 2 n + k ) IPI.

+

111. SELECTION

The goal of the selection process is to identify a subset of inputs, S I , lSZl= N,, in the given PLA which when re-encoded will reduce the cardinality of the binary cover to a maximum extent (more than any other subset of N, inputs). Re-encoding a set of inputs is a process that replaces each distinct combination of these inputs (which occur in

401

DEVADAS er U / . : BOOLEAN DECOMPOSITIONI N MIJLTILEVEL LOGIC OPTIMIZATION

the original PLA description) by a distinct binary pattern. The length of these binary patterns may be less than, equal to, or greater than the number of inputs being re-encoded. The only constraint on the pattern length (the number of re-encoding bits) is due to the fact that no binary pattern may be assigned to more than one input combination. If for a set of inputs of cardinality n , , Nd G 2''~distinct input combinations exist, the number of re-encoding bits required is Nh >, log( N d ) . Our approach to estimate the cover cardinality after re-encoding is to estimate the cardinality of the optimal multiple-valued cover produced by replacing all distinct combinations of the selected inputs by a single multiplevalued variable. Each distinct combination becomes a different value of the multiple-valued variable. The cardinality of the minimum cover of the new multiple-valued input, binary output logic function is the minimum cardinality that can be achieved by re-encoding the selected inputs. Informally, the iterative selection algorithm proceeds as follows: 1) All inputs (or a subset of selected inputs from the previous iteration) are picked, and each distinct input combination in the original PLA is represented by a value of a multiple-valued variable. 2) A complete undirected graph where each vertex in the graph is an input to the PLA is constructed. The graph has weighted edges whose weights are all initially set to zero. 3) The multiple-valued cover is minimized using a multiple-valued logic minimizer like ESPRESSO-MV [13]. 4) Next, the multiple-valued cover is examined. Each implicant in the multiple-valued cover contains one or more values which correspond to the original binary input combinations. For each implicant, the set of binary input combinations which have merged to form this implicant is found. The inputs which prevent this set of binary input combinations from merging in the original binary cover are found for each implicant. 5) Given the set of inputs for each implicant, the edge weights in the graph are modified. Essentially, a weight directly proportional to the number of merged input combinations in the implicant and inversely proportional to the number of inputs preventing this merge from occurring in the original binary cover is added to the edge between each pair of inputs in the set. 6) Given the graph with weighted edges, a set of vertices (inputs) of cardinality N, with the maximum sum of weights of interconnecting edges is found. Thls set of inputs is the selected set. It has been found that iteratively selecting a smaller and smaller set of inputs is a better heuristic than a single-pass selection of N, inputs from all n inputs to the PLA. A more formal description of the selection algorithm follows. We are given a binary cover P n x k .(If the cover is minimal, all L = IPI cubes c, = ( c , ~ c, , ~ ,. e,,,) are distinct, i.e., differ in at least one bit). We construct a new function P;xk, whose input is a single multiple-valued +

' 100 010 101 011

3x3

'

001 010 100 101

olooolo

'"

1x3

1x3

1000 0 0 1

+

0010 1 0 0 0001 1 0 1

Fig. 2.

3

0100 0 1 0 0011 1 0 0 .AA. A n * lUUl vu I

Selection

variable mlPl. Each cube g, E PLX,,corresponds to a value of the variable miP': g,( j ) =1 if j

=i

else 0,

1 < . i dL

Thus, a function with n binary-valued inputs, P,,x,,, is converted into a function with a single multiple-valued input, P,'xA. P;xk is then minimized to produce P{k,,. We illustrate this transformation with an example. A binary cover P 3 x 3 and the resulting functions PlXi and P;L3 are shown in Fig. 2. We have a graph C( V , E , W( E )) where V = { x, } are the vertices in the graph. x,. i = 1 . . . n , are the n input variables to the PLA. The edges in graph E = { o,, u,}Vi, ji > j ; the graph is complete and undirected. Initially the weights of the edges W(E ) = 0. The pseudo-code below illustrates the calculation of weights of the edges in the graph W ( E ) : ill:

(1,

-

calculate-edge-weights( ): { foreach (cube g, E P { L k ) { c,= { cJ: g , ( j ) = l } . 1 < I d L ; X,= { x,:3c,, C A E- c,,c1, f c , , , } :

",

=

lC,lL(I~,l-~);

foreach ( x , y

E

X I , x # J,) { + w,;

w(x, y ) = w(x, y )

1

1

1

C, is the set of input combinations in the original binary cover which merge to form the implicant m , in the minimized multiple-valued cover. X I is the set of input combinations which prevent this merging in the original cover. For example, two binary implicants c,. cI E P,,,,, which differ in two (or more) bit positions, r and s. i.e., cII # c , ~ and e,,, # cJJ, cannot merge due to the input variables x, and x,. If any input takes on different values in the cubes in C,, it is included in X,.The weight of the edge between each pair of inputs in X I is incremented by w,. The rationale for the calculation of M', is as follows. If the inputs in the set X,are selected, then C, cubes in the binary cover will merge into a single multiple-valued implicant. Since the goal is maximum cardinality decrease, the edges between these inputs are weighted correspondingly. However, since we want to select a fixed number of inputs, the cardinality of X , is also a factor. The weight is inversely proportional to the number of inputs in X,. A single input cannot prevent a merging of cubes by itself in a binary cover, so the cardinality of IX,l > 2. What we are

402

IEEE JOURNAL OF SOLID-STATE CIRCUITS, VOL.

looking for is the largest possible reduction in the cardinality of the cover (given by IC,/ for each implicant) selecting the smallest number of inputs (given by IX,I). Given the graph G ( V , E , “ ( E ) ) a set of N, vertices, SI = { v k } (inputs), is selected such that Ns

Ns

C J=I+l ~

~

~

~

~

(1)

1-1

is maximized. T h s selection of inputs is performed by exhaustive search. Typically, the number of inputs N, to the logic functions encountered in practice is d 100. We restrict the number of inputs selected, N,, to vary between two and eight and thus an exhaustive search algorithm which has a complexity of O(N,&)is feasible. A heuristic polynomialtime algorithm that will serially select N,’ ( < N,) inputs at a time until N, inputs are selected can be used if N, is large. The selection algorithm has been experimentally shown to be a good heuristic for a large class of functions (see Section V). In addition, we can prove that the algorithm produces an optimum selection, i.e., a maximum reduction in multiple-valued cover cardinality, for a certain class of functions.

24, NO. 2, APRIL 1989

weights of edges between inputs xl, . xk for any k out the n inputs to F. Call the multiple-valued cover produced by selecting all x, E X , F,. Obviously, IF,*/< IFI+2k-1. Each of the implicants in F,, has been prevented from forming in the original binary cover by every pair of inputs x i , xJ 3 1< i , j < k , and possibly other pairs of inputs y rx , 3 y > k or z > k . Therefore the clique C E G, comI xprising ~ the inputs ~ x l , ~. . . x k , has ~ eachI of its edges ~ ~ incremented by w, (in the inner loop of function calculateedge-weights( )) for every implicant g, E F,. Weights of other edges in the graph not in C may also be incremented by w,, but at every iteration of the outer loop in function calculate-edge-weights( ), k

k

c c

(2)

W(X,~Xh)

u = l h=u+l

is incremented by k x k h

c c

u = l h=u+l

-

1x w,. We immediately have

k

k

W(X,>Xb)>

h

c c

w(s[ql>s[rl)

y=l r=y+l

(3) Q.E.D.

W q I , s [ r lEX.

IV. PLA DECOMPOSITION Theorem 3.1: Given an optimal binary cover P n x k , the cardinality of the optimal multiple-valued cover produced by replacing all distinct combinations of any I d k inputs by a single multiple-valued variable is greater than or equal to l P l f 2I-I. Proof (by contradiction): Let us assume that the multiple-valued cover has a cardinality M < IPI t 2I-l. It is true that any single-output function with r inputs can be represented by a cover of cardinality < 2r-1. Therefore, each of the implicants of the multiple-valued cover can represent at most 2‘-’ binary implicants. This means that the multiple-valued cover can be transformed into an equivalent binary cover of cardinality M X 2‘-’< I PI, implying that the original binary cover was nonoptimal. Q.E.D. Theorem 3.2: Given a set of functions F, each with n input variables X = x l , x 2 , . . . x , of the form ~ + ~ , * * * , F., = ( x i @ x 2 * *@. x ~ ) . G ~ ~ ( x ~x,,) -k ( X 1 @ X 2 . .

. @ X k ) * G r 2 ( X k + l.,, *X,,)Vi, . G,,n GI, = (p

with k >, 2, the optimal selection for k inputs is x l , ’ ’ . xk and will be produced by the selection algorithm. Proof: Selecting xl, . . x k will result in a multiple-valued cover cardinality IFlt2k-’, since I x 1 @ x 2 ... @xkl = I x l @ x , . . @xkl= 2 k - 1 . This is the maximum possible for any selection of k inputs by Theorem 3.1. We now have to prove that the graph G constructed by the selection algorithm (in the first iteration) has the maximum sum of

-

Given a set of selected SI when targeting a PLA implementation, the goal is to optimally re-encode the different binary combinations of the input variables in SI so as to minimize the number of product terms in the original PLA, Pnxk. First, the input cubes c, E P n x k are separated to form ( U , , si), where U , represents that part of c, corresponding to the unselected binary-valued inputs, and s, represents the part of c, corresponding to the selected binary-valued inputs SI. The cubes c, are made disjoint in si, i.e. s, n sJ = (p if s, f sJ

to produce c,’ E P i x k . Note that IP’( > ]PI. A trivial transformation IPI -+ IP’I exists, where each of the s,’s is a miniterm. However, this may result in a very large lP’l >> IPI, (IP’l d 21”’ x IPl), decreasing computational efficiency (IS11 is the number of selected inputs). Thus, we would like to find a transformation which minimizes IP’I while satisfying the s, disjointness constraint. A simple strategy of splitting a s, cube only if it intersects another cube sJ suffices to keep lP’l from increasing exponentially with / S I I. The worst-case complexity is, however, exponential. Re-encoding is illustrated using a simple example in Fig. 3. Each of the four distinct combinations of the first two inputs of the binary cover P 3 x 3of Fig. 3 is replaced with a distinct binary pattern to produce a new cover P F 3 x 3 . Minimizing PF3x3 produces a cover PF,’,, of smaller cardinality. We now describe the algorithms used in the re-encoding process. In Section IV-A, we give some definitions which

~

~

DEVADAS et

U/. :

BOOLEAN DECOMPOSITION I N MULTILEVEL LOGIC OPTIMIZATION

3x3

100 111 101 110 000 010

100 100 010 010 001 101

pF 3x3

010 001 011 000 100 110

100 100 010 010 001 101

p F 3x3

403

B. Re-encoding Satisfving All Constraints

Our approach to solving the constrained encoding problem is different from [6] and [12]. In [6], a row-based 1 - 0 001 000 010 encoding scheme has been proposed. This encoding scheme - 1 0 100 constructs A row by row. This row-based encoding scheme Fig. 3. Encoding. fails to be effective for large examples [12]. A column-based encoding scheme, which constructs A column by column will be used in the following sections. Some results in [6] was proposed in [12]. Here, the constraint matrix M , is are also given. The re-encoding algorithm used when no compacted using (3) above and A is constructed incremenconstraint is placed on the number of usable encoding bits tally as MT. If at any point a constraint is already satisfied is described in Section IV-B. A modified algorithm which by A , then it is discarded. This is possible even if all allows for the specification of a bound on the number of relationships using (3) have been exploited as we will show. We prove a result stronger than (3) here and formuencoding bits is described in Section IV-C. late the constraint compaction problem as a constraint ordering problem. A. Definitions, The Procedure and Related Work

3

001 1 0 0

3

Ol1 loo

Let D be a set of nodes where each node corresponds to a distinct s,. D is represented by a multiple-valued variable with ID1 values, ml’l, each value corresponding to a node in D. Replacing the s, E e,‘ E P,,’,, with a multiplevalued variable mlDI, we obtain a new cover Q(,,+I,+l)xk, which has a n - [SI1 binary-valued inputs and a single multiple-valued input. Q is minimized using a multiple-valued logic minimizer (e.g.. ESPRESSO-MV [13]) to produce Q ~ , , ~ , , , , + , ~ , , . Define a code matrix A E { O , l } I D l x * ’ h whose rows are the new encoding of the nodes in D.Define a constraint matrix M , E { O , l } @ ’ ~ x ~ D ~ :

Theorem 4.1: Given a constraint matrix M,., A = M,T satisfies all constraints which are obtained by bit-wise-intersecting two or more rows in M,. or their (bit-wise) complements in any combination.

Proof: Construct a constraint C , which is the bit-wise intersection of the rows or complement of rows in M , in any combination. We assume without loss of generality that C is constructed using all the rows in M , in true or complemented form. (If C is constructed using a subset of rows, then we can identify a matrix M,‘ corresponding to this subset of rows. We then have to prove that A‘ = M 2) product terms in the binary cover after re-encoding using A . The degree of partial satisfaction is p. If we had a constraint matrix M , and an encoding matrix A which satisfied x constraints in M,., 2-partially satisfied y rows of M,, and 3-partially satisfied the rest of the z rows in M,, the number of product terms required in the binary cover would be x + 2 x y 3 x z. The goal of a constrained encoding algorithm is to find an encoding matrix A which completely or partially satisfies constraints in such a way that the total number of product terms required by the binary cover is minimum.

+

DLVADAS

C l U[.

Given an A , the complexity of checking if A satisfies a constraint C is O ( N , * N,), where N,, is the number of nodes (rows in A ) and N, is the length of the encoding (columns in A ) . If A does not satisfy C, determining the degree of partial satisfaction of C, namely, p , involves an exact binary logic minimization, and is NP-complete. We have developed a polynomial-time algorithm whch provides an estimate of p given C and an encoding matrix A . This algorithm is described below. partial-sat-degree(A , C): { cubeset = $; foreach ( i 3 C(i) = 1) { didmerge = FALSE; foreach (cube g J E cubeset) { merge = TRUE; foreach ( k 3 C ( k )= 0) { if (super(g,, A ( i ) ) n A ( k ) + $1 { merge = FALSE; break; } if (merge) { d, = distance(g,, A ( i)); didmerge = TRUE; } else d, = INFINITY

1

if (didmerge) { pick g , E cubeset so d , is minimum; g, = super(g,, A ( i )I: } else { cubeset = cubeset U A ( i ) ;

1

1

return (Icubesetl):

1

405

: BOOLLAN DECOMPOSITION IN MULTILEVEL LOGIC OPTIMIZATION

this section allows greater freedom during the selection step, thus producing better results (smaller PLA’s). V.

IDENTIFYING BOOLEANFACTOKS

During multilevel logic optimization, factoring algorithms are used to identify a good set of factors, which when extracted from the network result in large reductions in network area/literal count. Algebraic factoring algorithms have been proposed in the past (e.g., [2], [3]). The factors identified by these algorithms are used as algebraic or weak divisors. Boolean or strong division is a more powerful technique, but is also more time-consuming, since it involves logic minimization. In the previous section, we showed how re-encoding input combinations could reduce the product term cardinality of a PLA. Indeed, the process of re-encoding is a Boolean factorization/division technique. Multiple-valued minimization attempts to reduce the cardinality of the multiple-valued cover Q,,, produced by representing distinct input combinations as values of a single multiple-valued variable. Each implicant in the minimized cover Q~,,pls,,+llx,, represents a factor, i.e., a set of input combinations on the selected set of inputs. The minimization of cover cardinality results in the identification of a minimum set of factors which occur many times in the network. These factors, if extracted, can significantly reduce the literal count of the logic network. Decomposition algorithms which focused on minimizing the number of product terms in binary covers were presented in the previous section. We describe modifications here which, given a two-level representation of a binary cover as a starting point, enable the selection of factors that can maximally minimize the literul count of the cover, whle producing a multilevel network. To select a good set of Boolean factors, we need the notion of the value of a Boolean factor. It is indeed very difficult to estimate the value of a Boolean factor. Strong division, being a global optimization technique, is difficult to predict. The value of a factor f in Q [ , ~ p l S , , f , l x ~ is given by

The function super( cl, c2) returns the smallest cube that contains the two argument cubes, cl and c2. The function distance( cl, c2) returns the distance between cl and c2, i.e., the number of bit positions they differ in. The algorithm above constructs a minimal set of cubes, cubeset, L? = ( 1, -1) x ( 0 , - 1) (4) whch contains the codes of all the nodes in C, but does not intersect the codes of nodes not in C. Partial-sat- where l f is the number of literals in / and 0, is the degree( ) is used in conjunction with the algorithms find- number of occurrences of f in Q’. Given the original optimal-ordering( ) and select-constraint( ) of Section two-level network P , l x k ,it can be shown that the reduction IV-B. in the number of literals by strong dividing P with f will This algorithm based on partial satisfaction of con- be > U!. Thus, the optimized multiple-valued cover prostraints is more powerful than the algorithms in [6] and duced after selection, Q’, provides a guide to the values of [12]. It provides a much better estimation of the re- the different factors. encoded cover cardinality when a limit on the number of Given this definition of the value of a factor, it remains encoding bits is placed. Typically, selecting a large number to find the values of all the factors in Q’ and select factors of inputs during the selection step produces a small multi- with the hghest values. of is easily found for any f E Q’. ple-valued cover cardinality but a large number of con- Finding l f exactly for a given f involves performing logic straints have to be satisfied. Too many bits may have to be minimization and is therefore NP-complete. However, the used to completely satisfy these constraints resulting in too algorithm partial-sat-degree( ) of Section IV can be modilarge a decomposition PLA. The algorithm proposed in fied to produce a good estimate of I, for any f E Q’. given

406

IEEE JOURNAL OF SOLID-STATE CIRCUITS, VOL.

24, NO. 2, APRIL 1989

an encoding matrix A . T h s estimation algorithm is described below: Exam.

estimate-literals( F,A ): { cubeset = foreach (node n j 3 F(i)= 1) { didmerge = FALSE; foreach (cube gj E cube) { merge = TRUE; foreach (node n k 3 F ( k ) = 0) { if (supr(@, A ( i ) @ n j ) n ( A ( k ) @ n k ) merge = FALSE; break;

5xpl 9sym Z5xuI

+;

1

#

$1 {

root sa02 sea

inp

10 1 10

65 87 63

orig. area 1560 1653 1512

8 I 5 10 I 4 41 I 35

57 58 334

1197 1392 39078

7 9 7

out

prod

S.

i. 5 4 5

area PLA-1 475 450 532

4 5 6

210 328 1332

area rat. PLA-2 544 0.65 285 0.44 544 0.71

CPU time 7.0 4.0 7.0

756 10.80 5.0 992 10.93 19.2 27846 10.74 546.1

1

if (merge) { gj = suPer(g,, A ( i ) @ n ; ) ; didmerge = TRUE;

1

1

if (!didmerge) { cubeset = cubeset U ( A ( i)@n ;);

1

1

return (number of literals in cubeset);

1 The algorithm attempts to construct a set of cubes cubeset with minimal literal count containing the codes of all the nodes in the factor F, but not intersecting the codes of the nodes F. The operator @ denotes concatenation of bit vectors. Since strong division rather than re-encoding is being performed, the selecting inputs SI remain in the decomposed network. Therefore, the nodes are concatenated with the encoding matrix A whle estimating the number of literals. Estimate-literals( ) is used in conjunction with a modification of the algorithm find-optimal-ordering( ) (Section IV-B) to select a good set of Boolean factors in P given Q'.

VI. RESULTS Decomposition results obtained on a large set of benchmark PLA's are given in Table I. The PLA's were all optimized using the logic minimizer ESPRESSO before decomposition. In the table, the number of inputs to the original PLA (inp), the number of outputs (out), the number of product terms (prod) after two-level minimization, and the area of the PLA (orig. area) are given. The number of selected inputs in decomposition (si.), the areas of the two resulting PLA's (area PLA-I and area PLA-11), the ratio of areas after and before decomposition (rat.), and the CPU seconds required for decomposition on a VAX 11/8800 are given. The numbers under the ratio column are calculated by dividing the total area of the two resulting PLA's by the area of the original PLA. As can be seen,

large reductions in areas have been obtained (some numbers are as low as 0.2). A simple timing analysis indicated that the delays of the decomposed PLA pair were smaller than those of the original PLA for all the examples. The CPU times required for decomposition are quite reasonable. The examples x7dn and seq are very large and hence require significantly more time than the other examples. A large fraction of the CPU time is expended by multiplevalued minimization during the selection and encoding phases. Typically, not all constraints corresponding to the selected inputs have been satisfied. Topological optimizations like folding are typically performed on large PLA's. It is relevant to compare the areas of the original and decomposed PLA's after folding. The decomposed PLA's are generally sparser than the original PLA and hence are more amenable to optimization. In fact, for all the examples above, the area reductions after folding (the program GENIE [4] was employed) were at least as great as those for the unfolded PLA's. For standard cell or gate-array implementations of logic, a good estimate of area is the number of literals (transistors) in the logic. The factors identified by the decomposition algorithms, described in Section V, serve as an excellent starting point for multilevel logic optimizers. This is illustrated in Table 11. For each example, the multilevel logic optimizer MIS [2] was made to execute a primarily algebraic optimization script (with two-level Boolean minimization operations). Then, selected Boolean factors were first used as strong divisors before executing the same algebraic script. The number of literals before and after optimization and the CPU time required for optimization for both algebraic and Boolean division algebraic scripts are given in Table 11. The number of strong divisors selected is also indicated (s.d.). As can be seen, in almost all cases, better or comparable results were acheved in significantly faster time using the Boolean division with an algebraic script rather than the algebraic script alone. For 3 out of 18 examples, namely, root, sa02, and vg2, worse

+

DEVADAS

et

U/. :

BOOLEAN DECOMPOSI’TION I N MULTILEVEL LOGIC OPTIMIZATION

TABLE I1 MULTILEVEL OPTIMIZATION R~suLrs

results are obtained. This is because the algebraic script is tuned to perform optimization on a two-level network rather than a network on which strong division has been performed. VII.

CONCLUSIONS

Multilevel implementations of logic can be substantially smaller and faster than corresponding two-level, i.e., programmable logic array (PLA) implementations. Work in the area of multilevel logic optimization has been concentrated primarily in the development of algebraic techniques for factoring and decomposing logic equations. In this paper, we have presented algorithms for Boolean decomposition, which can be used to decompose a PLA into a set of smaller interconnected PLA’s such that the overall area of the resulting logic network, deemed to be the sum of the areas of the constituent PLA’s, is minimized. These algorithms can also be used to identify good Boolean factors whch can be used as strong divisors during logic optimization to reduce the literal counts/area of general multilevel logic networks. Excellent results have been obtained on a wide range of examples.

REFERENCES [ l ] K. Bartlett, W. Cohen, A. J. De Geus, and G. D. Hachtel, “Synthesis and optimization of multilevel logic under timing constraints,” I E E E Trcriis. Computer-Aided Des., vol. CAD-5, pp. 582-596, Oct. 1986. [2] R. Brayton, R. Rudell, A. Sangiovanni-Vincentelli,and A. Wang, “Mis: A multiple-level logic optimization system,” I E E E Truns. Cornpuler-Aided Des., vol. CAD-6, pp. 1062-1081, Nov. 1987. [3] R. K. Brayton and C. McMullen, “The decomposition and factorization of Boolean expressions,” in Proc. Int. Symp. Circuits Sjsr.. (Rome, Italy), May 1982, pp. 49-54. [4] S. Devadas and A. R. Newton, “Topological optimization of multiple-level array logic,” I E E E Truns. Computer-Aided Des., vol. CAD-6, pp. 915-9!?, Nov. 1987. [5] D. Bostick et U / . , The boulder optimal logic design system.” in Proc. Int. Con/. Computer-Aided Des., Nov. 1987. [6] G. De Micheli et a/., “Optimal state assignment of finite state maclunes,” I E E E Truns. Cornpuler-Aided Des., vol. CAD-4, pp. 269-285, July 1985.

407

[7] J. Darringer et ul., “Logic synthesis through local transformations,” I B M J . Res. Decrelop., pp. 272-280. July 1981. [8] J. Darringer er U/., “Lss: A system for production logic synthesis.” I R M J . Res. Detielop., Sept. 1984. [9] K. Bartlett et U/., “Multi-level logic minimization using implicit don’t cares.” in Int. Conf. Computer Des.: VI.SI i n Computers, Oct. 1986. [lo] R. K Brayton et ul.. “The Yorktown silicon compiler.” in Proc. l i f t . S ~ w i p Circuit.$ . $,,st., June 1 [11] M. Hofmann, “Automated, hesis of multi-level combinational logic in cmos technology, .D. dissertation, Univ. of Calif.. Berkeley, 1985. [12] G. De Micheli, “Symbolic dcaign of combinationa!, a logic circuits implemented by two-level macros. Computer-Aided Des.. vol. CAD-5, pp. 597-616, Sept. R., Rudell and A. Sangiovanni-Vincentelli.“Multiple-valued mini[13] mization for PLA optimization,” I E E E Truiis. Computer-Aidetl Des.. vol. CAD-6, pp. 727-751, Sept. 1987. [14] T. Sasao. “PLA decomposition,” presented at the MCNC 19x7 Logic Synthesis Workshop. May 1987. [15] R. A. Wood. “A high density programmable logic array chip.” I E E E Truris. Computers. vol. C-28. pp. 602-608, Sept. 1979.

Srinivas Devadar received the H.Tech degrec in electrical engineering from the Indian Institute of Technology. Madras, in 1985 and the M.S. and Ph.D. degrees in electrical engineering from the University of California. Bcrkeley. in 19x6 and 1988, respectivclv. He is currently an Assistant Professor of Elcctrical Engineering at the Massachusetts Institute of Technology, Cambridge. His research intcrcsts are in the area of computer-aided design of VLSI circuits and systems. with emphasis on logic bynthesis. test generatioin. design for testability. and automated layout techniques.

Albert R. Wang received the B.S. degree in computer science and applied mathematics froin the University of California, San Diego, in 19x4. He is currently working towards the Ph.D. degree in the Department of Electrical Enginecring and Computer Sciences at the University of California, Berkeley. His current research interests include inultiple-level logic synthesis and optimization, multiple-level logic verification, and sequential logic synthesis and optimization.

A. Richard Newton (S’73-M’78-SM’86-F‘XX) was born in Melbourne, Australia, on July 1. 1951. He received the B.Eng. (elec.) and M.Eng. Sei. degrees from the University of Melbourne, Melbourne, Australia in 1973 and 1975. respectively, and the Ph.D. degree from the University of California, Berkeley. in 1978. He is currently a Professor and Vice Chairman of the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley. He is an Associate Editor of the IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGNOF ICAS. the Technical Program Chairman of the 1988 and 1989 ACM/IEEE Design Automation Conferences, and a consultant to a number of companies for computer-aided design of integrated circuits. His research interests include all aspects of the computer-aided design of integrated circuits, with emphasis on simulation, automated layout techniques, and design methods for VLSI integrated circuits. Dr. Newton was selected in 1987 as the national recipient of the C. Holmes McDonald Outstanding Young Professor Award of Eta Kappa Nu. He is a member of Sigma Xi.

408

IEEE JOURNAL OF SOLID-STATE CIRCUITS, VOL.

Albert0 Sangiovanni-Vincentelli (M74-SM81F’83) received the Dr. Eng. Degree (summa cum laude) from the Politecnico di Milano, Italy, in 1971. From 1971 to 1977 he was with the Instituto di Elettrotecllia ed Elettronica, Politecnico di Milano, Italy, where he held the position of Research Associate, Assistant, and Associate Professor. In 1976 he joined the Department of Electrical Engineering and Computer Sciences of the University of California at Berkeley, where he is presently a Professor. He is a consultant in the area of computeraided design to several industries. His research interests are in various aspects of computer-aided design of integrated circuits, with particular emphasis on VLSI simulation and optimization. He was Associate Editor

24, NO. 2, APRIL 1989

of the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS. and is Associate ON COMPUTER-AIDED DESIGNOF Editor of the IEEE TRANSACTIONS INTEGRATED CIRCUITS AND SYSTEMS and a member of the Large-scale Systems Committee of the IEEE Circuits and Systems Society and of the Computer-Aided Network Design (CANDE) Committee. He was the ON CIRCUITS Guest Editor of a special issue of the IEEE TRANSACTIONS AND SYSTEMS on CAD for VLSI. He was Executive Vice-president of the IEEE Circuits and Systems Society in 1983. In 1981, Dr. Sangiovanni-Vincentelli received the Distinguished Teaching Award of the University of California. At the 1982 IEEE-ACM Design Automation Conference, he was given a Best Paper and a Best Presentation Award. In 1983, he received the Guillemin-Cauer Award for the best paper published in the IEEE Transactions on CAS and CAD in 1981-1982. At the 1983 Design Automation Conference, he received a Best Paper Award. He is a member of ACM and Eta Kappa Nu.