LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN XSLUY Report No. 38k H*3?4 jyuLZh SYNTHESIS OF OPTIMAL DOUBLE-RAIL LOGIC NETWORKS USING NOR-OR GATES BY INTEGER PROGRAMMING by Coimbatore Subramanyam Chandersekaran February, 1970 Report No. 38U SYNTHESIS OF OPTIMAL DOUBLE-RAIL LOGIC NETWORKS USING NOR-OR GATES BY INTEGER PROGRAMMING * by Coimbatore Subramanyam Chandersekaran February, 1970 Department of Computer Science University of Illinois Urbana, Illinois 6l801 This work was supported in part by the National Science Foundation under Grant No. NSF GJ - 503 and submitted in partial fulfillment of the requirements for the degree of Master of Science in Electrical Engineering, February, 1970. Digitized by the Internet Archive in 2013 http://archive.org/details/synthesisofoptim384chan Ill ACKNOWLEDGEMENT The author would like to express his gratitude to his advisor, Professor S. Muroga for his guidance and encouragement during the preparation of this thesis. The author also wishes to thank Mr. C. R. Baugh for the many constructive ideas he put forth. IV TABLE OF CONTENTS Page 1. INTRODUCTION 1 2. OPTIMUM NETWORK DESIGN OF DOUBLE -RAIL LOGIC CIRCUITS USING NOR-OR GATES BY INTEGER PROGRAMMING 2 3- INTEGER PROGRAMMING AND IMPLICIT ENUMERATION k k. NOR-OR SYNTHESIS 8 5. AUGMENTATION OF VARIABLES 22 6. TABULATION OF RESULTS 28 7- CONCLUSION 35 LIST OF REFERENCES 37 APPENDICES 39 1. INTRODUCTION This report catalogs all optimal NOR-OR gate networks for three variable switching functions. The synthesis has been done by integer programming, and double rail logic realizations of all three variable functions have been obtained (a) when the available external inputs are the external variables only, and (b) when the available external inputs are the external variables and their complements. For func- tions of three variables, there exist Uo functions that represent the PN (permutation of variables, negation of a given function) equivalent classes and 10 typical functions that represent the NPN (negation of variables, permutation of variables, negation of a given function) equivalent classes. This is believed to be the first known listing of optimal NOR-OR gate networks for all three variable NPN equivalence classes of switch- ing functions. 2. OPTIMUM NETWORK DESIGN OF DOUBLE -RAIL LOGIC CIRCUITS USING NOR-OR GATES BY INTEGER PROGRAMMING This report presents the synthesis of single output, multilevel, loop-free networks of NOR-OR gates that realize an arbitrary given switching function by integer programming. A synthesis of "feed-forward" optimal logic networks using thresh- old gates by integer programming was first described in [12] [13]' A feed-forward network of NOR-OR gates is one in which all the gates are arranged according to levels and each NOR-OR gate can receive the in- puts only from the external variables x , x , ..., x or from outputs of gates at preading levels. Subsequently in [10] a somewhat different formulation was used to characterize the feed-forward network, viz., the all-interconnection network . In this formulation, interconnection between every distinct pair of gates was permitted, with the exception of the output gate which had no output interconnections to other gates. Then inequalities were added to prevent loops in the optimal network. This new network formulation considerably speeded up the network syn- thesis. By double -rail logic we mean a logic network where for every gate both the gate output and its complement are available. In con- trast to this, the situation where only one of them is available is called single-rail logic . From the above it is obvious that NOR-OR networks are double-rail logic networks. The optimal networks cataloged in this report have been synthesized assuming infinite fan-in, fan-out although fan-in, fan-out and level con- straints can very easily be incorporated into the formulation. The integer programming algorithm used for obtaining the optimal networks is the im- plicit enumeration method which is described in detail elsewhere [9] [11] • T151 Swee obtained optimal networks of NOR-OR gates for 35 out of the kO three variable functions of PN equivalence classes. By suitably changing his formulation, considerable speedup in computation time (of the order of 5 approximately) was achieved. The changes also enabled us to obtain optimal realizations for 3 of the 5 remaining functions in the PN equivalence classes. All 10 representative func- tions of NEW classes of 3 variables were synthesized using double-rail logic. 3- INTEGER PROGRAMMING AND IMPLICIT ENUMERATION In this section we outline the integer programming problem and the implicit enumeration algorithm for solving it; for details refer The mathematical theory behind the implicit enumeration scheme is outlined in [l] [5] [6] [7]» An integer programming problem with n unknown variables and m constraints is in general stated as follows: minimize c x subject to b + A x > where [c. , .... c ], c. >0 i = l, ..., n 1' n i - b= [b^ ..., b m ] A = [a. .] ij in are coefficient matrices and x = [x_, , .... x ] is an n-dimensional 1' ' n vector of variables. In this report all the x.'s assume integral value of or 1 and all coefficients assume only integer values. The implicit enumeration algorithm has been computationally proved to be one of the most efficient methods for solving this type of zero- one problem. It implicitly enumerates all the 2 solutions without explicitly and exhaustively examining all of them and picks up the best feasible solution. Let us start by defining the following: A solution is an assignment of or 1 to all the variables in x. A solution satisfying b + A x > is a feasible solution , if not, an infeasible solution . A feasible solution that minimizes c x is an optimum feasible solution . A partial solution S is defined as an assignment of binary values to a proper subset of the n variables. A variable that has not been assigned is called a free variable , a variable that has been assigned is a fixed variable . A completion of a partial solution S is a binary assignment to all free variables. We outline the implicit enumeration algorithm as it is shown in Fig. 3.1. With a given partial solution S and the incumbent solution (the feasible solution having the smallest value of the objective function obtained thus far), the block entitled "CHK-IEQ" is entered. At this point, examine whether some of the free variables must be set to 1 or if each inequality is to be satisfied. Scanning through the inequalities until no more free variables can be assigned, S with these free variables assigned becomes a new partial solution S . Next the partial solution S is checked to determine which of the following 3 cases occurs. (l) Feasible : The completion of S obtained by setting all free variables to is found to be feasible. It is compared with the incumbent and the better of the two is maintained as the incum- bent. The backtrack procedure is initiated to obtain a new partial 2 solution S by changing some of the assigned variables according to * a certain rule. * Ft 1 The backtrack procedure was first proposed by Glover . A detailed explanation can also be found in [6] [9] and will not be described in this report. Fig. 3»1 Implicit Enumeration Algorithm AGMT - VAR : Augment S on the right by j or -j, where x . is any J free variable. ca: ie Are any variables forced to or 1? Yes Augment S on the right by the forced variables with underline. CHK-IEQ Is it found that a better feasible solution than the incumbent does not exist? cannot Yes decide Is there a better feasible solution than the incumbent? Replace the incumbent by the new better feasible solution. I 'J Backtrack : Locate the right most element of S which is not underlined. If none exists, terminate; otherwise, change the sign of the element, underline it and delete all e lements to the right. (2) Infeasible : If at least one inequality is not satisfied by S whatever binary values are assigned to the free variables, then S is discarded immediately by initiating the backtrack procedure. 2 The backtrack procedure forms a new partial solution S from S . (3) Augment S : If neither of the above two cases occur, a 2 free variable is assigned to 1, forming S . The choice of this variable greatly affects the convergence and it should be made ac- cording to the type of problem being solved. 2 After replacing S with S , the entire procedure is repeated by reentering the block "CHK-IEQ. " By cycling through this procedure repeatedly, the computation results in the implicit enumeration of all possible solutions. When the computation terminates, the incumbent is the optimum solution. The checking procedure of each inequality such that one of cases (l), (2) and (3) is quickly identified is explained in [9l« The implicit enumeration algorithm converges in a finite number of steps, but the efficiency of the algorithm heavily depends on the nature of an indi- vidual problem. Our computational experience shows that tailoring the block labeled AGMT-VAR in Fig. 3«1»1 (the subroutine which augments the partial solution when (3) occurs) to a given particular problem speeds up the convergence. As an example, the computational speedup in the synthesis of NOR-OR logic networks over , was achieved by suitably modifying the block AGMT-VAR. 8 k. NOR-OR SYNTHESIS k.l NOR-OR Synthesis The NOR-OR gate is a combinational gate that provides both the logical OR and its negation (NOR) as outputs. In practice they are fabricated as ECL (emitter coupled logic) circuits as an example. These circuits possess the advantages of extremely high speed of operation (about 1 nanosecond). As a result of its characteristics the NOR-OR gate may in specific networks simply be only a NOR gate (OR output not used) or an OR gate (NOR output not used). At this point we introduce some notation. We shall assume that the network comprises of R gates, n external variables (x , . .., x ) and their complements (x , . .., x ) and unless otherwise specified realizes the function f : 2 -»• 2. Also all connections to external variables or their complements, gate outputs and interconnections between gates are also treated as variables in our formulation. v is the connection from x to the i-th gate. v, 1 is the connection from x, to the i-th gate. — k — k v. = 1 indicates that the connection stated above exists. k v. = indicates that the above connection does not exist. k v, = 1 indicates that the connection stated above exists. — k v = indicates that the above connection does not exist. — k Since only completely specified functions are considered, each input vector x = (x , ..., x ) is numbered as x J j = 1, 2, ..., 2 from x^ = (0, ..., 0) through x^ 2 ' = (l, . .., l). $., represents the connection from the OR-output of gate i to the k-th gate. (The values of are explained in the following). $., represents the connection from the NOR-output of gate i to the k-th gate. (The values of $.. are explained in the following). „ ~1K ( ' 1 P. represents the OR output value of the i-th gate for the -+(i) j-th input vector x . P. i = (1 -P. J represents the NOR output value of the i-th gate for the j-th input vector x . Let p.. ^ denote $., P. ^ + 3> (l - P.^M. lk ik i -lk i ' k.2 Characterization of NOR-OR Gate The NOR-OR gate with inputs from three external input variables x , x , x may be characterized as follows. (Subscripts of P, P", 0, t are omitted). X l x ? X 3 $P = O(l-P) P Refer Section k.2 for detailed explanation. 10 P = x ^ x^ ^ x • $P = (x ^ Xp ^ x ) = x 1 Xp x where <$> and $ are variables which specify existance of OR and NOR interconnections respectively. The value of $ and <$ determine the nature of the gate. This is explained in the following table. Table 1+.2.1 $ 4. Gate Type Outputs of gate not used 1 NOR output of gate used 1 OR output of gate used 1 1 Both NOR, OR outputs used It can be seen that $. . and . . cannot both be equal to 1, as then gate j could only have constant outputs of and 1. 0. . $. E£ ij f v f = f v f = 1 This restriction is stated as <&. 4 + 3> < 1 ij -ij - for all i ^ j. It should also be noted that and determine only the output that is to be connected. The OR output value will refer to P and the NOR output value will refer to P = 1 - P. 11 4.3 Formulation of the Problem We shall now consider the synthesis of an n variable R-gate single output network with infinite fan-in and fan-out. Such a network is first formulated as an "all-interconnection" network. An example of such a network is shown in Fig. 4.3 where the numbering of gates proceeds from the "output gate" onwards, the output gate being assigned the number 1. For multiple -output networks, given S functions f , fp, ..., f that are to be realized, it is assumed that each function is realized as the output of exactly one gate in the network and the outputs of these gates are set to the same values as the functions they realize. We shall in this report however, restrict our attention to single- output networks. Fan-in, fan-out and level constraints can be incorporated if necessary as additional inequalities in the integer program. The network to be realized is formulated as a set of inequalities with possible additional inequalities corresponding to the restrictions imposed. If a lower bound of the number of gates required for realizing a given function is known by other means, R is set to this number, otherwise R is set to 1. This problem together with its objective function is solved by the implicit enumeration scheme. If the problem has a solution for R, the solution is an optimal solution. Otherwise R is incremented by 1 and the whole process is repeated again. This procedure will terminate in a finite number of steps since the function is realizable for some R. Refer Section 4 4. for detailed explanation. -K--K- Refer Section 4.5 for detailed explanation. 1-U(l-P k (d) ) Xj—X. 1 = -L i^k (for j = 1, ..., 2 n ) ( k = 2, ..., R ). Here U is set to a sufficiently large number so that when R = 1, (2) becomes nonrestrictive and when R = 0, (k = 2, ... R) (3) becomes nonrestrictive. In the program we set Uto (R + n+ 2) to achieve the above. For the remainder of this report we will assume that U retains its above value. U. 5.2.2 Output Gate The output gate is either an OR gate or a NOR gate. To determine which of the two outputs of the output gate assumes the same value as the function to be realized for every input vector x , a variable X is introduced. K = 1 indicates that the function is realized at the NOR output, \ = indicates that the function is realized at the OR output. The inequalities for the output gate are ; for f(x) = 1 n R W 2 [v] x^ j) + v* (1-x^))] + 2 P. 1 ( « j) > 1-UX Jo = J- X— ^ 15 (5) E [v* Xi (j) + vj (1-x^^] + Z p.^) > U(l- \) and for f(x) = n R (6) z 0^ (d) + v^ (l-x^)] + e p i:l (j) l-U(l-X), yC'—.L X — tC 4. 5.2. 3 Gate Interconnections p is the input to the k-th gate from the i-th gate for the iK j-th input vector x . Algebraically this is stated as (j) = $ p _(j) + $ d.p.^")). lk lk i -ik i This must be rewritten as a set of linear inequalities. The following inequalities serve this purpose: (8) -1< -p. (j) - a + p.. (j>) - i ik ik (9) -1 < -P. ^ + - p., ^ — i ik ik (10) < p. ^ - $.. + P., ^ — l -ik ik (11) < p/«" + a - p., ^ for (i = 1, ..., R) - i -ik ik (k = 1, ..., R) k ^ i (j = l, ..., 2 n ). The inequalities described in U. 5*2.1 to U. 5*2.3 completely describe the NOR-OR network. 16 4«5»3«1 Internal Connections Between Two Gates The first additional inequality states 12) $>.. +*...< 1* (1 < i < k < R), lk -lk - — — — ' 4.5.3.2 Input Connection Condition This condition specifies first of all that every gate must have k k an input connection in at least one of v., v„, $.,> $., should be equal to 1 for k = 1, . . . , R. It also specifies that the number of input connections to a gate k plus the number of interconnections from the NOR output of this gate k to any gate j, must be greater than or equal to 2. (k = 2, ..., R and j = 1, 2, . .., R). This pre- vents the occurrence of the following type of gate which can be eliminated by connecting the input to the output. (13) I (v* + v k ) + S ( 2 - Z * i=l * I i=l lK ^ K i=l K1 i^k i^k (k,.= 2, ..., R) (lk) £ (v] + vj) + i (* n + ^) > 2 - ^ £l± -X In other words, (13) may be stated as EXTERNAL CONNECTIONS NOR OUTHJT Z( INPUTS TO) + Z(FROM ALL OTHER ) > 2 - Z( CONNECTIONS )• GATE k GATES TO GATE k FROM k TO ALL OTHER GATES r . Explained in 4.2. 17 ^.5-3-3 Output Condition (k ^ l) This condition states that every gate k (k = 2, ..., R) must have its NOR or OR output connected to at least one other gate j (j = 1, ..., R). If gate k has only one output, (15) with (13) together forces the NOR output of k to be connected to some other gate in the network. R (15) S (0^. + $ k .) > 1 (k = 2, ..., R) i=l i^k h. 5»3'^- Condition for Output Gate This condition ensures that either the OR or NOR output of gate 2 is connected to gate 1, the output gate. (16) $ 21 + $ 21 > 1 ^-♦5«3«5 Triangular Condition A The following triangular network configurations must be prevented because the outputs of gate k can be realized with two or less gates. 18 Redundant Circuits Optimal Realization ^ X f f^fVfirvh = E> E> (Connections between two gates are eliminated) b. i g J - f k fvfvcrN/h = t> O (Connections between two gates are eliminated) d. i h k j V>-Jf s, g = fg f v f g v h = f h i 19 The following inequalities impose the restriction described above. (it) (* ik +«i k ) + (*u + £i d ) + * Jk - 2 R (18) ( ° ik + **> + { % + ^^ 1 + (1 -V + 1 ± <*jj + V #k (for all i ^ j, j ^ k, i t k) 1+. 5.3.6 Triangular Condition B This condition imposes restrictions similar to triangular condition A but deals with configurations consisting of two gates and an external input variable x„. Analogous to (17) is (19 )• This inequality prevents the following network. ( J i k; i = 1, . . . , n ) Gate j is not needed in this network and is redundant. To prevent synthesis of such networks we introduce inequality (19) • (19) v i + 4 + v i + 4 < 2 -$ jk (0 i kj i = 1, ..., n) The following redundant network produces a constant output of at the NOR output and 1 at the OR output. (20) prevents the inclusion of such subnetworks in the optimal realization. 20) ^ ♦ jj ♦ vJ + ^ < 2-* Jk ♦ £ (*.. ♦ * w ) 20 R i^k (for all j ^ kj £ = 1, ..., n) x i — T^X X i' j \> 1 k V output = ^.^»3«7 Solitary OR Outputs (k ^ l) To establish a priority between the NOR and OR output interconnections of every gate, we impose the restriction that if a gate has only an OR out- put interconnection it can be eliminated (except for the output gate). A gate with only an OR output interconnection reproduces its inputs as inputs for some other gate. This could have been done by another gate which in addition has its NOR output connected to some other gate in the network and thus reduces the number of gates needed to realize a function. (21) accomplishes this purpose. R R (21) U E $.. - Z $.. > (for j = 1, ..., R) i=l -3* i=i ^ " h. 5. 3-8 Two Inputs to Each Gate (22) strengthens restriction (20) by requiring that if a gate has an OR output it must have at least two inputs. This is advanta- geous since a network containing a gate k with an OR output and only 21 a single input to k could have realized the OR output with one less connection by bypassing the gate k. This eliminates some trivial networks. For example, the first of the following two networks would be found by the integer programming approach precluding the second. no. of connections = 5 x. O -P o U ctf -H O CMS •H O -P £> H (U S C O o no. of connections = 5 The inequality stating this condition is: n 22) Z £=1 k kx R Z i=l i^k <*ik + *±J " 2 \j * ° (for k - 1, . .., R; t 4- k). Summarizing (21) and (22) characterize the priorities of input and output interconnections. The values established are: (1) A gate must have at least one output connection. (2) If it has only one output connection, then the output must be the NOR output connection. (3) If it has an OR output connection, then the gate must have a NOR output connection or at least two inputs. 22 5. AUGMENTATION OF VARIABLES During the execution of the implicit enumeration algorithm, at times with a given partial solution S, we cannot decide (a) whether there exists a better feasible completion of S, or (b) even if there are some feasible completions, there is no better feasible completion of S than the incumbent. At this stage we must then pick one of the free variables and assign 1 or to this variable, augmenting S on the right without underline. The choice of the free variable that is set is made in the block labeled AGMT-VAR in Fig. 3«1» In this section we describe in detail the procedure by which the free variable is chosen and set to 1. This choice is very important as it reduces computation time considerably. We always start with the free variable associated with the output gate (gate number l) and proceed to gates 2, 3> etc., until we reach the gate R. Ibaraki et al proposed a new AGMT-VAR scheme based on David- [1+] son*s desirability order of gates for the synthesis of networks of NOR-AND gates. In this report a modified version of this AGMT-VAR scheme is described in detail. This modified version considerably reduces the computation time of synthesis for NOR-OR networks using both single and double -rail logic. Our comparison of computation time was made against that of Swee. (Refer Section 6 this report for comparison). Fig. 5*1 is a block diagram of the modified version of the block AGMT-VAR as used in our program. 23 (e Enter AGMT-VAR D Is there anyp (J) set to 1 No Yes Yes Determine output type, gate type, network type Determine gate i with smallest number which defines network type Determine output P. j) = with smallest j that represents gate type Set =1 lk Return to CHK-IEQ Set free variable that provides most \desirable cover of P. ^ ' Fig» 5'1 Block Diagram Of AGMT-VAR 2k 5.1 Types of Covers We introduce the concept of an isolated gate. In any partial solution S for some gate i if none of the 0. . or $. . is equal to 1 (j = 1, . .., R; j ^ i), gate i is called an isolated gate * We shall first define the concept of "covering" the output P, of gate k. Assume that the NOR-output of gate k is specified to zero for the j-th input vector x . The NOR output of gate k is given by P k • I f \ = °> at least one of the inputs to gate k for the j-th input vector must be equal to 1. If this condition is satisfied we say that P, is covered , otherwise P, is uncovered. We now K K. proceed to define the following classifications of an output P, K. of the gate k for the j-th input vector x : COV; if there exist i or i such that P- k = 1 and x«^' v^ = 1 ( i ) k or (l-Xp J ) v- = 1 (i.e., covered). * (i) G : if there exist gate i such that $ = 1 and P. = * or lk 1 <&.. = 1 and P. («" = *. (G* stands for the gate i with P. ^ or P. ^ ' -lk 1 1 1 unassigned (* denotes "unassigned")) . VC ; if there exist an external input variable 1 such that x» (j) = x and v k p = * or x.^ = 1 and v^ = *. (VC* stands for the variable x.^ or x, = 1 with connection being *). * (i) - (i) GC ; if there exist gate i such that P. Vd/ or P. d/ = 1 and cor- 11 responding $., or $ , = * when the gate i is not isolated. (Gate i lk — ik with P. or P. = 1 and connection being *) . 11 GC j if there exist gate i such that P. VJ; orP/ J/ -* and corresponding $., or $ = * where the gate i is not isolated. (Gate i with P. ' = * and connection being*). NWG; if there exist gate i such that P.' J ' or P/^ = * and 11 corresponding <£>. or $. = * where the gate i is an isolated gate. '^NWG stands for new gate). 25 We now postulate a desirability order among the set of all possible classifications for any uncovered output. This choice ranges from most to least desirable cover in that order: * * * * * COV, G , VC , GC , G C , NWG. 5.2 Augment Variable Scheme At first we give a detailed description of the block AGMT-VAR that chooses the free variable which is to be set to 1. The scheme for selecting the free variable will be given in terms of output type , #- gate type and network type. Our attention is restricted to non- isolated gates only. During the execution of the implicit enumeration algorithm, some of the free variables, e.g., p., are set in the block entitled lk of the p., ^' are set. Hence after entering the block AGMT-VAR, we lk CHK-IEQ,. Also during prior progress through the block AGMT-VAR, some H< first scan all the p sequentially in the order indicated in the iK. block diagram Fig. 5.1. When the first p ., that is equal to 1 is encountered, the corresponding $., and $.. are checked in that . — ik lk order. If $ is free, it is set to 1. If, however, 3> is already — lk ' -ik set, then $.. is scanned and if $., is free it is set to 1. If both ik ik $.. and cb have already been set, the scanning of p.. is continued -ik ik rf ' to ik until the next p ., that is equal to 1 is encountered and the whole process is repeated. However, if one of either $.. or <£> can be set — ik ik -* These terms are defined later in this section. 26 to 1, the current partial solution is augmented and we reenter the block CHK-IEQ, to see whether any more variables can be assigned and underlined. Ultimately we reach a stage where for every p ... that is set IK to 1 both $ and are set. We then proceed towards a determination of output type, gate type and network type. For each of the uncovered outputs P. = of each non-isolated gate i, all possible ways of covering the output are determined. Using the desirability order defined previously, the most desirable classification is picked. This most desirable classification is called the output type . The output type for all covered outputs is COV. Among all the output types for a given gate, the least desirable output type is picked. This least desirable type is called the gate type . The network type is then defined as the least desirable gate type. The variable to be specified is determined by examining the gate which defines the network type (this being the least desirable gate type). If there exists more then one such gate, the gate with the smallest number is chosen. The output P. = that represents the gate type is then chosen. If there is more than one output with the same output type as the gate type, the output P. V,J ' with the smallest j is chosen. For example, if the gate type of gates 3 and 5 are the same as the network type, gate 3 is picked. A table describing the various types and the free variable that is set follows. Rules are also given in this table for breaking ties if they exist. 27 Type Variable Decision cov -X- G * vc -* GC NWG ik k k -I or v £ All outputs covered and the present solution is a feasible solution P-v "that is * with least i such that p. n = 1 or $,. =1 . . . ik -ik ig chosen. k k The v- or v . that is * with smallest i such that the largest number of uncovered outputs is covered is chosen. The P ±k that is *,with the least i such that p. ' = 1 and <£> = * or $ = * and gate i is not isolated is chosen. The P. k that is * with the least i such that gate i is isolated is chosen. 28 6. TABULATION OF RESULTS In this section we summarize some of the statistical relationships among the networks cataloged in Appendices 1.2, 1«3> 1«^ and 1. 5« 6.1 PN-Equi valence Classes [15] Swee synthesized optimal networks with NOR-OR gates for 35 representative functions of three variables assuming that complemented variables are not available at the network inputs. This is the case of PN-equi valence classes. (Permutation of variables and negation of a function). By employing a different formulation and by suitably modifying the implicit enumeration scheme, the average computation time per function as compared to Swee has been considerably reduced. The average computation time per function for all optimal solutions for our modified scheme was 0.75 seconds for 3 gate networks (com- pared to 1.21 seconds for Swee), 2.89 seconds for k gate networks (15.06), 19.64 seconds for 5 gate networks (102.63) and 231.15 seconds for 6 gate networks. Fig. 6.1.1 is a graph depicting average computation time against number of gates for functions belonging to PN-equi valence classes. Vertical lines in the figure indicate the fluctuation in computation time for different functions for the same number of gates. * The all-interconnection network formulation is used, while Swee used the feed-forward network formulation [10]. The scheme of augmenting variables is more sophisticated than Swee*s case. 29 Fig. 6.1.1 PN-Equivalence Classes 1000 Modified Formulation 5 6 No. of Gates 30 10.000 Fig. 6.1.2 PN-Equi valence Classes - 1000 - 100 - 10 100 500 300 1500 U00 2000 500 2500 No. of 600 Var. 000 No. of Ineq 31 Fig. 6.1.2 shows the relationship between average computation time, number of variables and number of inequalities. The fluctuation in computation time for different functions has already been indicated. 6.2 NPN-Equi valence Classes Optimal networks for all three variable functions were also synthesized using NOR-OR gates, and assuming that x., , .... x and x n , .... x are avail- 1 n 1 n able at the network inputs. This is the case of NPN-equi valence classes. All functions of three variables are classified into ten NPN-equi valence classes. The average computation time for 3 gate networks was 0.79 seconds, for k gate networks was 5.96 seconds and for 5 gate networks was 37-82 seconds. These results are graphed in Fig. 6.2. The tables on the following pages show in greater detail the relation between average computation time, number of iterations and number of gates. 32 Fig. 6.2. NPN-Equi valence Classes 5 B No. of gates 33 a. COMPUTATION TIME FOR NOR-OR NETWORKS PN-EQUIVALENCE CLASSES RESULTS OF SWEE* 3 RESULTS MODIFIED PROGRAM No. of Ave. Ave . no . Ave. Ave. feasi- comp. of iter- comp. no. R ble time ations time of fcts. per per iter- fct. fct. ations 3 5 1.21 23.92 •75 22 h 11 15.06 382.30 2.89 64.37. 5 U 102.63 ^r253.91 19.6k 363.4 6 3 - - 231.15 3,458 7 2 optimal — — # * Networks could not by synthesized due to excessive computation time; feasible solutions were obtained however. 3h NPN-EQUIVALENCE CLASSES No. of Ave. Ave. no. R feasible comp. of fcts. time per fct. iterations * 2 . 1 * 2 - - 2 1 0.15 16 3 5 0.79 22 h 3 5-96 115 5 1 37.82 6k3 Computed by hand. 35 7. CONCLUSION In this report we have demonstrated the technique of using a modified version of the implicit enumeration scheme for the synthesis of NOR-OR networks using double -rail logic. (A similar modified version of the implicit enumeration scheme has been used for NOR/AND , AND/OR gate synthesis). Thus the versatility of the integer programming approach has been displayed to handle a variety of gate types, network restrictions and objectives with minor changes in the algorithm. Optimal networks were synthesized for 38 of the 40 representative functions of the PN-equivalence classes and 10 representative functions of the NPN-classes of three variables. The computation was performed on an IBM 360/751 system using the G level Fortran IV compiler. The computation time for 38 representative functions of the PN- equivalence classes was 15 minutes, Vf seconds and for 10 represen- tative 'functions of the NPN- equivalence classes was 1 minute. In both cases the average computation time increased exponentially as the number of gates in the network increased although there was con- siderable fluctuation in computation time for different functions for the same number of gates. Computation time for functions in PN- equivalence classes ranged between .55 seconds and .^h seconds (average •75 seconds) for 3 gate networks, 2.08 seconds and k.$2 seconds for k gate networks (average 2.89 seconds), 1^.71 seconds and 28. 71 seconds for 5 gate networks (average 19.6U seconds) and 202 and 282 seconds 36 for 6 gate networks (average 231*15 seconds). For the NPN-equi valence classes the range was .7^+ seconds to .87 seconds for 3 gate networks (average .79 seconds) and k.lk to 8.80 seconds for h gate networks (average 5*96 seconds). The range of maximum to minimum computation time was 1.7 for 3 gate networks, 2.36 for k gate networks, I.96 for 5 gate networks and 1.39 for 6 gate networks for functions "belonging to PN equiva- lence classes. For the NPN-equi valence classes the ration was 1.17 for 3 gate networks and 2.10 for k gate networks. 37 [2] [3] LIST OF REFERENCES Balas, E., "An Additive Algorithm for Solving Linear Programs With Zero-one Variables," Operations Research , vol. 13, no. h, pp. 517-5^9, July-Aug., 1965. Breuer, M. A. , "implementation of Threshold Nets by Integer Linear Programming," IEEETEC, vol. EC-14, no. 6, pp. 950-952, Dec, I965. Cameron, S. H. , "The Generation of Minimal Threshold Nets by an Integer Program," IEEETEC , vol. EC-13, no. 3, pp. 299-302, June, 1964. Davidson, E. S., "An Algorithm for NAND Decomposition of Com- binational Switching Function," Ph.D. dissertation, Department of Electrical Engineering and Coordinated Science Laboratory, University of Illinois, 1968. Fleischman, B. , "Computational Experience With the Algorithm of Balas," Operations Research , vol. 15, no. 1, pp. 153-155, Jan. -Feb., 1967. [6] [7] [8] [91 [10] [11] Geoffrion, A. M. , "integer Programming by Implicit Enumeration and Balas' Method," SIAM Review , vol. 9, no. 2, pp. I78-I9O, April, I967. Glover, F. , "A Multiphase -dual Algorithm for the Zero-one Integer Programming Problem," Operations Research , vol. 13, no. 6, pp. 879- 919, Nov. -Dec, I965. Hellerman, L. , "A Catalog of Three -variable OR-invert and AND- invert Logical Circuits," IEEETEC , vol. EC-12, no. 3, pp. 198- 223, June, 1963. Ibaraki, T. , T. K. Liu, C. R. Baugh and S. Muroga, "implicit Enumeration Program for Zero-one Integer Programming, " Report no. 305, Department of Computer Science, University of Illinois, January, 1969. Ibaraki, T. , T. K. Liu, C. R. Baugh and S. Muroga, "Optimal Network Design Using NOR and NOR-AND Gates by Integer Programming," Report no. 293, Department of Computer Science, University of Illinois, January, 1969. Liu, T. K- , "A Code for Zero -one Integer Linear Programming by Implicit Enumeration," Master thesis, Department of Computer Science, University of Illinois, 1968. 38 Muroga, S. and T. Ibaraki, "Logical Design of an Optimum Network by Integer Linear Programming-Part 1, " Report no. 26k, Department of Computer Science, University of Illinois, July, 1968. [13] :ih] [15] Muroga, S. and T- Ibaraki, "Logical Design of an Optimum Network by Integer Linear Programming-Part 2," Report no. 289, Department of Computer Science, University of Illinois, December, 1968. Taniguchi, K. , N. Tokura, T. Kasami and H. Ozaki, "Logical Functions Realizable by a Planar NAND Network, " The Transactions of Electronics and Communications Engineers of Japan, vol. 51-C, no. 2, pp. 59-65> Feb., 1968. Swee, R. S., "Optimum Network Design Using NOR-OR Gates by Integer Programming," Master thesis, Department of Computer Science, University of Illinois, 1970* 39 Appendix A Tabulation of Optimal NOR-OR Networks In this section all the optimal networks for each function of three variables are listed. Table A-l lists all optimal NOR-OR networks for each function of three variables, synthesized on the assumption that complemented input variables are not available and table A-2 lists all optimal NOR-OR networks for each function of three variables obtained on the assumption that both input variables and their complements are available. The procedure for looking up the optimal network for a given function "f" is as follows. The octal number corresponding to the function is at first determined from the truth table of the function. Function x 1 x~ x value f 1 f 10 f 2 11 f 1 f k 10 1 f 110 f 6 111 f ? We then group the f. to obtain the octal number 0„0 as shown below. f 7 f 6 f 5 f k f 3 f 2 f l f °2 °1 °o This octal number designates the function "f" and hereafter is always used to identify the function. ko We now refer to the PN-equi valence class, (table A-l). If we disallow complements of input variables in the desired optimal network, or to the NPN-equi valence class; (table A-2) if we allow both input variables and their complements in the desired optimal network. Having chosen the desired table, the entry under the octal number for "f" is noted. This is a number whose last three digits represent the octal number of the function "g, " that is the representative function of the equivalence class f is in. The remaining digits give the network number of g. We illustrate this with an example. Let f = a b c The octal number of f is 2. The entry for this number in the NPN equivalence class (table A-2) is 6,376. This tells us that f is equivalent to function 376 and that the optimal network number for 376 (function g) is 6. Since 2(f) and 376(g) belong to the same NPN equivalence class, the network for 2 can be obtained from 6, (the network for g), by performing any or all of the following three operations: (a) negating function g (376) J (b) negating the variables of g; (c) permuting the variables of g. The operations to be performed can be determined by inspection. In the example f=abc g = a ^ b ^ c. At first we negate g : g = a b c. Then negate c to c to obtain f. In the network, the negation of the function is obtained by changing the output at which the function is realized from OR to NOR or NOR to OR. 1+1 In this example we therefore (1) change OR output to NOR; (2) change c to c to obtain the optimal network for f. Optimal network of g Negation of g = g Change c to c g = a v b ^ c = a b c f = a b c Tables A-l and A-2 in appendix B give a listing of the functions that have been chosen as representatives from each equiv- alence class along with details about their optimal networks viz. number of gates (total, NOR, OR, NOR/OR), number of interconnections, levels and the circuits realizing these functions. 42 Table A-l PN-Equi valence Classes 1 2 3 4 5 6 7 00 1D000 1001 2002 3D003 2002 3D003 10006 4007 10 5010 11011 4D012 7013 4DO02 7013 3016 2D252 20 2002 3D003 10006 4007 10006 4007 33351 8027 30 31275 2827U 12032 13033 12032 13033 15036 6250 40 5010 11011 1+D0I2 7013 31275 28274 12032 13033 50 27237 38236 16052 23216 26233 35232 17056 18057 60 1+DGQ.2 7013 3016 2D252 12032 13033 15036 6250 70 26233 35232 17056 18057 6D074 34230 19076 5D077 100 5010 11011 31275 28274 4D012 7013 12032 ' 13033 110 27237 38236 26233 35232 16052 23216 17056 18057 120 4D012 7013 12032 13033 3016 2D252 15036 6250 130 26233 35232 6DO7U 34230 17056 18057 19076 5D077 140 27237 38236 26233 35232 26233 35232 6D074 34230 150 1+0227 226 36207 37206 36207 37206 22203 21202 160 16052 23216 17056 18057 17056 18057 I9076 5D077 170 36207 37206 22203 21202 22203 21202 20201 9177 200 9177 20201 21202 22203 21202 22203 37206 36207 210 5D677 19076 18057 17056 18057 17056 23216 16052 220 21202 22203 37206 36207 37206 36207 226 40227 230 31+230 6D074 35232 26233 35232 26233 38236 27237 240 5DO77 19076 18057 17056 34230 6D074 35232 26233 250 6250 15036 2D252 3016 13033 12032 7013 4D012 260 18057 17056 23216 16052 35232 26233 38236 27237 270 13033 12032 7013 4D012 28274 31275 11011 5010 300 5D077 19076 3^230 6D074 18057 17056 35232 26233 310 6250 15036 13033 12032 2D252 3016 7013 4D012 320 18057 17056 35232 26233 23216 16052 38236 27237 330 13033 12032 28274 31275 7013 4D012 11011 5010 340 6250 15036 13033 12032 13033 12032 28274 31275 350 8027 33351 4007 10006 4007 10006 3D003 2002 360 2D252 3016 7013 4D012 7013 4D012 11011 5010 370 4007 10006 3D003 2002 3D003 2002 1001 1D000 ^3 Table A-2 NPN-Equi valence Classes 1 2 3 1+ 5 6 7 1D000 6376 6376 3D37^ tetf 3D 37^ 11202 7250 10 6376 11202 3D37 i + 7250 3D37^ 7250 7250 2D252 20 6376 3D37 1 + 11202 7250 11202 7250 16150 1^350 30 12201 10230 10230 825^ 10230 825^ 13152 7250 >+0 6376 11202 3D37^ 7250 12201 10230 10230 825^ 50 11202 16150 7250 1^350 10230 13152 82 5^ 7250 60 3D37^ 7250 7250 2D252 10230 825^ 13152 7250 70 10230 13152 825^ 7250 UDO7U 10230 10230 3D 37^ 100 6376 11202 12201 10230 3D37^ 7250 10230 825^ 110 11202 16150 10230 13152 7250 li+350 825^ 7250 120 31)37^ 7250 10230 82 5^ 7250 2D252 13152 7250 130 10230 13152 UDO7U 10230 825^ 7250 10230 3D37^ 1^0 11202 16150 10230 13152 10230 13152 UDO7I+ 10230 150 16150 17226 13152 16150 13152 16150 10230 11202 160 7250 1^350 825^ 7250 825^ 7250 10230 3D37^ 170 13152 16150 10230 11202 10230 11202 12201 6376 200 6376 12201 11202 10230 11202 10230 16150 13152 210 3D37^ 10230 7250 825*+ 7250 82 5*+ 1^350 7250 220 11202 10230 16150 13152 16150 13152 17226 16150 230 10230 kDO^k 13152 10230 13152 10230 16150 11202 2^0 3D37^ 10230 7250 825^ 10230 k'DO'jk 13152 10230 250 7250 13152 2D252 7250 825*+ 10230 7250 3D37^ 260 7250 825U 1^350 7250 13152 10230 16150 11202 270 825^ 10230 7250 3D37^ 10230 12201 11202 6376 300 3D37^ 10230 10230 kVOfk 7250 825*+ 13152 10230 310 7250 13152 825^ 10230 2D252 7250 7250 3D37*+ 320 7250 825^ 13152 10230 li+350 7250 16150 11202 330 825^ 10230 10230 12201 7250 3D37^ 11202 6376 3^0 7250 13152 825^ 10230 825i+ 10230 10230 12201 350 1^350 16150 7250 11202 7250 11202 3D37^ 6376 360 2D252 7250 7250 3D37^ 7250 3D 37^ 11202 6376 370 7250 11202 3237*+ 6376 3D37^ 6376 6376 1D000 hk ises Table B-l FUNC- NEGA- NET- NUM- NUM- TION TION FUNCTIONAL WORK NUMBER BER BER CODE OF NUM- OF OF OF (OC- FUNC- EXPRESSION BER GATES CON- LEV- TAL) TION TOT NOR OR NOR- OR NEC- TIONS ELS OOO 377 ID 003 37^ } ib 3D 1 1 2 1 012 365 \ ic 1+D 2 2 3 2 07 k 303 ab V ab 6D 1+ 3 1 8 3 077 300 a N/ b 5D 3 2 1 1+ 2 252 125 a 2D . 1 1 001 376 1 ibe 1 1 1 3 1 002 375 "i ibe 2 2 2 1+ 2 006 371 abc V abc 10 1+ 3 1 10 3 007 370 ab V ac 4 3 2 1 6 2 010 367 ] ibe 5 3 3 5 2 Oil 366 abc \/ abc 11 1+ 1+ 9 3 013 361+ ab V ac 7 3 3 5 3 016 361 ab v/ ac 3 2 2 k 2 027 350 ab v ac v _bc 8 1+ 3 1 9 2 032 3^5 ac V abc 12 1+ 3 1 9 3 033 3hk ac V be 13 1+ 3 1 7 3 1* 1+ 3 2 1 7 3 036 3to ab ^ ac v/ abc 15 1+ 3 1 10 3 052 325 ac V be 16 1+ 3 1 7 3 056 321 ab V be 17 1+ 3 1 8 3 057 320 _a N/ be 18 1+ 3 1 6 3 076 301 ab ^ ab V ac 19 1+ 3 1 9 3 177 200 a ^ b V c 9 1+ 3 1 6 2 201 176 abc V abc 20 5 5 12 3 202 175 abc sx abc 21 5 5 10 3 203 174 abc V ab 22 5 5 11 3 206 171 abc ^ abc V abc 37 6 6 15 3 207 170 abc ^ ab \y ac 36 6 5 1 12 3 216 161 ab ^ ac \S be 23 5 5 10 3 2k 5 5 10 1+ 25 5 5 10 1+ 226 151 _a + b + c * 227 150 ab v ac V be ^ abc 1+0 7 7 15 1+ 230 ll+7 abc V bc_ 31+ 5 5 10 1+ 232 1*5 ac v be v abc 35 5 5 11 1+ 233 Ikk ab ^ be N/ be 26 5 5 10 3 236 ll+l ac v be V ab v abc 38 6 5 1 1 13 3 39 6 5 2 2 13 3 237 1U0 be ^ a V be 27 5 5 11 3 250 127 ac V be 6 3 3 5 2 27I+ 103 ab ^ ac v ab 28 5 5 9 3 29 5 5 1 1 9 3 30 5 5 2 2 9 3 275 102 ab v ac V ab v ac 31 5 5 11 3 32 5 5 1 1 11 1+ 351 026 ab ^ ac V be ^ abc 33 5 5 15 3 h5 Appendix B Catalog of 1*4- Representative Functions of NPN-equivalence Classes Table B-2 FCT. NEGA- NO. OF NO. CODE TION FUNCTIONAL NET- CON- OF (OCT- OF WORK NOR- NEC- LEV- AL) FCT. EXPRESSION NO. TOT NOR OR OR TIONS ELS Degenerate 000 377 ID 074 303 ab ^ ab Ud 3 2 1 6 2 5D 3 3 6 2 252 125 a 2D 37^ 003 a ^ b 3D 1 1 2 1 Non-de generate 150 227 abc ^ abc v abc 16 h 3 1 12 2 152 225 ac v be v abc 13 h 3 1 1 8 3 201 176 abc ^ abc 12 3 2 1 8 2 202 175 abc ^ abc 11 3 3 7 2 226 151 a + b + c 17 5 5 16 2 18 5 4 1 16 2 230 ikf abc v be 10 3 2 1 6 2 250 127 ab ^ ac 7 2 2 k 2 25^ 123 ab ^ ac 8 3 3 '6 2 9 3 2 1 6 2 350 027 ab v ac v be 14 k 4 8 3 15 k 3 1 8 3 376 001 a v b v- c 6 1 1 3 1 1+6 Appendix C Optimal NOR-OR networks for functions of three variables assuming complements of input variables are not available. Functions with octal codes 226.227 are not included. k 7 t f o f 1 4 XI A u 1 IO A z r\ u xt A f\ o lo ( 1 £ A > (\ > 'U t- T — 1 / A Ir-J u _JL_ o z r- 1 \ r e HH ft A~^ A 3 , J /\ /\ u. A A A u """* o CO CO o O m (0 o M f ] OO o o <\j O TT O jO U o z CO u> O t lo 1 o l-o lo j . IU i-s i u XI IO > IX) A (- r ^ > f -f z A A J u IO (— r "H r> f i 1 A ! i u. L- u A 060 M . i-H o O O A o o OjO U O O T N K O J3 O o z Q - m 0> ' t IS 1 -O i f A z o > A 1 <-> UJ o lo T T 1- 1X1 o \% JnL > H L. z i l-fi Z) i A lo A A Ll. p ( |( ]i c } CO ^ jO O f- f>- ID h- O CJ CO O O O O U O jO A O O .O O U O £l O Q Q ^- oo z CO U> i i u 1 A uo /\ lo / \ IO i i z o O > U > P > Jr 1- lo As £1 IO rT 1X1 IO r z 1 i 1 r i ° z> A A A L-J u. L r ' jT o A • o o N N <0 fO T 1 O O o n O O o z O O fO • r- 48 z o O Z 3 O n I a l-O Z o I- u z z> ro ro O S 2T. O (- o z =3 fO o o z 18 * ' o lu I O Z o z 3 O IO o> A k 9 U O □ a < O o en o <-> z 3 CD C\J is O 2 (M 12 $ 50 z o 1- o z => u_ — o Z Z o h- o 2 r> u. i i I 1 ' p o z o A -Q l i 1 D L — 1 > 1 O -O /K 1 o f A / \ z > 1 1 1 * o 1 ID o u. o CX> c CM L~J U-J CM 1 u a A o sr z sf Tr £ A O U-J > i — n^ — i \& AAlK > i ' z 1 o 1 l_l 1 1 o I o A u H > Q ° o |-Q z 1 o 3 U. o r^- u CM CM A o PO w z *r 1 u 51 Appendix D Optimal NOR-OR networks for functions of three variables with both input variables and their complements are available. 52 g o 3 O Z to CLfllU loi-oo lo^io o I- <_> z 3 O z o I- u z 3) o 3 u. o o o .£ a> 53 z o h- c_> z z> Ll O z z o t- o z 3 U. -— O — z u f (?) z A o ( \ (- ff) LI u r PT z o 1 3 P n U. rV UA ID mmhihi CM III II III 1 CM o jdio i6lomj io no txou o CD z o f z © 1 • o (\ t- © JrJ u o r rr z i i 3 r^ U_ 1 u. hi sAA 10 mmhihi CM Ml Ml Ml III CM od'j iolo u i o du atom o N z Appendix E Glossary of Symbols Used 5^ Symbol (l) Internal connections Meaning . . Interconnection from the 0R- output of i-th gate to the j-th gate. If . . =1 the connection exists"? if = the connection does not exist. $. -ij P . l (j) p (J) _. 1 _ p (j) i i ik ik i -ik i Interconnection from the NOR- output of i-th gate to the. j-th gate. If . . =1 the connection exists, if $. . = the connection does not exist. OR -output value of the i-th te for the j-th input vector ff 3 NOR-output value of the i-th te for the j-th input vector & Input to the k-th gate from the i-th gate for \ the j-th input vector (x ). 2) External connections k k rpm x. t rf= i i: k-th gate. v* = I indicates that the variable x« is con- nected to the k-th gate. v = indicates that x« is not connected to gate k. Connection from x» to k-th gate v. - 1 indicates x tf is connected to gate k. v. = indicates that x„ is not £ is not con- nected to gate k. 3) Other symbols X Used to determine which of the two outputs of the out- put gate realizes the given function. \ = indicates that the function is real- ized at the OR-output. X = 1 indicates that the function is realized at the NOR-output < 55 R Number of gates in the network. n Number of external variables. U Sufficiently large positive number (U is always set to n + R + 2). f (x) Output value of a network of gates with input vector x. *** *s