LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 510.84 no. 764-7^9 aop.2 S; !. w°.Vwl*drHwn on or before the latest Date stamped below. ?IsuU in dismissal from the University. ,^,<; IIRRARY AT URBANA-CHAMPAIGN UNIVERSITY OF ILLINOiSJJBRARY^T^^^^^^^^^^^^,^— ^fjov 3 -m 'OCI 17HEC1 \ L161 — O-1096 lU, if iif/J f, yiucDCS-R- 75-768 7^/L.t< A CODE FOR DESIGNrWG OPTIMA.L NETWORKS BY IMPLICIT ENUMERATION USING THE ALL- INTERCONNECTION INEQUALITY FORMULATION (A PROGRAMMING MANUAL FOR ILLODIE-AIF) by Keith Richard Hohulin November, 1975 JHEtieRARYOFTHE JAN 16 1975 UNIVERSITY OF iluiimOIS DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS Digitized by the Internet Archive in 2013 http://archive.org/details/codefordesigning768hohu urucDCS-R-75-768 A CODE FOR DESIGNING OPTIMAL NETWORKS BY IMPLICIT ENUMERATION USING THE ALL- INTERCONNECTION INEQUALITY FORMULATION ( A PROGRAMMING MAMJAL FOR ILLODIE-AIF) by Keith Richard Hohulin November 1975 Department of Computer Science University of Illinois at Urbana- Champaign Urbana, Illinois 618OI This work was supported in part by the National Science Foundation under Grant No, GJ-U0221 and was submitted in partial fulfillment of the requirements for the Master of Science degree, June 197^. Ill ACMOWLEDGEMENT The author wishes to express his gratitude to his advisor, Professor Saburo Muroga, for his careful reading, constructive criticism, and valuable suggestions for the improvement of the original manuscript. The author also expresses his appreciation to Dr. T.K. Liu for his many hours of consultation as well as his helpful suggestions for improving the original manuscript. Finally, the author thanks R. Cutler and J.K. Hu for reading the original manuscript and providing many helpful comments. This work was supported in part by the National Science Foundation under Grant No. NSF-GJ-U0221. TABLE OF CONTENTS Page CHAPTER 1. INTRODUCTION ' 1 2. PROBLEM DESCRIPTION 6 2.1. Definitions 6 2.2. The Basic Inequalities 11 2.3. Additional Inequalities ik 2,k The Network Synthesis Problem as an Integer Programming Problem. . . . • ' o . .17 3. PROGRAM DESCRIPTION 22 k. GENERATING THE INEQUALITIES 32 4.1. Generating the Basic Inequalities » . .' 32 4.2. Generating the Additional Inequalities kO 4.3. The Order of the Inequalities kO 5. THE SCHEME FOR AGMT-VAR o ^3 6. INPUT. . 47 7. OUTPUT ,58 APPENDIX A .63 APPENDIX B „76 APPENDIX C o , 77 LIST OF REFERENCES ' 88 PROGRAM LISTING 90 CHAPTER 1 INTRODUCTION Integer programming problems in which the variables are assigned the values or 1 only are called 0-1 programming problems. The implicit enumeration method is known to be an efficient algorithm for solving 0-1 problems. ILLIP (iLLinois Integer Programming Code) was developed by T. Ibaraki, C.R. Baugh, T.K. Liu and S. Muroga [k] to solve general 0-1 problems. A programming manual for ILLIP (which was coded by T.K. Liu and C.R. Baugh) was written by T.K. Liu [6]. The problem of designing optimal networks was successfully solved by S. Muroga, T. Ibaraki, C.R. Baugh and T.K. Liu [l],[i|],[5],[8],[9],[lO],[ll] by tailoring ILLIP to the network syn- thesis problem. This approach allows optimal networks to be designed under arbitrary constraints within a reasonable computation time. This report is a programming manual for ILLODIE-AIF (iLlinois LOgical Design by Implicit Eniimeration using the All- interconnection Inequality Formulation) - a FORTRAN IV computer program (coded by T.K. Liu and the author) which uses the basic algorithm of ILLIP but is designed specifically for solving network synthesis problems. Details of the algorithm used in ILLODIE-AIF can be found in [l],[U] Let all of the gates in a network be arranged in a line with the output gate (one of the output gates in the case of a multiple output net- work) on the far right. If each gate in the network. can have as its inputs only the outputs of the preceeding gates on its left as well as the connec- f tlons of the external variables, then the network is called a feed-forward The external variables are the variables of the switching function which the network realizes at its output. The term "variables" without the adjective "external" refers to the unknowns in the inequality formulation of the network synthesis problem (see Chapter 2). network . When a function is given to be realized, ILLODIE-AIF synthesizes feed-forward networks using the all- interconnect ion inequality formulation which permits an interconnection between every pair of gates (see [l] for details of the all- interconnect ion formulation). Since this formulation could easily derive networks with loops, a special subroutine to prohibit loops has been incorporated into the program. The use of the all-inter- connection inequality formulation reduces the computation time by precluding a large number of partial solutions which are equivalent to each other except for permutations of the gates [l] . One attractive feature of ILLODIE-AIF is its flexibility which is achieved through the inequality formulation. First, network synthesis prob- lems with different gate types can be solved by using inequalities which characterize networks of the desired types. ILLODIE-AIF can synthesize net- works with only one gate type (e.g., NOR networks) as well as networks with mixed gate types (e.g., networks with a, mixture of AND gates and OR gates). The notation ANP/OR will be used to denote networks with a mixture of AND gates and OR gates. Networks with a mixture of gate types should not be confused with networks such as ECL networks in which the output gate realizes both the NOR and OR functions. Second, arbitrary constraints can be specified for the networks. For example, a maximum value for the fan- in and/or fan- out of each gate can be specified, or the maximum number of levels in the networks can be restricted. These arbitrary constraints are usually in- corporated into the program as additional inequalities. However, it is sometimes convenient to implement restrictions on the networks by writing a special subroutine. For example, inequalities could be included to prevent loops in the networks synthesized by ILLODIE-AIF, but it is more practical to use the special subroutine mentioned above. The user of ILLODIE-AIF specifies the number of gates the networks are to contain. This value remains constant throughout the computation and ILLODIE-AIF finds all the networks which have a minimum number of inter- connections for the specified number of gates subject to any arbitrary con- straints provided in the additional inequalities. The usual design objective is to find all networks for a given function which have first the minimum number of gates and second the minimum number of interconnections. To achieve this objective using ILLODIE-AIF, the user must eventually specify the min- imum value for the number of gates. A procedure for determining this min- imum value for the number of gates is discussed in section 2.k. The network synthesis problem has the following characteristics: the number of inequalities is larger than the number of variables; the coefficient matrix of the inequalities is very sparse; and most of the non- zero coefficients are -1 or 1. For example, for an 8 gate NOR network which is to realize a function of three external variables, the number of inequal- ities is 1,5^6, the number of variables is 592 and the number of non-zero coefficients is 9^683 (1"^). In general, as the number of gates and/or external variables increases, the difference between the number of inequal- ities and the number of variables increases and the percentage of non-zero coefficients decreases. The use of the following programming gimmicks helps to improve the + speed of the program. The non-zero coefficients of the inequalities are stored in memory both rowwise and columnwise so that each coefficient can Pseudo-underlining (discussed in [h] ) is not used in ILLODIE-AIF. be fetched efficiently. The concepts of the maximum sum and the minimum sum of each inequality (see Chapter 3) are used to improve the rate of con- vergence of the algorithm. The time required to check the inequalities for the various conditions which arise during the computation is reduced throiogh the use of chain checking (see Chapter 3)» Chapter 2 of this report contains algebraic descriptions of the inequalities which characterize the networks for a given switching function. It also discusses the integer programming formulation of the network synthesis problem and establishes the correspondence between the integer programming formulation and the algebraic inequalities. Chapter 3 gives a summary of the functions of the main subroutines in the program. Chapter k describes GEN-IEQ, the subroutine which generates the inequalities. Network synthesis problems with different gate types can be solved using ILLODIE-AIF by simply changing the inequalities. Four different versions of GEN-IEQ, have been developed which allows the user a degree of flexibility in that NOR, NOR/NAND, NOR/AND, and AND/OR network synthesis problems can be solved by using the appropriate subroutine. In each case additional inequalities which reflect special properties of the gate types being used are also generated. The use of additional inequalities increases the complexity of GEN-IEQ, but it also reduces the computation time [71- Chapter 5 contains a discussion of AGMT-VAR, the subroutine which assigns a value of or 1 to a variable (a free variable in the terminology of the implicit enumeration method). The method used in AGMT-VAR is a modified version of the method described by Davidson [2],[13]. Chapters 6 and 7 provide the necessary information for anyone who wants to use ILLODIE-AIF to solve network synthesis problems. Chapter 6 gives a complete description of the input data cards for the program. Both the format and the interpretation of the printed and punched output from the program are discussed in Chapter 7' Appendix A gives a complete example and Appendix C gives a thorough discussion of the additional inequalities in the current version of the program. Appendix B contains a summary of the parameters and variables used in the algebraic descriptions of the inequalities and additional inequalities given in Chapter 2, Chapter k, Appendix A and Appendix C. Table 1.1 shovrs the number of FORTRAN instructions in ILLODIE-AIF for each of the four versions of GEN-IEQ as well as the amount of core storage required to run the program. VERSION OF NUMBER OF INSTRUCTIONS BYTES OF CORE STORAGE STORED GEN-IEQ GEN-IEQ TOTAL PROGRAM DATA TOTAL NOR 327 2135 67K 266k 33 3K nor/and 373 2181 74k 266K 340K nor/nand ^06 2214 74k 266k 34ok and/or 29k 2102 72K 266k 338k Table 1.1. The Number of Instructions and Core Requirement for ILLODIE-AIF. CHAPTER 2 PROBLEM DESCRIPTION 2.1. Definitions Suppose a network has R gates and n external variables x, , Xp, . . . , X . ILLODIE-AIF was written to design networks which have o.ompletely speci- + — » fied output functions, and thus all of the 2 possible input vectors x = (x^ , X , ..., X ) must be considered. Each of the input vectors x is numbered as x^'^^ (j- 1, 2, 3, ..., r = 2^) from x^"'"^ = (0, 0, ..., O) through x^^^ = (l, 1^ •-') l)' Let w represent the connection from external variable x to gate k and, if the complements of the external variables are available, k — k let V represent the connection from external variable x, to gate k. If w. (or V, ) =1, the connection exists. If w (or v , ) =0, the connection does not exist. Let the interconnection from the i-th gate to the k-th gate be denoted by a., . The interconnection exists if a., =1 and does not exist if ^ ik ik a. =0. Let P. denote the output value of the i-th gate when the external variables connected to the network assume the values of input vector x^"^ . Finally, let P-^ = ol ^^K (p|^^ = 1 when the output of gate i is 1 for input vector x and there is a connection from gate i to gate k. 3-^ = when either the output of gate i is for input vector x or gate i is not connected to gate k or both. ) A summary of the notations used in this paper is given in Appendix B. It is possible, though somewhat cumbersome, to change ILLODIE-AIF so that networks which have incompletely specified output functions can be designed. The variables defined above are sufficient for describing the in- equalities which characterize networks which consist of only one gate type (e.g., NOR gate networks). However, to describe the inequalities for net- works which consist of two types of gates, two additional definitions are necessary. First, let A., represent the type of the i-th gate. For NOR/AND and NOR/NAKD networks X.. = 1 if the i-th gate is a NOR gate and X. = if the i-th gate is an AND or NAND gate. For AND/OR networks X. = 1 if gate i is an OR gate and X. = if gate i is an AND gate. Second, let 7.P = cc (l-P. ). The motivation for defining the 7., is given in section 2.2. ^ 1 ^ ik The basic configuration of a feed -forward network which realizes some switching function f(x) is shown in Fig. 2.1.1 in terms of the w, v and a variables defined above. Networks with loops cannot be derived using this configuration because there are no a variables to represent the connections from the output of each gate to the gates on its left. Fig. 2ol.2 shows the all-interconnection formulation of a network in terms of the w, v and Oi variables. In this formulation there is an ex variable to represent the connection from each gate (including the output gate) to all of the other gates. ILLODIE-AIF uses the all-interconnection formulation but derives only feed-forward networks by using a subroutine called PHTLP (see Chapter 3) to prohibit any loops which could be formed. The a variables which represent the connections from the output gate to all of the other gates in the network could be eliminated from the all -interconnect ion formulation since PHTLP will automatically set them to zero. However, these o; variables are included for uniformity. Similarly, the P, P and 7 variables correspond- ing to the output gate could be eliminated, but are included for uniformity. 8 Figure 2.1.1. A Feed-forward Network (Gates 3 through R-2 are not explicitly shown. ) OO 10 I fo CO s o^ ^ — ^ y*^^ o .'■^s H H H K pq H « 1 Erf W < K K C K K « a M c C K CM ^—^ V ' J g P^ ^w-^ K « 5 B < K C C S g> OJ CVJ p. S o X M H CO C "K c -St- c EH FH CO CM •H OJ •H OJ fxT •\ •\ •s i ga « c K C K K « cc; « • K K cc o •\ »» •\ •v •\ •^ •\ • •\ »\ • •v •\ *\ • ^ ; • • • • • • • • •% • • •» • • • w CO g i • • • • • • . en . on • • . m ^ p •\ •v •\ •\ *v •^ •\ »> •\ •v •^, •\ •\ •^ -v H O CQ O) C\J CM CVJ OJ CM CVJ CM OJ CM OJ CM CM CM OJ < H H H H r-\ H X H H •n »v •s, H H H H H H 1 II II II II II II -su II II II II II II II II ^ -P ^ -P ^ -H -H ■H "^ M -H -o ^ X —I •'-i Ci4 CO og h" "h 1 'h s CC pq i 1 K «_ o pq ej] pc; « pc; « V — « M PQ J— 1 c C •^ — • K PC ^ 1^ 1 i «r H C CM H C5 H ^ O O g CO ) « c « C « C < as CM CM CM § H •v •\ H 1 . »> H 1 o « H K d K C K . : K PC K PC • • F-H O « • 1 • • • • 1 CO o •\ •% •\ •s •\ >v •\ • •v •\ « p pq CO a . « « • •s 1 • • *\ • , •s. W S K • . • • . CXI 1 • "^ . CM • . CvJ w CO H • • • • • + ! . n~) • + en • . + cn h & X X X P>H P •\ •n •\ »\ •v ' •^ •v *» *> •^ •^ •\ o O CO C\J OJ OJ CVJ OJ •^ ro CM OJ »> CO CM CM •V CM H H H H CO W P ] •n •n •\ •v •^ + •V •s ♦v -|- •% •v >v + -v > 9 S H H H H H >J OJ H r-\ M <-{ H H ^ H II II II II II II II II II II II II II li II f M -P ^ +3 X -H •H -o X -H -rs X3 ,^ •H -r-a CO 1 <.»— ^ •— ^v ^^"*v ;y •r-3 •ro X •>-0>:J pq 15 ^>^ d" -P.-'^ — ' -H ca ^ <: • , • • • • • > H CM ro 1 UA VD l>- n Table 2.1.1 shows the range of values for the subscripts and superscripts of the variables defined above for both the basic feed-forward configuration and the all-interconnection formulation. 2.2. The Basic Inequalities The inequalities discussed in this section are called basic inequal- ities because they completely characterize the networks which are to be designed. A complete description of the basic inequalities for a network with R NOR gates is given below. Also, some of the basic inequalities for a NOR/NAND network are used to explain the motivation for the 7 variables defined in section 2.1. Complete discussions of the basic inequalities for NOR/AM), NOR/NAND, and AND/ OR networks are given in [l],[5] and [12], respectively. Using the definitions given in section 2.1, inequalities characterizing all- interconnection formulation networks with R NOR gates are described as follows (assuming the complements of the external variables are not available): . T t t . T "^ik - k t=l 1=1 :/k (2.1) - Z w^ xi^^ - Z ^^.P >0 - U(l-R^^*b , T t t . , ik — k t=l 1=1 k = 1, 2, 3, • • • > R n J ~ -L^ <— f j, •••^ ■^ ~ '— • 12 Here U is a positive number large enough so that the upper inequality is non- restrictive (always satisfied) if P} = 1 and the lower inequality is non- K. restrictive if p} = 0. The first summation in each inequality of (2.1) gives the number of external variables which are connected to gate k and are equal to 1 for input vector x^*^ . Likewise, the second summation counts the number of gates which are connected to gate k and have outputs equal to 1 for input vector x . If P/; = 0, the first inequality requires that the value of one of the summations must be greater than 0. (For a NOR gate to have its output equal to 0, it must have at least one input equal to _, the second inequality requires that the value of both sum- K. 1. ) If p^^ ^ = 1, mations be 0. (A NOR gate must have all inputs to have a 1 output.) Inequalities (2.1) characterize all of the gates in the network. Of course the values of P '^ (j = 1, 2, 3, . . . , r = 2 ) (i.e., the values of the output gate) are the values of the switching function f(x) realized by the network. Since the values of P are known, it is actually not necessary to include both inequalities for the output gate for each value of j. That is, the range of values for k in (2.1) could be changed to k = 2, 3j '-•} R and the output gate could be represented by the inequality or n R Z w^ xp^ + Z ^[\^ > 1 if f(x^'^'^) = {v[^^ = 0) t=l ^ ^ i:.2 ^-^ ^ - Z wj x^^^ - Z p[^^ > if f(x^'^'^) = 1 (Pp^ = 1) for j =1, 2, 3, ..., 2^. Thus, using inequalities (2.1) for the output gate includes 2 unnecessary inequalities, but the uniformity of (2.1) makes 13 subroutine GEN-IEQ, simpler. To complete the basic inequalities for an R gate NOR network, the non-linear relation 3.!^ = o; P. is represented by the following IK iK 1 linear inequalities:: -Pr^ - a., + ^:P > -1 X ik ik — Fr^ + a., -2^)p > 1 ik ik — (2.2) i =1, 2, 3^ • • • ^ R k = 1, 2, 3, ..., R(i?^k) j = 1, ?, 3, ..., r = 2"". The following example illustrates the use of the 7.^ • For a IK NOR/NAND network one set of inequalities for a NAM) gate is of the form n R z w^ (1-x^^^) + z a.^ (i-ppb > 1 - u(i-p^^h - u K^ t=l i=l - E w^ (l-x|J') - E a.^ d-Pp')) > - UPj^J) - U X^ t=l 1=1 k =. 1, 2, 3, ..., R 3 ~ -^f '-) iy '''} r = c: (2.3) n Using the 7.^ variables defined in section 2.1, these inequalities can be rewritten as n R Z w!^xp^+ Z 7^i^ > 1 - U(l-P^^^) - U A. (2.U) t=l "^ ^ i=l ^^ ~ ^ ^ -A lU t=l 1=1 k = 1, 2, 3, ..., R i = 1, 2, 3, '.., T = 2^ since xp^ = (1-xf^^). t t Inequalities (2.3) could be implemented directly. However, in the subroutine AGMT-VAR, which is discussed in Chapters 3 and 5^ it is convenient to have all the inequalities in the form of (2.1). For inequalities (2.1) AGMT-VAR searches for aw, v or 3 variable which has not been assigned a value and assigns a value to the variable it selects. Using inequalities (2.U) rather than inequalities (2. 3) allows AGMT-VAR to treat the 7 variables in the same manner as the 3 variables of (2.1). 2.3. Additional Inequalities Unlike the basic inequalities of section 2.2, the additional in- equalities described below are not essential for characterizing a network o Instead, additional inequalities reflect special properties of certain net- work configurations as well as special properties of the gate types being used. These inequalities are usually effective in reducing the computation time [7]. It should be noted that it may be necessary to modify or delete some of the additional inequalities described in this section if other additional inequalities such as those for fan- in and /or fan-out restrictions are added (see the discussion at the end of Appendix C). The following discussion describes the additional inequalities for 15 a single output NOR network with R gates where gate 1 is the output gate [l]. The network is to realize a function of n external variables (x , x , ..., X ), and it is assumed that the complements of the external variables are not available. In each case the verbal description is followed by an algebraic description which is given in terms of the w. and a., « (l) Each NOR gate except the output gate must have at least one input from the external variables or at least two inputs from the other gates. n R 2 E W , + Z a., > 2 t=l 1=1 k = 2, 3, , R i^k (2) If three NOR gates in a network are connected as shown in Fig. 2,3.1> then it can be proven that the network is not optimal. Inequalities which prohibit triangular connections no other output connections Figure 2.3.1. Triangular Connection of Three NOR Gates, ^ A complete discussion of the additional inequalities for NOR, NOR/AND, NOR/NAND and AND/OR networks is given in Appendix C. 16 are given by i = 1, 2, . . . , R J = 1, 2, ' ' ' > R k = 1, 2, ' ' ' y R i ^ J ^k. This property is true even if NOR gate i is replaced by external variable x. . 1 -"i - ^i - ^Ok ^ £ ^Ji > -2 i/k J — ^} '- ) • • ' ) R k = 1, 2, ..., R i - 1, 2, ..., n (3) All NOR gates except the output gate connect to at least one other gate. R Z Q; . >1 k ^ 2, 3, ..., R 3=1 ^ (h) All NOR gates which are connected to the output gat( are not connected to any other gate. 17 R -U a. ^ - z a > -U i = 2, 3, . . . , R ^^ k=2 ^^ ~ Mi U is a positive integer large enough so that the inequality becomes non-restrictive if a. ^ = 0. il 2.U. The Network Synthesis Problem as an Integer Programming Problem Any 0-1 programming problem can be defined as: minimize c z subject to b + A z > 0. (2.5) Here c = (c^ , c , ..., c ) is an N-dimensional row vector; z = (z , z , ••., z,^) is an N-dimensional column vector; b = (b, , b^, • • • » b ) is an m-dimen- N J \ jL' 2' ' m sional column vector; A = [a. .] is an m x N matrix; and is the m-dimensional column vector whose entries are all zero. The variables z for t =1, 2, •••, N can assume the values or 1 only. Any assignment of or 1 to all of the variables z. is called a solution , and any solution that satisfies b + A z > is called a feasible solution . Otherwise a solution is said to be infeasible . An optimal solution is a feasible solution which minimizes c z. If no feasible solution exists, the problem is called infeasible . Any assignment of or 1 to part of the variables is called a partial solution. The variables which have been set to or 1 in a partial solution are called fixed variables while the remaining variables are called free variables . For the network synthesis problem each z variable uniquely represents a w, V, a, V, p, X. or 7 variable (defined in section 2.1). The objective 18 function c z represents the interconnections in the network. The intercon- nections include both the connections from the external variables to the gates and the connections among gates and can be represented by R n . R n . R R Z L wi + L L vi + L Z a (2.6) j=l t=l 0=1 t=l ^ i=l k=l "^ Mi for a network with n external variables and R gates. Values can be assigned to the coefficients c. of the objective function c z by comparing the inner product c z with expression (2.6). That is, c. = 1 if z. represents a w, v or a variable and c. = if z. represents a P, p, A. or 7 variable. Finally, the basic and additional inequalities described in sections 2.2 and 2.3, respectively, are represented by expression (2.5)- The coefficients of the variables and the constants in the expressions for the basic and additional inequalities determine the values of the a. . and b in (2.5). ij k ILLODIE-AIF is usually used to obtain networks which have first a minimum number of gates and second a minimum number of interconnections. By minimizing c z under the constraints b + A z > which are formed under the assumption that the networks have R gates, ILLODIE-AIF obtains the net- work (or networks) with R gates which have a minimum number of interconnec- tions assuming a feasible solution exists. Thus, to achieve the desired objective, it is necessary to find the smallest value of R for which a feasi- ble solution exists. This value of R can be found as follows: begin ^-rlth an initial value for R and solve (2.5). If there is no feasible solution, set R to R + 1 and solve (2.5) again. Repeat this procedure until a feasible solution is obtained. If a feasible solution is found when (2.5) is solved with the initial value of R, then set R to R-1 and solve (2.5) again. Repeat 19 this procedure until (2.5) becomes infeasible. Since the computation time for ILLODIE-AIF increases exponentially (roughly speaking) as R increases, it is in the best interest of the user to specify an initial value of R which is too small rather than too large. That is, if R is the smallest value of R for which a feasible solution exists, the computation time for values of R smaller than R is much shorter than the computation time for R , and the computation time for values of R greater than R^ is much longer than the computation time for R . The manner in which the w, v, a, P, p, \ and 7 variables are re- presented by the z variables is indicated by the following example. Assume the network to be synthesized is to realize a two variable function f(x). Assume also that the complements of the external variables are available as inputs to the network, that the network can have two gate types (e.g., NOR/AND), and that R = 3 is being used as an initial value. Table 2.U.1 shows the sub- scripts i of the variables z. which represent the w, v, a, P, 3, \ and 7 variables. For this example N = 8I. If the assumption that the complements of the external variables are available is removed. Table 2.^.1 (b) is elim- inated and the subscripts of the z. are changed accordingly (3-,p becomes z , a becomes z , etc.; and N = 75). On the other hand, if the network is to have only one gate type (e.g., NOR), both (f) and (g) are eliminated from Table 2.4.1 and N =: ^h. Finally, if the complements of the external variables are not available and the network is to have only one gate type, (b), (f) and (g) are eliminated from Table 2.U.1; 3 becomes z , a becomes z , etc.; and N - kQ. 20 (a) (b) X"^ \ 1 2 1 1 2 2 3 J+ < 5 6 X"^ \ 1 2 1 7 8 2 9 10 ^^ 11 12 (c) (d) 1 1 2 3 h ^12 13 lu 15 16 o(j) ^13 17 18 19 20 ^21 21 22 23 21+ o(j) ^23 25 26 27 28 ^31 29 30 31 32 ^32 33 3h 35 36 1 1 2 3 ^ ■)f* 37 38 «2k 39 ^Hf 1+0 ^3k i+1 1+2 ■x-x- Table 2.1+.1. The Subscripts of the z Variables 21 (e) X 1 2 3 h p(j) ^1 ^3 kk ^5 kG 2 hi kQ h9 50 p(j) 3 51 52 53 5i+ (f) X 1 2 3 ^. 55 56 57 (g) \ 1 2 3 k ^12 58 59 60 61 ^13 62 63 6i| 65 ^21 66 67 68 69 ^23 70 71 72 73 ^31 7^+ 75 76 77 ^32 78 79 80 81 Table 2.4.1. The Subscripts of the z Variables (continued) 22 CHAPTER 3 PROGRAM DESCRIPTION The program for ILLODIE-AIF consists of twenty seven subroutines, but they can be grouped logically into the following seven main subroutines: INIT (iNITialize), GEN-IEQ (GENerate - InEQualities), CHK-IEQ (CHecK - In- Egualities), AGMT-VAR (AuGMenT - VARiable), BCKTRK (B aCKTR acK), CHNGMM (CHaNGe Maximum sum and Minimum sum), and PHTLP (ProHibiT LooP). Fig. 3*1 shows the linkage between these subroutines. Arrows which originate and terminate at the same subroutine represent FORTRAN IV subroutine CALL statements. That is, subroutine CHNGMM is called by subroutines AGMT-VAR, CHK-IEQ, and BCKTRK and will return to the subroutine from which it was called when its computa- tion is completed. Similarly, PHTLP is called by CHNGMM. Arrows which orig- inate at one subroutine and terminate at another represent a more general kind of program flow. For example, the program flow between subroutines CHK-IEQ, AGMT-VAR and BCKTRK is controlled by a subroutine called GEOF (not shown in Fig. 3.1)' The remainder of this chapter contains a brief descrip- tion of each of the seven main subroutines. 1. INIT This subroutine initializes several program parameters after reading the problem parameter card (see Chapter 6). Then INIT does one of the following (depending upon the value of one of the parameters): (a) If the program is to generate the objective function and the inequalities, INIT transfers to GEN-IEQ. GEN-IEQ generates the objective function, and GEN-IEQ and INIT work together to 2? GEN-IEQ 1 1 \ 1 INIT -- 1 i r I CHK-IEQ, ^ / i I A(^T-VAR v_y BCIdRK 3 CHNGMM C J I PHTLP Figure 3.1. Linkage Between Main Subroutines 2U generate the inequalities (see Chapter h) . (b) If the objective function and inequalities are provided on cards, INIT reads the objective function first and then the inequalities. The inequalities are read one at a time, expanded if necessary and properly stored. INIT also generates the initial partial solution which consists of the following two parts (depending on what the user provides): (a) The P variables for the output gate (P|^^ for j =1, 2, 3, ..., 2 ) which are assigned values according to the values of the switching function f(x). (b) Any variables to which the user wants to assign specific values (either or l). Part (a) is always included in the initial partial solution while part (b) is optional. All variables in the initial partial solution are underlined. If a variable z in a partial solution is underlined, then the partial solution in which z, is assigned the opposite value need not be considered. 2. GEN-IEQ Since the number of inequalities in most network synthesis problems i is large, it is impractical to punch the inequalities on cards. For this reason subroutines called GEN-IEQ, were developed to generate the inequalities. The concept of underlining was first discussed in [3]« Statistics on the number of inequalities for NOR and NOR/ AND network synthe- sis problems can be found in [l]. Similar statistics for NOR/NAND problems are given in [5] . 25 Chapter k of this report will discuss in greater detail how the inequalities are generated. GEN-IEQ, is also used to generate the objective function, cz. 3. CHK-IEQ Whenever a new partial solution is formed, CHK-IEQ will check the inequalities to determine whether any free variables must be set to or 1 in order to satisfy some inequality. If any such free variable is found, it will be set to the required value and underlined. If a fixed variable in a partial solution is underlined, then during backtrack the opposite value of this variable need not be assigned. However, it is usually not necessary to check all of the inequalities each time a new free variable is fixed. That is, at any point in the sequence of partial solutions, some inequalities may be such that they will always be satisfied regardless of which free variables are fixed. To make use of this fact, a method called chain checking is used based on the array CLSP. CLSP(l) consists of the row number of the next in- equality to be checked after the I-th inequality is checked. If the I-th inequality is not in the chain, then CLSP(l) = 0. Thus the non-zero entries of CLSP form a chain of the row numbers of the inequalities which must be checked. The remainder of this section describes how CHK-IEQ checks an in- equality. Assume a partial solution, F, is given byF = (d. , d. , ..., d. } ^1 ^2 ^k where d. is the binary value (0 or l) assigned to fixed variable z. for j = j , j , ..., j . Some of the z. may be underlined which is denoted by d . . Let ^ k J —J W be the set of the remaining free variables. To faciliate the discussion of CHK-IEQ,, the following three vectors are defined. 26 (a) Partial sum: y(F) = (y^(F) , y2(F), ..., yj^)) where y. (f) = "b + Z a. . d. for i = 1, 2, . . . , m. z.€F ^^ ^ J The notation Z means that the summation is taken over all z.€F J fixed variables. (b) Maximum sum: u(f) = (u (F), u (F), ..., u (F)) where u. (f) =b.+ L a..d.+ L a.. ^ z.eF ^J J z.ew ^J J 3 a. .>0 y. (f) + Z a. . for i = 1, 2, m. Z.€W ^«^ J a. .>0 The notation Z means that the summation is taken over z.€W a. .>0 all free variables with positive coefficients, (c) Minimum sum: 1(F) = (i^(F), i^iT) , ..., I (f)) where i. (F) = y, (F) + Z a. . for i = 1, 2, . . . , m. z.ew ^ a. .<0 The notation Z means that the summation is taken over z.ew J a. .<0 ij all free variables with negative coefficients. Thus u. (F) is the maximum value that the left hand side of the i-th inequali- ty can achieve for all solutions which contain F. Similarly, i. (F) is the minimum value. If the i-th inequality needs to be checked (i.e., CLSP(l) ^ O), 27 then CHK-IEQ, will do one of the following depending on the value of u. (F) [h] . (a) If u. (F) < 0, then no feasible solution containing F exists. The program wi.lJL backtrack by transferring to BCKTRK. (b) If u. (F) - 0, then all free variables with negative coefficients in the i-th inequality are set to zero and underlined; and all free variables with positive coefficients in the i-th inequality are set to one and underlined. (c) If u. (f) > 0; then, for all free variables z. which have co- efficients satisfying ja..] >u.(F), CHK-IEQ will either set z. to one (if a. . > O) or set z. to zero (if a. . < O) and under- line it. In (b) and (c) above the program also compares the value of the objective function for the current partial solution, F, with the current upper bound on c z . If the bound is exceeded, the program transfers to BCKTRK. The vectors u(F) and i(F) must be updated each time a free variable is fixed. If u. (F) changes for some i, i is added to the end of the chain of inequalities to be checked because the i-th inequality must be checked. All of the inequalities in the chain are repeatedly checked until one of the following occurs: (a) u. (f) < for some i. In this case there can be no feasible solutions which contain F so the program transfers to BCKTRK. (b) A feasible solution is found. The feasible solution is print- ed only if the value of the objective function, c z, for the feasible solution is less than or equal to ZMAK where ZMAX is the current upper bound on c z . The program then transfers to BCKTRK. 28 (c) No more free variables can be fixed by CHK-IEQ, so the program enters AGMT-VAR. k. AGMT-VAR When CHK-IEQ, cannot fix any more free variables, the program enters AGMT-VAR. AGMT-VAR does one of the following: (a) If all of the variables are fixed, a feasible solution has been found. As before, the feasible solution will be printed if it gives c z a value less than or equal to ZMAX where ZMAX is the current upper bound on cz. The program then transfers to BCKTRK. (b) One free variable, say z., is fixed according to the scheme discussed in Chapter 5« The program transfers back to CHK-IEQ, to check the inequalities for the new partial solution which is the previous partial solution plus z.. (c) If no free variable can be fixed by the scheme discussed in Chapter 5^ then there are no feasible solutions which contain the current partial solution. The program transfers to BCKTRK. 5. BCKTRK When AGMT-VAR or CHK-IEQ either finds a feasible solution or dis- covers that no feasible solution exists containing the current partial so- lution, the program enters BCKTRK in order to generate a new partial solution. The program returns to CHK-IEQ after the new partial solution is generated by the backtrack scheme described below. This backtrack scheme guarantees that all possible solutions will be implicitly enumerated [3]. To facilitate the description of the backtrack scheme let us 29 describe how a partial solution is stored in ILLODIE-AIF. Two arrays, X and XS, are used to represent a partial solution. X indicates what value has been assigned to each fixed variable and XS indicates whether or not each fixed variable has been underlined. Initially X and XS are empty. When the I-th free variable is fixed, X(l) and XS(l) are assigned the corresponding sub- script with the proper sign. X(l) = J means that z was set to 1 while X(l) = -J means that z was set to 0. Similarly, XS(l) = J means that z was not underlined while XS(l) = -J indicates that z was underlined. For example, J if the current partial solution is given by F = (3^-^^ 2}), then X = (3^-^^ 2) and XS = {-3, h,-2]. If AGMT-VAR or CHK-IEQ sets z. to and underlines it, then the new partial solution is F = (_3^-^^ ^,-6} whi.ch is represented by X = (3,-^, 2,-6} XS = {-3, ^,-2,-6} (3.1) In BCKTRK all underlined variables to the right of the right most non-underlined variable jn the sequence of numerals in F are changed to free variables. The right most non-underlined variable is then set to its opposite value and underlined thus forming a new partial solution. For example, if the current partial solution is given by (3.I), then BCKTRK changes z and z^ to free variables. The right most non-underlined variable, z, , is then set to 1 and underlined. The new partial solution is given by F = {3, ^] which is represented as X = {3, ^) and XS = (-3^-^)« If, upon entering BCKTRK, all the fixed variables are underlined, then all possible solutions have been implicitly enumerated. All optimal solutions to the problem have been printed. If no feasible solution has been found, the given problem is infeasible. 30 6. CHNGMM CHNGMM updates u(F) and i(F) each time a free variable is fixed. Since free variables can be fixed by CHK-IEQ, AGMT-VAR, and BCKTRK, CHNGMM can be called by each of these subroutines and will return to the subroutine which called it when its computation is finished. If a free variable, z., is set to 1, CHNGMM will update u(F) and ^(f) by setting u. (F' ) = u. (F) and H. (F' ) = i. (F) -l-a. . if a. . > 0, 1 1 1 1 ij ij ' u. (F' ) = u. (F) +a. . and H. (F' ) = H . (F) if a. . < 0, 1 1 ij 1 1 ij ' u. (F' ) = u. (F) and l. (F' ) = L (F) if a. . = 0, i =1, 2, ' ' • , m. If z . is set to 0, then CHNGMM will set J u. (F* ) = u. (f) - a. . and L (F' ) = St. (F) if a. . > 0, u. (F' ) = u. (F) and L{Y' ) = i. (F) - a. . if a. . < 0, u.(F')=u. (F) and L{Y')^L(j) if a. . = 0, i =1, 2, • • • ; ni. CHNGMM has two other functions. First, CHNGMM assigns values to the elements of the array CLSP. Second, CHNGMM calls PHTLP to ensure that the network remains loop free. 7. PHTLP A gate, L, is called a successor of a gate, J, (and gate J is called a predecessor of gate L) if and only if there exists a sequence of gates J = J_, J , J , ..., J = L such that the output of gate J. is connected to 31 gate J, ^ for i =0, .... s-1 (i.e., a^ _ = a^ ^ = . . . = a^ ^ = l). ^+1 Vl V2 Js-l-^s Whenever the connection variable, ^j} from the output of some gate, H, to the input of another gate, I, is set to 1, PHTLP is called to insure that the network remains loop free. PHTLP stores the gate numbers of all the succes- sors of gate I (including gate l) in the array SCR and the gate numbers of all the predecessors of gate H (including gate H) in the array PRD. Then the a variables representing the connections from each gate in SCR to every gate in PRD are set to 0. 32 CHAPTER k generatinct the inequalities ^.1. Generating the Basic Inequalities In ILLODIE-AIF the subroutines GEN-IEQ and INIT are used to generate the inequalities. How these two subroutines are used to generate the basic inequalities for a network with R NOR gates and n external variables is dis- cussed in this section. The same method is used to generate the basic inequal- ities for and/or, N0R/NAJ)JD and NOR/AND networks. The basic inequalities for a network with R NOR gates and n external variables (without their complements) given in Chapter 2 are repeated here for convenience. The R NOR gates are characterized by the inequalities I wSi^^ + 2 ^[P >1- up(^) (i+.l) t=l ^ ^ i.l ^^ - k iA - Z wl^ xi^^ - Z ^^.P >0 - U(l-R^^^ t=l ^ ^ i=l ^^ - ^ k = 1, 2, 3, ..., H J = 1, 2, 3, ..., r = 2^^. As before, U is a positive number large enough so that the upper inequality- is non- restrictive if P^"^ "^ = 1 and the lower inequality is non- restrictive if Pp^ = 0. The relation ^[^ = <^-i ?• is represented by the inequalities k ik ik i 33 ■ p^^^ - a., + ^^P > -1 1 ik ik — P?^^ 4- a., - 2 ^[p > 1 ik ik - (^.2) i = 1, 2, 3, . . . , R k = 1, 2, 3, . . . , R(i/^k) 3 = 1, 2, 3, . . . , r =2^ n For each fixed value of k, there are 2 inequalities formed from each inequality in (U.l) (as j goes from 1 to 2 ). Similarly, for each com- n bination of values for i and k, there are 2 inequalities formed from each inequality in {k.2). Each such group of 2 inequalities will be referred to as a block of inequalities. As an example, let R = 3 and n = 2. The first inequality in (^.l) yields the following block of inequalities for k=l: (It. 3) J , 3. „1 43) , „1 ,(3) , ,(3) , ,(3) , „ p(3) > , ,,k: .1 4'^ . .\ X W . 4^) . 4^) . U P(^) > 1 Similarly, the second inequality in (^.l) yields the following block of inequalities for k = 1; 34 i = l: -w^ x(l) - „^ x(l) - ,W . 3(1) . „ ,(1) ^ .„ , = .: -.1 xf ) - „^ 4^) - ,(^) . 4f - „ p(^) > .„ = 3: -w^ xf) . „1 ,(3) . 3(3) . 3(3) . „ p(3) > .„ d = ^: .„! xf ) . .1 x(^) - 4J) - eW . „ p(^) > .u For i = 1 and k = 2, the first inequality in (i+.2) yields the following block of inequalities: J = 1: -i^' - ^2 ^ ^[2 > -1 (h.k) J = 2: .p|2^ - a^2 + ^[f > -1 j = 3: -Pp^ - a^2 + ^[l^ > -1 0=^: -p1^^ - a,, . el^L> -1 Finally, for i = 1 and k = 2, the second inequality in (1|.2) yields the following block of inequalities: 3 = 1: pj^^ + a^2 - 2PJ2^ > (i+.5) (2) _ _ 0.(2) ^^ (h.6) J = 2: P^ ^ + 0^2 - 2Pi2^ > .(3) , ^ 0.(3) 1 j = 3: P;-"' + ^2 " ^^12 - ° (^) , ^ oo(^) j = k: P^^^ + 0^2 ■ ^^12 - ^ 35 Now, using Table 2.U.1, inequalities (^.3), (^-^), (^+-5) and (4.6) can be rewritten in terms of the variables z, . The value nXR+l=7is used for U. Inequalities (4.3) become 3=1: Oz^ + Oz^ + Iz^^ + Iz^^ + Tz^^ > 1 j = 2: Oz^ + izg + Iz^^ + Izg^ 4- 7^38 > 1 j = 3: Iz^ + Ozg + Iz^^ + Iz^^ + Tz^^ > 1 3 = h: Iz^ + IZg + Iz^g + Izg^ + Tz^Q > 1 Inequalities (h.k-) become J = 1: -Oz^ - Oz^ - lz^5 - IZ23 - TZ3^ > -7 j = 2: -Oz^ - iz^ - iz^g - iz^^ - 7Z38 > -7 j =3: -iz^- OZ2- iz^^-lz^^- TZ3^^-T 3 = k: -Iz^ - IZ2 - lz^8 - 1^26 - ^\0 ^ -^ Inequalities (4.5) become j = 1: -1Z3^ - 1Z3^ + Iz^ >-l. j = 2: -lz3g - 1Z3^ + Izg > -1 j = 3: -1Z3^ - 1Z3^ + iz^ > -1 j = h: -Iz^Q - Iz^^ + Iz^Q > -1 (4.7) (4.8) (4.9) 36 Finally, inequalities (^.6) become (i+.io) j = 1: Iz^^ + Iz^^ - 2z^ > j = 2: Iz g + Iz - 2Zg > j = 3: 1^33 + izj^ - 2zg > J = "*= I^UO + 1"31 ■ 2"l0 ^ ° Observing the patterns of both the coefficients and subscripts of the variables, z , in the blocks of basic inequalities leads to the definitions given below. These definitions are important for understanding how GEN-IEQ and INIT are used to generate the basic inequalities. 1. The n variables, z , which represent the n variables, w , in a block of inequalities are called type W variables. The co- efficients of type W variables follow a binary counting up pattern from (0, 0, ..., O) to (1, 1, ..., l) as j goes from 1 to 2^. 2. If the complements of the external variables are available as inputs to the network, then the n variables, z , which repre- sent the n variables, v, , in a block of inequalities are called type V variables. The coefficients of type V variables follow the binary counting down pattern (1, 1, ..., l), (1, 1, •••, 1, O), ..., (0^ 0, ..., O) as j goes from 1 to 2 . 3. The r = 2 variables, z , which represent the r variables, p-'l } or the r variables, P. , are called type D variables. 37 Type D variables have the following property: if dz appears in the first inequality of a block^ then dz appears in the second inequality, etc., where d is some integer constant. Also, for networks which have more than one gate type (e.g., nor/and), the 2 variables, z , which represent the 2 variables, 7., are type D variables. The name "type D" is suggested by IK the "_diagional" pattern followed by the variable subscripts. k. The variable, z , which represents the variable, oc , in a block of inequalities is called a type C variable. Type C variables have the property that dz appears in each inequality of the set. A non-zero constant term in a block of inequalities is also defined to be of type C. In networks with more than one gate type, the variable, z , which represents the variable, k. , is also a type C variable. The name "type C" is suggested by the fact that the variable subscript remains _constant throughout the block of inequalities. Before GEN-IEQ, and INIT generate the inequalities, INIT reads the problem parameter card (see Chapter 6) which contains values for n and R. Using these values GEN-IEQ and INIT generate the basic inequalities one block at a time in the following manner. GEN-IEQ, provides the necessary information about the first inequality of a block by specifying values to three arrays. TEMP is used to store the subscripts, h, of the variables, z ; VAL is assigned the values of the coefficients of the variables; and TP is assigned the type of each variable. If the constant term, b, in the first inequality of the block is non-zero, this information is stored in TEMP(l), VAL(l) and TP(l) since other subroutines of the program are structured under the assumption 38 that the constant term is stored first in TEMP, VAL and TP. The non-zero constant term is represented by TEMP(l) = 0, VAL(l) = b and TP(l) = C. TEMP(l) is set to to distinguish the constant from the other variables in the inequality and TP(l) is specified as C since the non-zero constant term is defined to be of type C. The information about the other variables in the first inequality is placed in the three arrays in an arbitrary order. If the first inequality has n type W or V variables only the variable with the smallest subscript is specified by GEN-IEQ. The other variables will be generated automatically by INIT. When GEN-IEQ has stored all of the information about the first inequality of a block, the program transfers to INIT where all the variables except the constant term are rearranged according to the descending order of the absolute value of the variable coefficients. This rearranging makes it easier for CHK-IEQ to check condition (c) described on page 2?. INIT then uses the information about the first inequality of the block provided by GEN-IBQ, to form all 2 inequalities of the block. The process of forming all 2 inequalities in INIT is based on the types which were assigned, to the variables by GEN-IE)5,. These types define the coefficient and variable subscript patterns for the entire block of inequalities. Finally, INIT stores the necessary information (coefficients, subscripts, etc.) about each inequality of the block in the proper arrays. Further details about these arrays are not pertinent to this discussion. The program then transfers back to GEN-IB3, which stores the information about the first inequality of the next block in the arrays TEMP, VAL and TP. As an example consider the inequalities in (^.7). GM-IIR stores the information for the first inequality in the arrays TEMP, VAL and TP as follows : 39 \ . L \ 1 2 3 h 5 TEMP(L) 1 15 23 37 val(l) -1 1 1 1 7 tp(l) c W D D D Notice that the constant term is moved to the left hand side of the inequality before the arrays are filled . INIT then rearranges the variables as follows : \ L \ 1 2 3 k 5 TEMP(L) 37 15 23 1 VAL(L) -1 7 1 1 1 TP(L) C D D D W (^.11) Next, INIT uses the information in (4.11) to form all four inequalities of (U.7). The constant term, -1, is included in a2J. four inequalities since TP(l) = C. TP(2) = D, TP(3) = D and TP(U) = D cause INIT to include 1^^^, Iz and Iz^o in the first inequality; I'^^^Q} ■^'^-tf. ^^^ -^^pii ^^ ^^® second inequality, etc. Since only the variables with non-zero coefficients in an inequality are stored, TP(5) = W causes INIT to include Iz^ in the second inequality; Iz in the third inequality; and both Iz and Iz in the fourth inequality. Thus the inequalities formed by INIT are < -1 + Tz^^ + Iz^^ + Iz^^ <-l + 7^38 + lZi6 + 1^21+ ■*" ^^2 < -1 + 7z + Iz + Iz^^ + Iz^ < -1 + Tz^Q + Iz^g + IZg^ + Iz^ + Iz^ ko Notice that in each inequality the variables are still arranged according to the descending order of the absolute value of the variable coefficients. k.2 Generating the Additional Inequalities In general, additional inequalities, like those described in Chapter 2, cannot be grouped into blocks (as defined in the previous section). Thus the type definitions given in section k.l are not valid for additional inequalities. GEN-IEQ and INIT are used to generate the additional inequali- ties in the same way they are used to generate the basic inequalities except that the additional inequalities are generated one at a time rather than one block at a time. GEN-IEQ provides the information about each additional in- equality by specifying the appropriate values to the arrays TEMP and VAL (TP is filled with blanks). As before, if the constant term in the inequality is non-zero, it must be stored in TEMP(l) and VAL(l). The program then transfers to INIT where all of the variables (but not the constant terra) are rearranged according to the descending order of the absolute value of the variable coefficients. However, upon discovering that the types of the variables have not been specified, INIT merely stores the inequality in the proper arrays. The program then transfers back to GEN-IEQ which specifies values to TEMP and VAL for the next additional inequality. 4.3 The Order of the Inequalities When searching for a free variable to fix, it is sufficient for AGMT-VAR to consider only a subset of the basic inequalities which character- ize the gates in the network (e.g., inequalities (U.l) for a network with NOR gates) (see Chapter 5). To make use of this fact, AGMT-VAR was programmed ^1 under the assumption that the inequalities are stored in a certain order. Thus, GEN-IBQ, and IKTT generate the inequalities in the order described below. Not only are the basic inequalities which characterize the gates in the network generated first, but they are also generated in a specific order which depends on the gate types being used. The inequalities for gate 1 (the output gate) come first followed by the inequalities for gate 2, etc. If gate k is a NOR or AND gate, the inequalities for gate k are generated in the following order: [2 inequalities which are restrictive if P =0; J = 1, 2, . . . , 2 } k {2 inequalities which are restrictive i If gate k is a NMD or OR gate, the order is if pf^^ =1; = 1, 2, ..., 2^'} {2 inequalities which are restrictive if pA =1; J = 1^ 2, . . . , 2 } [2 inequalities which are restrictive if 'P-^ =0? J = 1^ 2, . . . , 2 ] For example, in a NGR/^AND network synthesis problem the basic inequalities which characterize the gates are generated first and in the following order (of course for any gate k the NAND inequalities could come before the NOR inequalities): k2 [2 NOR inequalities which are restrictive if P^ =^ (2 NOR inequalities which are restrictive if P^'' = 1 [2 NMD inequalities which are restrictive if P "^ "^ = 1 2 NAND inequalities which are restrictive if f[^ ^ 3 = 1, 2, ..., 2^} d - 1, 2, ..., 2^} J = 1, 2, ..., 2^} = 1, 2, ..., 2") n ( t) [2 NOR inequalities which are restrictive if Vlr = [2 NOR inequalities which are restrictive if Vr^ - 1 K -,n { 2 NAND inequalities which are restrictive if P. (j)^ 1 R [2 NAND inequalities which are restrictive if P}> = K j = 1, 2, ..., 2"} J = 1, 2, ..., 2^} J = 1, 2, ..., 2^} j = 1, 2, ..., 2"] The remaining basic inequalities and the additional inequalities are generated in an arbitrary order. i^3 CHAPTER 5 THE SCHEME FOR AGMT-VAR The objective of AGMT-VAR is to select an inequality which is not satisfied and then fix a free variable in that inequality according to the scheme described in this chapter. AGMT-VAR does not need to consider all of the inequalities generated by GEN-IEQ,. All additional inequalities can be ignored by AGMT-VAR since the variables in these inequalities will be assigned values by CHK-IB5, (specifically, by either condition (b) or (c) on page 27). Also, basic inequalities such as inequalities (2.2) for NOR gate networks need not be considered by AGMT-VAR since they will be satisfied by conditions (b) and (c) of CHK-IEQ,, Finally, basic inequalities of the form (2,1) which are restrictive when P^ = 1 for NOR and AND gates and when P^^^ = for NAND and OR gates will be satisfied by condition (b) of CHK-IH^ and need not be considered by AGMT-VAH. For example, all of the basic inequal- ities generated by the second expression in (2.l) can be ignored by AGMT-VAR. Thus AGMT-VAR only needs to consider a subset of the inequalities. It is important to note the difference between the subset of in- equalities which must be considered by AGMT-VAR and the inequalities which must be checked by CHK-IEQ. AGMT-VAR must consider a fixed subset of in- equalities, while the subset of inequalities checked by CHK-IEQ, continually changes during the computation. To make the most efficient use of these facts, the basic inequalities are generated in a certain order (see Chapter ^) to simplify AGMT-VAR, and the method of chain checking (see Chapter 3) is used in CHK-IEQ. For each inequality (call it i) which it must consider, AGMT-VAR takes the following action. First, the value of the P variable is checked. If the P variable is free, the i-th inequality is skipped. If the P variable is fixed, AGMT-VAR checks ^.(F). If ^. (f) > 0, the inequality is skipped since it is already satisfied. If ^. (F) is negative, the X. variable is checked if the network has more than one gate type. The X. variable is set to 1 if it is free. Otherwise, the only free variables in the inequality are either w variables, v variables or p variables. Each free w, v or 3 variable is assigned a type according to the following definitions [l]. The variable type is: k k VC'^ : if the variable is w or v (a Variable with Connection being *). G-^ : if the variable is 3^^ with cl^ = 1 and P^'^ ^ = * (a Gate h with p(j) ^ ^). h — GC-^ : if the variable is a^^ with P^^^ ^ ^ * and 0' = * where gate h is not isolated (a Gate h with Connection being *). G^*: if the variable is p^^ with P^'^" ^ = * and a_ = * where gate h is not isolated (a Gate h with P/ = * and Connection being *). NWG if the variable is ^^^^ with P^" ^ = * and ol^ = * where gate h is isolated (aNeWGate). The above variable types can be ordered from most desirable to t + During the computation a variable can have one of three values: (zero), 1 (one) or -^ (a free variable). A gate, h, is said to be isolated if it is not connected to any other gates in the current partial solution (i.e., if all a (k^h) are or *) . h3 least desirable as G^, VC*, GC-^, G*C-^ and NWG (5-1) Why the desirability ordering in (5«l) is used is more obvious in some cases than others. For example, G-^ is preferred to G-^C* because G-^C^ requires both an additional interconnection (cx v.) and the fixing of a free variable (P} ) while G* only requires that a free variable (P/^*^ ) be fixed. On the other hand, it is not intuitively obvious why G-^ is preferred to VC*. VC* requires an additional interconnection while G* does not. However, the fixing of a free variable required by G'^ could make some other inequality harder to satisfy, It was empirically concluded that (5.l) is the best desirability ordering. Finally, the type of an inequality is defined to be the same as the best vari- able type for that inequality. The best variable type is chosen since it tends to minimize the number of interconnections. In AGMT-VAR the inequalities which must be considered are scanned one at a time (looking for free w, v and p variables), and each inequality is given a type. If at any point the inequality being scanned is determined to (1) t be of type NWG, AGMT-VAR immediateily sets the type NWG variable, p.^ , to 1 Ik and underlines it. The gate connected to the network is set to a type dif- ferent from the gate it feeds (i.e.. A.. ^ K) if the network has more than one gate type (e.g., NOR/AND). Also, if some inequality is scanned and does not have any free variables, the current partial solution is infeasible. Otherwise, the inequality with the least desirable type is chosen and the free variable with the best variable tjrpe for that inequality is fixed. If Subsequently, a and P. are set to 1 when the inequalities are checked again by CHK-IEQ. Thus AGMT-VAR, in effect, connects the isolated gate to the network. h6 two inequalities have the least desirable type, the one with the smallest number of free variables is chosen. The inequality with the least desirable type is chosen for two reasons. First, if the problem has a feasible solu- tion, the inequality with the least desirable type must be satisfied some- time; and if it is not satisfied as soon as possible, the number of free variables for that inequality may be smaller when CHK-IEQ is called again later in the calculation. Consequently, that inequality may be harder to satisfy. Second, if the current partial solution may lead to solutions which exceed the current bound on the value of the objective function, the bound may be exceeded earlier since the cost (in terms of the number of gates and/ or connections) associated with the inequality with the least desirable type tends to be greater. Each time AGMT-VAR fixes a free variable the program transfers to CHK-IEQ,. hi CHAPTER 6 INPUT The easiest and most practical approach for generating the inequali- ties for ILLODIE-AIF is to use GEN-IEQ and INIT (see Chapter ^4-). However, early versions of the program read the inequalities from cards, and this capability is maintained in the current version of the program. Thus, the discussion of the input data cards for ILLODIE-AIF given in this chapter includes a discussion of how to provide the inequalities on cards. The following definitions facilitate the discussion of the input data cards. (a) A problem refers to using ILLODIE-AIF to synthesize networks which realize a set of one or more switching functions. (b) A problem- set refers to a group of one or more problems which use the same parameter card (to be discussed later in this chapter) and the same inequalities. (c) A multiple-problem- set refers to a group of one or more problem- sets. If the inequalities are generated by the program, all networks synthesized for a multiple-problem- set must be of the same gate type (or types) since only one version of GEN-IEQ, can be used at a time. However, if the inequalities are read from cards, the networks synthesized for each problem-set may be of a different gate type (or types ) from the networks for the other problem-sets. kS The order of the cards in the input deck for a problem and a multiple -problem- set are shown in Fig. 6.1 and Fig. 6.2, respectively. Since all arrays and nearly all variables in the program are defined as half-word integers, all numerical data with three exceptions must be in the range -15 15 from -2 to 2 -1. All numbers are read using a FORTRAN I format which requires that they be right justified in their assigned fields on the data cards to be read correctly. 1. THE TITLE CARD Each problem-set must have exactly one title card which may contain any suitable title for the problem- set. The contents of the title card will be printed as a heading for the output (see Chapter 7)- The program does not try to obtain any information about the problem-set from the title card. 2. THE PARAMETER CARD This card contains six problem-set parameters each of which occupies five columns. (a) NOVR NOVR, punched in columns 1 through 5^ is the number, n, of external variables (x , x , . . . , x ) of the given switching (output) function(s). Theoretically NOVR could be any number, t NOGT, NOVR and NOPT which will be explained later are defined as full-word t -?1 ^1 integers and can range from -2 to 2 -1. Actually, all the data in network synthesis problems are well within these ranges. These ranges are for the IBM 360/75. ^9 END CARD INITIAL PARTIAL SOLUTION CARD(S) LAST FUNCTION TITLE CARD LAST FUNCTION CARD ZBAR CARD FIRST FUNCTION TITI£ CARD FIRST FUNCTION CARD INEQUALITY CARDS OBJECTIVE FUNCTION CARD(S) PARAMETER CARD TITLE CARD Figure 6.1. Tlie Input Deck for One Problem 50 END CARD (LAST PROBLEM-SET) ZBAR CARD, FUNCTION AND FUNCTION TITLE ' CARDS, INITIAL PARTIAL SOLUTION CARD(S) . (LAST PROBLEM, LAST PROBLEM-SET) ZBAR CARD, FUNCTION AND FUNCTION TITLE CARDS, INITIAL PARTIAL SOLUTION CARD(S) FIRST PROBLEM, LAST PROBLEM-SET) TITLE CARD, PARAMETER CARD, OBJECTIVE FUNCTION CARD(S), INEQUALITY CARDS (LAST PROBLEM- SET) END CARD (FIRST PROBLEM-SET) ZBAR CARD, FUNCTION AND FUNCTION TITLE CARDS, INITIAL PARTIAL SOLUTION CARD(S) (LAST PROBLEM, FIRST PROBLEM-SET) ZBAR CARD, FUNCTION AND FUNCTION TITLE CARDS, INITIAL PARTIAL SOLUTION CARD(S) (FIRST PROBLEM, FIRST PROBLEM-SET) TITLE CARD, PARAMETER CARD, OBJECTIVE FUNCTION CARD(S), INEQUALITY CARDS (FIRST PROBLEM-SET) Figure 6.2. The Input Deck for a Multiple-Problem-Set. 51 but practical considerations (the amount of core storage needed, the number of inequalities, the computation time, etc.) limit NOVR. In ILLODIE-ArF NOVR must be less than or equal to four although the program could be modified to handle functions of more than four variables, (b) NOGT NOGT is the number of gates in the network and is punched in columns 6 through 10. The output subroutines are designed, to handle networks with a maximum of ten gates. However, these subroutines could be changed to allow for networks with more than ten gates. Once set, NOGT remains fixed throughout the calculation and, if the problem is feasible, all networks with a minimum number of interconnections for that value of NOGT are found. What value of NOGT to choose and how to choose it depend upon the objective of the user. The usual objective for using ILLODIE-AIF is to find the network or networks for a given switching function which have first the minimum number of gates and second the minimum number of interconnections. The following approach is reasonable for finding the minimum value of NOGT. Choose a reasonable estimate of the optimal value of NOGT (perhaps by a simple hand calculation using a Karnaugh map) and attempt to solve the problem using ILLODIE-AIF. If the problem is infeasible (i.e., no solution exists) increase the value of NOGT by 1 and run the problem again. Repeat this process until the first value of NOGT is found for which a solution exists. 52 This value of NOGT is the minimum value. On the other hand if the initial estimate of NOVR results in a feasible solution, decrease the value of NOVR by 1 until the first value of NOGT is found for which the problem is infeasible. The value of NOGT 1 greater than this last value is the minimum value of NOGT. (c) NOKGT NOKGT is the number of gate types in the network and is punched in columns 11 through 15. In ILLODIE-AIF NOKGT is either 1 or 2. The problem would have to be reformulated if the user wanted to synthesize networks with more than two gate types (for example, k variables which can only assume the values and 1 cannot be used for networks with more than two gate types). (d) TYIN TYIN, punched in columns l6 through 20, indicates whether the inequalities will be read from cards or generated by the program. TYIN = PG if the program will be used to generate the inequalities, and TYIN = CD if the inequalities will be read from cards. (e) CPNCP CPNCP indicates whether or not the complements of the external variables (as a group) are available and is punched in columns 21 through 25. The complements are available if CPNCP = CP and are not available if CPNCP = NC. 53 (f) NOPT NOPT Indicates the number of output gates in the network (i.e., the number of output functions the network is to realize) and is punched in columns 26 through 30, The current version of the program is capable of handling networks with any number of output functions subject to the restrictions on the sizes of NOGT, WOVE, etc. 3. THE OBJECTIVE FIMCTION CARD(S) If TYIN = PG, the objective function, cz, will be generated by the program. However, if the inequalities are read from cards, the user must also specify an objective function on cards. The objective function is punched in col"umns 1 through 72 of each card. Columns 73 through 80 are not read by the program. The first seventy-two colimins are divided into eighteen fields with four columns to a field. The numbers are read from the cards in pairs. The first nimiber read is the coefficient of the variable and the second number is the subscript. Thus columns 1-U, 9-12, ,,,, and 65-68 contain variable coefficients and columns 5-8, 13-l6, ,,., and 69-72 contain the respective subscripts. For example, if columns 1 through 8 of an objective function card contain bbb^+bblO, then ^z^^ is part of the objective function. Only the non-zero coefficients and their respective subscripts need to be specified. Also, the numbers are usually punched on the cards according to the ascending order of the subscripts. The end of the objective function is signaled by putting a negative number in the subscript field immediately following the subscript field of the last non-zero coefficient. If the last non-zero The letter b is used to represent a blank, 5U coefficient occurs in columns 65 through 68, then an additional card with a negative number in columns 5 through 8 is necessary. k. THE INEQUALITY CARDS As in the case of the objective function, the inequalities are punched in columns 1 through 72 only. Each card is divided into nine fields with eight columns in each field. Each field is used as follows: the first column contains the type of the variable (here, the variable types are those defined in Chapter h rather than Chapter 5 and are denoted as b (blank), V, W, D or C); the next three columns contain the value of the variable coefficent; and the last four columns contain the subscript of the corresponding variable. The numbers on the inequality cards are read into the array INPT which is dimensioned such that each inequality is limited to a maximum of ten cards (i.e., 90 non-zero coefficients). If an inequality has a non-zero constant, it must be punched in the first field of the first card for that inequality. The remaining fields must be filled according to the descending order of the absolute value of the variable coefficients. The end of an inequality is indicated by punching a negative number in the last four columns of the field immediately following the field which contains the last non-zero coefficient. If the last non-zero coefficient occurs in the last field of a card, an additional card with a negative number in columns 5 through 8 is required. The end of the inequalities is signaled by a special card which contains any symbol (except b, V, W, D or C) in the first column and a negative number in columns 13 through I6. For the basic inequalities the user specifies the information about the first inequality of each block and INIT generates the entire block of 55 inequalities as described in Chapter h (also, see Appendix A for an example). Furthermore, the order of the inequality cards must be the same as the order described in Section ^.3. If the program is used to generate the inequali- ties, the objective function and inequality cards are simply omitted. 5. ZBAR CARD ZBAR, p-unched. in columns 1 through 5, is an upper bo\and on the value of the objective function. If no upper bound is known, ZBAR = NOVR X NOGT + NOGT X (NOGT-l) is always sufficient since NOYR X NOGT allows each external variable to be connected to every gate and NOGT X (NOGT-l) allows each gate to be connected to every other gateo 6. THE FUNCTION CARD The function card contains the truth table of a switching (output) function and must be punched (one column for each value) beginning in column 6. Since the program can solve problems with up through four vari- ables, the number of columns needed will vary (sixteen columns for a four variable function, eight columns for a three variable function, etc.)« The truth table values must be punched in the following order (in this case for a three variable function): f(0,0,0), f(0,0,l), ..., f(l,l,0), f(l,l,l). For a problem with more than one output function, a function card is punched for each function and placed in the input deck as shown in Fig. 6.1. 7. THE FUNCTION TITLE CARD Following each function card there must be exactly one function title card which may contain any suitable information about the output 56 function such as its algebraic representation. The function title card is read and printed as explained in Chapter 7« It is convenient but not neces- sary to punch the truth table of the output function on the function title card in exactly the same columns as on the function card. With this pre- caution the function and function title cards could accidently be inter- changed and the program would still work. 8. THE INITML PARTIAL SOLUTION CARD(S) If a partial solution to the problem is known, the user can specify it on the initial partial solution cards. This is done by spejif^ing values which are read into the arrays X and XS which are defined on page 32. Only columns 1 through 72 of each card are read, and each card is divided into twelve fields with six columns in each field. The first five columns of each field contain the subscript of a variable in the initial partial solution. This number is read into the array XS and must be negative if the variable is to be underlined. The last column of each field is used to determine whether the variable is to be set to zero or one. If the number in the last column of the I-th field is 1, X(l) is set to XS(l). If the number is 0, X(l) is set to -XS(l). For example, if the first variable in the initial partial solution is to be Xo and it should be set to 1 and \ander lined, then the first six columns of the first initial partial solution card should contain bbb-80. If the next variable is x , and it should be set to 1 and not underlined, then columns 7 through 12 should contain bbblUl. Such a card would set XS(l) to -8, X(l) to 8, XS(2) to Ik, and X(2) to 1^. Thus columns 1 - 5, 7 - 11, ..., and 67 - 7I contain subscripts (either positive or negative) while columns 6, 12, ..., and 72 indicate to what 57 value the variables are to be set. All columns to the right of the field which corresponds to the last variable in the initial partial solution must be blank. If the last variable is in the last field of a card, a blank card must be inserted next in the input deck to signal the end of the initial partial solution. If the user does not wish to specify an initial partial solution, a blank card must be inserted in the input deck where the initial partial solution cards would have been. 9. THE END CARD The end of each problem- set is signaled by an EKD card which contains a negative number in the first five columns. When ILLODIE-AIF finishes a problem, it begins the next problem by reading the ZBAR card, the function card(s), the function title card(s) and the initial partial solution card(s) for the next problem. When the program detects the end of a problem- set (i.e., reads and END card), it begins the next problem-set by reading the title card, parameter card, objective function card(s), inequality card(s), etc., for the next problem-set. The program terminates when there are no more input cards to be read. 58 CHAPTER 7 OUTPUT In addition to printing all feasible solutions found (assuming the problem is feasible), ILLODIE-AIF also prints some job statistics and other information which may be helpful in determining whether or not the program is working properly. The purpose of this chapter is to describe both the printed and punched output of the program. A complete example of the printed output is given in Appendix A. First, the title card (see Chapter 6) is printed as a heading for the output. This is followed by a title for the variable table (Table 2.i+.l) and then the variable table itself. Of course w. is represented as W(l, l), V. as V(l, l), etc., and each variable z is represented by its subscript t. Next the inequalities for the problem ai^e printed twice. First, they are printed in exactly the same format they would be in if they were provided on cards, i.e., they are printed as they appear in the arrays TP, VAL and TEMP after the variables have been rearranged according to the descend- ing order of the absolute value of the coefficients but before INIT forms the blocks of basic inequalities (see Chapter k) . The inequalities are also printed after INIT forms the blocks of basic inequalities. This time they are printed in the form -b < A z where the symbol "<" is replaced by the letters "LE". In both cases only the variables with non-zero coefficients are printed. In between the two printings of the inequalities, the total number of variables N, the number of inequalities m, the number of external If the inequalities are read from cards (TYIN = CD), the first printing of the inequalities is omitted. 59 varialDles n, the number of non-zero coefficients in the inequalities, and the objective function are printed. To separate the printing of the inequalities from the printing of the solutions, the function title is printed ten times at the bottom of two consecutive pages. If the problem has more than one output function, each function title is printed ten times with the first function title printed last. Next the value of each partial sum y. (F^^) (i =1, 2, ..., m) (see Chapter 3) is printed where F_ is the initial partial solution. F„ is then printed in the form of the arrays X and XS followed by the time required for initialization (i.e., the time required by INIT and C^EN-IEQ). The rest of the output depends upon the outcome of the problem. ILLODIE-AIF prints the time, the current partial solution (X and XS) and a line of statistics every 1000 iterations where each entry into the subroutine CHK-IEQ, is counted as one iteration. The time value printed is the amount of execution time elapsed since the initialization time value was printed. The line of statistics (hereafter referred to as LINESTAT) includes OF (the value of the objective function), NO. ITER (the number of iterations), EKTDX UNFS (the number of times the program transfers from CHK-IEQ to BCKTRK because the current partial solution is infeasible), EXTDX FSBL (the number of times CHK-IEQ, finds a feasible solution), CGPSNS (the number of times CHNGMM is called which is equal to the total number of variables fixed by University of Illinois timing subroutines are used to provide the time values printed by the program. Values called GETYS, CYCLES and OFBND are also printed even though they are no longer meaningful. 60 the program) and FIXJ (the number of times the subroutine AGMT-VAR is entered). All of these statistics are cumulative for each computer run except OF. Also, the program punches the current partial solution every 2000 iterations in exactly the same format as the initial partial solution cards described in Chapter 6. This allows these cards to be used as initial partial solution cards ^f the program is interrupted before the problem is finished and the user wants to resume the computation. After each partial solution is punched, the program also punches the corresponding value of the objective function. This card serves two purposes. First, it makes it easier to separate the different partial solutions which may be punched. Second, it can be used as a ZBAR card if the problem is to be continued. In this case it must be remembered to move the ZBAR card in front of the partial solution cards to maintain the order of the input cards described in Chapter 6. The order of the cards punched by the program is shown in Fig. T'l- If a problem is not finished after 40,000 iterations, the program goes on to the next problem. The frequency (in terms of the number of iterations) with which partial solutions are printed and./ or punched can be changed, by changing the appropriate FORTRAN DO loop parameters within the program. If the problem is feasible, ILLODIE-AIF will print all feasible solutions which give c z a value less than or equal to the current value of OF. The value of OF is updated each time a feasible solution which lowers the value of c z is found. For each such feasible solution the program prints the values of the arrays L, W, A and V (if the complements of the external variables are available). For example, let the problem to be solved be specified as a two variable (NOVR =2), two gate (NOGT =2), NOR problem with no complements of the external variables available (CPNCP = NC). Also, let the output function to be realized be x sy x (Olll). Then, one feasible solution as it would be printed by the program is given as follows : k 61 ZBAE CARD AT 4000 ITEEIATIONS PARTIAL SOLUTION AT 4000 ITERATIONS ZBAR CARD AT 2000 ITERATIONS PARTIAL SOLUTION AT 2000 ITERATIOl^ Figure 7.1. The Order of Partial Solutions Punched by the Program. 62 K=12 J=12 L(l) W(1,K) A(1,J) L(2) W(2,K) 1 1 A(2,J) 1 Since the problem has only one gate type, the values for the array L can be ignored. The values of the W array show that both x^ and x are connected to gate 2 while the values of the A array indicate that gate 2 is connected to gate 1 (the output gate). LINESTAT is printed immediately before each feasible solution is printed. In addition, after the last feasible solution is printed, the value of each variable for the last feasible solution, the time and LINESTAT are printed. This time value is also the amount of execution time elapsed since the initialization time value was printed. The final printing of LIKESTAT is useful for estimating how much of the computation time was spent in proving the optimality of the feasible solutions found. If the problem is infeasible, then the value of each variable is printed as 0. LINESTAT and the amount of time spent trying to find a feasible solution are also printed. 63 APPENDIX A AN EXAMPLE To provide an example of the input to and the output from the pro- gram, let us obtain all optimal AND/OR networks for the switching function A B N/ A B using ILLODIE-AIF. This example has the following parameters: NOVR = n = 2 (two external variables), NOKGT = 2 (two types of gates are available), CPNCP = CP (the complements of the external variables are avail- able), and NOPT = m = 1 (one output function). Let us assume that the net- works have three gates (i.e., NOGT = n = 3)* In addition, the objective function and the inequalities are to be read from cards (TYIN = CD). The arbitrary constraint that the output gate should be an OR gate is added to illustrate how to provide an initial partial solution. Using the variables w, , v, , a.^ , P.? , P^ , \ and 7., which t' t ik' ik ' k ' k xk were defined in Chapter 2, the basic inequalities for this example are given by: 2 2^ Z vj xp-^ + E ^Jt x^^^ + Z 7??^ > 1 - U p/^^ - U \ t=l ^ ^ t=l "^ ^ i=l ^^ - ^ ^ 2 V f.\ 2 ,, , . 3 - Z v^ xp^ - Z wj; xp^ - Z 7??^ > -U(l-p/^"^) - U A i=l ' - iA , . t ^t , % ^t ^t .% ^ik ^ -"^"-"k ^ - ^ ^^ t=l t=l 1=1 (Al) 2 2'^ Z w^ x'J) + E v^ x^3) + Z p(j) > 1 - U(l-p(^>) - U(l-X^) t=± t=l X=l ,l^\\ tfl ^ ^ iSl'i^ >-UP^^)-U(l-^) i^ k = 1, 2, 3 j = 1, 2, 3, h. 6k When A. = 1^ the first two inequalities of (Al) become non- restrictive and the last two inequalities represent an OR gate. When >v = 0, the last two inequalities become non-restrictive and the first two inequalities represent an AND gate. The two non-linear equations 3.^^ = a P;'^ ^ and 7.'^^ = o: (l-P.^'^) = lie XK 1 XK XK X a - P.|! ai'e represented by the following linear inequalities: ^)P - 2a., + ?r^ + 27:, > xk xk X xk — -3^[l^ + 3a^^ - Pp^ - k7\_l^ > -1 (A2) - z s:^-^ + u P. ^ > t=i "^ ^ - t^i i = 1, 2, 3 k = 1, 2, 3 i ^^ j = 1, 2, 3, k. The following additional inequalities are also included; 1. Each gate has at least two inputs. 223 Z w^ + Z v^ + E a > 2 k ^ 1, 2, 3. (A3) Ul ^ i=l ^ i=l ^^ i;^k 2. Each gate, except the output gate, has at least one output connection to another gate. 3 Z O^ > 1 k = 2, 3. (aU) i=l '^^ i^k 65 3. The triangular condition (see page 15) holds even if gate j con- nects to other gates in addition to gate k. -^ij -^ik-^Jk>-2 (A5) i - 1, 2, 3 J = 1, 2, 3 k = 1, 2, 3 i ^ J ^ k. k. If two gates, i and k, are of the same type (i.e., both are AND gates or OR gates) and gate i is connected to gate k, then gate i must have at least one more output connection, assuming that no fan- in restriction is placed on the network. 3 "it ' '"i ' '"k ^ik — Z q;_.^ + A.. + >v - a_. ,_ > t=l '^ (A6) 3 it "i '\ ""ik — Z a,^ - K - K - a,, > -2 t=l t^i t;^k i = 1, 2, 3 k = 1, 2, 3 i -^ k. 66 5. Each optimal network must have at least one AND gate and one OR gate. 3 L \. > 1 i=l ^- - Z \. > -2 i=l "- (AT) The input cards for this example problem (shown in Table Al) are to be prepared in accordance with the discussion in Chapter 6. The discussion on page l8 and Table 2.4.1 are used to provide the information on the objec- tive function cards. The inequality cards are punched using the description of the inequalities given above, the discussion in Chapter ^4, and Table 2.U.I. The initial partial solution requires the output gate to be an OR gate as is desired. The output for this problem follows. H CVJ cn o o § ON CVl 67 I H O H H CO H H H ONONOnOnONONONONONONONOn OnOnONONOnONONOnONO\ONON I I I I I I I I I I I I H K O EH CO K OJ <: P-H o H CO W O § H Of o OJ ro OJ H H VO ON H H Lr\co en H H H H OO OJ H H H H H H O ON H 0\ I H H -:t-:t ONONOOCO OOOOO O UAUA t—c—OJ OJ t— t^rom[>-i:^oj c\j OJ <; H r^ r-\ I POO VO VO H VO VO OJ H r-{ r-^ r-{ H I H H I QpQPPOOOO HoooooooooJOJ tr—h- OJiiAirNHHvoVDHH ON ON I ON ON I ON ON I ON ON I ON ON ON ON H H H H H H I I I H H H H QQPPlPQPlQQPlPlO ir— t^l>-I>-ONONONONHr-jHi-iONCV-)ONOOONI>- ON^-ONHONH H rH H H ON-4- ON J- ON-=r ON-ij- ONLTNONLTN I I I I I I I I I I I I I I :s;s>>:s:s>>:sr2>> o o o o H o H I O H^^HH000O0O0OLrNLrNLrNLrN0O^O^-l^— H HLTNLfNONONrOOOONONON rHHHHOJOJcuOJOJOJromONONON I I I HHHHHHHHHHHHHcv~)HpoH en H en r-\ en r-i en I I I I t I I I I I I I >>^:s>>:ss:>>:s:2 o-)oocY-)ooi>-t— [>-h-H H H H roi>-oooo >-ONl^o -:d-J-J-J-J--C|-^_:t irNLTNLlALrN-d- OO-Ct" rO_:t rO_d-_;f UA_ztLrN^ H OJ cn OOOOOOOOQOQO H c-l H CVJ c— LTN on ^-t-I^-^-^-t-^-^-^-[>-^-[^-HooHooH roH(r)HooHooHHH I I I I I I III onopoooooooooooooooooooooqo irNirNLrNLTWOVOvovo D^C— t^l>-oooo OJ ojvovoo O-d-^oDoo roH on irNLfNirNLrNLfNLrNLrNLfNLrNLfNLrNLfNLTNLrNVDVDVOVO t^ l>-l>-I^-|^-|^H OJ OJ D—D—D— h-i^-i^i^-t— ^-^-^-^-a^-:±OJ-d-oJJ-cvlJ- oj-=fai-:t h h i-\ II II II I I I I I I I I I ooooooooooooooppppooqpppopp OOOOOOOOOOOOt^OOOOONOOOHOCVJOrO[>-H ry~\ r/~\ rr\ — t- -+- -t- -4- -4- i r\ en en -=f -=f _d- _:t -^ LfN H HI>-0O[r— Ht--rO^-HI>-ooi>-OJHOJHOJHOJHOJHCVlHI>-I^-[>- iHiHiHi I I I II OOOOOOOOOOOOOOOOOOOOOOOOPPO o EH 0) H o o o EH H EH o o o M EH o M EH o w OJ o o OO o >H P EH OJ OO-Ct- LTNVO t-OO ON O H OJ OO-Ch irNVO I^-OO ONO H OJ m-:t LfNVO [>- HHHHHHHHHHOJOJOJOJOJOJOJOJ S m pq S S o <:<;<:<;<;<;-CO en m en <-i r-\ H 00 O OJ H H H H H ON I ON ON ON ON I ON ON I ON ON I ON ON I < r^^ tji,vj _^ ONONONONONONONOOONr--ONOONONONCVJONHONON HH -3 ONOnOnOnONOnONcy-iONOO ON^ O-v en ON_:t ON_d- On ON ^ I I I I I I I I I I I I II * N H H H H a)_=^vDONONO(^JcoHl^ONoo^-^-coooNONOOJHHOJ^-^- ONON-d--ct- oo^ en en en en en en -:t ooooj--d-J--J--* ltnltn I I H H H HHHHHHHH I I I I I I I r-\ r-{ r-{ H r-\ r-{ ^ I I I I •-{ H H I I I^-ONHOCVIOD^-OO^. OJH t>-VO OO C—ONLTNO t-HLTNOJ^vOMD^O H-=|-J- ooooj- po^j- en -VO LrNtr-V£) C— ITvLPiON en-:t ooooonj--^-=t- LrNLfNLrNLr\irNLrNir\ir\LrNirNLrNLrNir\LP>ON HHHHHHHHH I I I I r-{r-{HH<-ir-\r-{r-\Hr-{<-4 rsf ■-• ^ Kt V > >4 rv m ^ ^ pg rg -■ X 70 o e X o o o o oooooooo * KMMMKMMM OOOOOOOO — ♦♦♦♦*♦♦♦ ♦ ♦♦♦♦♦♦♦•♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ ♦ if>«r»*m«f-»o^M»o-<'v«o»o»<«»o-<«'# I I I I I I I I I I I I OOOOOOOO I I I I I I I I I I I I OOOmOOOO * — ♦♦♦♦♦♦♦♦ in — — '«->'> — — — ^mlMwO(^s^- fvi«p.QrMsp-aBnF-s ^ Ui X K I ^ o < : X X XXX o o o III ^i \^ ^ ^ ^ ^ ^ m ^ ^ uj ^ ^ m u ^ ^ yj lu ^ ^ m w lu ^ O id o o o fcd -^fMf^'^u>^^-cD(^o«4(^Jr^o<'|/^■0^-aD^O^4 K M K X ^ ^ vH X X ^ «-4 X X X K »4 X X XXX * * 1 • 1 * 1 ♦ 1 * * * 1 * 1 ♦ * * ♦ * 1 * * 1 1 1 ♦ ♦ ♦ in4CM«<^4•4 ^4 p4 C4 ^^1-4 114*4 cMCM^iM«cM^rM'a(«)'«in'Om«inai'iNrin «^(Mcn4''^a>0'Oin ^CMCMIMfNJ'4' •# ^iniM •Of- to (Mcg rg p. to » O 9' O .4 •* * * in CM m in CM •4 IM m in in in m xxxxxxxxxxxxx XXXXXKXXXX X X X X X X X X XXX XXX XXXXXKXXXX XXX X X X K K X X X X X X • 1 1 1 III 1 I 1 1 1 ********** * ♦ 1 1 1 1 ♦ * * * 1 1 1 * * * 1 1 1 1 1 ********** * * * 1 1 1 I ♦ ♦♦♦♦♦♦ 1 1 1 ♦ ♦ ♦ ♦ m* W^ .4 ♦ •* in « m a -4 »4 ^ Of-«o O *♦ m m o>4iM«n«.4(Mcn'«'^r4i«\^MCMm«B UN o •a ^ r.r- K ^- CM « m in o<^o^0aD«tol^Jcn^ln<^^(^9»rln•o inininininininininmmininininininininininininminininin«'0inininin«incnmin««««.#4'.^.#r-r~r-r->t'#<#'*r--r-p- XXXXXXXXXXXXXXKXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXKKXXKXKXXKXXXX ^^^-K^•K^•^-^^"^.^-^•^.^•^»^.^.^.^^-KcMcM^MCM■♦***CM<^lCM»■•♦^lnor- cMoor^h*i->f-KP-^f*p^^eoaotoQDtoqDa) 72 •4 NO ♦ ♦ ♦ » K S «♦«♦«*«♦♦ KKMKMKKMK ♦ « « • ON ♦ ♦ ♦ ♦ * * ♦ « « * « ♦ m O o » » m ■# ■» K K K K X X X X X X ♦«*««♦*♦«♦ * * * * «> » e m ♦ ♦ ♦ 3 K • (M CM N ♦ ♦ ♦ m mm * * m * ♦ * •♦ 3 3 * •M * * ♦ ♦ ♦ r- <^ ^- m m m * * m * * ?oo — 2S^r^^ K M M K XXX K X X X X XX X X X X XXX X X X X 1 1 1 1 1 1 ♦♦♦♦♦♦♦♦♦♦ till * * * * • 1 I * * * i i 1 * * * • ♦ ♦ • * * * * * ♦ 1 1 ♦ ♦ 1 • 1 * * * ♦ 1 ♦ 1 • * * 1 1 1 1 1 1 1 i .M ^.t (M CMm ♦ IM IM «M iM m m IM^. m •-■♦•♦ 1*> m •♦ m ♦ •# «^ •e in ir ir>r-r~ii>in# m m wt H Id * 't ir> it\ ie\ XXKXXXKXXXXXXXXKXXXXXXXXXXXXXXXXKXXXXXXXXXXXXX ) I • I I I I • I • I I I I I I I ) I I I ********************************************** Hi lU lAJ m tlJ lAJ m UJ ilJ 111 111 til m In iti Hi 111 III ^|« t|p lii iti II* 1^1 111 m III ^n titt|. iti i|i 1(1 It! Ill HI i|i 111 n4 1 lij tn .11 m m *40000^*4^4^000000000000rsj4rgfgrMCMN(^OCMOrgOrMOi>lOfNjOfM*4fg ) III! I I I I • I I I t I I I I 73 ♦♦♦♦♦♦♦♦♦♦ oooooooooo ouuouuuoou X XX X X XXX XX 3333333333 U.ILU.U.U.U.U.ILI1.U. 7h ********** oooooooooo 3333333333 oooooeooo 75 m o •^ e •« o z o r- ee 0.4 K •'O OM ^ r> e K o K r- o e>-t •I h> .M e ,4 r> m e aH a^ o me •4(M o t^o o«M h- ^• e a 4^• e o 4 «M •^ .^ O •< •« I • I <# aM e >4 N -< 1 I « r- e oiM ^- ^-.^ O IM fn »>■ e e e « ^• •-■ e o " 4> m •< t-t o o s ft. h- «• U III lU m o e e 4 O >4 p4 ^ <>( m « « « e'o >4 «/) ui m ^ IK oo o u > u «M o e o p4 0-4 ti4 1 ^^ ^^ ^^ T ^-» •^ m in N M « « •♦ <«• m Vt o 1 1 1 1 m •» !tl I/I 1 M M h> Ol r4 o «4 O >40 «4e »< CM m > > > 4 e •4 Oil o M M )< M •-HM m S X X ^o e ^ O O O ^4 ^4 v4 N' » N « N N H »< «M m ♦ if> « r- ,^ r4 m -t it\ o f~ >( K K K M X K ?0 O i-l O O •-■ N N II II N n O t-) <^' m '4' tri « -4 «Nj m * m >o K W X K X X » X o o e o o o -4 (^ o ^4 IM m « m CM m * in « f- X X X X X X X o o o •-< o e o • » e -4 iM m « •-< m ■# in <0 F- X X X X X X X O P ^4 o •^ o o K T II N N N II r- • 9 o •-■ CM m w CM -r in « f- X X X X X X K o e o •-< •4 o o « ^ ■> ^ O ^ CM »4 cMm in « f- X X X X X X X o o o o o o o II H II N II N It in 4) ^» CD cr o t-4 r^ cM.m ^ « r- xxxxxxxx >40000000 <#in«r-B9'0'4 f^ (M m ^ in K 00 xxxxxxxx •mOOOOOOO «>f'4'in.>..><«-> cMi'i'#in'OKoo> »4 CM m •«• in o t- •4 o o .^ xxxxxxxx X ac X X .MCMmnilMIIIIIIIIN •'•••••4rMm-rin«r>B >>> ^cMm'4-in-Oh-i xxxxxxxx z I/I .o a. o> o CD l/l U. CM X o X Ol o 76 APPENDIX B SUMMARY OF PARAMETERS AND VARIABLES The parameters and variables used in the algebraic descriptions of the inequalities and additional inequalities given in Chapter 2, Chapter h, Appendix A and Appendix C are listed below. 1. n is the number of external variables (x. ) in the network. 2. R is the total number of gates in the network. 3. m is the number of output functions (gates) in the network. k. w. represents the connection of external variable x to gate k. X) t 5. When the complements of the external variables are available, k — V, represents the connection from external variable x to gate k. 6. a., represents the connection from gate i to gate k, 7. P. denotes the output value of the i-th gate when the external variables connected to the network assume the values of input vector X (j) 8. ^[p = a., v[^\ ik ik 1 9. 7., = OL., (1-P. (used only for mixed gate networks). ik ik 1 10. \. indicates the type of gate i in mixed gate networks. The A. definitions are summarized in Table Bl. Gate types in the network A.. = \. = 1 1 1 nor/nand nor/and and/or NAND NOR AND NOR AND OR Table Bl. The \ representation in mixed gate networks. 77 APPENDIX C ADDITIONAL INEQUALITIES Section 2.3 contains a discussion of the additional inequalities for NOR networks in which the complements of the external variables are not available. Also, the additional inequalities for AKTO/OR networks which have 2 external variables and 3 gates are discussed in APPENDIX A. The purpose of this appendix is to give a complete general description of the additional inequalities for NOR, NOR/NAND, NOR/AND and AND/OR networks as they are generated by the current versions of GEN-IEQ,. (Also, differences between the current versions and earlier versions of the additional inequalities will be mentioned whenever appropriate. ) Other discussions of these additional in- equalities are given in [l], [5] , [12] , [1^+] . For each additional inequality given below, a verbal description is followed by an algebraic description in terms of some of the parameters and variables defined in Appendix B. Some of these additional inequalities may have to be modified or deleted if other inequalities such as those for fan- in and/or fan-out restrictions are added to the program. I. Input Inequalities A. NOR Networks When the complements of the external variables are not avail- able, each gate except the output gates has at least one input from the external variables or at least two inputs from the other gates. 78 n R 2 Z w^ + Z a., > 2 t=l * i=l ^^- k = m+1, . . . , R When the complements of the external variables are available, each gate except the output gates has at least two inputs. n ^ n R Z w + z V . + z a., > 2 t.l * t=l ^ 1=1 ^^- k = m+1, . . , , R B. nor/and Networks Each AND gate has at least two inputs and each NOR gate has at least one input. n R Z w , -f Z a., + \. > 2 t=l ^ i=l ^^ ^- or k = 1, ..._, R "^ k ^ k ^ Z w , + Z V , + z a., + \. > 2 t=l ^ t=l ^ iA ^^ ^" k = 1, • • • , R when the complements are available. C. NOR/NAND Networks Each gate has at least one input. n k R z w + z a > 1 t=l 1=1 iA k = 1, . .. , R or n , n , R Z w + Z V + Z a > 1 t=l ^ t=l "^ i=l "-^ ~ i^ when the complements are available. k = 1, ..., R D. AKD/OR Networks Each gate has at least two inputs, ^ k '^ k ^ Z w + Z V + Z OL >2 t=l ^ t=l ^ i=l ^^ iA k = 1, ..., R II. General Triangular Condition - NOR, NOR/NAMD and NOR/AND Networks, 79 no other output connections Figure CI. General Triangular Condition 80 A. If three gates are connected as shown in Fig. CI, then it can be proven that the network is not optimal. R -a. . - a., - a., + L a. „ > -2 ij ik jk ^^^ j^ - i/i i = h, ..., R J = h, ..., R k = 1, • • • , R i ;^d /k where h = 1 if m > 1 and h = 2 if m = 1. That is, gate i or gate j can be gate 1 (always an output gate) if the network is a multiple -output network. (It should be noted that in earlier versions of the program h = 1 was always used for NOR networks while h = 2 was always used for NOR/NAITO and NOR/AND networks.) B. Even if gate i in Fig. CI is replaced by an external variable, the network is not optimal. When the complements are not available: k ^ -^. - w^ - Q., + Z a. ,, > -2 t t jk ^^^ ji - j = h, . . . , R k = 1, . . . , R J ^ k t = 1, . . , n 81 Also, when the complements x are available: -vi - v_^ - a., + E a.n> -2. jk i=l m ji j = h, ' • * } R k = 1, . . . , R J ^ k t = 1, ... J n Again h = 1 if m > 1 and h = 2 if m = 1. (Also, as above, in earlier versions of the program, h ^ 1 was always used for NOR networks and h = 2 was always used for NOR/NAND and NOR/AND networks., In addition, the inequalities for the case when the complements are available were not included previously for NOR/ MND and NOR/AMD networks even when the complements were avail- able. ) III. Extended Triangular Inequalities other output connections permitted Figure C2. Extended Triangular Condition 82 A. nor/and Networks If three gates are connected as in Fig. C2 and at least one of gates j and k is an AND gate, then the general triangular con- dition holds even if gate j has other output connections. -a. . - a., - a., + \. > -2 "> i = h, ..., r ^^ ^^ ^^ ^ ~ [ j = h, ..., R -a. . - a., - a., + A. > -2 ( ^ j '^'I'y ^ ij ik jk k - J 1 / J / k This condition is still true if gate i is replaced by an external variable. When the complements are not available: 'wi - vr - a + X. > -2 ~^ j = h, ..., R ^ * ^^ ^ " I k = 1, ..., R t t jk k— J t=l, ...,n When the complements are available: -t -\ -"ok ^^5 ^-2 ^ i:i::::;R t t ik k— J t=l, ...,n Again h = 1 if m > 1 and h = 2 if m = 1. (Only h = 2 was used in earlier versions. Also, the inequalities for the case when the complements are available were omitted previously even when the complements were available. ) B. NOR/NAND Networks If gate j is a NOR gate and gate k is a NAND gate or vice versa, then the general triangular condition holds even if gate j has other output connections. 83 -a. . - a., - a., - \. + \ > -3 ij ik jk J k - ■a. . - a., - oc., + k. - \ > -3 xj ik jk J K - i = h, . . . , R j = h, . . ., R k = 1, ..., R This condition is still valid even if gate i is replaced by an external variable. When the complements are not available: t t 3 k t t a ■jk ^j + \ > -3 a., + X. - \ > -3 ok J k - ^ j = h, • • • ^ R k =1, ..., R J /^ k t =1, . . . , n When the complements are available: ■^ - ^t - °jk - ^0 ^ \ > -3 ■^t - ^t - «Jk + ^j - \ > -3 j = h^ • • • ^ R k = 1, ..., R J ^ k t =1, . . . , n As before, h = 1 if m > 1 and h = 2 if ra = 1. (Only h = 2 was used in earlier versions of ILLODIE-AIF. Also, the inequalities for the case when the complements are available were omitted pre- viously even when the complements were available. ) C. AKD/OR Networks If three gates are connected as in Fig. C2, then the network is not optimal. -a. . - a., - a.^ > -2 i = h, . . . , R 13 IK JK — j = h, ... , R k = 1, ..., R i ^ 3 ^^ Qk Again h = 1 if m > 1 and h = 2 if m = 1. (Only h = 1 was used in earlier versions of the program. ) IV. Output Condition - NOR, NOR/AIJD, NOR/NAKD and AND/OR Networks All gates except the output gates connect to at least one gate. R k=l Mi V. Connections to Outputs Condition - NOR, NOR/ AND and NOR/NAND Networks Gates which are connected to all of the output gates are not con- nected to any other gates. m R -U Z a. . - Z a > -(raXU) j=l ^^ k^+1 ^^ k;^i i = m+1, . . . , R Here U = n+R+2. VI. Other Conditions A. NOR/NAND Networks If gate i has only one input, it can be a NOR gate (i,e., \ can be set to 1 and underlined). n . R Z w^ + Z a + \ > 2 i = 1, . . . , R t=l ^ k=l ^^ ^ ~ k/i or 85 n . n . R Z w + Z V + Z t=l ^ t=l "^ k-1 OL . + \. > 2 Kl 1 — X ~ X f % . , y R k^i when the complements are available. (Early versions of the program did not generate any inequalities for this condition when the com- plements were available. A later version of the program generated only the second set of inequalities even when the complements were not available. This had the effect of generating the following inequalities when the complements were not available: n . R 2Z wj+ Z a.+A.. >2 t=.l ^ k==l^^ ^- i = 1, ..., R Mi These inequalities are not incorrect, but they are less restrictive than desired. ) B. and/or Networks 1. If gate i connects only to gate j, then gates i and j must not be of the same type. R X. + \. - a. . + z a,, > kii R ■\. - X. - a. . + z a., > -2 1 J ij ^^1 ik- k;^i >l J i = m+l, . . . , R j =1, . . • , R i ^ J 86 The first inequality keeps both gates from being AND gates while the second inequality keeps both gates from being OR gates. 2. Each network has at least one AND gate and at least one OR gate. Z X.. > 1 i.l ^- R - Z X. > -(R-1) i=l ^- This concludes the discussion of the additional inequalities in- cluded in the current versions of GEN-IE^. However, other additional inequal- ities can be added. For example, consider using ILLODIE-AIF to design networks under fan-in and fan-out restrictions. The following inequalities will incorporate such restrictions: n . R - Z w^ - Z a. . > -FI j = 1, . . . , R t=l ^ i=l ^J - or i;^j n . n . R ■ Z w^ - Z v^ - Z a. . > -FT j = 1, . . . , R t=l ^ t=l ^ i=l ^^ i^J when the complements of the external variables are available. 8? and R ■ Z a. . > -FO i= m+1, . . . , R 3=1 "-' - R -La... > -FOO i =1, . . . , m ^ k - Z w > -FOX t =1, . . . , n k=l ^ ^ k - Z V > -FOX t - 1, . . . , n k=l ^ when the complements are available. In the above equations FT, FO, FOO and FOX denote the maxim-am fan-in for gates, the maximum fan-out for non-output gates, the maximum fan -out for output gates and. the maximum fan -out for external variables, respectively. The user must be careful when adding other inequalities such as those for fan-in and fan-out restrictions into the program since the new inequalities may make some of the current ones invalid. For example, the input inequalities given in I for NOR, NOR/AM) and MD/OR networks do not hold in general when the fan -in restriction is imposed. 88 LIST OF REFERENCES [l] Baugh, C.R. , Ibaraki, T. , Liu, T.K. and Muroga, S. , "Optimal Network Design Using NOR and NOR-AND Gates by Integer Programming", Report No. 293; Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, January, 1969* [2] Davidson, E.S., "An Algorithm for NAND Decomposition of Combinational Switching Systems", Ph.D. dissertation. Department of Electrical Engineering and Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, Illinois, I968. [3] Geofferion, Arthur M. , "Integer Programming by Implicit Enumeration and Balas' Method", SIAM Review , Vol. 9, No. 2, pp. I78-I9O, April, I967. [k] Ibaraki, T. , Baugh, C.R. , Liu, T.K. and Muroga, S. , "An Implicit Enumer- ation Program for Zero-One Integer Programming", Report No. 305, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, January, 1969. Also published in International Journal of Computer and Information Sciences, pp. 75-92, March , 1972. [5] Ibaraki, T. , Djachan, D. , Liu, T.K. and Muroga, S. , "Synthesis of Optimal Networks With NOR and NAND Gates by Integer Programming", Report No. 427, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, January, 1971« [6] Liu, T.K., "A Code for Zero-One Integer Linear Programming by Implicit Enumeration", Master Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, I968. [7] Mora-Tovar, Jose J., "A Study of the Effect of Additional Inequalities in Integer Programming for Logical Design", Master Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, August, 1972. [8] Muroga, S., Threshold Logic and Its Applications , Wiley- Interscience, John Wiley & Sons, New York, Chapter Ik, I97I. [9] Muroga, S. and Ibaraki, T. , "Design of Optimal Switching Networks by Integer Programming", IEEE TC , Vol. C-21, No. 6, pp. 573-582, June, 1972. [10] Muroga, S. and Ibaraki, T. , "Logical Design of an Optimal Network by Integer Linear Programming - Part I", Report No. 26h, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, July, I968. [11] Muroga, S. and Ibaraki, T. , "Logical Design of an Optimal Network by Integer Linear Programming - Part II", Report No. 289, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, December, I968. 89 [12] Nakagawa, T. and Muroga, S. , "Comparison of the Implicit Enumeration Method and the Branch- and -Bound Method for Logical Design", Report No. h33, Department of Computer Science, University of Illinois at Urbana- Champaign, Urbana, Illinois, June, 1971' [13] Nakagawa, T. and Muroga, S. , "Exposition of Davidson's Thesis 'An Algo- rithm for NAND Decomposition of Combinational Switching Systems"' , UIUCDCS-F-7I-869, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, August, 1969- [ik] Shiau, L.E., "Design of Optimal One-Bit Adder Networks by Integer Linear Programming", Master Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, January, 1971* 90 PROGRAM LISTING « » * xxxxx * * * ♦ * * * X( JX) = S(JAD) = JX = JX+ DO I SUP IF IC PS(S (PS(S ( N S ( S (CLSP CLSPCNCT NCT3=SUti CLSP(NCT IF IF IF PT LT -ilE LT. -CH CF( JAD 1 1 00 = R LCF UB) Ud) U<^) (SU 3) = ( JAD +1) (JAD -H ) -l+S^G G) .LT. ) RETURN ) GOTO 200 ANGE POS SUM (PS) AND JAD) 1= BEG, END 0W( I ) (I)) 40,100,60 = PS(SUB) * CLCFI I ) .LT. 0» GO TO 90 ) 50, 100 ,100 6) .NE. 0) GO TO 100 SUB NIPT U4 N NCX COL (20000) R*=A SUBK VN)=I SUB2(VN)=J SUP( VN)=0 30 CONTINUE DO 40 K=l, NIPT VN=$P( I ,K) TP(VN)=P SUBK VN) = I SUB2( VN)=0 SUPIVN )=K 40 CONTINUE IF (VN .GT. Nl GO TO 50 VN=$L( I ) TP( VN)=L SUBK VN)=I SU82( VN)=0 SUP( VN)=0 50 CONTINUE RETURN END SUBROUTINE IMPLICIT I INTEGER*4 COMMON » COMMON COMMO DTPSNS ilXf *, NTEGER*2 ( A-T , V NOGT, NOVR» NIP NOVR U2 ZBAR KS JTS ROW (20000) PS ( 4000) CLPT( 2000) X I 2000) SUB2( 2000) CLLS( 2000) NCT5 NUNDLX *) -Z,$) Tt NOPT NOGT U3 M JX CLCF(20000) ^WPT( 4000) NS I CLLT( XS ( SUP ( NCT2 NCT6 NFIXJ 4000) 2000) 2000) 2000) NIPT U4 N NCX COL (20000) RWLTI 4000) CLVT( 4000) OF ( 2000) S ( 2000) TP ( 2000) NCT3 NGETYS RWLS( 4000) U3=U3+1 BEG = CLPT (JAD +1) ENO = CLLT (JAD *l ) -K-BEG IF( (END-BEG) .LT. ) RETURN IF{ KS .LT. ) GOTO 200 XCL)=1 CHANGE POS SUM (PS) AND NCX=NCX4-0F( JAD) X(JX) = JAD NEG SU>^ (NS) NOPT JAO LTS ewCF(20000) YS ( 4000) CLSP( 4000) XHAT( 2000) SUBK 2000) NCT4 NNEWX S(JAD) = 1 JX = JX+1 00 100 SUB = RO IF(CLCF( 40 PS(SUB» IP (PS(SUb) IF (NS(SUB)) 50 IF (CLSPCSUB CLSP(NCT3I=S NCT3=SUB CLSP(NCT3)=S GOTO 100 60 NS(SUB) 100 CONTINUE IF (JX .GT. RETURN 90 IP (I .Eg. E 11=1+1 DC 98 K = I I , SUB = RGW(K) IF (CLCF(K)) 92 PS{SU8)=PS(S GO TO 98 9b NS{SUB)=NS(S 98 CONTINUE 99 RETURN 1 X(L) = CH 20U X(JX) =-JAO S(JAO) = -1 JX = JX+1 DO 300 SUB = RQ in CLCF 240 NSISUB) GOTO 300 260 PS(SU3) IF (PSISUB) If^ (NS(SU3)) 270 IF (CLSPISUB CLSP(NCT3J=S NCT3=SUR CLSP{NCT3)=S 300 CONTINUE IF (JX .GT. RETURN 310 IF (I .FQ. t 11=1+1 no 318 K = I I , SUB = RUW(K) IF (CLCF(K)) 312 NS( SUB)=NS( S GO TO 318 315 PS(SUB)=PS(S 318 CONTINUE 320 RETURN 1 400 RETURN 2 END 1= BEG, END W( I ) D) 40,100,60 = PS(SUB) + CLCFd ) .LT. 0) GO TO 90 50, 100 ,100 ) .NE. 0) GO TO 100 UB UB = NS(SUB) + CLCF( I ) N) GO TO 400 ND) GO TO 99 END 92,98,95 UB)+CLCF(K) UB)+CLCF(K) ANGE P3S SUM (PS) AND NtG SUM (NS) 1= BEG, END W( I ) ( I ) ) 240,300,260 = NS( SUB) - CLCF( 1 ) = PS(SUB) - CLCF( I ) . LT. 0) GO TO 310 270, 300, 300 ) .NE. 0)G0 TO 300 UB UB N) GO TO 400 ND) GO TO 320 END 312, 318,315 UB)-CLCF{K) UB)-CLCF(K) SUBROUTINE EXTDX (ZX, *,♦,*) IMPLICIT INTEGER*2 IA-T,V-Z,$) INTEGER*^ NOGT, NOVR» NIPT, NOPT COMMON 1 f COMMON L 2 .3 5 6 7 NOVR U2 ZBAR KS JTS ROW (20000) COMMON PS ( CLPT( X I SU02< CLLSC NCT5 NUNOLX '. (NUM. 4000) 2000) 2 000) 2000) 2000) NOGT U3 M JX CLCF(20000) RWPTI 4000) &3, NS ( CLLTI XS ( SUP ( NCT2 NCTS NFIXJ &400I 4000) 2000) 2000) 2000) NCT3)GU TO 310 .GE. 0) GO TO 10 70, 130 .NE. 0) RETUt^N I RWLT( I ) - I .NE. 0) GOTH 5 NENP ) GOTO 10 c t CALL MAX Z RETURN I 3 I=NCT2 U4 = U4+1. GO TU 4 10 IF (I .Eg. I=NCT2 4 NCT2 = CLSP( I I CLSP( I )=0 IF (NSI I ) R=PS( I ) IF(k) 30, 30 CONTINUE IF (CLSP(I) CLSP( I )=NCT2 NCT2=I RETURN 1 70 NbEG = RWPT( I ) NEND = N8FG ♦ IF (CGL(NBEG) NBEG = NBEG+1 5 IF (NBEG .GT. DO 80 K=NflEG,NEND SU8=CnL( K) IF(S(SUB).NE.O) GO TO flO IF(RWCF(K)| 110, 80, 120 llO XS( JX) =-SUB JAO=SUR KS = -1 CALL CGPSNS ( Z X , (130,&400» GO TO 80 120 XS(JX)=-SUB KS = 1 JAD=SUB CALL CGPSNS ( ZX , (.30, &400 ) 80 CONTINUE IF (NCX .GE. ZBAR) GO TO 30 GO TO 10 130 NBEG=RWPT( I ) NEND=NBEG+RWLT( I ) -1 IF (COL(NBEG) .EJ. 0) NBEG=NBEG+1 IF (NBEG .GT. NENO) GO TO 10 135 DO 140 K=N8EG,NEN0 SU8=C0L( K) IF (RWCF(K) .GT. R) GO TO 130 IF ( -RwCF(K» .LE. R) GO TO 10 NIPT U4 N NCX COL (20000) RWLT( 4000) CLVT( 4000) OF ( 2300) S ( 2000) TP ( 2000) NCT3 NGETYS KWLS( 4000) NGPT JAO LTS RWCF(20000» YS ( 4000) CLSP( 40001 XHAT( 2000) SUBK 2000) NCT4 NNEWX 180 UO 310 320 325 400 (ZX,&30*&^00) ,NE 0) GF GO TO 140 ZBAR> GO ir (S(SUB) .NE. 0) GO TO 140 XS( JX)=-SUB JAO=SUB KS = -1 CALl CGPSNS GO TO 140 IF ( S(SUB) IF (NCX+OF(SUB) JAD=SUB XS( JX)=-SU8 KS = I CALL CGPSNS CONTINUE GO TO 10 CONTINUE CONTINUE IF (CLSP(I) CLSPI I )=NCT2 NCT2=I NUM = CALL MAXZ (NUM,KJ25,&400) RETURN 1 TO 30 (2X,G30,&400I NE. 0) RETURN 2 IF (NUM RETURN 2 CONTINUE IF (CLSP( I ) CLSP( I )=NrT2 NCT2=I RETURN 3 END Q. -n GO TO 3 ,Nb. 0) RETURN 3 SUB IMP INT COM COM ROUT I L ICIT EGER* MON f MON COMMON DAT DAT DIM CAL JAD DIN ONE TYP DO IF 00 IF 20 CON A WWT A GS ENSIO L LST = P = NIP = 1 E = -l no G ( lEND 20 AA (GT. T I N Ut NE FIXJ INTEGE 4 NGGT, NOVR U2 ZbAR KS JTS ROW ( PS ( CLPTI X ( SUB2i CLLS( NCT5 NUNOL ♦BBT,AA ♦VC$,GC N ISGT ISG( ISG T*2 (ZX *) R*2 {A-T,V-Z,$) NOVR, NIPT, NOPT NOGT U3 M JX CLCF(20000) RWPT( 4000) 20000) 4000) 2000 ) 2000) 2000) 2000) NS ( CLLT( XS i SUP ( NCT2 NCT6 NFIXJ T,PPT,LLT,GGT $,G$C$,NWG /I (20) , CNKGT (20) T, CNKGT, lEND, 4000) 2000) 2000) 2000) /I. 2, 3, 4, 2, 3. 4, 5 CEND) NIPT U4 N NCX COL (20000) RWLT( 4000) 4000) 2000) 2000) 200C) CLVT( OF ( S ( TP ( NCT3 NGETYS RWLS( 4000) 5,6 / / T=l,NGGT .EQ. 0) GO TO 25 =1, lEND EO. ISGT( AA) ) GO TO 110 NOPT JAO LTS RWCF(200G0) YS ( 4000) CLSP( 4000) XHAT( 2000) SJ-^K 2000) NCT4 NNEWX 25 CONTINUE SRT=DINP*(GT-l) IF ($L(ONE) .LE. N» SRT=SRT»2 DO 100 K=l,NIPT SUB=$P1GT,K) IF (S(SUB) .Eg. 0) GO TO 100 I I=SRT+K IF (NS( I I » .GE. 01 GO TO 21 BEG=RWPT (II ) EN0=8EG+RWLT( I I)-l GO TO 29 27 IF (NSdI+DINP) .GE. 01 GO TO 100 IF (iL(ONE) .GT. N I GO TO 100 8EG=RWPT( II+OINP) END=BEG+KWLT( II«-DINP)-l 29 CONTINUE COONT=0 ISCONT=0 SMCT=5000 ISB=5000 WB=N+l ODR=100 3i> DO 90 L=BEG,END SUB = COHL) IF ( SUB .LE. 0) GO TO 90 IF ISISUB) .NE. 0) GO TO 90 IF (SUB2(SUB) .NE. 01 GO TO 30 IF (TP(SUB) .NE. LLT) GO TO 36 KS = l JAD=SUR XS( JX)=JAO CALL CGPSNS ( Z X , &200, &220 ) RETURN I 16 CONTINUE COUNT=CUUNT+I IF (ODR .LE. VC$) GO TO 90 Wrt=SUB OOK=VC$ GO TO 90 30 IF ( lEND .EG. 0) GO TO ^3 on ^0 AA = l, I END IF (SUBKSUBJ .NE. ISGT(AA)) GO TO ^0 ISCUNT=ISC0NT+1 IF ( ISR .LT. SUB) GO TO 90 IS8=SUB GO TO 90 40 CONTINUE 45 CONTINUE C0UNT=C0UNT+1 A2=$AI SUBl (SUb) , SU82(SU3)» IF ( S(A2)) 50, 50, 60 50 PP=$P(SUBl(SUB) ,K) IF {S{PP> .NE. 0) GO TO 55 IF (ODR .LE. G$C$) GO TO 90 Wb=SUB ODR=G$C$ GO TO 90 55 IF (ODR .LE. GC$) GO TO 90 WB=SUB OOR=GC$ GO TO 90 60 IF (ODR .LE. G$l GO TO 90 UOk=Gt WB=SUB 90 CONTINUE 6t) IF (WB .L6. N) GO TO 95 70 IF (ISB .EQ. bOOO) RETURN JAD=ISB GO TO 1^0 95 CONTINUE IF (ISCONT .GE. l> COUNT=COUNT+l IP (TYPE-OOR) 152,151,100 151 IF (SMCT .LE. COUNTJ GO TO 100 GO 70 153 15? TyPE=ODK 153 S^CT=CCUNT JAn=WH 100 CONTINUE 110 CONTINUE IF (JAD .EQ. 0) GO TO 201 KS = 1 XS( JX)=JAD CALL CGPSNSCZX, &200, £220) RETURN 1 120 KS=1 X<^ (JX)=-JAO GTKT=JAD CALL CGPSNS (ZX, f.?00, &220I IF ( iL(ONE) .GT. N) RETURN 1 JAl) = $L(SUB1( JAD) J IF (S(JAD) .NE. 0) GO TO 210 GTFD=$L(SUB2(GTKT )) IF (S(GTFO)) 51,51,61 51 KS=1 GO TO 121 61 KS=-1 121 XS(JX)=JAO CALL CGPSNS ( ZX , L2Q0fL2ZO) 210 RETURN I 200 RETURN 201 IF ($L(ONF) .GT. N ) RETUi-^N 2 DO 205 I=1,N0GT AB=$L{ I > IF (S( AB) .NE. 0) GO TO 205 JAO=AB KS = -1 XS( JX»=JAD CALL CGPSNS (ZX, G200, &220) RETURN 1 205 CONTINUE 220 RETURN 2 END INTEGER FUNCTION FUNCT*2(XX, Y ) IMPLICIT INTEGER*? (A-T,V-Z,t) INTEGER*^ XX, Y, NV,NG, NRG, NIPT INTEGER*^ NOGT, NOVR, NIPT, NOPT COMMON NOVR , NOGT I , 02 , U3 COMMON ZBAR , M I , KS , JX f NIPT » NOP t U4 f N f JAD t NCX f LTS I , JTS , CLCF(20000), COL (20000), RWCF(20000) 3 . ROW (20000)i , RWPT( 4000) f RWLK 4000), YS ( 4000) * f PS C 4000), NS ( 4000) , r CLVTi 4000), CLSPC 4000) 5 , CLPT{ 20001 CLLT( 2000), OF { 2000), XHAT( 2000) 6 , X ( 2000) , XS ( 2000) r S ( 2000), SUBK 2000) 7 , SUB2( 2000), » SUP ( 2000), » TP ( 2000) COMMON CLLS( 2000), NCT2 NCT3 , NCT4 I NCT5 , , NCT6 , NGETYS , NNEMX 2 NUNDLX , NFIXJ , RWLS( 4000) DATA CP /•CP« / NV=XX NG=Y NIPT=2**NV NBG=NIPT*(NG-l) WB=1 V8=WB+NV*NG IF (NCT5 .NE. CP) VB=WB 6ETA=V8+NV*NG ALPHA=BETA+NBG*NG PB=ALPHA+(NG-1 )*NG LAMDA=P6+NIPT*NG GAMA=LAMDA+NG FUNCT=NflG RETURN ENTRY i^i I ,K) $W =WB+NV*( I-l)«-K-l RETURN ENTRY $V(I,K) iV =V8+NV*( I-l )+K-l RETURN ENTRY i3( I , J,K) JJ = J IF (J.GT.I) JJ=JJ-1 $H =BtTA*NBG*( I -I ) ♦N I PT* ( J J- 1 ) +K- I RETURN ENTRY $ACI , J) JJ = J IF (J .GT. I) JJ=JJ-l $A =ALPHA+ (NG-1 )♦ ( I-l ) RETURN ENTkY SP(I,K) tP =PB+NI PT«( I-l) +K-1 RETURN FNTRY $L ( I ) $L =LAM0A+I-1 RETURN ENTKY $G(I,J,K) JJ = J IF (J. GT. I) JJ=JJ-l $G =GAMA+NbG*i I-l )+NIP" RETURN END ♦ J J-1 'T«( JJ-i )*K-l I SUBROUTINE GEOF (UB) IMPLICIT INTEGER+2 (A-T,V-Z,S) INTEGER*4 NUGT, NHVR, NIPT, NOPT INTtGER*4 TIME ,ITIMEZ , CT 1 , CT2 , CT3 , CT4 , CT5 , CT6 , C T 7 ,C T d INTEGER*4 KT I M EZ , JT IMEZ , I T I ME COMMON NOVR , NOGT , NIPT , NOPT » U2 , U3 , U4 CUMKON CGMMflN 1 iO 30U 10^0 15 25 35 30 40 1010 50 1030 DIMFNS RrAf 1 IF (16 CALL P MND=JX on 5 I li- (X( JAD=X( CALL P CONTIN FORMAT CT2 = CT3 = CT4 = CT5 = cr6 = CT7 = CT3 =0 NFS = U=KT IM 'J=U-5 5 IJ=U/10 PRINT FORMAT ITI,VE = CALL S UTIN:E = DO 8 DO 7 5 DO 70 CT2 = hi 'P VAT CALL E CGMTIN GOTL; 5 CONTIN CT4 = GOTO 6 CONTIN CT5 = GOTT 5 CONTIN CT7 = FORMAT CALL F GO TO CONTIN FORNAT CALL N CTl = i|2 lU 30 AR Rt -I = 1 I ) I) HB UE ( ZtiAR KS JTS ROW (20000) PS ( -^000) CLPT( 2000) X ( 2000) SUB2I 2000) CLLS( 2000) NCT5 NUNULX N DUMMY(2500) ,ZrtAR .LT. ) GO TO SET (ZX, &300) JX CLCF( 20000) RWPT( 4000) NS ( CLLT( XS ( SUP ( NCT2 NCT6 NFIXJ 4000) 2000 ) 2000) 2000) N NCX COL (20000) RWLT( 4000) CLVT( 4000) OF ( 2000) S ( 2000) TP ( 2000) NCT3 NGtTYS RWLS( 4000) JAO LTS RWCF(20000) YS ( 4000) CLSP( 4000) XHAT( 2J00) SUBK 2000) NCT4 NNFWX 80 ,NND .LE. 0) GO TO 5 LP(ZX,t5,C5) 115) £Z 0. 30 ( • 36 TI KT KK II LK CT ( XT UE UE CT ue CT UE CT ( IX 60 UE ( (•CANC ) o,u OTI 000 MFZ I ^E 2 + 1 //• DX ME IN SECONOS I S • fi-H,Z ) ( ITIME) ZI 0) I ,20 1, 2 1000 ENTER EXTDX' ) (ZX,&25,&30,&35) 4+1 5 + 1 7+1 //•ENTER FIXJ') J(ZX,&70,&15) //•ENTER NFWX* ) X (ZX, f.60) CT3 = U4 CT6=U3 PRINT 310, NCX ,CT1 , CT2,CT3, CT4, CT5,CT6 , CT7 ,CT8 OF'.llX, 'GETYSSex, 'NO. ITER* ,7X, • CYCLES • ,5X UNFS«,5X, 'EXTDX FSBL«,6X, • CGPSNS •,9X, 'FIXJ* ,10X 2,'0FBND«, / 19,8115 ) ST=1 PTS=0 N8 = CALL PRNTCXHAT, ST, N8, PTS) 60 CONTINUE 1020 FORMAT (//'ENTER UNOLX') CALL UNDLXCZX,665,&90,650) 65 CONTINUE 70 CONTINUE U=KTIMEZ(0)-UTIME U=U/100. PRINT 300, U ST=0 NR = PTS = 1 CALL PRNT (XHAT, ST, NB , PTS) CTUU2 CT3 = UA CT6=U3 PRINT 310, NCX ,CTl , CT2,CT3, CT4, CT5,CT6 , CT7 ,CT8 7b CONTINUE BEG = NI PT*NOPT-H ENO = jx 00 UO IN=BEG,ENO IF ( XS(IN) .EQ. X(IN)) GO TO 100 DUMMY (IN) = GO TO 110 100 DUMMY (IN) = 1 110 CONTINUE nUMMY(JX) = PUNCH 120, ( XS( IN),DUMMY( IN) , IN=dEG,tNDJ 120 FORMAT ( 12(15,11)) PUNCH 350,ZBAR 350 FORMAT (215) 80 CONTINUE 90 CONTINUE U=KTIMEZ(0)-UTIME U=U/100. PRINT 300, U CT1=U2 CT3 = U-V CT6=U3 ANCX=ZBAR-1 PRINT 310,ANCX ,CT1 , CT2,CT3, CT't, CT5,CT6 , CT7 ,CT9 360 FORMAT ( // /5X , • P SEU= • , I 1 5 , 5X , • ZERO= • , I 1 5 ) GO TO 1 800 RETURN END SUBROUTINE GETYS COMPUTE NEW YS(I) BY APPLYING COLUMN JAO IMPLICIT INTEGER*2 (A-T,V-Z,$) INTEGER*^ NOGT, NOVR, NIPT, NOPT COMMON NOVR , NOGT , NIPT , NOPT 1 t COMMON L 2 3 4 !> 6 7 U2 ZBAR KS JTS ROU ( PS I CLPT( X ( SUB2( CLLS( NCT3 NUNDL GETYS COMMON 1 Z f 42 FGRMATC U2=U2*l NCF=CLPT NCFFND = 1F(CLLT( UO 10 1= J = ROW( I ) YS( J)=YS( J)+CLC 10 CONTINUE 43 FCRMATC ^0 RETURN END (JAD+l) NCF *■ IJAD+l ) . =NCF,NCF GETYS 20000) 4000) 2000) 2000) 2000) 2000) ENTER CLLT( JAD EJ.O) GO E!>iD F( I)*KS EXIT • , U3 M JX CLCF(2U000) RWPTl 4000) NS ( CLLT( XS ( SUP ( NCT2 NCT6 NFIXJ + 1) -I TO 20 l>i) 4000) 2000) 2000) 2000) U4 N NCX COL (20000) RWLT( 4000) CLVT( 4000) OF ( 2000) S ( 2000) TP ( 2000) NCT3 NGETYS RWLS( 4000) JAD LTS RvJ3 H JX CLCF( 20000) KWPT( 4000) NS ( <,000) CLLT< 2000) XS ( 2000), SUP ( 2000) NCT2 NCT6 NFIXJ NIPT , U4 N NCX , COL (20000), RWLT( 4000), CLVT( 430J), OF ( 2000), S ( 2000), TP ( 2000) NCT3 , NGETYS , R>f5X,'N0 OF NGN ZERO COEF =«,I6) 10 30 40 50 SUBROUTINE IMPLICIT I INTEGfcR*4 COMMON I t COMMON 1 2 3 5 6 7 COMMON I 2 DIMENSION DO b AA=1, ISGT{AA)=0 CNKGT( AA)= CONTINUE DO 10 1=1 CNKGT( I )=I END1=NCPT EN02=0 BEG=N0PT+1 DO 50 I=B DO 30 J=l IF (J .EQ SU8 = $A( I ,J IF (SI SUB CONTINUE ENu2=END2+ ISGT(END2) GO TO 50 END1=ENDI+ CNKGT( ENDl CONTINUE RETURN END LSTISGdSGTt CNKGT, ENQ2, ENDIJ NTEGER*2 (A-T,V NOGT, NOVRt nip NOVK U2 ZflAR KS JTS ROV^ (20000) 4000) 2000) 2000) 2000) 2000) PS ( CLPT( X { SU32( CLLS( NCT5 NUNOLX ISGT(20) 20 ,NOPT -Z,$) T, NOPT NOGT 113 M JX CLCF(20000) RWPT( 4000) NS ( CLLT( XS ( SUP i NCT2 NCT6 NFIXJ CNKGT(20) EG, NOGT ,NOGT . I) GO TO 30 ) ) .GT. 0) GO TO 40 1 = 1 1 ) = I 4000) 2000) 2000) 2000) NIPT U4 N NCX COL (20000) RWLTI 4000) CLVT( 4000) OF ( 2000) S ( 2000) TP ( 2000) NCTJ NGETYS RWLS( 4000) NOOT JAD LTS RWCF(20000) YS ( 4000) CLSPt 4000) XHAT( 2000) SUBU 2000) NCT4 NNEv^X MAIN PROGRAM IMPLICIT [NTEGER*2 (A-T,V-Z,$) INTfcGFR*4 NOGT, NUVR , NI^T, NOPT TIME , ITIMEZ KTIMEZ ,JTIMEZ,ITIME NUVR , NOGT U2 , U3 ZDAR , M KS , JX JTS , CLCFI20000) ROW (20000), RWPT( 4000) PS ( 4000), NS ( 4000) CLPT( 2000), CLLT( 2000) X ( 2000), XS ( 2000) INTEGER*4 INTFGER*4 COMMON , COMMON NIPT , U4 N NCX , COL (20000), RWLT( 4000), CLVT( 400U), OF ( 2000), S ( 2000), NOPT JAD LTS RWCF( 20000) YS ( 4000) CLSP( 4000) XHATI 2000) SUBU 2000) 20 10 15 7 , SUB2( 2000), SUP ( 20001, TP ( 2000) COMMON CLLS{ 2000), NCT2 , NCT3 , NCT4 I , NCT5 , NCT6 , NGETYS , NNEWX 2 ♦ NUNDLX , NFIXJ , RMLS( 4000) EQUIVALENCE (TYIN,JXI DATA CARD/»CD'/ CONTINUE ITIME=360000 CALL STIMEZ(ITIME) CALL INTL IF (TYIN.EQ.CARL;» GO TO 10 CALL GTINEQ GO TO 15 CALL INTLC CALL TAbPT CALL CLFVAR CALL RWTUCL CALL GEOF (UB) GO TO 20 END SUBROUTINE MAX Z ( NUM, IMPLICIT INTEGER*2 (A-T, lNTbGER*4 COMMON COMMON , f f f * NJGT, NOVR, NI NOVR U2 ZBAR KS JTS ROW (20000) COMMON PS ( CLPT( X ( SUB2( CLLS( NCT5 NUNOLX 4000) 2000) 2000) 2000) 2 000) ♦,*) V-Z,S) PT, NOPT NOGT U3 M JX CLCF(20000) RWPT( 4000) IF (NCX-Z^AR+1) 15 CONTINUE RETURN 16 DO 17 K=l, N IF (OF(K) .EO. IF ( S(K) .NE. XS( JX)=-K NUM=-1 JAD = K KS = -1 CALL CGPSNS 17 CONTINUE 19 RETURN 1 20 RETURN 2 END 19, l(j NS ( CLLT( XS ( SUP ( NCT2 NCT6 NFIXJ 15 0) GO TO ) GO TO 17 17 (ZX,tI5,£20) 4000) 2000) 2000) 2000) NIPT U4 N NCX COL (20000) RWLTC 400J ) CLVT( OF ( S ( TP ( NCTi NGtTYS RWLSI 4000) ^000) 2000) 2000 ) 2000) NOPT JAD LTS RrtCF( 20000) YS ( 4000) CLSP( 4000) XHAT( 2000) SJBK 2000) NCT4 NNFWX SUBROUTINE NEWX (ZX, *) COMPARE ZrtAR AND OBJECTIVE FUNCTION IMPLICIT INTEGER*2 (A-T,v-Z,$) INTEGER+4 NOGT, NOVR, NIPT, NOPT COMMON NOVR , NOGT I f U2 , U3 TO FIND A NEW SOLJTION NIPT U4 NOPT COMMON ZBAR KS JTS ROW (200001 12 12 PS t 4000) CLPT{ 2000) X ( 2000) SUB2( 2000) COMMON CLLS( 2000) NCT!j MUNDLX A2 f-ORMAT(« MEV^X ENTER') if(ncx.(;e.zbar ) go to ZBAR = .MCX + l DO 10 K=1,N XHAT(K)=0 10 CONTINUE DO II L=1,N IF(X(L).LE.O) GO TO I I J=X(L) XHATC J)=l 11 CONTINUE LTS=1 Rt TllrJN CUNTINUE I Fi.)RMAT(« NEWX EXIT • , LTS=1 RETURN 1 ENO M JX CLCF(200aO) RWPT( 4000) NS ( CLLT( XS ( SUP ( NCT2 NCT6 NFIXJ 13) 4000) 2000) 2000) 2000) N NCX COL (20000) RWLT( 4000) CLVT( 4000) OF ( 2000) S ( 2000) TP < 2000) NCTi NGETYS RWLS( 4000) JAD LTS RWCF(20000) YS ( 4000) CLSP( 4000) XHAT( 2000) SJBK 2000) NCT4 NNEWX SU IM IN C J BKOU PLIC TfcGE MMON Ct.'MMON COMMON IF TH TO 01 OA IF IF FI RE EN SC IF 1 = on » OOF E GA GAT MEN'", TA W (T (S{ NP Gl = l 01 = 1 R( 1) (8 SCR( 10 TINE IT IN R*4 N N U Z K J R P C X s C N N INTE TES P E J ION f B,A, P( JAD JAD) THE PHB TEGE OGT, OVP, 2 BAR S TS uW ( S ( LPT( ( UB2( LLS( CT^ UNDL kCON RECE AND SCk( PfL, ) .N .Lfc. GATE LP (7X, * R*2 (A-T, NUVP, NI 20000) 4000) 2000) ^000) 2000) 2000) NECTKJN B DING TO G THESE INT 20), PRn( G. V,H E. A) -^ET 0) RETUR S SUCCESS , *) V-Zt i) NOGT 3 M JX CLCF(2 RWPT( NS ( CLLT( XS ( SUP ( NCT2 NCT6 NFI XJ ETWFEN ATE I t FRCONNE 20) URN N IVF TO 000 0) 4000) 4000) ^000) 2000) GATE I AN NOT CTIONS NIPT U4 N NCX COL (20000) RWLT( 4000) NOPT JAO LTS ^■wCF( 2000 0) YS ( 4000) CLVT( 400U), CLSP{ 4000) OF ( 2000), XHAT( 2000) S ( 2000), SUBK 2000) TP ( 2000) NCT3 , NCT4 NGETYS , NNEwX KWLS( 4000) Ar40 GATt J IS SET TJ ONE FEED THOSE GATE SUCCESSIVE ARE SET TO ZERO /I, 2, 3, 4, 5, 6, 7,8 GATE J AND PUT THEIR GATE NO. IN SC^ =SUrt2( JAD) EGl .GT. LNCl) BEGl) J =1, NOGT GO TO 2 GO TO 10 . 0) GO TO 10 GO TO 10 IF (I .EO. J) SUB = $A( I ,J» IF (S(SUB) .LE DO 8 JK=l,ENDl IF (SCR( JK).EU.J) 8 CONTINUE eN01=ENDl+l SCR(END1)=SUB2 1010 F0RMAT(*0«//15X,*Y= :«,16I7) DO 40 I=l,NOGT DO 30 J=1,N0GT IF ( I .EQ. J) GO TO 30 JJ = J IF (J .GT. I) JJ=J-1 flEG=8ETA+NBG*( I - 1 ) +N I PT* ( J J- 1) ENO=BEG*NIPT-l PRINT 1020, I, J, (SUB, SUB=BEG,END» 1020 FORMAT ( /6X , ' B ( • , 12 , • , ' ♦ I 2 , ' , Y ) = 30 CONTINUE 40 CONTINUE PRINT 1010 , (SU8,SUB=l,N0GT ) dEG=ALPHA-NOGT+l ENO=ALPHA-l DO 50 I=1,NUGT BEG=BEG+NGGT-1 END=EN0+NGGT-1 DO 4b IZ=l,NOoT IF { IZ.EU. I) GO TO 43 IF ( I Z . GT . n GO TO 44 ZZ( IZ)=dEG-H-IZ GO TO 45 44 ZZ ( IZ)=3EG-2+IZ GO TO 45 43 ZZ( IZ)=99999999 45 CONTINUE PRINT 1033, I, UZ{SUB> ,SUB=1,N0GT) 1J3U FORMAT ( /9X , • A( • , I 2 , • , Y ) = :«,16i7) 50 CONTINUE PRINT 1010, ( SUB,SUB=1,NIPT J BEG=P8-NIPT END=PB-1 DO 60 1=1, NOGT BEG=BEG+NIPT £NO=END+NIPT PRINT 1040, I, ( SUB,SUB=BEG,ENDI 1040 FORMAT ( /9X , • P ( • , 12 , • , Y ) = :',16I7) 60 CONTINUE IF (NCT4 .LT. 2J RETURN PRINT 1010, (SUB,SUB=1,NUGT) BEG=LAMDA EN0=8EG*-N0GT-I 2050 FORMAT (/12X,»L(X)= :*, 1217) PRINT 2050, (SUB,SUB=BEG,END) PRINT 1010, (SUB, S'J8 = 1, NIPT) DO 90 I=l,NOGT DO 80 J=l,NOGT IF (I .EQ. J) JJ = J IH (J .GT. [) GO TO 80 JJ=J-l BEG=GAMA*N8G*( I-l )*-N I PT*( J J- I) END=BEG+NIPT-l PRINT 1060, I, J, ( SUB,SJB=BEG,END) 1060 FORMAT (/6X, • Gl • , I 2 , • , • , I 2, • , Y )= : 80 CONTINUE 90 CONTINUE RETURN END 1617) SUBROUTINE UNOLX (2X, *,♦,*) UNDERLINE THE RIGHTEST NOT UNDERLINED IMPLICIT INTEGER*2 (A-T,V-Z,i) INTEGER*^ NOGT, NGVR, NIPT, NOPT XS AND DROP THOSE AT ITS RISHT NOVR U2 Z6AR KS JTS RUW (200001 4000) 2000) 2000) 2000) 2000) NOGT U3 M JX CLCF(20000) RWPTI 4000) NS ( CLLT( XS ( <^UP ( NCT2 NCT6 NFIXJ COMMON 1 COMMON 1 , 2 , 3 , 4 , PS ( 5 , CLPTI 6 , X < 7 , SUB2( COMMON CLLS( 1 , NCT5 2 , NUNDLX 42 FORMAT (• UNDLX ENTER* ) 1 IFIJX.6U.I) GO TO 12 SUB=-XS(JX-I ) IF (SUB .LT. 0) SUB=-SUB BEG=CLPT(SUB+l) EN0=CLLT(SUB+1 )+BEG-l DO 3 AA=BEG,END IF (PSCROWCAA)) .GE. 0) GO TO 3 IF (CLSPIROWCAA) ) .N£. 0) GO TO CLSP{NCT3)=R0W( AA) NCT3=R0W(AA) CLSP(NCT3)=R0W(AA) 3 CONTINUE 5 L = JX-l IF(XS{L).GT.O) GO TO 15 S(-XSI L) ) = XS(L)=0 IF( X(L).LE.U) J^D=X(L) KS = -l GO TO 20 10 JAD = -X(L ) KS = 1 20 X(L)=0 CALL RVPSNS JX=JX-1 IF (JX.GT.l) 11 CONTINUE 12 PRINT 13, (I, 4000) 2000) 2000) 2000) GO TO 10 GO TO 5 NIPT U4 N NCX COL (20000) RWLT( 4000) CLVT( OF ( S ( TP ( NCT3 NGETYS RWLS( 4000) 4000) 2000) 2000) 2000) NOPT JAO LTS RWCF(20000) YS ( CLSP( XHAT( SUBU NCT<, NNEWX 4000) 4000) 2000) 2000) XHAT(I), 1=1, N» 0) GO TO 16 13 FORMAT ( 11(2X,«X( PRINT 14, ZBAR l^ FORMAT (2X,I4) 43 FORMATC ONDLX EXIT • RETURN Z XS(L)=-XS(L) IF (X(L) .GT JAO=-X(L) KS=1 GO TO 17 JAO=X( L) KS = -1 X(L)=-X(L) CALL RVPSNS JX = JX-l CALL CGPSNS (ZX,&1,£200) LTS = RETURN I 200 RETURN 3 END 13,' ) = • ,iin 18) 15 130 lb 17 SUBROUTINE GTINEQ GENERATE INEQUALITIES FOR AND-OR NE THE CARDS MARKED WITH BLUE ON THE T ADDITIONAL INEQUALITIES WHOSE EFFEC THESE CHANGES WERE PUT IN THE PROGR MAKE ALL FOUR VERSIONS OF GTINEQ UN THESIS- APPENDIX B). IMPLICIT INTEGER*2 (A-T,V-Z,$» INTEGER*^ NOGT, NOVR, NIPT, NOPT T WORKS. OP IMPLEMENT CHANG TIVENESS HAVE NOT B AM ON MAY I, 197^ I IFORM (SEE HOHULIN COMMON NOVK , NOGT 1 , U2 f U3 COMMON ZBAR , M 1 • KS » JX 2 f JTS ♦ CLCF(20000 3 t ROW (20000), RWPT( ^000 4 f PS ( 4000), NS ( <»000 5 f CLPT( 2000), CLLT( 2000 6 « X ( 2000), XS ( 2000 7 f SUB2( 2000), SUP ( 2000 COMMON CLLS( 2000), NCT2 1 , NCT5 , NCT6 2 , NUNDLX , NFIXJ DIMENSION T£MP( 100) ,VAL( I00),INPT(2 EQUIVALENCE ( TEMP ( 1 ) , X ( I ) ) , ( VAL ( I ) , 102 ) ) ,(CMT3,X(203) ) ,( Sg,X( 20'») ) ,(INP DATA Bl,B2,Gi,G2,OK /'Bl', DATA W,V,D,C,B /'W*,* DATA NR,ND,AO,GT,ST,IN,GT,OU,FI ,F0 70) X(10 T(l) •B2' NIPT U4 N NCX COL (200001 RWLT( 4000) CLVT( 4000) OF ( 2000) S ( 2000) TP ( 2000) NCT3 NGETYS RWLS( 4000) ES IN THE EEN TESTED. N ORDER TO MASTER NOPT JAD LTS RWCF(20000) YS ( 4000) CLSPC 4000) XHAT( 2000) SUBK 2000) NCT4 NNEWX I , • AD« /•CL« GT SI IN' / ,BLK , 'GT 1)1 ,(CMT1,X(201)) ,(CMT2,X(2 ,XS( I )) ,*Gl' ,'G2' , 'OR' / D', 'C, ' • / / • / DATA CL ,SI DATA E /'E'/ PRINT 1011 1011 FORMAT CI') C GENERATE OBJECTIVE FUNCTION 00 70 1=1, NOGT DO 71 J=1,N0VR OF ($V( I, J) )=1 71 OF(iW( I, J) )=1 DO 72 JJ=1,N0GT IF (JJ.EQ.I ) GO TO 72 QF($A( I ,JJ)|=1 72 CONTINUE 70 CONTINUE N0P1=NUPT+1 U=NnGT-i-N0VR + 2 0NE = 1 CCCCCCCBASIC INEQULITIFSCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC UO 100 1=1, NOGT CALL CLEAR CMT1=AD CMT2=BLK CMT3=GT SQ=I TEMPID^O VAL(l)=-l TP(n=C TEMP(2) = $L( I ) VAL(2) =U TP(2)=C TEMP(3)=*P( I, ONE) VAL(3)=U TP( 3)=0 TEMP(<^^ = $W(I ,ONE» VAL(4) =1 TP(4)=V TeMP(5)=SV( I,f3NE) VAL(5) =1 TP(5)=W N=5 DO 101 J=1,N0GT IF (J.EO.I) GO TO 101 N=N+1 TEMP(IM)=$G( J,I,ONE» VAL(N)=1 TP(N)=D 101 CONTINUE CALL SPUNCH 00 102 AA=l,N 102 VAL( AA)=-VAL( AAI VAL(2)=-VAL(2) VAL(1)=U CALL SPUNCH CALL CLEAR CMT1=0R TEMP( 1 )=0 VAH1)=2*U-1 TP(1)=C TEMP(2)=$L( I ) VAL(2) =-U TP(2)=C TtMP(3)=$P(I,0NE) VAL(3)=-U TP( 3)=D TtMP{4)=$W( I tONEI VAL(4) =1 TP(4)=W T£MP(5)=$V(I,0Nt) VAL(5)=1 TP(5)=V N=5 on 151 J=1,NUGT IF (J.tO.I) GO TO 151 N=N+l T£MP(N)=$0( J,I,CNE) VAL (N)=l TP(N)=0 151 CONTINUE CALL SPUNCH 00 152 AA=1,N 152 VAL{AA)=-VAL(AAJ VAL( 1)=U VAL(2)=-VAL{2) CALL SPUNCH 100 CUNTrNUE CMT1=AD CMT2=0R CVT3=0U 00 200 I=l,i\OGT" DO 201 J=1,N0GT IF (J. Eg. I ) GO TO 201 CALL CLEAR SQ=I*10+J TEMP(1)=$A(I,J) VALC l)=-2 TP(1)=C TEMP(2)=$P(I ,ONE) VAL(2l=l TP(2)=D TeMP(3)=$G(I ,J,ONE» VAL(3)=2 TP(3)=D TEMP(4)=$B(I ,J,ONE» VAL(4)=1 TP(4)=D N=4 CALL SPUNCH CALL CLEAR TEMP(1)=0 VAL( l)=l TP(1)=C TEMP(2)=$A(I , J) VAL(2I=3 TP(2)=C TEMP(3)=$G(I ,J,ONE» VAL(3)=-^ TP(3)=D TEMP(*|=$P( I ,ONE> VAL(4)=-1 TP(<»)=D TEMP(5)=i6( I ,J,ONE) VAL (5)=-3 TPi5)=0 N=5 CALL SPUNCH 201 CONTINUE 200 CONTINUE CMT3=GT DO 250 I=l,NOGT CALL CLEAR SO=I TEMPI! )=$P( I ,ONE) VAL(1)=U TPa) = N=l 00 251 J=1,N0GT IF ( I.EO.J) GO TO 251 N=N+1 TEMP(N) = $ti( I , J,ONE) VAL(N)=-1 TP(NI=D 251 CONTINUE CALL SPUNCH 250 CONTINUE CCCCCCtACH GATE HAS AT LEAST CMT3=IN DO 300 I=1,N0GT SQ=I CALL CLEAR TEMPI! )=0 VAL(l)=-2 N=l DO 301 L = UNOVR N=N + l TWO INPUTCCCCCCCCCCCCCCCCCCCCCCCCCCC TEMP(N)=$W(I ,L) VAL(N)=l N = N+l TEMP(N)=$V(I ,LI 301 VAL(NI=l DL) 30^ J = 1,N0GT IF (J.EQ.I ) GO TU 302 N=N+1 TFMP(N)=SA(J, I ) VAL(N)=1 302 CONTINUE CALL SPUNCH 300 CONTINUE CCCC ALL GATES EXCEPT THE OUTPUT GATES CONNECT TO AT LEAST ONE GATE CCC C'»^T3 = 0U DO 400 I=N0P1,NCGT CALL CLEAR SQ=I TEMPC l»=0 VAL(i)=-l N=l DO 401 J=1,N0GT IF (J. £0,1) GO TO 401 N=N+l TfcMP(N)=$A( I , J) VAL(N)=1 401 CONTINUE CALL SPUNCH 400 CONTINUE CCCCCCTkAINGULAR INEOUALITIESCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC C IJ = 2 FOR SINGLE-OUTPUT NETWORKS; IJ = 1 FOR MULTIPLE-OUTPUT C NETWORKS. PREVIOUSLY ONLY IJ=1 WAS USED. IJ = 2 IF ( NOPT .GT. 1 ) IJ = I C^^Ti = AD CMT2=0R CMT3=ST su=o DO 600 I=IJ,N0GT 00 600 J=IJ,NOGT IF (J. EW. I ) GO TO 600 DO 601 K=1,N0GT IF (K.EQ.I .UR.K.tO.J) GO TO 601 CALL CLEAR S0=SQ+1 IF (SO.GE.IOO) SQ=l TEMPd )=0 VAL{1)=2 TFMP12)=$A( I , J) VALl?)=-l TEMP(3»=$A(I ,K) VAL(3)=-1 TEMP(4)=$A( J,K) VAL<4)=-1 N=4 call spunch 601 continue 600 continue cmti=tw CMT2=SM CMT3=TY DO 900 I = N0P1,N0GT 00 900 J=1,N0GT IF (I.EQ.J) GO TO 900 SQ=I*10*J CALL CLEAR TEMP(l)=0 VAL( 1)=0 TEMP(2) = $LU ) VAL{2)=1 TEMP(3)=$L( J) VAL(3)=1 TEMP(4)=$A(l, J) VAL(^I=-1 N=4 DO 901 K=l,NOGT IF (K.EO.I.OR.K.EO. J) GO TO 901 N=N-H TEMP(NI=$A( I ,K) VAL(N»=I 901 CONTINUE CALL SPUNCH VAL(I)=2 VAL(2)=-VAL(2> VAL(3)=-VAL(3) CALL SPUNCH 900 CONTINUE CMTI=1 CMT2=AD CMT3=1 SQ^OR DO 1000 I=I,NOGT N=N+I TEMP(N)=$L( I ) 1000 VAL(N)=1 CALL SPUNCH VALIU=NGGT-1 DO 1001 AA=2,N 1001 VAL(AA)=-VAL(AA| CALL CLEAR TEMPI 1 1=0 VALU)=-l N=l CALL SPUNCH CALL CLEAR INPT(1)=E INPT(6)=-99 N8 = 6 CALL INTLP(NB) RETURN END SUBROUTINE GTINEQ C GENERATE INEQUALITIES FOR NOR-ANO NETWORKS. C THE CARDS MARKED WITH BLUE ON THE TOP IMPLEMENT CHANGES IN THE C ADDITIONAL INEQUALITIES WHOSE EFFECTIVENESS HAVE NOT BEEN TESTED, C THESE CHANGES WERE PUT IN THE PROGRAM ON MAY 1» 1974 IN ORDER TO C MAKE ALL FOUR VERSIONS 0*= GTINEQ UNIFORM (SEE HOHULIN MASTER C THESIS- APPENDIX 8). IMPLICIT INTEGER*2 (A-T»V-Z,$) INTEGER*^ NOGT, NUVR, NIPT, NOPT COMMON NOVR I , U2 COMMON ZBAR 1 , KS 2 , JTS 3 , ROW ( 4 , PS ( 5 , CLPT( 6 , X ( 7 » SUB2( COMMON CLLS( 1 , NCT5 2 , NUNOL DIMFNSION TEMP( EQUIVALENCE (TE 102) ) , (CMT3,X(20 NIPT f NOPT U4 N NCX COL (200001 RWLT( 4000) CLVTI 4000) OF ( 2000) S ( 2000), TP ( 2000) NCT3 NGETYS RWLSI 4000) 100) ,VAL( 100) ,INPT{270) MP(1),X( 1) ) , (VAL(l) ,X(101) ).(CMTi,X(201 ) ) , (CMT2,X(2 3) ) ,(SQ,X(204)), (INPT<1),XS(1)) 20000) 4000) 2000) 2000) , 2000) 2000) NOGT U3 M JX CLCF(20000) RWPT( 4000) NS ( 4000) CLLT( 2000) XS ( 2000), SUP ( 2000) NCT2 NCT6 NFIXJ JAD LTS Ri VAL{1)=U TP(ll=D N=l 00 251 J=l,NOGT IF (I.EQ.J) GO TO 251 N=N+I TEMP(N)=$8( I , J.ONE) VALlN)=-l . TP(N)=D 251 CONTINUE CALL SPUNCH 250 CONTINUE CCCCCCEACH GATE HAS AT LEAST CMT1=NR CM-^2=A0 CMT3=IN 00 300 I=1,N0GT sg=i CALL CLEAR TtMP( 1 )=0 ONE INPUTCCCCCCCCCCCCCLCCCCCCCCCCCCC VAL(n=-2 TEMP(2» = $LCn VALC2l=l N=2 DO 301 J = UNOVR N=N-H TEMP(N)=$W(I , J) VAL(N)=1 IF (NCT5 .NE. CP I GO TO 301 N=N+1 TEMP(N)=$V(I ,J) VAL(N»=1 301 CONTINUE 00 302 K=l,NUGT IF (K .EO. I) GO TO 302 N=N-H TEMP(N)=SA(K, I ) 302 VAL(N)=1 CALL SPUNCH 300 CONTINUE CCCC ALL GATES EXCEPT THE OUTPUT GATES CONNECT TO AT LEAST ONE GATE CCC CMT3=0U DO 350 I=N0P1,N0GT CALL CLEAR TEMPin=0 VAL( l)=-l N=l SQ=I DO 351 K=1,N0GT IF (K .EO. I ) GO TO 351 N=N+1 TEMP(N)=$A( I,K| 351 VAL{N)=l CALL SPUNCH 350 CONTINUE CCCCCCTRAINGULAR I NEQUAL I T lESCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC C IJ=2 FOR SiNGLE-OUTPur NETWORKS; IJ=1 FOR MULTIPLE-OUTPUT C NETWORKS. PREVIOUSLY ONLY IJ=2 WAS USED. IJ = 2 IF ( NUPT .GT. 1 ) IJ = 1 CMT3=ST so=o DO 400 I=IJ,NOGT 00 401 J=IJ,NOGT IF (J .FQ. I ) GO TO 401 DO 402 K=l,NOGT IF (K .GQ. J .OR. K .EO. I ) GO TO 402 CALL CLEAR SQ=S0+1 IF (SQ .GE. IJO) S0=1 TEMP( 1)=0 VAL( n=2 TEMP(2 I^SAU , Jl VAL(2)=-1 TEMP(3)=*A( I,Kl VAL(3) =-1 TEMP{4)=$A(J,K| VAL(4)=-l N=4 DO 403 P=l,NOGT IF (P .Ey. I .OR. P .EO. J .OR. P .to. K) GO TO 403 TEMP(N) = $A( J.PJ VAL(N)=1 ^03 CONTINUF CALL SPUNCH 402 CONTINUE 401 CONTINUE 400 CONTINUE DO 500 J=IJ,NOGT DO 501 K=1,N0GT IF (K .to. J ) GU TO 501 DO 502 L = UNnVR SQ=S0+1 IE (SO .GE. 100) SU=l CALL CLEAR TEMP( 1 ) = VALI l)=2 Tt MP(2 )=$W(K,L» VAL(2l =-1 TEMP(3)=$W( J,L) VAL(3) =-1 T£MP(4)=$AIJ,K) VAL(4)=-l N=4 DO 503 P=l,NOGT IF (P .Ey. K .OK, f N=N+1 TEMP(N )=$A(J,P) VAL(N)=1 503 CONTINUE CALL SPUNCH IF ( NCT5 .NE. CP ) GO TO 502 TtMP(2) = $V(J»L) TE^^P(3) = tV(K,L) CALL SPUNCH 502 CONTINUE 501 CONTINUE 500 CONTINUF 00 600 J=IJ,NOGT DO 601 K=1,N0GT IF (K .EQ. J) GO TO 601 00 602 L=UNOVR S0=.':Q+1 IF (SQ .GE. 100) SQ=1 CALL CLEAR TEMPd )=0 VAL{1)=2 TEMP(2)=$W( J,L) VAL{2) =-1 TFMP(3»=$W(K,L) VAL(3»=-1 TEMP{4)=$A( J,K) VAL{4) =-1 TEMP(5 ) = $L( J) VAL(5)=1 N=5 CALL SPUNCH Su=SU+l IF (SQ .Gt. 100) SQ=1 TEMP(N )=$L(K) CALL SPUNCH EQ. J ) GO TO 503 IF ( NCT5 .NE. CP ) GO TO 602 TEMP(2) = $V(J,L) TEMPO! = $V(K,L) CALL SPUNCH TEMP(N) = $LCJ) CALL SPUNCH 602 CONTINUE DO 650 I=IJ,NOGT IF ( I .EQ. J .OR. I .EO. K) GO TO 650 SU=S0+1 IF (SQ .GE. 100) SO=l TEMP(1)=0 VAL(U=2 TEMP(2»=$A| I,K» VAL(2J=-1 TEMPO J = SA( I, J) VAL (i)=-l TEMP(4)=$A( J,K) VAL(4)=-I TEMP(5)=$L( J) VALI 5) =1 N=5 CALL SPUNCH SQ=SO+l IF (SU .GE. 100) SQ=l TEMP(N)=$L(K) CALL SPUNCH 650 CONTINUE 601 CONTINUE 600 CONTINUE CCCC GATES WHICH ARE CONNECTED TO ALL OF THE OUTPUT GATES ARE NOT CCCC CONNECTED TO ANY OTHER GATES CCC CMT3=CL DO 700 I=N0P1,NCGT SU=I CALL CLEAR TEMPil )=0 VALI 1) =NOPT*U 00 695 J=2,N0PI JMl=J-l TEMP( J)=$A{ I , JMl) VAL{J)=-U N=J 695 CONTINUE DO 701 K=NOPl,NnGT IF (K .eg. I ) GO TO 701 N=N*-1 TEMP(N)=$A( 1 ,K) VAL IN) =-1 701 CONTINUE CALL SPUNCH 700 CONTINUE CALL CLEAR INPT( 1 )=E INPT(6)=-99 N8=6 CALL INTLP(NB) RETURiNj END SU8»