Digitized by the Internet Archive in 2013 http://archive.org/details/nornetworktransd885hukc /c 6 . n ' C UIU K7 "? JO CDCS-R-77-885 ltf& 1 NOR NETWORK TRANSDUCTION SYSTEM (Principlies of the NETTRA System) UILU-ENC 77 1742 by August 1977 K. C. Hu S . Muroga DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS The Library SEP 3 1977 University ol Illinois ft "''•ono-Chamoaiqn UIUCDCS-R-77-885 NOR NETWORK TRANSDUCTION SYSTEM (Principles of the NETTRA System) by K. C. Hu S. Muroga August, 1977 Department of Computer Science University of Illinois at Urbana-Chanpaign Urbana, Illinois 61801 This work was supported in part by the National Science Foundation under Grant NSF DCR73-03421. ii ABSTRACT The network transduction programs, including NETTRA-PGl , -PI, -P2, -Gl , -G2, -G3, -G4, -El, and -E2 are combined as a large program system named the NETTRA system (NETwork TRAnsduction system). The NETTRA system can design near-optimal, multiple-output, multi-level and loop-free NOR(NAND) networks under fan-in/fan-out restrictions and/or level restriction. Given function(s) may be completely or incompletely specified and both complemented and uncomplemented external variables are permitted as inputs. The user can specify the control sequence (the types of the initial net- work methods and the types and the order of the transduction procedures to be applied) to solve his problem. Besides, four control sequences are provided for the users who are not interested in the details of how to specify the control sequence. Facilities for treating unfinished jobs due to the expiration of com- putation time are also provided by the system. i i i ACKNOWLEDGMENT During the period of the research of NOR(NAND) network transduction methods, many people, besides the authors, were involved. They are Messrs. Y. Kambayashi, H. C. Lai, J. N. Culliney, K. Hohulin, B. Plangsiri, J. G. Legge, and R. Cutler. The authors wish to express their thanks to Messrs. H. C Lai and J. N. Culliney for valuable discussions and comments in designing the NETTRA system. The excellent typing job done by Mrs. R. Taylor and Mrs. J. Wingler is also acknowledged. iv TABLE OF CONTENTS Page 1. INTRODUCTION 1 2 . OUTLINE OF THE NETTRA SYSTEM 5 3 . REVIEW OF BASIC IDEAS AND PRINCIPLES 10 3 • 1 Initial Network Synthesis 10 J.1.1 Universal NOR Network Method 10 3.1.2 Three-Level Network Method 16 3-1.3 Branch -and -Bound Method 26 3.1.1* Tison's Method 34 3.1.5 Gimpel's Algorithm 42 3.1.6 Level-Restricted Initial Network Method 51 3 .2 Fan-in/Fan-out Restricted Transformation 59 3 .3 Transduction Procedures 75 3 .3 .1 Basic Definitions and Ideas 75 3.3-2 Pruning Procedures 80 3.3.3 Procedures Based on Gate Merging 82 3.3.^ Procedures Based on Gate Substitution 87 3.3.5 Procedures Based on Connectable and Dis connectable Functions 91 3 -3 «6 Procedures Based on Error-Compensation 94 3.3.7 Considerations of Fan-in/Fan-out Restrictions and Level Restriction 99 3.3.o Assembly of the transduction programs for the NETTRA system 103 V Page k . DETAILED ORGANIZATION OF THE NETTRA SYSTEM 107 k.l Functions of Important Subroutines 107 k.2 Control Subroutine MAIN Ill k.J Overlay Structured Program 132 5 . STATISTICS AND EXPERIMENTAL RESULTS 140 5 . 1 Comparison of Initial Network Methods 141 5 -2 Comparison of Transduction Procedures 157 5 -3 Determination for Control Sequences 171 6 . CONCLUSIONS 207 REFERENCES 209 1. INTRODUCTION In the synthesis problem of logic networks, how to get derivation of optimal NOR(NAND) networks for a given switching function (or a set of switching functions) is important and interesting since basic logic gates of many integrated circuits (for example, RTL (Resistor-Transistor Logic), DTL (Diode-Transistor Logic), ECL (E m itter-Coupled Logic), IIL (integrated-Injection Logic) and VMOS) realize NOR or NAND functions. Existing logic design methods for synthesizing NOR (NAND) networks are classified into the following five groups: (1) Switching algebraic methods [7], [10], [27] . (2) Map factoring method [28], [31], [kl] . (3) Exhaustive method [8]. (k) Integer programming methods (implicit enumeration method formulated inequalities [29], [30], [32], [33], [3 1 !-] and branch-and-bound method without inequalities [ 1 4-],[37l-) (5) Transformation methods [5L [6],[l6], [23], [28], [35] . The switching algebraic methods can produce optimal networks only under very specific constraints (such as two-level or three-level networks without fan-in, fan-out restrictions). The map factoring method is easy * This branch-and-bound method finds optimal networks by using the concepts of covered and uncovered components, possible covers, selection criterion of uncovered components and desirability. It does not try to solve inequalities (like the integer programming method does) . to use by hand for problems with four or fewer external variables, but the optimality of the results is not guaranteed. The exhaustive method can be applied only to networks with very few gates (usually at most 5) . As the number of gates in a network increases, it becomes excessively time-consuming to exhaust all feasible networks (networks which realize given functions and satisfy given restrictions) for the given problem. The integer programming methods produce optimal networks in much shorter time than the exhaustive method. (The integer programming methods consist of the implicit enumeration method based on inequality formulation and the branch-and-bound method without inequalities . The branch-and-bound method is usually more efficient than the implicit enumeration method, though it is much harder to implement [36].) But as the number of gates in a network exceeds 10, the integer programming methods (both the implicit enumeration method and the branch-and-bound method) become too time- consuming for practical use. When people need a synthesis procedure which can treat a logic network with many gates, the network transformation methods seem promising although they do not guarantee the optimality of the results. Some NOR(NAND) network transformation methods were discussed in [5], [6], [28] . Recently more general transformations were studied by T. Nakagawa, H. C. Lai and S. Muroga (the transformations are combined with the branch-and-bound method in order to improve the efficiency of the branch-and-bound algorithm [35]), H. Lee and E. S. Davidson [23] and Y. Kambayashi, H. C Lai and S. Muroga [16]. In the past few years, the research group of S. Muroga developed a new approach for the design of near-optimal NOR(NAJOT)) networks. This new approach is named the transduction methods (transformation and reduction) . Any network designed by some known method, which is called an initial network, is transformed and reduced into a simpler network by the transduction methods . The transduction methods are based on the concepts of permissible functions which were originated by Y. Kambayashi and S. Muroga [17] • Y. Kambayashi, H. C. Lai, J. N. Culliney and S. Muroga developed the whole sets of algorithms for various kinds of transduction procedures [2][1*J-][15][22] and then, they implemented the algorithms into the transduction programs [1][19][20][21] . K. C. Hu, K. R. Hohulin and B. Plagsiri then considered fan-in, fan-out and level restrictions into the transduction procedures [9l[H][l2][38] • L. G. Legge designed a transformation program which is able to transform a network into fan- in/fan-out restricted form [2^] . The NETwork TRAn sduction (NETTRA) system was designed recently to organize the initial network programs (will be described in detail later), the transformation program and the transduction programs together so that anyone can use this system to design near-optimal NOR (NAND) networks under fan -in, fan-out and/or level restrictions. The purpose of this report is to review the basic principles of the transduction procedures and explain how the NETTRA system is organized, The transduction methods are designed for finding near-optimal NOR networks We can design a near-optimal NAND network for a given function by (1) designing a NOR network for the dual of the given function and (2) replacing each NOR gate with a NAND gate in the resulting NOR network. The transduction methods, hence, can also be used for near-optimal NAND network design. In this report, we will concentrate in discussion of NOR networks only. The detailed contents of this report are as follows: Chapter 2 provides the outline of the system. It explains how the system treats a given problem (i.e., how to derive a near-optimal network for a given switching function (or a set of switching functions) under certain constraints specified by a user) and also describes what initial network methods and transduction procedures are included in the system. Chapter 3 gives primarily the review of basic principles of the transduction procedures. Section 3*1 introduces briefly the methods for finding initial networks (this part was never explained in detail in other reports). Sections 3-2 and 3-3 give summaries of basic principles for the fan- in/fan-out restricted transformation procedure and the transduction procedures. Chapter k provides the explanations of the functions of important subroutines, the detailed organization of the control subroutine MA. IN, and the overlay structure of the system. Chapter 5 gives the statistics and the experimental results. The effects of different initial network methods and the effectiveness of different transduction procedures are -x- compared. Four control sequences are designed for the user's convenience Chapter 6 provides the conclusions. The meaning of the control sequences will become clear later. 2. OUTLINE OF THE NETTRA-SYSTEM The NETTRA- system can treat the following four types of problems: (1) Find near-optimal networks for the given function(s) under no fan- in/fan-out restrictions or level restriction. (2) Find near-optimal networks for the given function(s) under only fan-in/fan-out restrictions. (3) Find near-optimal networks for the given function(s) under level restriction only. (k) Find near-optimal networks for the given function(s) under both fan- in/fan-out restrictions and level restriction. Since type (l) and type (3) problems can be considered as special cases of type (2) and type (k) problems, respectively, the approaches which can treat type (2) and type (k) problems can also solve type (l) and type (3) problems . In this chapter, we introduce the outline of the NETTRA system primarily based on the approach for solving type (2) and type (k) problems. The NETTRA system designs near-optimal networks for any given switching function(s) under only fan-in/fan-out restrictions (i.e., type (2) problem) according to the following procedures: Step 1 : Find an initial network for the given function(s) by a conventional design method to be specified by a user as an As an alternative, the initial network designed by any other method can even be read into the NETTRA system. option, ignoring fan-in/fan-out restrictions. Usually the initial network can be obtained very easily (i.e., in a very short time), but it may have many redundant gates and connections and it may not satisfy the given fan- in/fan-out restrictions . Step 2 : Apply the transduction procedures to simplify the initial network found in step 1 or the network obtained in step h without considering fan-in/fan-out restrictions . Usually the initial network is simplified, but the resultant network may not be fan-in/fan-out restricted. If the resultant network is fan-in/fan-out restricted, then we obtain a solution. Otherwise go to step 3 • Step 3 : Employ the transformation procedure (developed by J. G. Legge) to transform the network obtained in step 2 into fan- in/fan-out restricted form. Step h: Apply the transduction procedures considering fan- in/fan-out restrictions, to simplify the fan- in/fan-out restricted network in step 3 • The resultant network after applying steps 1, 2, 3 and k is a near-optimal solution for the given problem. But the sequence of steps 2-3-^- can be applied repeatedly to try to simplify the network further . If the given problem has both the fan- in/fan-out restrictions and level restriction (i.e., type (k) problem), the above k steps can still be used. But it is not guaranteed that a feasible network will be obtained by this approach even if there do exist optimal solutions for the given problem. Another approach for a problem with both fan- in/fan-out restrictions and level restriction imposed is explained below: Step 1' : Find a level-restricted initial network for the given problem. This initial network may not satisfy the fan-in/fan-out restrictions. Step 2' : Apply the fan- in/fan-out restricted and level-restricted transduction procedures to simplify the network obtained in step 1' without violating the level restriction. If the resultant network after applying step 1* and step 2' satisfies fan- in/fan-out restrictions, then a feasible network has been obtained. A similar but more complex approach is implemented in [12] and is also included in the NETTRA system as an option (this will be explained in Chapter k and Chapter 5) • Several conventional methods are used in deriving initial networks for the NETTRA system. They are: (1) Universal NOR network method [28]|>2] . (2) Three-level network method. (3) Branch-and-bound method [37] • (k) Tison's method [3][3l]|>0]. ( 5 ) Gimpel ' s algorithm [ 7] . (6) Level-restricted initial network method [12] . Method (l) through method (5) are for fan-in/fan-out restricted problems. Each method has advantages and disadvantages and will be discussed in * This method starts from the result obtained by Tison's method (k) detail in Chapter 3- Method (6) is used only for level-restricted and fan-in/fan-out restricted problems. There is one transformation procedure included in the system which can transform a non- fan- in/non- fan-out restricted network into fan- in/fan-out restricted form. The transduction procedures are classified into the following five groups according to their characteristics and capabilities: (1) Pruning procedures [2][20]. (2) Procedures based on gate merging [19][22][38] . (3) Procedures based on gate substitution [2][19] [20][22][38] . (k) Procedures based on connectable and disconnectable functions [l][9][l>i] . (5) Procedures based on error- compensation [ll][15][21] . The basic principles and algorithms of these transduction procedures will be reviewed in Chapter 3 • The FORTRAN subroutines which realize the initial network methods, the transformation procedure and the transduction procedures are organized by the control subroutine MAIN. Figure 2.1 shows a general flowchart for the NETTRA system, where l/o supporting subroutines are used for inputing data, printing the results and punching the intermediate results. In the previous reports on the transduction procedures, (2), (3) and (k) are grouped as "General procedures." INITIAL NETWORK SUBROUTINES CONTROL SUBROUTINE MAIN TRANSFORMATION SUBROUTINE SUPPORTING SUBROUTINE TRANSDUCTION SUBROUTINES Fig. 2-1 General flowchart for the NETTRA-system. 10 3- BASIC IDEAS AND PRINCIPLES 3 .1 Initial Network Synthesis In the NETTRA system, there are currently six methods which can derive initial networks . Some methods produce initial networks in a very short time, and some methods take a longer time but produce initial networks with fewer gates and/or fewer connections . For any given switching function, if we start from different initial networks and apply the same transduction procedures, then we will usually get different results . Since the initial network design methods have to be combined with the transduction procedures to obtain the near-optimal networks, it is not easy to judge which initial network design method is superior to others. The statistics in Chapter 5 gives some picture of the influence of initial networks on the final results. 3.1.1 Universal NOR Network Method [28] Given an n-variable switching function f (with external input * i n variables x , x , ...,x ), let S = {m. |m. is a minterm, i = 0,1, 2,..., 2 -1} (i.e., S is the set of all minterms) and let M = {m. |m. e S and f (m. ) = 1] Then the function f can be expressed with the minterm expansion £ m. . m.eM x i As can easily be seen, f can also be expressed as Em.. Hence if m.eS-M x l * For the sake of convenience, assume that f is single-output and completely specified. 11 there exists an NOR network in which each gate realizes a function which is a minterm contained in S-M, then we can feed the outputs of these gates as inputs to another NOR gate to realize the function f at the output of this new NOR gate. The gates which are useless to realize this function can be eliminated (the elimination is actually done by the transduction methods) . The universal NOR network method can construct a NOR network consisting of 2 gates with only uncomplemented external variables as network inputs. Each gate in this network realizes a function which is an element in S (i.e., a minterm). Therefore, any switching function f n * can be realized by the above approach with at most 2 gates. Figure 3«1«1-1 shows a 3-variable universal NOR network. The function realized by each gate is also shown. The algorithm for generating the universal NOR network is presented below . Let n be the number of external variables, and let the level number ? of a gate I be the maximum among the level numbers of gates along all paths connecting gate I and the output gate, which has gate level 1. In the n-variable universal NOR network, 1 < I < n+1 must hold. Algorithm for Generating the Universal NOR Network (1) Connect all external variables to the highest level (the (n+l)-th level) gate. (2) For each £ such that 1 < £ < n+1, find all possible sets of combinations of £-1 external variables. Connect each set of £-1 external variables to an i-th level gate. The network requires exactly 2 gates only when f is a one-minterm function. 12 f = x y x g, 12 3 X l X 2 X 3 f = X_ X. x_ g 9 13 3 X l X 2 X 3 f g 3 = X l X 2 X 3 f g, = X l *2 X 3 X l X 2 X 3 X l X 2 X 3 Fig. 3.1.1-1 3 variable universal NOR network (f is the function realized g i at the output of gate i . The outputs of some of these gates are connected to an extra gate whose output is to realize a given function.) 13 (3) For each i-th (1 < i < n+l) level gate I, connect the outputs of all higher level gates which have external variable sets including the external variables to gate I, to gate I. ( + ) For the output gate, connect the outputs of all higher level gates as its inputs. The validity of the algorithm can easily be proved by the map factoring method for NOR network design [28] [31], hence it is omitted here. A three -variable Karnaugh map and the corresponding loops derived by the map factoring method are shown in Fig. 3-1-1-2. Each shaded circle in Fig. 3-1 -1-2 corresponds to a minterm which is shown in Fig. 3.1.1-1. The following properties are observed with respect to the above algorithm: (a) The number I, of gates in any level £ (l < i < n+l) is T n - ( n ^ - . n! 1 £ ' K &-V ~ (£-l)\(n-Ul)\ (b) The total number of gates in the universal network is n+l n+l n+l , v T n - y ( n ) - y n! P n L l ~ L ^ ~ L ♦95 92 Fig. 3.1.1-2 The 3-variable Karnaugh map with loops and shaded circles for proving the algorithm for generating the universal network by using map factor- ing method. 15 f = 2(0,2,3, 4,6,7) Fig. 3.1.1-3 Example 3.1.1-1 16 It is easy to find that there are many redundant gates and connections in Fig. 3.1.1-3« For example, gates 3, 6, 7 and 8 are useless for realizing f and hence can be removed. The transduction procedures can then be applied to remove redundant gates and connections as many as possible . 3-1.2 Three -Level Network Method It is mentioned in section 3.1.1 that any switching function f can be expressed as L m. , where S is the set of all minterms and M Is m. eS-M x i the set of minterms which corresponds to 1-vectors . (An input vector x is called a 1-vector if f(x) = 1; it is called a O-vector if f(x) =0.) The three-level network method developed by Y. Kambayashi is also based on the above idea to design a NOR network with only uncomplemented external variables as inputs, but the networks designed by this method are restricted to those with at most three levels. Before presenting the algorithm, let us introduce the following definitions: Let V be the set of all n-dimensional binary (0 or l) vectors, where n is the number of external variables. Definition 3.1.2-1 - Given two input vectors X n = (x__,...,x_ ) - ^ 1 11 ' In and X 2 = (x 21 , . . .,x 2n ), then t ^ < t„ if x ±1 < x 2± for every i = 1, . . .,n but x, < x . for at least one i. X, and X_ are said to be equal (x n =X ) li 2i J- ^ J- d - if x.. = x_ . for every i = l,...,n. X.. and X p are said to be incomparable if none of X ± < X 2 , X < X and X = Xp holds. Definition 3.1.2-2 - The weight W(X) of an input vector X is the number of ones in X. The distance between two input vectors X and X ' is d(X x , X 2 ) = W(X X X 2 ), where ^ X g = (x n © x^, . . ., x^ e x 2n ) . 17 Definition 3-1 -2-3 - A Z-set is a maximal set of input vectors (i.e., no other Z-set is a proper subject of this Z-set) such that the following conditions are satisfied: (1) In each Z-set, all vectors must be O-vectors and there exists one and only one O-vector which is greater than any other O-vectors. (2) O-vectors X, and X do not belong to the same Z-set if X < X and there exists another 1-vector X-, such that X., < X_ < X^ holds. X n 3 1 3 2 1 X belong to the same Z-set if the above condition does not hold. (3) In each Z-set, there exists at least one vector X which does not belong to any other Z-set. -* -x A Z-set, in which X is greater than any other vectors, is denoted — fc X- — K -X ~" * -X- by Z(X ) . X is called the root of Z(X ) . Definition 3»1«2-^- - A Y-set is a maximal set of input vectors such that the following conditions are satisfied: (1) In each Y-set, all vectors must be 1-vectors and there exists one and only one 1-vector which is greater than any other 1-vectors. (2) 1-vectors X and X do not belong to the same Y-set if X < X and there exists another O-vector X^ such that X., < X_ < X^ holds. 3 13 2 X and X belong to the same Y-set if the above condition does not hold. (3) In each Y-set, there exists at least one vector X which does not belong to any other Y-set. -* *■ A Y-set, in which X is greater than any other vectors, is denoted ""* "X — * -X ~~ *" X- by Y(X ) ■ X is called the root of Y(X ). 18 Example 3»1«2-1 - In Fig. 3-1 -2-1, the given four-variable switching function is f = £ (2, 5,6,7, 9, 13, 1^, 15) • There are 3 Z-sets and 3 Y-sets according to the previous definitions . Z(llll) = {(1111), (1110), (0110), (1101), (0101), (0111)} Z(1101) = {(1101), (1001), (0101)) Z(0110) = {(0110), (0010)} Y(1011) = {(1011), (1010), (0011)} Y(1100) = {(1100), (1000), (0100), (0000)} Y(001l) = {(0011), (0001)} Notice that { (0000), (0001 )} is not a Y-set because (0000) e Y(001l) violates condition (iii) of Definition 3. 1.2-1*. Also any subset of the Y-sets (or the Z-sets) shown above is not a Y-set (or a Z-set) . In the three -level initial network method (the output gate is the first level gate), each Y-set may correspond to a third-level gate. In order to know which third-level gates should feed which second- level gates, the "adjacent relations" among the Y-sets and the Z-sets is introduced below. Definition 3.1.2-5 - Y(X ) is said to be adjacent to Z(X ) if (1) there exist a X 7 e Y(X_ ) and a X, e Z(xJ such that d(X z ,X, ) = 1 and the X, < X^ and (2) for every pair X e Y(X ) and X, e Z(X ), no X, < L holds. Example 3.1.2-2 - In Fig. 3.1.2-1, consider the Z-set Z(llll) and Y-set Y(1100) first. Since the 1-vector (1100) e Y(1100), the 0-vector (1110) e Z(llll), (1100) < (1110) and d(H00, 1110) = 1, condition (l) of the previous definition is satisfied. Besides, no vector which belongs to Z(llll) is less than (<) any vector which belongs to Y(1100), so condition (2 is also satisfied. Hence the Y-set Y(1100) is adjacent to the Z-set Z(llll). Similarly, Y(1011) and Y(001l) are found to be adjacent to Z(llll) . 19 i x w m •H 20 The adjacency relations for the given example can be summarized as follows : Y(0011) is adjacent to Z(llll) and Z(1101) . Y(1100) is adjacent to Z(llll), Z(llOl) and Z(0110) . Y(1011) is adjacent to Z(llll) only. Notice that each Y-set (or Z-set) does not have to be adjacent to some Z-sets (or Y-sets) . The following is such an example. Example 3-1-2-3 - In Fig. 3-1-2-2, the given function is the 3-variable parity function. There are k Y-sets and k Z-sets and each Y-set or Z-set consists of only one vector. Apparently, Z(00O) is not adjacent to any Y-set and Y(lll) is not adjacent to any Z-set. Definition 3-1-2-6 - The f3-set of an input vector X is the set of all uncomplemented external variables which appears as zeros in X. Example 3.1.2-4 - The 0-set of 1100 is {x , x, } ; the p-set of 1111 is the empty set 0. Now we are ready to present the algorithm. Algorithm for generating the three-level NOR network : Step 1 : Find all Z-sets and Y-sets for the given function f and then calculate the adjacency relations. Step 2 : Construct a third-level gate for each Y(x) which is adjacent to some Z-sets. The inputs for this gate are the elements (external variables) of the 3-set of the X. Step 3 : Construct a second-level gate for each Z(X) . The inputs for this gate are the elements of the 3- set of the X and the outputs of those third-level gates which correspond to the Y-sets which are adjacent to Z(X) . If Y(X ) and Y(X ) are adjacent to Z(X) and 21 *>. 4 Y(100) Z(OOO) Fig. 3.1.2-2 Example 3.1.2-3 22 X > X , then the corresponding third-level gate for Y(X ) is not necessary to be connected to the corresponding second-level gate for Z(X) . Step k : Feed the outputs of all second-level gates to the first-level gate (the output gate) . Stop. Example 3-1-2-5 - Following the above algorithm, a three -level network for Example 3.1.2-1 is obtained in Fig. 3 .1-2-3 • In Fig. 3-1-2-3, the outputs of gates 1, 2, and 3 correspond to the Y-sets Y(llOO), Y(001l), and Y(l01l), respectively; and the outputs of gates h, 5 and 6 correspond to the Z-sets Z(0110), Z(1101) and Z(lll), respectively. Since Y(l01l) and Y(001l) are adjacent to Z(llll) and (0011) < (1011), the output of gate 2 (corresponding to Y(001l) is not connected to gate 6 (corresponding to Z(llll)) according to step 3. In the above algorithm, the function realized at the outputs of each second-level gate is the disjunction of minterms which correspond to 0-vectors in the corresponding Z(X) . The input of the first- level gate is, therefore, the disjunction of all minterms which correspond to all 0-vectors of f . The detailed proof is omitted here. An interesting phenomenon which arises in the previous algorithm is that we cannot get a network whose output gate has external variables as inputs. The following is an example. Example 3.1.2-5 - Give the 3 -variable function f = Z(0, 3) in Fig. 3-l-2-U(a) and (b), the three-level network is obtained by applying the algorithm. Apparently, gate 2 and gate 5 are redundant and can be removed; i.e., we can connect x to gate 6 directly. 23 =E> F = z (2,5,6,7,9,13, 1U,15) Fig. 3.1.2-3 A three-level network for Example 3.1.2-1. 24 Y(OOO) \ y (a) X x 2 X !3~r>~. Xj-+ U> (b) 25 Zj^)° T^) •> f=2(0,3) Fig. 3.1.2-4 Example 3.1.2-5. Gate 2 and gate 5 are redundant 26 The above algorithm for generating the three-level network does not guarantee the minimality of the numbers of gates and connections. But because of the simplicity of the algorithm, it is good for finding initial networks for the NETTRA system. 3.1.3 Branch- and-bound Method The branch-and-bound algorithm was applied by E. S. Davidson [h] to the synthesis problem of optimal combinational networks for arbitrary switching functions using NAND gates, by introducing the desirability order and other speed improvement gimmicks. T. Nakagawa and H. C. Lai implemented Davidson's algorithm for NOR gates by using simpler heuristics than Davidson's and also by incorporating a new gimmick called "redundancy check" [37l • The branch-and-bound algorithm used in designing initial networks in the NETTRA system is the simplified version of Nakagawa and Lai's algorithm, it only finds the first feasible solution but doesn't try to obtain the optimal solutions for the given function. Let x , I = 1, ...,n, be n external variables, and let f be the given function. The x , I = 1, ...,n, and f are expressed in the following way: X i ~ l''''' X H 2 - ±, f-if ,../- 1 ) Again, for the sake of convenience, only the single-output network case is considered here. 27 For example, if f = xjl v x x x , then x = (00001111) x 2 = (00110011) (3.1.3-1) "3 and = (01010101) f = (01011000) Let us assign an NOR gate to f, as shown in Fig. 3 • 1-3-1 • The output of this NOR gate is expected to eventually realize the given f, though at this stage the gate does not realize f yet since no inputs are connected. This network with a single gate is called the initial solution, f= (0 101100 0) Fig. 3»1»3-1 The initial solution to f = x x v x x x The output of the NOR gate is assigned f, but the gate has no inputs yet. 28 The algorithm starts with the initial solution, and expands the initial solution by connecting external variables, by introducing new gates, or by making interconnections among gates, so that the resulting loop-free network realizes the given function. In accordance with (3.1.3-1), the output of each gate to be introduced into the network is represented in the form of 2 -tuple as (P , ...,P ), where each P^ for j = 0, ...,2 -1, may assume the values or 1. It should be noted, however, that the algorithm will not assign a definite value or 1 at once to all components, P ' s, of a gate. Accordingly, we use the symbol * to denote that the value of P is unassigned. Let us find out a 2 n -l necessary condition that the output (P , ...,P ) of any gate in an NOR 2 n -l network satisfies. Consider two gates, i and k. Let (P.,...,P. ) and 2 n 1 (P , ...,P ' ) denote the outputs of gate i and gate k, respectively. If k -K. gate i is connected to gate k, then the components P. and P must satisfy the following condition, no matter whether or not gate i and gate k have other inputs, because the gates perform NOR operation: and E? = for all j such that P? = 1 k i P? = for all j such that P? = 1 l k (3.1-3-2) gate k gate i ( 1 1 1 1 1 ^ ( i i o i ) o ) Fig. 3 .1.3-2 If there are 1-components in the output of an NOR gate, then corresponding components in its immediately preceding/succeeding gates must be 0. 29 A similar condition must also hold between the output of gate k and an external variable x , when x is connected to gate k, regardless of other inputs to gate k: P J = for all j such that x 3 = 1, " (3.1.3-3) and x J = for all j such that P J = 1 I k If the assignment of binary values to the components P ' s of the 2 n -l output (P , . ..,P ) of a gate satisfies the above condition with respect to all of immediately preceding/succeeding gates and all connected external 2 n -l variables, then we call this assignment of (P , ...,P ) a feasible assignment . (Notice that some of components P ' s could be *.) Using the concept of feasible assignment, let us define an "intermediate solution . " Definition 3 .1-3-1 - A network of R gates, R > 1, with external variables x is called an intermediate solution if the network satisfies the following set of conditions : (i) The entire network has no loops. R gates are numbered 1 through R, as gate 1, . .., gate R. (ii)-a The first gate (i.e., gate 1) is assigned the output function. (ii)-b The outputs of the remaining gates (i.e., gate i, i = 2, ...,R), if any, are completely or incompletely specified. Each gate i for i = 2, ...,R, is connected to at least one of other gates in the network. (iii) The assignment of the output of each gate is feasible. Notice that the initial solution defined previously is a special case of an intermediate solution. 30 An intermediate solution network may or may not realize the given function. An intermediate solution whose network realizes the given function is said to be a feasible solution . (A feasible solution whose cost is the least among all feasible solutions is an optimal solution , though we do not intend to obtain it . ) J o Definition 3-1-2-2 - A component P = of gate k is said to be covered , if gate k has at least one input (i.e., the output of gate i or external variable x„) whose i -th component (P. or x, ) is 1. P, = of I o . v i l ' k J o gate k is said to be uncovered, if P is not yet covered. " " " " ri Fig. 3-1 -3-3 is an example of intermediate solution, where some components are already covered. (The covered components are shown with underlines . ) Clearly an intermediate solution is a feasible solution if all output components P = in all gates k are covered. J o Definition 3«l«3-3 - Suppose P in gate k is an uncovered — —_ — _— ^_ — — — — — - j^ 3 o component in a given intermediate solution. P, can be covered either by an external variable or by a gate if the external variable or the gate is a possible cover, as follows: In the NETTPA- system, the "cost" of a network is defined by C = A x R + B X I, where R is the number of gates, I is the total number of inputs to gates (i.e., the sum of connections of external variables and interconnections among gates), and A, B are non-negative coefficients (i.e., weights). Different combinations of weights A and B imply different design problems. For example, A > and B = implies finding a network with as few gates as possible, not counting the number of connections, A » B > implies finding a network with as few connections as possible after the number of gates is reduced to as few as possible. 31 f = X-,X v X..X x„ 13 12 3 (01011000) (10 10 0) (0 0001111) x (* 1 0) (*0*00 1**) (•* 1 * * * * *) (00110011) x x (0 101010 1) Fig. 3»l«3-3 Example of an intermediate solution for f = x x v x x x . where some components are covered and others are not (the covered components are underlined). 32 (i) An external variable x which is not yet connected to gate k is a possible cover of P = if x satisfies the following condition: 3 o x =1, and x 3 = for all j such that P J = I. £ k (Il) A gate i which is already connected to gate k is a 3 o possible cover of P = if gate i satisfies the following condition: j° - *. l (ill) A gate i which is not yet connected to gate k is a possible cover of P =0 if gate i satisfies the following condition: a connection of gate i to gate k will not form any loops, 3 o P. = 1 or * and i ' P? - or * for all i such that P J = 1. l k V (IV) A gate which is not yet incorporated in the intermediate solution is a possible cover. This gate is called a new gate , and satisfies the following condition: The ouptut components are all *. Sometimes there exists more than one possible cover for an uncovered component. In order to treat all possible covers and enumerate all inter- mediate solutions systematically, the following definitions are introduced. 33 Definition 3.1.3-4 - The selection criterion of uncovered components (SCUC) is the criterion under which an uncovered component p' = is selected from an intermediate solution under consideration. Definition 3.1.3-5 - The implementation priority of - possible covers (IPPC) is the priority under which the order of implementation among the pos- sible covers for the selected uncovered component is determined. Definition 3.1.3-6 - The cost ceiling , or the incumbent cost , C is used to preclude all intermediate solution whose cost exceeds the cost of the current best feasible solution. The basic form of the algorithm is given below. The branch-and-bound algorithm for finding the initial networks : Step (start ) : k = 1 Let S denote the initial solution. Set C to A x 50 + B x 99. ^ Step 1: Calculate the cost C, of the current intermediate solution S, . k k Compare C with C. If C is greater than C, then go to step 7; otherwise go to step 2. Step 2 : Search for an uncovered component in S, . . If there is none, then go to step 8; otherwise go to step 3. Step 3 : Select one uncovered component from S , according to the selection criterion of uncovered component (SCUC). Let P denote it. * The branch-and-bound algorithm for finding an initial network which is used in the NETTRA system is a simplified version of the algorithm for finding the optimal networks. Since only the first feasible solution is required, the cost ceiling C is set to the value such that all intermediate solution networks whose number of gates and connections exceed the possible maximal values (restricted by the core available) are precluded. t This means that the numbers of gates and connections in any network is re- stricted to be at most 50 and 99, respectively. 34 Step 4 : Make a list of all possible covers of P. Step 5 : Select one possible cover from the list, according to the imple- mentation priority of possible covers (IPPC) . Step 6 : Increment k by 1. Implement the possible cover selected at step 5, generating the augmented intermediate solution, S . K. Go to step 1. Step 7 : The cost of the intermediate solution network is greater than C. Stop. Step 8 : Print the Cost C, and the feasible solution S . Stop. The detailed discussion of the selection criterion of uncovered com- ponents (SCUC) , the implementation priority of possible covers (IPPC), the speed improvement gimmicks, the redundancy checks, and the algorithm for finding the optimal networks are given in [37]. It should be noticed that the branch-and-bound method (outlined in this section) used in the NETTRA system can also design networks for incom- pletely specified and multiple-output functions with both complemented and uncomplemented variables or only uncomplemented variables as inputs. 3.1.4 Tison's Method We can construct a two-level (if both complemented and uncomplemented external variables are permitted as inputs) or a three-level (if only com- plemented external variables are permitted as inputs) network based on each ■k minimum product for a given switching function. The following is an example to show this. * The formal definitions for minimum product and minimum sums will be given later. 35 Example 3.1.4-1 - The four-variable function f = I (0,3,7,11,12,13, 15) has a minimum product (x s, x v x^) (x.. v x_ ^ x. ) (x„ v x.) (x.. v x v x„) . The corresponding two-level and three-level networks are shown in Fig. 3. 1.4-1 (a) and Fig. 3.1.4-l(b), respectively. X X X 4 Xl *3> i>- (a) The two-level network based on the minimum product !3> 33n (b) The three-level network based on the mininimum product Fig. 3.1.4-1 Example 3.1.4-1 36 Obviously, no gate or connection can be removed from the networks based on minimum products without changing the outputs. Besides, according to experience, the networks based on the minimum products usually have low costs. Therefore if we can find some efficient way to generate the minimum products for the given function, then we can obtain economical intial net- works easily. Tison's method [40] is one way to obtain the minimum sums for a given function. Since the minimum products can be obtained by (1) finding the mini- mum sums for the dual of the given function, and then (2) by exchanging con- junction and disjunction in the minimum sums, we can apply Tison's method to design initial networks. Now let us review Tison's method for finding the minimum sums. The following definitions are introducted first to facilitate later discussions. Definition 3.1.4-1 - Let two switching functions be f(x) and g(x). If every x satisfying f (x) = 1 satisfies also g(x) = 1 but the converse does not necessary hold, we write f(x) £ g(x). and we say that f implies g . Definition 3.1.4-2 - An implicant of a switching function f is a term which implies f. An implicate of f is an alterm implied by f . Definition 3.1.4-3 - A term P is said to subsume another term Q, if all the literals of Q are factors of P. Similarly an alterm P is said to subsume another alterm Q if all the literals of Q are among literals of P. Definition 3.1.4-4 - A prime implicant of f is defined as an implicant of f such that no other term subsumed by it can be of an implicant of f . A prime implicate of f is defined as an implicate of f such that no other alterm subsumed by it can be an implicate of f. 37 Definition 3.1.4-5 - A variable whose complemented and uncomplemented literals both appear in a disjunctive form f-P v Q v ... vl of a switching function f is called a biform variable . If only one of the literals for a variable appears, the variable is called a monoform variable . Definition 3.1.4-6 - Assume two terms, P and Q given. If there is exactly one variable, say x, appearing without inversion in one term and with inversion in the other, in other words, if P = xP' and Q = xQ' (no other vari- ables appear with complement in one of P' and Q' without complement in the other), then the product of all literals except the literals of x, i.e., P'Q' is called the consensus of two terms, P and Q. Assume two alterms, V and W given. If there is exactly one variable, say x, appearing without inversion in one alterm and with inversion in the other, i.e., if V = x v V and W = x v W where V and W are free of literals of x, then the disjunction of all literals except those of x, i.e., V v W with duplicate literals deleted is called the consensus of two alterms , V and W. Definition 3.1.4-7 - An irredundant disjunctive form for f is a dis- junction of prime implicants such that removal of any of them makes the re- maining expression not equivalent to the original f. An irredundant conjunctive form is a conjunction of prime implicates such that removal of any of them makes the remainder not equivalent to f. An irredundant disjunctive form (also an irredundant conjuctive form) for a function is not necessarily unique. Definition 3.1.4-8 - Prime implicants which appear in every irredundant disjunctive form for f are called essential prime implicants of f . Prime impli- cants which do not appear in any irredundant disjunctive form for f are called absolutely eliminable prime implicants of f . Prime implicants which appear in 38 some irredundant disjunctive forms for f but not in all are called conditionally eliminable prime implicants of f. Essential prime implicates, absolutely elim- inable prime implicates, and conditionally eliminable prime implicates are similarly defined. Definition 3.1.4-9 - Among irredundant disjunctive forms of f , choose these with a minimum number of prime implicants. Among them, those with a mini- mum number of literals are called the minimal sums , or the minimal disjunctive forms for f . The minimal products (or minimal conjuctive forms ) are irredundant conjunctive forms of f with a minimum number of literals, among irredundant con- junctive forms of f with a minimum number of prime implicates. Definition 3.1.4-10 - The disjunction of all prime implicants of a switching function f is called the complete sum or the all prime implicants disjunction . Tison's method for finding the minimum sums for a given function f con- sists of two major steps: Step I : Find all prime implicants of f. Step II : Find all irredundant disjunctive forms of f using the prime impli- cants found in step I. The following two procedures (Procedure I and Procedure II) realize step I and step II, respectively. Procedure I (Tison method for the derivation of prime implicants) : Assume that a function f is given in a disjunctive form f - P v Q v ... v T, where 39 P, Q, ..., T are products, and that we want to find all prime implicants of f. Denote the set of P, Q, ..., T, with S. (1) Among the set of P, Q, . .. , T, first delete every term subsuming another from the given expression. Find biform variables. Then choose one of them. (2) For each pair of products, i.e., one with the complemented literal of the chosen variable and the other with the uncomplemented literal of that variable, generate the consensus. Add the generated consensus to S. From S, delete every product which sub- sumes another. (3) Choose another biform variable in the current S (when a subsuming product is deleted, a variable which was biform may become monoform) and go to Step (2). If all biform variables are tried, go to Step (4). (4) The procedure terminates and all the product in S are desired prime im- plicants. Example 3.1 .4-2 - Given f = x n x.x. v x-x„ ^ x.x_ v x_x. ^ x„x. 124 13 2 3 24 34 Following (1), we found that x„ and x, are biform variables. Let us choose x_. Following (2), we get consensus x..x 9 for pair, x x„ and x x • and con sensus x.x. for pair, x.x and x_x. . 14 r 13 3 4 S: Subsumes (2) Following (3), we choose the remaining biform variable x, , go back to Following (2), we generate two consensi as follows: 40 j ! X- X« j XrtX^ ^ XrtX#j X^X.j X _ X ,, , X-X. But when we add x x and x x„ to S, all of them subsume the products contained in S. So they are eliminated. Now, the current S contains all prime implicants: x x„, x_x, , x„x, , x x, , x 9 x o an d x x_. Procedure II (Tison method for the derivation of all irredundant disjunctive forms ) : Assume we have all prime implicants of f, i.e., P, Q, ...,T found in Procedure I. Let S denote the set of these prime implicants. We want to find all irredundant disjunctive forms of f. (1) Label each prime implicant P with an index number I, denoting as PI. Using Procedure I with the following modification, let us find which prime implicants generate which prime implicant as consensus. (2) Choose the first biform variable, say x. We will find consensi with re- spect to x as follows. If P-,1, and P~I 9 generate a consensus with respect to x, in other words, if P = xp and P_ = xp , then the consensus P-,P 9 is indexed with the combination of the index numbers I,I 9 as: p i p 2 hh' Find all such indexed consensi with respect to x which can be generated from all the prime implicants in S. (3) Compare each of the indexed products derived in the previous step with all those in S, by regarding each indexed product to be a product consisting 41 of the original literals and index numbers as new literals (e.g., indexed product x ? x x 48 is regarded as a product consisting of literals x„,x„,x, , 4, and 8). If any product is subsumed by another, discard it and otherwise add it to S. (4) Choose next biform variable and return to Step (2). If all the biform variables are tried (each biform variable needs to be tried only once) , the indexed products in S denote all consensus relations. (5) For each prime implicant of f (although non-prime implicants of f are usually contained in the last S, we ignore all these non-prime implicants), find all the indexed products which contain this prime implicant. Then make the disjunction of all the index numbers contained in them. (i) Then make the conjunction of all these disjunctions. This conjunc- tion is called the Tison function , (ii) Multiplying out, treating index numbers as switching variables, obtain the complete sum. (iii) Corresponding to the index numbers in each term of the complete sum, make the disjunction of the prime implicants which have these index numbers. All disjunctive forms obtained are all irredundant disjunctive forms. Example 3.1.4-3 - For the function in Example 3.1.4-2, the prime im- plicants are x x~, x x, , x~x, , x..x, , x„x„, x x ? . Let us follow Procedure II to derive all irredundant disjunctive forms. Step (1): S = {x.x 1, x x 2, x„x.3, x n x.4, x_x_5, x..x_6} 13 Ik 34 14 15 12 Step (2): x and x. are biform variables. Let us choose x„. Two consensi are 3 4 3 then generated: x^x.13, x-x„15. 14 12 Step (3): The consensi generated in step (2) do not subsume any other product. So 42 the current S = {x x 1, x x 2, xx 3, x.x,4, x.x.5, xx6, x.x.13. r3 ^, Ar4 „, ^^ * iV , x 2 * 3 d, Xi x 2 d, x^. x 1 x 2 15}. Step (4): Choose the biform variable x and return to step (2). Step (2): Three consensi x 2 x 3 23, x.^24 and x x 123 are generated. Step (3): They do not subsume any other product, so S = {x x 1, x x 2 x x 3 13 2 4' 34' x l x 4 4 > X 2 X 3 5 ' x i x 2 6 ' ^13, x 2 x 3 23, x.^24, x.^123}. Step (4): Since all biform variables have been tried, S contains all consensus relations. Step (5): Form the Tison function: T = (1) (2) (3) (4 s/ 13) (5 - 23) (6 v 15 ^ 24 - 123) Multiplying out, we get T = 123 (456 v 145 s, 245 ^ 234 v 135 ^ 123) = 123 Therefore the minimum sum is x x ^ x x, ^ x~x. Besides the Tison 's method, there are many other ways to find the minimum sums. A software package named MINIPACK (MINImization PACKage) is under development by R. Cutler. In this package, Tison's method, the branch- and-bound method, the hybrid method (the combination of Tison's method and the branch-and-bound method) and Quine-McCluskey 's method [26] with the branch-and-bound method (developed by I. Suwa) are all included. The method used in NETTRA system is a straight-forward version of Tison's method. 3.1.5 Gimpel's Algorithm Gimpel's algorithm is a method for finding optimal (minimum number of gates is the only cost criterion) three-level NAND networks for any given 43 switching function with only uncomplemented external variables as inputs . Since the problem of designing optimal three-level NOR networks for the given function is equivalent to the problem of designing optimal three-level NAND networks for the dual of the given function, Gimpel's algorithm is also used to design initial networks in the NETTRA system. The detailed algorithm is very long and complicated [7]. Only the basic ideas are reviewed in this section. Let us call the output gate of a network the first-level gate. For the three-level NAND network shown in Fig. 3.1.5-1, the function realized at the output of each input gate (third-level gate) is of the form T where T is the product of uncomplemented external variables. The conjunction of func- tions realized at the inputs of each second-level gate has the form T_ T_ ... T ; here again, T n , T. , ... T for m > 0, are products of uncomple- u i m (J 1 m — mented external variables. The function realized by the network in Fig. 3.1.5-1 can thus be expressed as disjunction of these T T ... T expressions. Gimpel's algorithm aims at finding appropriate products T.. , . . . , T (each corresponds to a third-level gate) and expressions T_T., ... T (each corresponds to a second- 1 m level gate) so that the total number of gates needed is minimum. The follow- ing definitions and examples are useful for our discussions. Definition 3.1.5-1 - A frontal term is a product of different uncomple- mented variables or the constant 1. Example 3.1.5-1 - x, wxyz, 1 and wy are frontal terms whereas xy and xy v w are not. Every input gate in Fig. 3.1.5-1 realizes a function of the * In [7], this is called a TANT network. (Three-level AND-NOT network with J_rue inputs. ) 44 INPUTS X 2 THIRD-LEVEL GATES (INPUT GATES) O -O SECOND-LEVEL FIRST- LEVEL GATES GATE ^> INTER- CONNECTIONS 1 7 ~> ♦ f 'Iff. 3.1.5-1 A three-level TANT network 45 form P where P is a frontal term. Definition 3.1.5-2 - A permissible expression is any switching ex- pression (not identically 0) of the form T T ... T for m ^ where each T. is a frontal term. In a permissible expression T_T 1 ... T , T_ is called 1 m the head of the expression, whereas T-. . . . T is called the tail of the ex- 1 m pression and each T. is called a tail factor for i = 1, . . . , m. i Example 3.1.5-2 - xy(wx)(yz), xyz, x, 1, v(wxyz) and yxzw are per- missible expressions with heads xy, xy, x, 1, 1 and xw, respectively, whereas xvy, xy(xy) and x(l) are not permissible expressions. Definition 3.1.5-3 - An irredundant permissible expression is a per- missible expression in which no factor (either head factor or tail factor) can be removed without changing the function expressed. Definition 3.1.5-4 - A TANT expression is an expression of the form E.. ss E„ v • . . v E where E . is a permissible expression. Example 3.1.5-3 - w(wxy) v- xy(wxy) is a TANT expression. The TANT expression corresponds to the output of the TANT network shown in Fig. 3.1.5-1 Definition 3.1.5-5 - A permissible implicant of a switching function f is a function which implies f and which can be written as a permissible ex- pression. Example 3.1.5-4 - Given f(w,x,y) = yw ^ wx v ywx. The irredundant permissible expressions which imply f are listed below: wxy, (wx)xy, (wy)xy, (wxy)xy In a TANT network, the conjunction of functions realized at inputs of each second-level gate is a permissible expression. 46 w(xy) , w(wxy) wx, w(wx) wy, w(wy) wxy, wx(wy), wx(xy), wx(wxy) wxy, w(wx)y, w(xy)y, w(wxy)y wxy, w(wx)y, wx(wy), w(wx) (wy) These 22 irredundant permissible expressions are classified into 7 groups. Each member in the same group expresses the same permissible impli- cant. The members in the first group, (wx)xy, (wy)xy and (wxy)xy express the same permissible implicant wxy. As a matter of fact, the former three can be obtained by augmenting the tail factor with head variables in the latter expression wxy in three different ways: wxy = wxy s, xxy = (w ^ x)xy = (wx)xy; wxy = wxy v xxy v yxy = (w vx vy)xy = (wxy)xy; and wxy = wxy v yxy j (w ^ y)xy = (wy)xy. Definition 3.1.5-6 - The permissible expression which cannot be ob- tained by augmenting the tail factor with head variables in any other permis- sible expression, such as wxy in Example 3.1.5-4, is called the principal ex- pression for a given permissible implicant. Its tail and tail factors are called the principal tail and principal tail factors , respectively. Definition 3.1.5-7 - A prime permissible implicant (or PP-implicant) of a function f is a permissible implicant such that if any principal tail factor is removed from its principal expression, the resulting function will not be a permissible implicant of f. Definition 3.1.5-8 - A lower PP-implicant is a PP-implicant properly implying a prime implicant. An upper PP-implicant is a PP-implicant which is not lower. 47 Definition 3.1.5-9 - A permissible implicant is said to be simple if all its principal tail factors are complemented variables (in other words, if it can be expressed as a product of literals); otherwise, the permissible im- plicant is said to be compound . In the following, theorems are stated without proofs. Theorem 3.1.5-1 - If a permissible implicant P is compound, then P is an upper PP-implicant. Theorem 3.1.5-2 - Every prime implicant is an upper PP-implicant. Example 3.1.5-5 - Consider the function f given in Example 3.1.5-4. There are six PP-implicants for f, as shown in Table 3.1.5-1. Among them, there is only one compound PP-implicant, there are three prime implicants and there are four upper PP-implicants. Please notice that each prime implicant is an upper PP-implicant, since it does not properly imply itself. Table 3.1.5-1 The PP-implicants of the function in Example 3.1.5-4. PP-implicant Compound Prime Implicant Upper PP-implicant w(xy) X X xyw X X wx X X wy X X wxy wyx Theorem 3.1.5-3 - Let the minimization of the number of gates be the first cost criterion and let the minimization of the number of connections A way to find all PP-implicants will be explained later. 48 be the second cost criterion. The permissible implicants in each minimum TANT expression are PP-implicants . Theorem 3.1.5-4 - Let the minimization of the number of gates be the cost criterion. For any function f , there exists a minimum TANT expression in which every permissible implicant is an upper PP-implicant . Definition 3.1.5-10 - The maximum permissible implicant with head H is the disjunction of all permissible implicants with the common head H. Theorem 3.1.5-5 - The maximum permissible implicant P_ with head H of a function f can be written as P = H (it v ir v . . . v ir ) 1 z m where {tt, , tt„ ... tt } is the set of prime implicants which is implied by the 12m minterms with head H. Definition 3.1.5-11 - Let {S- ,... ,S } and {T- , .... T } be sets of I'm 1 n frontal terms. The set {S.} is said to be an overlay for {T.} if for each T x *- 1 1 there exists some some S. such that S. r»T.. If no S. can be removed without J J - i i destroying this property, then {S.} is said to be an irredundant overlay . Theorem 3.1.5-6 - Let HT ... T be the principal expression for the 1 n maximum is permissible implicant with head H of a function f. Then HS ... S^ i the principal expression for a PP-implicant of f if and only if (S l , ..., S } is an irredundant overlay (except the unit overlay {l}) for {T , ..., T }. Example 3.1.5-6 - The function given in Example 3.1.5-4 has three prime implicants of wy, wx and wxy. Minterm wxy implies prime implicants wx and wy. Thus by Theorem 3.1.5-5, w(wy v wx) = w (xy) yields the maximum per- missible implicant with head w. Minterm wxy implies prime implicants of wy only. Thus we obtain wx(wy) = wxy which is the maximum permissible implicant with head wx. For the similar reason wxy is a maximum permissible implicant wy 49 There is only one minterm wxy with head xy, so wxy is also a maximum permissible implicant. Take the maximum permissible implicant w(xy). There are three irredun- dant overlays (except {1}) for {xy} : {xy}, {x} and {y}. So we have three PP-im- plicants with head w: w(xy), wx, wy. Take the maximum permissible implicant wxy. There is only one irredundant overlay except {1} for {w} : {w}. So we have only one PP-implicant wxy with head xy. Applying Theorem 3.1.5-5 and Theorem 3.1.5-6, we can generate all PP- implicants for any function f and from these PP-implicants we can find all upper PP-implicants. But not all PP-implicants or upper PP-implicants are necessary for finding minimum TANT expressions. We give the following definitions, theorems and examples to explain how to get minimum TANT expressions. Definition 3.1.5-12 - A permissible implicant P n is dominant if for every permissible implicant P, either P P = or P r> P. Definition 3.1.5-13 - A permissible implicant is quasi-simple if at most one of its principal tail factors is compound. Definition 3.1.5-14 - A major PP-implicant is any upper PP-implicant not properly implying a dominant quasi-simple PP-implicant. Theorem 3.1.5-7 - A maximum permissible implicant with head H of a function f is dominant if and only if there exists at least one prime impli- cant with head H, and the disjunction of all the prime implicants with head H is disjoint with the disjunction of all the remaining prime implicants. Theorem 3.1.5-8 - For any function f there exists a minimum TANT ex- pression such that each permissible implicant is a major PP-implicant. Figure 3.1.5-7 - For the previous example, there are two major PP-im- plicants: w(xy) and wxy. The only question that remains is which particular irredundant permissible expressions should be chosen for each of these two major 50 PP-implicants. There are four irredundant permissible expressions for wxy: wxy, (wx)xy, (wy)xy and (wxy)xy and there are two for w(xy) : w(xy) and w(wxy), If we choose the last two expressions in both cases we are able to share input gates. The resulting minimum TANT network is shown in Fig. 3.1.5-2. X W Y > w Ch > o -*> f Fig. 3.1.5-2 The minimum TANT network for f The selection of major PP-implicants for a minimum TANT expression is essentially a minimum covering problem. The concepts of major PP-implicant table and cc-table are introduced in [7] to try to solve the minimum covering problem, with details omitted here. A procedure to speed up the processing of the cc- table which is the most time-consuming part of Gimpel's algorithm [7] is dis- cussed in [10] . Also notice that Gimpel's algorithm based on upper PP-implicants yields only networks with a minimal number of gates, not considering the number of connections, so a network which has the minimal number of gates as the pri- mary objective and the minimal number of connections as the secondary objective may not be obtained. 51 3.1.6 Level-restricted initial network method The level-restricted initial network method can expand a two-level or a three-level network, which is based on Tison's method, into a level-restricted network when both the fan- in/fan-out restrictions and the level-restriction are imposed. For the sake of convenience, we will assume that both uncomplemented and complemented external variables are permitted as inputs in the following dis- cussions. Assume that a minimum product for the given function f consists of £ alterms, and the i-th alterm (1 <_ i <_ £) consists of n. literals. The corres- ponding two-level network is shown in Fig. 3.1.6-1. Let the maximum fan- in of a gate be FI, the maximum fan-out of an external variable be FOX and the maximum fan-out of a gate be FO. In Fig. 3.1.6-1, if I > FI, then there is no fan-in problem at the first- level gate G, and we need to check the fan- in problems of the higher level gates only. If £ > FI, then we can solve this fan-in problem using the following approach: n 2 |j nz>- n, ill Fig. 3.1.6-1 Two-level network based on the minimum product In this paper, whenever we mention that "there is a fan- in problem at gate G", we mean that the number of fan-in of gate G is greater than the restriction FI. The jfan-out problem at a gate or an external variable is similarly defined. 52 (1) Partition the input functions of gate G into at most FI groups. (2) Realize the disjunction of the functions of each group by a two-level sub- network. (1) solves the fan- in problem at gate G. (2) increases the number of levels by one and may generate some fan-in/fan-out problems in those two-level subnetworks, But the fan-in problems can be solved by applying procedures (1) and (2) re- peatedly. It is easy to see that networks derived by this approach will have a tree structure, hence there is no fan-out problems for gates. There may be fan- out problems for external variables, but they can be solved by adding extra in- verters. Following the above procedures, we can always get a level-restricted network; since each time these procedures are applied, the number of levels of the network is increased at most by 1 (when both uncomplemented and comple- mented external variables are permitted as inputs, as we assumed). We can also follow these procedures repeatedly until a fan-in/fan-out restricted network is obtained. In procedure (1), how to divide the I input functions into FI groups I is an important problem. An improper formation of groups may generate more fan-in/fan-out problems in higher-level gates. Consider the network shown in Fig. 3. 1.6-2 (a). Suppose the disjunction of functions f 1 , f„, ..., and f, is to be realized by a two-level single-output subnetwork, where f. is the output function of gate i fed by n. inputs (external variables). In the worst case, all inputs (external variables) of the gates for f , , f , ..., and f are differ- ent. Assume they are x n , x„, ..., x . .. . (for simplicity, assume 1 I n i "*" n ? n k ■k In the case that only uncomplemented external variables are available, the number of levels of the network is increased at most by two each time the above procedures are applied. In this case it is also possible that the number of levels does not increase after applying procedures. 53 all uncomplemented). Then V f . ■ x, . . . x ^ x ...... x ^ . . . . , i 1 n n.,+1 n 1 +n„ x x n n +n +. . .+n. n +l ... n,+n_+...n. 1 2 k-1 12 k or V f . = (x . v x. v . . . v x ) (x .- v v . . , l l 2 n, n n +l ... x . ) . . . i=l 1 1 "l"^ 1 ? (x n n +n +.. .-hi +1 ^'" vX n 1 +n +..-.+n 1 ) (3.1.6-1) 1 2 k-1 12 k If we multiply out equation (3.1.6-1), we can get a disjuntive form which has k it n. terms and each term is a product of k literals. Taking the complement 1=1 x k of this disjunctive form, we can get a conjunctive form for V f.. This con- k 1=1 * junctive form has it n. alterms and each alterm is a disiunction of k literals. i-1 * A two-level NOR subnetwork can be obtained based on this conjunctive form. The k k total number of NOR gates in this subnetwork is it n. + 1, i.e., tt n. gates i=l X i=l X in the higher level and another one in the output level, See Fig. 3.1.6-2(b). An example is given gelow: Example 3.1.6-1 - Suppose f, = x, x , f = x~x , i.e., n = 2 and n_ = 2 are realized as part of a network, as shown in Fig. 3.1.6-3. Then \ v f 2 = (x 1 ^x 2 ) (x 3 V x^) = X, X_ s/ X n X. ss X X„ ss X X. Ij 14 23 24 = (x 1 v ■&) (x 1 v-x,)(x 2 v x„) (x 2 n/ x^) So a two-level subnetwork can be obtained in Fig. 3.1. 6-3 (b) r n i i Xi E> n k - L Xnj.-. + nk.i + i X ni +... + n k rn> iB* jH> T fl U+l EXTERNAL VARIABLES 54 D>— Fig. 3.1.6-2(a) V f. is to be realized by a two-level single-output subnetwork INPUTS ARE COMPLEMENTED EXTERNAL VARIABLES TWO- LEVEL SUBNETWORK EXTERNAL VARIABLES Fig. 3.1.6-2(b) The result after applying procedures (1) and (2). k There are II n. + 1 gates in the two-level subnetwork. X; x' r> ^;; s=x> 55 flVf; (a) The original network (b) The network after applying procedures (1) and (2) Fig. 3.1.6-3 Example 3.1.6-1 Of course, the above analysis is the worst case. Usually some x. and x. both appear in equation (3.1.6-1) so that many terms become identically zero after multiplying out equation (3.1.6-1) - this means that the total number of the second-level gates or the total number of fan-in of gate G 1 in Fig. 3.1.6-2 k _ is less than it n.. Sometimes x. (or x.) appears in more than one alterm in . , i l i i=l equation (3.1.6-1) so that many terms may contain fewer literals than k and also some terms subsume other terms and hence can be eliminated after multiply- ing out equation (3.1.6-1). In general, if more pairs of x. and x. appear in different alterms and x. or x. appears in more alterms, then fewer gates will have fan-in problems and fewer external variables will have fan-out problems in the resulting two-level subnetwork. Example 3.1.6-2 - Consider the two-level network in Fig. 3. 1.6-4 (a), where f = x x_x„, f = x x x , f = x,x,x and FI = FOX = 2. Since the output gate has 3 inputs, let us first solve this fan-in problem. It is obvious that 56 if we realize the disjunction of any two of the three functions f, , f and f by a two-level subnetwork, we can reduce the fan- in of the output gate by 1. Fig. 3.1.6-4(b) through Fig. 3.1.6-4(d) show the results of three possible ways of partitioning f, , f and f into two groups. In Fig. 3.1.6-4(b), f v f. is realized. f v f~ has two pairs of complemented and uncomplemented external variables and x_ appears twice. In Fig. 3.1.6-4(c), f v f_ is re- j 1 -^ alized. f ^ f has no complemented and uncomplemented pairs but x appears twice. In Fig. 3.1.6-4(d), f ? v f„ is realized. f 9 ^ f„ has one complemented and uncomplemented pair but no literal appears two or more times. Obviously, the result obtained in Fig. 3.1.6-4(b) is the best among three. Since this network still has fan-in problems, we apply the similar procedures to solve these problems. The fan- in/ fan-out restricted network which results is shown in Fig. 3.1.6-5. \3> 13> fi 3> Fig. 3. 1.6-4 (a) The original two-level network 57 X_l x? x 2 =£>t5>i nvts t> Fig. 3.1.6-4(b) The network after realizing f V f 1 2 :!3> x 2 =z> X, o- > O — **i f,wf. Fig. 3.1.6-4(c ) The network after realizing f,Vf_ 58 X 4 ;3> > n O f 2 vf 3 ♦ f Fig. 3.1.6-4(d) The network after realizing f 9 Vf~ O^O^" E>— Fig. 3.1.6-5 The fan-in/fan-out restricted network for f in Example 3.1.6-2, 59 In general if there are more common literals and if there are more pairs of complemented and uncomplemented literals appearing in equation (3.1.6-1), then the resultant two-level subnetwork will have fewer number of gates and also fewer gates will have fan-in problems. The following two criteria (1 as the primary criterion and 2 as the secondary criterion) are used in partitioning the input functions of a gate into groups to solve the fan- in problems: Criterion 1: Select the group which has the largest number of common literals. Criterion 2 : Select the group which has the largest number of pairs of complemented and uncomplemented external variables. The implementation of procedures (1) and (2) and the way to treat multiple-output network problems are detailed in [12]. 3. 2 Fan-in/ fan-out restricted transformations In this section we discuss the fan-in/fan-out restricted transforma- tion method [24]. Any NOR network that does not satisfy the given fan-in/fan- out restrictions can be transformed by this method into a fan-in/fan-out re- stricted network. A set of six transformations (T through T,) will be re- 1 o viewed one by one. The following definitions are introduced first: Let external variables be x,, x„ , ..., x (and x n ,x ,...,x when un- 1 2. n 1 Z n complemented external variables are available) and the network has R gates g, , g„, ..., g_. Let the maximum fan-in of a gate, the maximum fan-out of a gate (not an output gate) , the maximum fan-out of an external variable and the maximum fan-out of an output gate be FI, FO, FOX and F00, respectively. Definition 3.2-1 - A gate g. is said to be an immediate successor of gate g. (or external variable x.) if and only if the output of g ± (or ex- ternal variable x.) is connected to g. as an input. Let IS(g ± ) (or IS(x i >) denote 60 the set of all immediate successors of the gate g. (or external variable x.). Definition 3.2-2 - A gate g. is said to be an immediate predecessor of gate g. if and only if g. £ IS(g.). Let IP(g.) denote the set of all im- mediate predecessors of the gate g.. Definition 3.2-3 - Condition set CI consists of the following con- ditions for the application of transformation Tl : ^ |F0 if g. is a non-output gate (1) |lS(g.)| > / JFOO if g. is an output gate (2) |lP(g.)| must be less than or equal to FI (3) For every gate g e IP(g.), |lS(g )| must be less than FO (or K X K F00 for output gates). For every external variable x e IP(g.), rC J. |lS(x )| must be less than FOX. Definition 3.2-4 - Condition set C2 consists of the following condi- tions for the application of transformation T2 which is used to solve the fan-out problem of an external variable: (1) |lS(x.) I > FOX J (2) There exists a gate g. whose only immediate predecessor is ex- ternal variable x. : i.e., IP(g.) = {x.}. (3) For this particular gate g., FO if g. is a non-output gate (a) |lS(g,)| < [F00 if g. is an output gate f Definition 3.2-5 - Condition set C4 consists of the following condi- tions for the application of transformation T4 : (1) |lP(g i )| > FI |lS(g.)| and |lP(g.)| represent the number of elements in sets IS(g.) and IP(g.! respectively. 1 Condition sets which are numbered in correspondence to the transformation numbei by Legge []3] are used here, so there are no C„ and C,.. 61 (2) There exists a gate g. such that FO if g. is a non-output gate (a) |lS(g.)| < 1 FOO if g. is an output gate (b) every immediate predecessor of g. is also an immediate predecessor of g.. (3) |lP(g.)| - |lP(g.)| < FI Definition 3.2-6 - Condition set C6 consists of the following condi- tions for the application of transformation T6: (1) There exists a set of gates and/or external variables K = {x. , X l ..., x. , g. , ..., g. } (t may be or t may equal k in some cases) and X t X t+1 \ a set of gates H = {g. , g. , . .., g. } such that for every g. e H, IP(g. ) J l J 2 : h J r J r 3 K holds, for every g. e K, IS(g. ) z> H holds, and for every x. e K, IS (x. ) s s r r =3 H holds. (2) 2 <_ k £ FI. (3) 2 £ h <_ (FO) 2 (4) The number of gates in K with fan-out problems plus the number of gates in H with fan-in problems must be at least 2. Transformations Tl, T2 and T3 are used for solving fan-out problems, whereas transformations T4 and T5 are used for solving fan-in problems. Trans- formation T6 is used to solve the composite problem. Transformation Tl : If a gate (not output gate) g., shown in Fig. 3.2-l(a) has a fan-out problem and condition set CI is satisfied, then transformation Tl is applied as follows: a gate, g is added to the network, as shown in Fig. J 3.2-l(b) where the original gate g. is denoted with g'. after modification. The immediate predecessors of g. are connected as inputs to g.. As many output con- nections as necessary to correct g.'s fan-out problem — up to a maximum number 62 IP(g ± ) is(g i ) (a) IP(g i ) IS(g ± ) - D (b) Fig. 3.2-1 (a) Gate g. with fan-out problem (b) Gate g. 's fan-out problem is solved by applying Tl. After the transformation, the following relations hold. If |lS(g. )|< 2 x FO, then |lS(g. ) - d| = FO and |d| < FO. If |lS(g. )| > 2 x FO, then |lS(g. ) - d| > FO and |d| = FO. Here D denotes the set of gates fed by the transferred connections. 63 equal to FO — are transferred from g to g. (let the set of gates fed by transferred connections be designated D). Thus, in the case when |IS(g.)| is originally greater than two times FO, g. will still have a fan-out problem (although less than the original problem) following the transformation, and further transformations will have to be employed. The case for an output gate g. can be treated similarly. Transformation T2 : For any gate g. and any external variable x. sat- isfying condition set C2, the fan-out problem of x. is solved as follows: As shown in Fig. 3.2-2, add a new gate, g , as an immediate successor to gate g. K. 1 and transfer as many output connections (excluding the connection to g.) as necessary to correct x.'s fan-out problem — up to a maximum number equal to FO — from x. to the outputs of g (let the set of gates fed by the transferred connections be designated D). Then, the function x. is available at the output of gate g . Thus, in the case when |lS(x.)| is originally greater than FO + FOX, x. will still have a fan-out problem (although less than the original' problem) following the transformation, and further transformations will have to be employed. Transformation T3 : This transformation is used to solve the fan-out problem of a gate g. (or external variable x.) when neither condition set CI nor condition set C2 is satisfied. There are three general cases (each case will be discussed for a non- output gate, g., but the transformations for output gates and external variables are similar) : (1) If gate g. has a fan-out problem and FO < |lS(g.)| <_ (2 x FO) - 1, then the corresponding transformation results in Fig. 3.2-3. An output from gate g. is connected to a new gate, g.. An output from g. in turn is connected to another new gate, g . As many output connections as necessary to correct 64 IS(x ) - (g i ) '. is(g i ) (a) IS(x.) - D 3 (g!) D (b) Fig. 3.2-2 (a) IS(x.) exceeds the fan -out constraint (J (b) After application of T2, x. has only | IS (x.) - D| i immediate successors. However, if | IS(x .) |< FO -f FOX originally, then |lS(x.) - d| = FOX and |d| < FO after the transformation. If |lS(x.)| > FO + FOX originally, then |lS(x.) - d| > FOX and |d| = FO J after the transformation. 65 g ' s fan-out problem are transferred from g. to g (let the set of gates fed X IK by the transferred connectsions be designated D) . (2) If gate g has a fan-out problem and (2 x FO) - 1 < |lS(g.)| <_ 2 (FO) + FO - 1, then the corresponding transformation results in Fig. 3.2-4. The only difference between this transformation and that shown in Fig. 3.2-3 is that gate g. now fans out to I newly added gates, g , g , ..., g, where J k 1 k 2 k^ £ is the smallest integer such that (£ + 1) x FO - 1 _> |lS(g.)|. Output connec- tions are transferred from g. to g , g , ..., g such that g., g, , g, , ..., x k 1 k 2 k £ x k 1 k 2 g each will have a fan-out of FO while g will have a fan-out of k l - 1 k £ |lS(g.)| - I x FO + 1 (which will be <_ FO) . Let the sets of connections trans- ferred to g , . . . , g be designated by D , ..., D , respectively. k l *l I a o (3) If gate g. has a fan-out problem and |lS(g.)| > (FO) + FO - 1 then the corresponding transformation results in Fig. 3.2-5. The only differ- ence between this transformation and that described in Fig. 3.2-4 is that .gate g. now fans out to I newly added gates, g , g , ..., g, , where I is equal to 3 k l k 2 k £ FO. Output connections are transferred from g. to g , g , ..., g, , such that x k 1 k 2 k £ g., g , ..., g each will have a fan-out of FO (|d | = |d_| = ... = |d | = FO) . 3 k. K. 1 2. x. In this case, g. will still have a fan-out problem (although less than the original problem) following the transformation, and further transformations will have to be employed. Transformation T4 : Consider the two gates shown in Fig. 3.2-6 in which gate g. has a fan- in problem and there exists a gate g. such that IP(G.) cr IP(g.) If condition C4 is satisfied, then a new gate g is added as shown in Fig. 3.2-7. K Gate g, f s output is connected as an input to gate g. , and the output of gate g. is connected as an input to gate g . Finally, every connection from an immediate predecessor of g. is removed from g.. 66 • D Fig. 3-2-3 Gate g. after application of T3 when FO < |lS(g.)| < (2 X FO) - 1. After the transformation: |'IS(g.) - D + l| = FO and |d| < FO. is(g.) -U D v & x / W s — i g s=i rr j k 2 t-l >k . Di D: D H-l Fig. 3-2-U Gate g. after application of T3 when (2 X FO) - 1 < |lS(g.)l < (F°) 2 + FO - 1. After the transformation: \l)i |lS(g.)| - (Z X FO) + 1 < |D 2 | = c^lD^^I = FO, \D £ \ I FO, |lS(g!)| = |lS(g.) -U D J + 1 = FO, and I < FO. 1 1 s=l 67 I [ IS( gi ) -M D £ s=l iE> ^i • Di D- Fig. 3*2-5 Gate g. after application of T3 when |lS(g.)| > (FO) 2 + FO - 1. After the transformation: |Di| = ID2I = • •• = I |Dg|, I = FO and | IS ( g ± ) -|J D S I + 1 > FO. s=l 68 IP(gJ J IP(g.) - IP( gj ) Fig. 3»?-6 Gate g. has a fan-in problem and IP(g.) c IP(g.) holds. iPCgi) ip( gj ) ip(c,) J Fig. 3»2-7 The fan-in problem of g. is solved by transformation TU. After the transformation: |lP(g.) - IP(g.)| 4- 1 < FI. 69 Transformation T5 : This transformation is used to solve the fan-in problem of a gate g. when C4 cannot be satisfied. There are three general cases: (1) If gate g. has a fan-in problem and FI < |lP(g.)| £ (2 x FI) - 1, then the corresponding transformation results in Fig. 3.2-8. An output from a new gate, g., is first connected to g.. As many input connections as necessary to correct g.'s fan-in problem are transferred from g . to a new gate g and 1 IK. then the output of gate g, is connected to g. (in Fig. 3.2-8, D designates the set of gates whose output connections are transferred) . (2) If gate g has a fan-in problem and (2 x FI) - 1 < |lP(g.)| i i 2 j< (FI) , then the corresponding transformation results in Fig. 3.2-9. This transformation and that shown in Fig. 3.2-8 are similar, but in this case gate g. is fed by £ new gates g. , g. , ..., g. where Z is the smallest integer 1 : 1 3 2 2 l such that I x (FI - 1) + FI _> |lP(g.)|. For each gate g. (p - 1, 2, ..., I) , the output of another new gate, g is connected to g. . Input connections P P are transferred from g to g , g , . . . , g such that g , g , g , . . . , g 1 K 1 * 2 HL^ 1 K. ± K 2 K £ - 1 each will have a fan- in of FI while g will have a fan-in of |lP(g.)| - I x (FI - 1) (which will be <_ FI) . Here the set of connections transferred from g. to g (s = 1, ..., I) is designated D (s = 1, ..., I), respectively. IK S s i 2 (3) If gate g. has a fan-in problem and |IP(g.)| > (FI) , then the corresponding transformation results in Fig. 3.2-10. Outputs from I new gates 8^ » g. > • • • , g. , where I = FI, are connected to g.. Again, for each gate J l 3 2 J £ 1 8^ (p = 1, 2, . . . , £) , the output of another new gate, g, , is connected to P p g. . Input connections are transferred from g. to g, , g , ..., g such that J p X . 1 k 2 k £ g, , g , ..., g each will have a fan-in of FI. The only difference between K l k 2 k £ this transformation and that shown in Fig. 3.2-9 is that gate g. will still be 70 left with a fan-in problem after the transformation (although less severe than the original problem) and further transformation will have to be employed. IS(g j _) - D Fig. 3-2-8 Gate g. after application of T5 when FI < |lP(g.)| < (2 X FI) - 1. After the transformation: |lS(g.) - D + l| - FI and Id! < FI. Me ± ) - U D s=l Fig. 3.2-9 Gate g. after application of T5 when (2 X Fl) - 1 < |lP(g.)| Z FI 2 . After the transformation: |Di| = |D 2 | = ,.. = ID^^I = FI, |D^| = |lP(g i )| - i X (FI - 1) and l < FI - s=l 71 Dl D I \ Fig. 3.2-10 Gate g. after application of T) when |lP(g.)| > (FI) 2 . After the transformation: |Di| = \d 2 \ = ... = |dJ = FI, I I = FI and |lP(g!)| - |lP(g.) - (JD S | + I = |lP(g ± )| - (FI) 2 + FI > FI. s=1 ' Transformation T6 : This transformation is applied when condition C6 is satisfied. For example, consider the original subnetwork configuration in Fig. 3.2-11 in which there exists a set of gates K= {g. , g. , ..., g. } and a X l X 2 \ set of gates H = {g. , g. , ..., g. } such that the output of each gate g. is J h X J l J 2 connected to each gate g.. There are two general cases: (1) If the subnetwork in Fig. 3.2-11 exists and satisfies condition set C6 and h < FO, then the corresponding transformation results in Fig. 3.2-12. An output from g . , g . , g. is connected to a new gate g . The output of g in turn is connected to another new gate g . Gate g then is connected as an input to g 4 , g. , ..., g. . The h output connections from each of J h h' ~ 2 2 gates g , g , ..., g to gates g. , g. , ..., g. are removed. 1 2 \ ^1 ^2 J k 72 (2) If the subnetwork in Fig. 3.2-11 exists and satisfies condition 2 set C6 and FO < h < (FO) , then the corresponding transformation results in Fig. 3.2-11 Subnetwork structure upon which transformation T6 may- be applied. Fig. 3.2-13. The only difference between this transformation and that shown in Fig. 3.2-12 is that gate g now fans out to £ newly added gates g , g , p q-L q 2 ..., g where I is the smallest integer such that £ x FO >^ h. Output connec- q SL tions from each of g , g , ..., g will be fed to FO of the g.'s (i.e. q l q 2 q £ - 1 J g will feed g , g , ..., g ;g will feed g. , g. , ..., q l J l J 2 J F0 q 2 J F0 + 1 J F0 + 2 g. ; etc.). Gate g will fan-out to the h - (Jl - 1) FO gates: J 2F0 q £ g. , ..., g. . The h output connections from each of gates J (£ - 1) FO + 1 J h g,. > 8,. » •••» g. to gates g. , g. , . . . , g are removed. 1 2 \ 2 1 2 2 J k After T6 is applied at least one of the gates in Fig. 3.2-11 has its fan-in or fan-out problem completely solved while the fan-in and fan-out pro- blems of the rest of the gates may only be partially solved. The transformation methods were implemented as a transformation pro- gram by J. G. Legge. Many problems were run to test the effectiveness of these transformations. Table 3.2-1 gives the average percentage of the number 73 lg. 3.2-12 Subnetwork structure (Fig. 3,2-11) after the application of T6 when h < FO. After the transformation: |lS(g! )| = |is( g )| + i - h , |is( g - )| = |is( g . )| + i - h , ] 1 .. , |lS(g« )| .= |lS(g )| + 1 - h. |LP(g')| = |lP(g.)| + 1 - k k J J K l Ip (g'- 2 )l = l ip (gj 2 )l +i-k, ... , |ip( g . )| = |iP(g. )| + l - k. J h of times a certain transformation was applicable during a complete run of test networks for 30 4-variable functions and 30 5-variable functions for a given set of fan- in/ fan-out restrictions. (For given networks, some trans- formations cannot be applied because the corresponding conditions are not met.) This table shows that T5 was applicable in a greater percentage of cases (39%) than any other transformation (this means that on the average 39% of fan-in, fan-out problems occurred in a complete run are suitable for T5 to solve) , and Tl and T4 were not applicable very often (this is because that the special conditions which must be satisfied were not often satisfied) More details can be found in [24]. 74 °(^-l)FO + 1 Fig. 3.2-13 Subnetwork structure (Fig. 2.3.1.1) after the application of T6 when FO < h <_ (FO) 2 . After the transformation: |lS(g' )| = |lS(g, )| + 1 - h, |lS(g! )| = |lS(g )| + ll ll 12 12 1 - h, ... , |lS(g' )| = |lS(g )| + 1 - h. |lP(g' )| = k k J1 |ip(g )| + l - k, |iP(g' )| = |ip(g )| + l - k, ... , Jl 32 J2 |lP(g' )| - |lP(g, )| + 1 - k. 75 Table 3.2-1 The percentage of the number of times a transformation was applied during a com- plete test run. Transformation Tl T2 T3 T4 T5 T6 percentage 0.7 12.1 19.6 3.0 39.0 25.6 3. 3 Transduction Procedures In this section we provide a summary of all transduction procedures The details about the transduction procedures can be found in the references given in the following subsections. 3.3.1 Basic definitions and ideas Let X = {x 1 ,x 2 ,. . . ,x n >, Z = {z 1 ,z 2 ,...,z m >, V J = {v^v^ . . . ,v }, v g = { Vi'V2 Vr 1 and v o = { Vr+i'Vr+2'-'Vr^ } be the set of n external variables, the set of m output functions, the set of p input terminals, the set of R NOR gates, and the set of m output terminals, re- spectively. For simplicity we can assume only uncomplemented external vari- ables (x.'s) are available as input variagles, i.e., p = n. Let C={c ] be the set of connections, where c.. denotes a connection fed from ij v. e V T v V_ v. V to v. £ V vV . Let V = V T ^ V_ v V_. If there exists a 1 x t» o OG x u u sequence of gates v, .. , v, 9 , ..., v, between v. and v. with a non-negative KX ICZ K.t X * integer t such that v, , e IS(v.) , v. e IS(v, ., ) for q = 2, 3, ..., t and kl x kq k,q-l v. z IS(v. ), then v. is a predecessor of v. and v. is a successor of v.. 3 kt i J J i Let P(v.) and S(v.) denote the set of all predecessors of v. and the set of x l' 1 all successors of v., respectively. A function f. (completely specified or incompletely specified), The definition of immediate successors and immediate predecessors are given in the previous section. 76 realized at an input terminal, the output of a gate, or a connection (more precisely speaking, the function realized at the input of a next gate to which the connection feeds) , is represented by a 2 dimensional vector m (1) (2) f (2 n ) where fp) =1 if ^(x^ x 2 > •••* x n ) = 1 > i .(J) if ^(x-l, Xg, ..., x n ) = 0, I'' = * if f^xp x 2 , ..., x n ) =d^ t ) Ji-1 ,n-2 for j - 1 = 2 x x + 2 " x 2 + ... + x External variables are represented as follows = (0, 0, , 0, 1, 1, > i)» 7 V. x^ = Vi = (0 ' °' 1, 1 ' "*' *"' °' °' 1} 1)} x = (0, 1, 0, 1, ..., ..-, 0, 1* °; !)' Definition 3.3.1-1 - If no specified components of the network out- put functions change by replacing the function realized at input terminal v , gate v. or connection c.., by a function f, then function f is called a per- J ij missible function for input terminal v., gate v. or connection c.., respec- tively. 77 This is illustrated in Fig. 3.3.1-1. Suppose we want to find a permissible function for the function realized at the right end of connec- tion c. in the network in (a). When we replace the function realized at c by a function f of variables x , x_, ..., x as shown in (b) , f is a permissible function for c.. if specified components of z,, .... z in (b) ij 1 m are not different from those in (a) . Usually there is more than one per- missible function for c... Notice that permissible functions for a connection c. are separately defined from those for a gate v. with the same i. Therefore, when gate v. has more than one fan-out connection, there may be generally some permissible functions of v. which are not permissible functions of c..: and there may be 1 *J generally some permissible functions of c . . which are not permissible func- tions of v. . l Definition 3.3.1-2 - The set of all permissible functions for any input terminal, gate or connection can be consequently expressed by a single vector [17]. This set is called the maximum set of permissible functions , abbreviated as MSPF. Let G.,(v..) and G w (c.) denote maximum sets of permis- M i M ij sible functions for v. and c.., respectively. Let G(v.) and G(c.) denote i ij i ij arbitrary subsets of G w (v.) and G w (c..), respectively. Mi M ij Definition 3.3.1-3 - A gate or a connection is said to be S-redundant (implying single-redundant) if no specified components of the network outputs change by removing the gate or the connection. In some networks, no speci- fied components of the network outputs change if two or more gates and/or connections are removed while the outputs change if a single or a connection is removed. In contrast to "S-redundant," it is called M-redundant (implying multiple-redundant). A network without any S-redundant gates or connections is called S-irredundant. 78 V i V " V 1 • • A.. 1_^ • n m (a) in (b) Fig. 3. 3. 1-1 Permissible function gor connection c^ 79 There is a procedure (Procedure MSPF) which can calculate MSPF for a given network, and there is another procedure (Procedure SINM) which can obtain S-irredundant networks based on the MSPF's [17]. But the calculation of the MSPF's is time-consuming and in Procedure SINM each time an S-redundant connection is removed, the recalculation of MSPFs for the entire new network is required. Thus the concept of a compatible set of permissible functions is introduced to develop more practical procedures. Definition 3.3.1-4 - A tied subnetwork of a given network is defined as part of the given network satisfying the following conditions, where U is the set of input terminals, gates, connections and output terminals, contained in this subnetwork. (1) If v. e U, then S(v.) c U, (2) If c. . e U, then v. £ U and S(v.) cr U, (3) If v. e U, v. e U and v. e IS(v.), then c. e U. i J J i iJ Definition 3.3.1-5 - Let U be the set in input terminals, gates, connections and output terminals in a tied subnetwork N of a given network. All the sets of permissible functions, G(v.) and G(c.) (v. e U, c . . e U) , i ij i ij are said to be compatible with respect to this tied subnetwork if the follow- ing property holds with every subset W of U. (1) Replace the function at each element w in W by a function in G(w). (2) In the resultant new network each element u in U, which is not contained in W, realizes some function contained in G(u). (3) The above condition (2) holds, no matter which function G(w) is chosen for each w in condition (1) (i.e., condition (2) holds for every different choice of functions in G(w)'s for all the w's of W) . 80 As a special case, a tied subnetwork can be a given network itself. In this case if sets of permissible functions satisfy the above conditions, they are simply called compatible sets of permissible functions (CSPF's) . CSPF for an element u (e V U C) is denoted by G (u) . 3.3.2 Pruning Procedures For any given network, by comparing the outputs of the original net- work with the outputs of the network without a particular connection we can determine whether or not this connection is reduncant. This idea is simple but a computer program implementing this idea is too time-consuming to exe- cute. So in the pruning procedures, we calculate the permissible functions of a selected gate or the input connections of a selected gate to decide which input connections of the selected gate can be removed. Three differ- ent ways are used to prune redundant connections: (I) Pruning procedure based on CSPF's i For any given network this procedure calculates a set of CSPF's. Since the set of CSPF's is not unique for a non-trivial given network, it is desirable to choose a set of CSPF's such that as many CSPF's as possible consist of only Os and *s. Those connections c. with G (c . . ) consisting iJ c ij. of only Os and *s are redundant and hence can be removed. The detailed steps for pruning redundant connections are given in [2]. It is observed that the pruning procedure based on CSPF's takes very short computation time. Since only a sufficient condition for a 81 redundancy of a connection is used, a redundant connection sometimes cannot be detected by this procedure. (II) Pruning procedure based on O-fixed maximum set of permissible functions A O-fixed maximum set of permissible functions (OFMSPF) G_„(c..) OM ij for a connection c. . is defined as a subset of MSPF GM(c.) satisfying the following condition: for f (d) (v.) = G (d) ,(c..) = holds, l OM ij I and for f (d) (v.) = 1 , 6 ( ^(c ) - G^ d) (c ±j ) holds. In other words, the components of the OFMSF of a connection c.. are found first for the components of f(v.) which are fixed to and then found for other components of f(v.) by calculating the MSPF for c... It is proved that a connection c. is S-redundant if and only if the OFMSPF G (c..) consists of Os and *s [2]. The pruning procedure based on OFMSPF selects one connection c.. at a time according to a particular ordering and checks whether G..__(c..) contains only Os and *s. If this is true, then re- OM lj J move c . . and go to find another c..; otherwise go to find another c... These steps will be applied until no further pruning is possible. (III) Pruning procedure based on 1-fixed maximum set of permissible functions A 1-fixed maximum set of permissible functions (1FMSPF) G (v.) for for gate v. is defined to be a subset of G (v.) satisfying the following condi- tion: for f (d) (v.) = , G{ d) (v.) = G^ d) (v.) holds, and for f (d) (v.) = 1 , G^Cv.) = 1 holds, l 1M l In other words, the components of the 1FMSPF of a gate v. are found first for the components of f(v.) which are fixed to 1 and then found for other :omponents of f(v.) by calculating the MSPF for v.. 82 It is proved that a connection c.. is S-redundant if and only if for every d such that G (v.) = 0, s/ f (v ) = 1 holds [2]. The prun- J v,eIP(v.) k k J ing procedure based on 1FMSPF selects one gate v. e V at a time according to a particular ordering and checks whether for every d such that G (v.) = 0, ^ f (v ) = 1. If this is true, then remove c and go back to find v, eIP(v.) • *J k _i J v. fv . k i another v.; otherwise go back to find another v.. These steps will be repeated until no further pruning is possible. The pruning procedures aim at removing redundant connections only; but sometimes because of the removal of redundant connections, some gates also be- come redundant and hence can be removed. The pruning procedures (I) , (II) and (III) were implemented in the transduction programs NETTRA-PG1 , NETTRA-P1 and NETTRA-P2, respectively. Usu- ally, procedures (II) and (III) take longer computation time than procedure (I), but after applying either procedure (II) or procedure (III) , an S-irredundant network is always obtained. 3.3.3 Procedures based on gate merging Two gates v. and v. are said to be mergeable if the following condition are satisfied: * NETTRA-PG1 also realizes the simple substituting procedure, and this will be explained later. 83 (1) v. t S(v.) and v. t S(v.) (This guarantees that the resultant J i i 3 network is loop-free. ) (2) Each output terminal v ,_, . realizes a different function in n+R+i set z. for i = 1,2, . . . , m, after the following network recon- figurations: (2-1) Add connections from all gates and input terminals in IP (v.) - IP (v.) to gate v.. J i i (2-2) Add connections from all gates and input terminals in IP (v.) - IP (v.) to gate v.. 1 3 3 If two gates v i and v. are mergeable, then we can replace these two gates by gate v.. satisfying IP(v ) = IP(V.) sy IP(v.), IS(v..) - IS(v.) s/ IS(v.). Gate v.. is called the merged gate . A simple example is shown below: Example 3.3.3-1 - The network given in Fig. 3. 3. 3-1 (a) realizes func- tion f = x_ x„ \s x. x_. We can add redundant inputs x~ and x, to gates v, and 1 i. 1 Z Z 1 D v , respectively without changing the output of v„. By adding these redundant inputs we find that v and v are mergeable. The network obtained by merging gates v and v, is shown in Fig. 3. 3. 3-1 (b). Gate v, -, is the merged gate, b / o , / It is proved that gate v. and v. are mergeable if the following condi- tions are satisfied [22]: (1) v. i S (v.) and v t S(v.) 3 i i i (2) G (v.) fl G (v.) 4 $ C 1 C J (3) f(v.) • f(v.) e G (v.) fl G (v.), l 3 ex c j where symbol • denotes the logical AND operation for each component of f(v.) and f (v . ) . J 84 E> ~~j^Ty-o f -EXtt^^ (a) A given network *1 *2 '6,7 =^> zzE> — ° f (b) Simplified network Fig. 3.3.3-1 A simple example for gate merging The following definitions and theorems are needed for further de- scriptions : Definition 3.3.3-1 - A gate or an input terminal, v., is said to be connectable to a gate v. with respect to a set of permissible functions of J v., G(v.), if (1) the output function of v. remains in G(v.) after adding con- J J J J nection c.., and (2) the network obtained after this input addition is loop- ij free. Definition 3.3.3-2 - Connection c. is said to be disconnectable from ij a gate v. with respect to a set of permissible functions of v., G(v.) if the J 3 J output function of v. remains in G(v.) after removing c. from the network. 85 Definition 3.3.3-3 - The set of connectable functions to gate v. with respect to G(v.), K(v.), is the set of all functions such that the addition of any subset of these functions to v. as its inputs keeps the function realized at v. remain in G(v.). J J Theorem 3.3.3-1 - A gate or an input terminal, v., is connectable to v. with respect to set G(v.) if and only if the following conditions are sat- isfied: (1) For all d such that f (d) (v.) = 1, G (d) ( v .) = or *. c J where f (v.) is the d-th component of the output vector of gate v. . (2) v. is not contained in S(v.) where S(v.) denotes the set of successor gates of gate v. . 3 Theorem 3.3.3-2 - Connection C is disconnectable from gate v. with ij J respect to set G(v.) if and only if the following condition is satisfied: For all d such that f (v.) = 1, either G (d) (v.)=*or V f (d) (v) - 1 veIP(v.) v^v. l where v denotes logical OR operation and IP(v.) denotes the set of all immedi- ate predessor gates of gate v.. Theorem 3.3.3-3 - The set K(v.) of all connectable functions to a gate v. with respect to G(v.) is given by J J K (d) (v.) = for all d such that G (d) (v.) =1, and K (d) (v.) = * for all other d's. 3 86 Now we are ready to review the procedures based on gate merging. Procedure GMGC . Step 1 Find two gates v. and v. such that c — i J G (v.) n G (v.) = G (v..) / 0. C 1 C J C IJ Step 2 Consider an imaginary gate v.. whose CSPF is G (v..). Calcu- c — ij c 1J late the set K(v..) of all connectable functions to v... Step 3 Select the set U of gates and input terminals, v, satisfying the following conditions: (a) For all v e U, f(v) e K(v..). ij (b) For all v e U, v i S(v.) U S(v.) (loop-free condition) . Step 4 Connect all gates and input terminals in U to gate v . If ij the output function is contained in G (v..), then go to Step 5: otherwise v c ij i and v. cannot be replaced bv gate v J ' 6 ij Step 5 As V f(v) e G (v..) veil c « holds, using the disconnectable condition select a new input set U' (which is a subset of U) such that V f(v) e G (v..). veil' C 1J Step 6 Replace v. and v. by gate v.. which has input connections i j ij from all the gates and input terminals in U'. More general procedures are discussed in detail in [22]. The trans- duction procedures based on gate merging are implemented in the transduction program NETTRA-G3. 87 3.3.4 Procedures based on gate substitution For any given network if the disjunction of the outputs of some gates and external variables is found to be identical to the output of a gate v., then we can substitute the disjunction of -these outputs of gates and/or external variables for the output connections of gate v.. A simple example is shown in Fig. 3.3.4-1. Assume the disjunction of outputs of v.,, v -r . and external vari- able x is identical to the output of v., i.e., Then, the connections from v. to v,_ and v, _ can be replaced by the connections from v , v._ and x to v and v _ as shown in Fig. 3. 3. 4-1 (b). The following is a procedure for the substitution of a gate. Procedure SGC . Substitution of a gate using CSPF's. Step 1 Calculate CSPF's for all gates in a given network. Step 2 Select one gate v.. (2-1) Calculate a set H(v.) which is defined by l H(v ) = n K(v), veIS(v.) where K(v) is the set of connectable functions to gate v with respect to the CSPF for v (i.e., G (v)). (2-2) Let U be a set of all gates and input terminals satisfying v i S (v . ) , and f(v) e H(v.) for every v e U. (2-3) If V f(v) e G (v.), then go to Step 3; other- veU ° X wise repeat Step 2 until all gates are considered. Step 3 Substitute connections from gates and input terminals in U for the output connections of gate v.. 88 (a) Original network (b) After gate substitution Fig. 3. 3.4-1 Simple example for gate substitution 89 Instead of substituting outputs of gates and input terminals for gate v , we can generalize the procedure by substituting outputs of gates and input terminals for each output of gate v. (possibly a different set of outputs of gates and input terminals for each output of v.). A simple example is shown in Fig. 3.3.4-2. Gate v „ of the network shown in Fig. 3.3.4-2(a) has three outputs connecting to v., v., and v . These connections, however, can be re- o / o placed by connections from v , v and v , respectively. So we can remove gate v _ (see Figure 3.2(b)). The following procedure is a generalization of Procedure SGC. Procedure SOGC . Substitution of outputs of a gate using CSPF's. Step 1 Select one gate v.. Step 2 Calculate CSPF's for all gates, input terminals and output connections of v. according to some proper order. Step 3 For each output connection c.. of v., calculate a set U of gates and input terminals. U = {v|v e V p U V_, v i S(v.), f(v) E K(v.)}. J Step 4 If the following condition is satisfied then substitute con- nections from all elements in U to v for c : J ij V f(v) e G (c..). veU C ^ Disconnect some of these new connections by applying disconnectable conditions to gate v. . J Step 5 Repeat Step 3 and Step 4 for all output connections of gate v.. If there exists an output connection which cannot be substituted, then v. i i cannot be removed. If so, repeat the procedure on the original network by selecting another gate. 90 (a) A given network (b) After the substitution for each of the output connections of v 12 Fig. 3.3.4-2 A simple example for generalized gate substitution 91 The transduction procedures based on the substitution are implemented in the transduction program NETTRA-G4. 3.3.5 Procedures based on connectable and disconnectable functions The definitions of connectable and disconnectable functions are in- troduced in section 3.3.3. The following is proved in [14]: I. A gate or an input terminal, v., is connectable to a gate, v., with respect to set G(v ) if and only if the following condi- 3 tions are satisfied: (1) For all d such that f (d) (v.) = 1, l G (d) ( v .) = or * . 3 where f (v.) is the d-th component of the output vector of gate v.. (2) v. is not contained in S(v.) where S(v.) denotes the i J 3 set of successor gates of gate v. . II. A connection c. is disconnectable from gate v. with re- spect to set G(v.) if and only if the following condition is satisfied: For all d such that f (v.) = 1, either G (d) (v ) = * or 3 V f d (v) = 1 veIP(v.) v^v. J l The transduction procedures based on connectable and disconnectable functions intend to replace the input functions of gates and to remove discon- nectable inputs from gates. Some gates may become redundant after the removal of disconnectable inputs. An example is shown in Fig. 3.3.5-1, where the net- work realizes function f = x.x„x. v x_,x_x. v x^.x. v x.x.x, v x,x_x. vx,x„x„. 234 124 123 124 134 123 After calculating the CSPFs of the network shown in Fig. 3. 3. 5-1 (a), it is found 92 that x is connectable to gate 3 and gate 4 is cormectable gate 5. After adding these connections, the connection between gate 8 and gate 5 is found to be disconnectable. The simplified network is shown in Fig. 3.3.5-l(b). A procedure based on connectable and disconnectable functions is outlined below. The detailed descriptions are presented in [14]. Procedure based on connectable and disconnectable function s Step 1 : Select gate v. according to some order. If all gates have been considered, then stop. Step 2: Calculate the CSPF for v.. c — J Step 3: Calculate a set K(v.) of connectable functions with re- — J spect to G (v. ) . Step 4 : Select external variables contained in K(v.) and select gates (not in S(v.)) which realize functions in K(v.). Let Q be a set of these external variables and gates. Step 5 : Select a subset of Q of Q such that every element in set Q is essential for replacing the input connections of v. . An external vari- able or a gate v. in Q„ is an essential input of v. w.r.t G (v.) if and only 10 3 c j if there exists at least one d such that: G (d) (v.) = 0, f (d) (v.) = 1, and V f (d) (v) = 3 X veQ (v.) v^v. Step 6 : Select a subset of 0' of Q such that Q' cQ cQ and A f(v) e G (v.) veQ' c J Step 7 : Remove all connections which are inputs of v. and connect all elements in Q' to gate v. as inputs. 93 X 4 x 3 X 4 8 =£> (a) Network before transduction x- x 3 ^4 / 8 NEW CONNECTION REMOVED CONNECTION (b) Network after transduction (J 3»5-l An example for procedures based on connectable and disconnectable functions 94 Step 8 : Calculate theCSPF'sfor the modified network and remove all disconnectable connections. Remove gates which become redundant after the disconnectable connections are removed. Step 9 ; If the current network has a lower cost than the original network, then go to step 1. Otherwise, select another Q' and go to step 6. The transduction procedures based on connectable and disconnectable functions are implemented in the transduction programs NETTRA-G1 and NETTRA- G2. The primary difference between NETTRA-G1 and NETTRA-G2 is that NETTRA-G2 concentrates on removing specific gates from the network under consideration while NETTRA-G1 does not attempt to remove specific gates [1]. 3.3.6 Procedures based on error-compensation The basic idea in the transduction procedures based on error-com- pensation is simple. For any given network, a gate is selected according to an appropriate order. Assuming that this gate is removed, check the outputs of the network. If the outputs do not change, then the selected gate is re- dundant and can be actually removed. If the outputs do change, then try to compensate for these changes (errors) by reconfiguring the network. The selected gate becomes redundant if these changes can be compensated. The following definitions are introduced to facilitate the later descriptions. Definition 3.3.6-1 - A component of G (v.) for a gate v. is called a c 1 1 0-error (or CO if it is originally a 1 and it changes to because of the re- moval of other gates or connections in the network. Definition 3.3.6- 2 - A component of G (v.) for a gate v. is called a 1-error (or 1) if it is originally a and it changes to 1 because of the re- moval of other gates or connections in the network. 95 Definition 3.3.6-3 - A 0-component (or O-error-component) of the out- put of gate v. is covered by the input connection c.. if the corresponding component of c, is a 1. Definition 3.3.6-4 - The compatible set of permissible functions (CSPF) of a gate, an external variable or a connection is called a compatible set of permissible functions with errors (denoted by CSPFE) if it has some 1- error or 0-error components due to the removal of other gates and/or connec- tions. Definition 3.3.6-5 - A O-error-component in the CSPFE of a gate v. is called a primary O-error-component if it is covered by only one input connec- tion of this gate. A primary 0-error component is considered easier to be com- pensated. In order to compensate for error-components in the CSPFE of a gate, functions currently realized at other gates and external variables may be used. But in order to make the error-compensation more flexible, the concepts of potential outputs and potential output table (POT) were introduced in [15], and a procedure utilizing a potential output table was also given. A poten- tial output from a gate I is a function realized at I by connecting additional inputs to I. This potential output of I usually differs from the function currently realized at I, and therefore can be used to compensate for errors in a certain gate to which the current output function at I is not connectable. The principle used in generating potential output is called the triangular condition. In a loop-free NOR(NAND) network, suppose three gates are con- nected to each other to form a triangle. Then the connection from the highest level gate to the second highest level gate is redundant for realizing the output of the lowest level gate if the second highest level gates has no out- put connection other than the one to the lowest level gate. In Fig. 3. 3. 6-1 (a), 96 the dash-lined connection is redundant. Conversely, if two gates are both im- mediate predecessors of another gate, adding a connection between the first two will not affect the output of the other gate if the gate to which the new con- nection feeds has no output connection other than the one to the third gate. In Fig. 3.3.6-l(b), gate I and gate J are immediate predecessors of gate K. The connection of gate I to gate J will not change the output of gate K. But the output of gate J after making the bold-line connection may be different (a) The dashed connection is redundant (b) The bold-line connection can be made without changing the output of gate K Fig. 3.3.6-1 Triangular condition 97 from that before making the connection. In a similar manner, if three gates are all immediate predecessors of another gate, then adding one or two con- nections from some gates to the third gate will not affect the output of the lowest level gate. In Fig. 3.3.6-2, the networks in (a), (b), (c) and (d) realize the same function, but the outputs of gate K are not necessarily the same. Therefore, these different outputs of gate K can be used to compen- sate for error-components for other gates. The procedures based on error-compensation can be briefly explained by the following four steps: Step 1 : Select a gate in the given network according to an appropri- ate order . If all gates have been considered, then stop. Step 2 : Assume the selected gate is removed. Check whether the outputs of the network change or not. If the outputs do not change, then actually remove this gate and go to step 1. Otherwise go to next step. Step 3 : Construct the potential output table and go to step 4. Step 4 : Starting from the output gates, try to find some potential output functions which can compensate for the error-components found in step 2. If the errors can be compensated, then remove the selected gate and go to step 1. Otherwise, propagate the errors to the next higher level and repeat this step. If the errors have already been propagated to the highest level and still cannot be compensated, then go to step 1. Step 4 is much more complicated than steps 1, 2 and 3. In step 4 six subprocedures are used to compensate for errors: (1) Remove redundant connections. (2) Substitution for input connections from external variables with error-components. * Usually according to the number of O-components a gate has. 98 L rJT>J (a) the original network (b) Connecting I to K (c) Connecting J to K (d) Connecting I and J to K Fig. 3.3.6-2 A more general example of triangular condition 99 (3) Substitution for input connections from gates with primary errors. (4) Substitution for input connections by functions without error- components. (5) Adding connections to compensate for 1-error components. (6) Adding redundant connections from external variables. Subprocedure (1) through subprocedure (4) aim at compensating for 0- error components while subprocedure (5) aims at compensating for 1-error com- ponents. Subprocedure (6) only loosens the requirements of the predecessors of some gate to make error-compensation at later steps easier. The procedures based on error-compensation are much more complicated than any other transduction procedures. The details can be found in [15], [21], The procedures based on error-compensation are inplemented in the transduction programs NETTRA-E1, NETTRA-E2 and NETTRA-E3. The essential dif- ference among NETTRA-E1, -E2 and -E3 is that the central subroutines which realize the procedures based on error-compensation are called in different ways in NETTRA-E1, -E2 and -E3 [21]. 3.3.7 Considerations of fan-in/fan-out restrictions and level restriction In the previous sections, we do not consider the fan- in/ fan-out re- strictions and the level restriction in the transduction procedures. Since all IC logic families do have limits on the maximum number of fan-in and/or fan-out that a logic gate may have, the design of logic networks under the fan-in/fan- out restrictions is important. Besides, often we desire to design a "fast network", i.e., a network with short time delay between the inputs and the outputs, so the consideration of the maximum number of levels (which is pro- portional to the time delay) in a network as a restriction is required. 100 It was mentioned previously that the pruning procedures aim at remov- ing redundant connections only. For any given network which is already fan-in/ fan-out restricted and/or level-restricted, there will be no fan-in/ fan-out problem or level problem to be generaged by applying the pruning procedures. But this is not true if the transduction procedures other than the pruning procedures are applied. All transduction procedures, except the pruning pro- cedures and the procedure based on generalized gate substitution , are modi- fied to take into consideration the fan-in/fan-out restrictions and the level restriction. We will discuss the modifications briefly, assuming that the given network is already fan- in/fan-out restricted and level restricted. The following three cases will be discussed separately both for the fan-in/ fan-out restrictions and for the level restriction, since all trans- duction procedures consist of one or more of these operations: (a) Adding a connection from an external variable or a gate v. to another gate v.. (b) Merging two gates v. and v. into a one gate v.. by connecting a set of external variables and gates as input connections to gate v. . . (c) Substituting the current input connections or a subset of the current input connections of a gate by another set of external variables and the outputs of gates. I Consideration of fan-in/fan-out restrictions In case (a) the following conditions must be satisfied before adding the connection in order not to violate the fan-in/fan-out restrictions: The reason that this procedure is not modified is given in Chapter 5, 101 |IS(V.) I < FOX or FO and |lP(v.)| < FI, where |lS(v.) and IP (v.) are the current number of fan-out and fan-in of i ' j ' the external variable or gate v. and the gate v., respectively. If neither of the above two conditions is satisfied, then the new connection cannot be made even if all other conditions except the above two are satisfied. In case (b) each external variable or gate v which is going to be connected to gate v. . as an input must satisfy |lS(v)| < FOX if v is an external variable or I IS (v) I < FO (or F00) if v is a gate (or an output gate) in order not to violate the fan-out restrictions. The total number of the above v's must be less than or equal to FI in order not to violate the fan-in restric- tion. If we cannot find a set of v's such that the complement of the disjunc- tion of f(v)'s belongs to G (v..) and the total number of v's is equal to or less than FI (described in section 3.3.3), then we cannot merge gates v. and v. . 3 Since gate v.. must be connected to all immediate successors of gate v. and gate v., we have to check whether |lS(v.) U IS(v.)| <_ FO or not in order not to violate the fan-out restriction. If this condition is not satis- fied then we cannot merge gates v. and v.. In case (c) let us call the substituting set to be S' and the sub- stituted set to be S. Also let the gate under consideration be v.. Each external variable or gate v in the substituting set S' must satisfy the fol- lowing conditions in order not to violate the fan-out restrictions: 102 |lS(v)| < FOX if v is an external variable or | IS (v) | < FO (or F00) if v is a gate (or an output gate). Besides, the following condition must be satisfied in order not to violate the fan-in restriction at gate v.: I IP (v.) I - Is I + Is' I < FI i x i ii i i _ The left hand side of the above inequality is the number of fan-in of gate v. if the substitution is made. If the above inequality is not satisfied then we cannot make the substitution even if all other conditions are satisfied. II Consideration of level restriction A Let the gate level of the output gate be 1 , the gate level of the gate v be GLEVEL(v), and the maximum number of levels that the network may have be LEVLIM. In case (a) if v. is an external variable, then there will be no 1 level problem caused by connecting v. to v. as an input of v.. If v. is a i J J i gate and GLEVEL(v ) > GLEVEL(v.), then there will still be no level problem. But if v. is a gate and GLEVEL(v.) <_ GLEVEL(v.), then the following conditions must be satisfied in order not to violate the level restriction: GLEVEL(v.) + DIST £ LEVLIM, where DIST is the largest difference of gate levels between gate v. and all predecessors of gate v.. If the above condition is not satisfied, then the connection cannot be made. * We may not be able to do so for every output gate in the multiple-output case since in this case the output of some output gate can also feed other gates. 103 In case (b), for every external variable v which is to be connected to gate v.. as an input of v. . , there will be no level problem. But the fol- ij ij lowing conditions must be satisfied for a gate v which is going to be con- nected to gate v , in order not to violate the level restriction: ij DIST + 1 + max (GLEVEL(v . ) , GLEVEL(v.)) <_ LEVLIM, where DIST is the largest difference between gate v and all predecessors of gate v. Gates v. and v. cannot be merged if we cannot find a set S such that the conditions described in section 3.3.3 are satisfied and the above condition is satisfied by each gate in S. In case (c) each gate in the substituting set must satisfy the same condition as case (a) . The modifications for fan-in/fan-out restrictions and level restric- tion are implemented in the transduction subroutines based on gate merging, gate substitution, connectable and disconnectable functions and error-compensa- tion. Detailed explanations about the level restriction and the fan-in/fan- out restrictions are given in [12] and [9], [11], [38] , respectively. 3.3.8 Assembly of the transduction programs for the NETTRA system The transduction programs consist of five types of subroutines: the MAIN control subroutine, the I/O supporting subroutines, the subroutines for * In [9], [11] and [38], the transduction programs modified for fan-in/ fan-out restrictions are renamed as NETTRA-G1-FI-F0 , -G2-FIF0, -G3-FIF0, -G4-FIF0, -El-FIFO and -E2-FIF0. 104 finding initial networks, the subroutines for doing fan-in/fan-out restricted transformations and the subroutines for realizing the transduction procedures. In order to implement the NETTRA system, a new MAIN control subroutine and several new I/O supporting subroutines (the functions of these subroutines will be described in Chapter A) are written to organize the subroutines for finding initial networks, for doing the transformations and for realizing the transduction procedures (except for NETTRA-E3) together. Each type of transduction procedures (e.g., the transduction pro- cedures based on gate merging and gate substitution constitute two differ- ent types.) are usually realized by more than one subroutine. Table 3.3.8-1 gives the names of the central transduction subroutines in the transduction programs implemented in the past for realizing the corresponding transduc- tion procedures. For example, the central transduction subroutine in the transduction program NETTRA-G1 (the 5th row in Table 3.3.8-1) is named PRIIFF. It realizes the transduction procedures based on connectable and dis- connectable functions. The pruning procedures based on CSPF's are realized by the central subroutine PROCIP in the transduction program NETTRA-PG1. This type of prun- ing procedure has been found very efficient in removing redundant connections. Therefore they are included in many other transduction programs to remove re- dundant connections in a given network before applying more complex transduc- tions. This is the reason why pruning appears in the transduction programs NETTRA-G1, -G2, -G3, -G4, -El, -E2, and -E3 in Table 3.3.8-1. Notice that the subroutines for implementing the transduction program NETTRA-E3 are not included in the NETTRA system. The transduction program NETTRA-E3 is a "multi-path" application of the error-compensation procedures 105 fable 3.3.8-1 The central transduction subroutines of the transduction pro- grams implemented in the past for realizing the corresponding transduction procedures. Transduction Program NETTRA- PG1 PI P2 Central Transduction Subroutine Gl G2 G3 G4 El E2 E3 PROCIP RDTCNT PROCI PRIIFF PROCIV GTMERG PROCV PROCCE PROCCE PROCCE Transduction Procedures Realized By The Central Subroutine Pruning and gate substitution Pruning Pruning Connectable and disconnectable functions and Pruning gate merging and pruning gate substitution and pruning error compensation and pruning A simple type of substitution procedures is also realized by this subroutine, 106 (see [2|] for details). It needs 43K more core storage than the transduc- tion program NETTRA-E2 and it usually takes much more time than NETTRA-E2. Although the transduction programs (except NETTRA-E3) are all in- cluded and their names are not referred to separately in the NETTRA system, their symbolic representations (e.g. NETTRA-PG1, NETTRA-P1, etc.) are con- venient for referring to or for classifying the transduction procedures they realize. Some mnemonic names for the transduction procedures are designated based on the original symbolic names of the transduction programs for the above purpose in setting up input data. This will be explained in more detail in [13]. 107 4. Detailed Organization of the NETTRA System In this chapter we will first introduce the functions of some impor- tant subroutines. Then we will provide the detailed organization of the control subroutine MAIN. Since the total program size of the NETTRA system is greater than the maximum main storage available for the IBM 360/75J, the overlay structure is used in programming the NETTRA system. We will also explain what the overlay structure is and how we programmed the NETTRA system using the IBM 360/75J computer's overlay structure facility. 4.1 Functions of Important Subroutines In Fig. 2.1 we give the general flowchart for the NETTRA system. All subroutines included in the system are classified into the following five groups: (1) Subroutine MAIN (will be introduced in section 4.2). (2) Subroutines for realizing the initial network methods. (3) Subroutines for realizing the fan- in/fan-out transformation. (4) Subroutines for realizing the transduction procedures. (5) I/O supporting subroutines. The fan- in/fan-out transformations, some of the initial network methods and some of the transduction procedures are realized by more than one subrou- tine. Only the central subroutines that realize the initial network methods, the fan- in/fan-out transformations and the transduction procedures are de- scribed below: Subroutines for realizing the initial network methods 108 BANDB : This is the central subroutine for realizing the initial network method based on the branch-and-bound algorithm (see section 3.1.3). TANT : This is the central subroutine for realizing the initial network method based on Gimpel's algorithm (see section 3.1.5). TISON ; This is the central subroutine for realizing the initial network methods based on Tison's algorithm. The minimum sum is first found by this subroutine, and then the corresponding two-level or three-level net- work is constructed (see section 3.1. A). TISLEV : This subroutine realizes the level-restricted initial network method by expanding the network obtained by Tison's method (see section 3.1.6). It will be applied only when both the fan- in/fan-out restrictions and level restriction exist. THRLEV : This subroutine realizes the three-level network method for finding the initial networks (see section 3.1.2). UNIVSA : This subroutine realizes the universal NOR network method for finding the initial networks (see section 3.1.1). EXNT: This subroutine can "input" an initial network which may be obtained by any other than the above six methods. Subroutine for realizing the fan- in/fan-out restricted transformations JEFF : This is the central subroutine for realizing the fan-in/fan-out re- stricted network transformations (see section 3.2). Subroutines for realizing the transduction procedures * MINI2 : This subroutine calculates the CSPF's of a given network and removes redundant connections, i.e., it realizes the pruning procedure based on CSPF's (see section 3.3.2). This is one of the two central subroutines for subroutine PROCIP which is mentioned in Chapter 3. 109 SUBSTI : This subroutine realizes the transduction procedure based on simple substruction (see section 3.3.4). RDTCNT : This subroutine realizes the pruning procedure based on OFMSPE (see section 3.3.2). PROCI : This subroutine realizes the pruning procedure based on 1FMSPF (see section 3.3.2). GTMERG ; This subroutine realizes the transduction procedure based on gate merging (see section 3.3.3). PROCV : This is the central subroutine for realizing the transduction pro- cedures based on generalized gate substitution (see section 3.3.4). PRIIFF : This is the central subroutine for realizing the transduction pro- cedures based on connectable and disconnectable functions. This sub- routine does not try to remove specific gates (see section 3.3.5 or see [1] for details). PROCIV : This is the central subroutine for realizing the transduction pro- cedures based on connectable and disconnectable functions. But this subroutine concentrates on removing specific gates (see section 3.3.5 or see [1] for details). PROCCE : This is the central subroutine for realizing the transduction pro- cedures based on error-compensation (see section 3.3.6). I/O Supporting subroutines INPUT: This subroutine reads the control sequence cards. The information specified on the control sequence cards decides the types of the initial network subroutines and the transduction subroutines to be applied. SETEX : This subroutine sets up a truth table for n external variables when only uncomplemented external variables are permitted. * This is the other central subroutine for subroutine PROCIP which is mentioned in Chapter 3. 110 PUSHIN : This subroutine sets up a truth table for n complemented external variables when both complemented and uncomplemented external variables are permitted. SUBNET : This subroutine may be entered at three different points by a call to either SUBNET, UNNECE or PVALUE. SUBNET generates detailed information on the network configuration. It calculates the level number of each gate, lists all immediate successors and immediate predecessors for each gate and it also calculates the successor matrix which indicates the existence or non-existence of a path from gate i to j . UNNECE disconnects certain types of obviously unnecessary connec- tions in the network. PVALUE calculates the actual truth table for the entire network (ex- cept external variables). OUTPUT : This subroutine may be entered at five different points by a call to either OUTPUT, PAGE, LINE, TRUTH or CRT. OUTPUT assigns mnemonic names to external variables and gates for the purpose of achieving a readable print-out. PAGE ejects one page on the printer. LINE skips a specified number of lines on the print-out sheet. The number is specified by the argument in the call (e.g., "CALL LINE (5)" skips 5 lines). TRUTH prints out the truth table of the network currently stored as INC$MX. CRT prints out the network itself. SUMARY : This subroutine will prepare a summary for the result of each pro- blem. The summary contains the best cost obtained, the computation time Ill spent and the given problem specifications (the number of external vari- ables, the number of output functions, the maximum fan-ins, fan-outs and the maximum levels) . PUNCAD : This subroutine will punch on cards the information of the current network configuration when the specified time is to expire but the best network is not yet obtained. PARMP : This subroutine will punch cards for the unfinished jobs. The cards contain the information of the original problem specifications, the out- put functions, the control sequence and any other information for con- tinuing the unfinished jobs. 4.2 Control Subroutine MAIN Since the NETTRA system combines all of the transduction programs which were developed previously into one big program, it has the ability to do every- thing that each transduction program can do. Besides, the NETTRA system gives the user more flexibility in designing networks. The user can specify the type, the order and the number of times that some initial network subroutines or some transduction subroutines will be applied. The NETTRA system also has the facilities to treat the intermediate results when specified computa- tion time is to expire; the user can continually run the program next time without losing anything on the unfinished problem. The control subroutine MAIN for the NETTRA system, hence, is very much complicated. Any given problem, if there exists only fan- in/fan-out restrictions, is dealt with by the subroutine MAIN according to the general flowchart shown in Fig. 4.2-1. In Fig. 4.2-1 all decision blocks and execution blocks are labeled with integers. We explain these blocks in detail below: Block 1 : Check whether all problems are solved or not (more than one problem 112 can be submitted at each run). If all problems are solved, then stop. Otherwise go to block 2. Block 2 : Read in a new problem. Initialize some flags and parameters for further processing. Go to block 3. Block 3 : Check whether all specified initial network methods are applied or not (this means that for any problem we can start from initial networks derived by different methods and then apply the same non-fan-in/non-fan- out restricted transduction — fan- in/fan-out restricted transforma- tion — fan-in/fan-out restricted transduction sequence to get differ- ent results). If this is true, then go back to block 1; otherwise go to block 4. Block 4 : Select the next initial network method and call the corresponding subroutine and go to block 5. Block 5 : Check whether all specified non-fan-in/non-fan-out restricted trans- duction subroutines are applied or not. If this is true, then go to block 8. Otherwise go to block 6. Block 6 : Select the next transduction procedure and call the corresponding subroutine without considering the fan- in/fan-out restrictions and go to block 7. Block 7 : Check whether or not the selected transduction subroutine (in block 6) has been called the specified number of times. If this is true, then go back to block 5. If this is not true but the network cost is not im- proved after applying block 6, then we can also terminate the applica- tion of block 6 and go back to block 5. Otherwise go back to block 6. Block 8 : This block is reached from block 5. The fan-in/fan-out restricted transformation subroutine JEFF is applied to transform the network ob- tained in block 5 into a fan-in/fan-out restricted network. Go to block 113 Block 9 : Check whether all specified fan- in/fan-out restricted transduction subroutines are applied or not. If this is true, then go to block 12. Otherwise go to block 10. Block 10 ; Select the next transduction procedure and call the corresponding subroutine considering the fan- in/fan-out restrictions. Go to block 11. Block 11 : Check whether or not the selected transduction subroutine (in block 10) has been called the specified number of times. If this is true, then go to block 9. If this is not true but the network cost is not im- proved, then go to block 9. Otherwise go to block 10 to call the se- lected transduction subroutine again. Block 12 : This block can only be reached from block 9. It checks whether or not the loop consisting of non-fan- in/non-fan-out restricted transduction — fan- in/fan-out restricted transformation — fan-in/ fan-out restricted transduction has been applied the specified number of times. If this is true, then go back to block 3. This outer loop can also be terminated if there is no improvement in the cost. Otherwise go back to block 5. The following is an example which may facilitate the understanding of Fig. 4.2-1. Example 4.2-1 — For a given function f , let us apply the following initial network subroutines and the transduction subroutines: Initial network subroutines: UNIVSA, THRLEV, BANDB non-fan- in/non-fan-out restricted transduction subroutines: MINI2 2 times PRIIFF 2 times GTMERG 3 times PROCCE 2 times fan- in/fan-out restricted transduction subroutines: 114 ") READ IN A NEW PROBLEM AM) DO INITIALIZATION SELECT THE NEXT INITIAL NETWORK METHOD AND CALL THE CORRESPONDING SUBROUTINE SELECT THE NEXT TRANSDUCTION PROCEDURE AND CALL THE CORKESPONDING SUBROUTINE WITHOUT CONSIDERING THE FAN-IN/FAN OUT RESTRICTIONS CALL THE FAN-IN/FAN-OUT RESTRICTED TRANSFORMATION SUBROUTINE JEFF SELECT THE NEXT TRANSDUCTION PROCEDURE AND CALL THE CORRESPONDING SUBROUTINE CONSIDERING THE FAN-IN/FAN-OUT RESTRICTIONS Fig. 4.2-1 General flowchart for the subroutine MAIN when fan-in/fan-out restrions are considered, The execution of these loops can also be terminated whenever there is no further improvement in cost. 115 GTMERG 3 times PROCCE 2 times and the loop consisting of the non-fan- in/non-fan-out restricted transduction — fan-in/ fan-out restricted transformation — fan- in/fan-out restricted transduction is to be executed 3 times. The initial network subroutine UNIVSA will first be applied, and the subroutines MINI2, PRIIFF, GTMERG and PROCCE will be called one by one without considering the fan- in/fan-out restrictions. Each subroutine will be called as many times as specified, but its application will be stopped if the cost cannot be improved. The fan-in/fan-out restricted transformation subroutine JEFF is then called to transform the network into fan-in/fan-out restricted form. The transduction subroutines GTMERG and PROCCE will then be called as many times as specified, but its application will be stopped if the cost can- not be improved. The loop consisting of the non-fan/non-fan-out restricted transduction — fan- in/ fan-out restricted transformation — fan-in/fan-out restricted transduction will be executed three times as specified. But if there is no improvement in cost after the first or second iteration, then it will be terminated. The initial network subroutines THRLEV and BANDB will then be applied one by one and the same loop consisting of non-fan-in/non-fan- out restricted transduction — fan- in/fan-out restricted transformation — fan- in/fan-out restricted transduction will be followed as before to get near- optimal fan- in/fan-out restricted networks. For convenience, we will, from now on call a sequence of initial net- work subroutines, non-fan- in/non-fan-out restricted transduction subroutines, fan- in/fan-out restricted transformation subroutine, fan-in/fan-out restricted transduction subroutines, a control sequence to mean that the processing for 116 the given problem is controlled by this sequence. We will also call a se- quence of non-fan- in/non-fan-out restricted transduction subroutines, fan- in/fan-out restricted transformation subroutine, fan-in/fan-out restricted transduction subroutines, a TT-sequence (Transduction and Transformation se- quence) . This means that each control sequence is composed of one or more initial network subroutines and a TT-sequence. In the case that both fan-in/fan-out restrictions and level restric- tion are imposed, then subroutine MAIN will deal with design problems follow- ing the general flowchart shown in Fig. 4.2-2. The detailed explanation of Fig. 4.2-2 is given below. Block 1 : Check whether all given design problems are solved or not. If not, then go to block 2; otherwise stop. Block 2 : Read in a new design problem and initialize some flags and param- eters for further processing. Block 3 : Let LEVLIM be LREST, where LREST is the given maximum number of levels to be restricted and LEVLIM be the maximum number of levels to be used in finding a feasible network and LEVLIM 21 LREST (this will be explained later). Go to block 4. Block 4 : Call the initial network subroutine TISLEV to get a network whose number of levels is less than or equal to LEVLIM. This initial network may or may not be fan- in/fan-out restricted. Go to block 5. Block 5 through Block 9 : Call the transduction subroutines SUBSTI, GTMERG, PRIIFF, PROCIV and PROCCE one by one considering both the fan-in/fan- out restrictions and the level restriction. In each block, each trans- duction subroutine will be repeatedly called until there is no further improvement in cost. Block 10 : Check whether the number of levels (denoted by LEVM) of the network 117 obtained so far is less than or equal to the given restriction LREST or not. If this is true (the network is level-restricted), then go to block 12. Otherwise go to block 11. Block 11 : Check whether the corresponding initial network is fan-in/fan-out restricted or not. If it is not, then stop because no feasible solutions can be obtained. Otherwise go to block 14. Block 12 : This block is reached from block 10. Check whether the network ob- tained so far is fan- in/fan-out restricted or not. If it is, then go to block 13, since a feasible network is obtained. Otherwise go to block 14. Block 13 : Output the feasible network and go back to block 1. Block 14 : When this block is reached, the network obtained at this point must belong to one of the following two cases: (1) It is level-restricted but not fan-in/fan-out restricted. (2) It is not level-restricted and its corresponding initial network is not fan- in/fan-out restricted. For both cases, the "relaxation problem" is considered, i.e., we in- crease LEVLIM by 1 and go back to block 3 to find another initial network with a higher level limit. This new initial network apparently will not be level- restricted, but it may have less fan-in/fan-out problems than those initial networks with the lower level limit. Starting from this new initial network, the number of levels of the network may be reduced after applying the trans- duction procedures. As is mentioned in Chapter 2, there may not exist any network which satis- fies both the level restriction and the fan-in/fan-out restrictions. The gen- eral flowchart shown in Fig. 4.2-2 does not guarantee that a feasible network can be found even if there do exist optimal networks. But the statistics show that the results obtained by this approach are reasonably good (see 118 YF.S ( stop \ YES READ IN A NEW PROBLEM AND DO INITIALIZATION ( ST " P ) NO LEVLIM ♦■ LREST CALL TISLEV CALL SUBSTI CALL GTMERG CALL PRIIFF CALL PROCIV CALL PROCCE NO YES 14 LEVLIM ♦ LEVLIM+1 I 3 OUTPUT THE FEASIBLE SOLUTION Fig. 4.2-2 General flowchart for the subroutine MAIN when both fan-in/fan-out restrictions and level restriction are considered. 119 Chapter 5 or see [12] for more details). The detailed flowchart for the subroutine MAIN is shown in Fig. 4.2-3(a) through Fig. 4.2-3(f). This detailed flowchart will facilitate those readers who are interested in how the subroutine MAIN is actually pro- grammed. In Fig. 4.2-3 one or more steps are grouped as a block (shown in each dashed rectangle), and the details for each block is explained below. Block 1 through block 7 (Fig. 4.2-3(a)) are for initialization. Block 8 through block 20 (Fig. 4.2-3(b)) are for finding the initial networks. Block 21 through block 29 (Fig. 4 . 2-3 (c) ) are for applying the transduction procedures without considering fan-in/fan-out restrictions and level restric- tion. Block 30 through block 33 (Fig. 4.2-3(d)) are for applying the fan- in/ fan-out restricted transformations. Block 34 through block 43 (Fig. 4.2-3(3)) are for applying the transduction procedures considering fan-in/fan-out re- strictions (and level restriction). Block 44 (Fig. 4.2-3(f)) is for the con- trol flow for considering the level restriction. Block 1 : Set the flag SIGNAL=0 and then read a "specification card". SIGNAL is used to tell whether the data to be read in belongs to the first pro- blem set or not. Initially SIGNAL is set to zero; this means that the data to be read in belongs to the first problem set in this run. SIGNAL will be set and kept as 1 after the first problem has been read in. Six parameters are contained in the "specification card". The "specification card" is used to tell what kinds of input data cards are needed for each problem set. The meaning of those parameters will be explained later. Block 2 : Reset MSIIME, which is used to test whether the specified computation time limit is to expire or not. Check whether the heading card should be read in or not depending on the values of HEAD and SIGNAL. If the current * The heading card usually tells what problem is going to be solved, 120 problem is not the first problem and HEAD=1 , then read the heading card. Go to block 3. Block 3 : Depending on the values of PARM and SIGNAL, check whether the param- eter card should be read in or not. Twelve parameters are contained in the parameter card. The brief meaning of each parameter is introduced below: N: the number of external variables. M: the number of outputs (or the number of given functions) . A: cost coefficient for the number of gates. B: Cost coefficient for the number of connections. UC: this parameter indicates the type of external variables permitted — only uncomplemented or both complemented and uncomplemented. TFI: maximum number of fan-in for gates. TFO: maximum number of fan-out for gates (not output gates). TFOX: maximum number of fan-out for external variables. TFOO: maximum number of fan-out for output gates. LREST: maximum number of levels. P0PT1: this parameter indicates whether the detailed processes of each transduction probram are to be printed or not. P0PT2: this parameter indicates whether the detailed processes of the initial network program TISLEV are to be printed or not. RERUN: It indicates whether the current problem is executed for the first time or it is not finished last time and will be continued this time. Nor- mally RERUN=0. t This is the case that each of the following problems has its own heading card. HEAD=0 implies that the following proglems are the same as the first one except possible difference in some restrictions. For the sake of simplicity, we do not include the checks for rerunning the un- finished job in the flowchart. But when RERUN=1 then we will start from the point where the job was stopped last time. 121 NEPMAX: This parameter denotes the maximum number of error components permit- ted in the transduction procedures based on error-compensation. Usu- N-l ally it is not specified and will be set to value 2 internally. IF SIGNAL=1 and PARM=0, then no parameter card is needed for the cur- rent problem set. Go to block 4. Otherwise read in the parameter card and set default values for those parameters which are not specified by the users. Block 4 : Depending on the values of SIGNAL and SEQC, check whether or not the control sequence card(s) should be read in. If SIGNAL=1 and SEQC=0, then no control sequence card is needed for the current problem; go to block 5. Otherwise read in the control sequence card(s), encode the in- formation into decimal numbers and store these numbers in proper arrays; go to block 5. Block 5 : Depending on the values of SIGNAL and FUNC, check whether or not the output function card(s) should be read in. If SIGNAL=1 and FUNC=0, then no output function card is needed; go to block 6. Otherwise read in the output function cards. Block 6 : Set SIGNAL=1 and select an initial network subroutine specified in the control sequence card(s) (this is equivalent to LIJ-«-LIJ+l, where LIJ is initially) . If all initial network subroutines have been ap- plied, then go back to block 2 to read another problem set; otherwise go to block 7. Block 7 : Set information for making a summary at the end of this problem, set the truth table for external variables, and set initial values for some parameters. Now it is ready to start execution of the current problem. Block 8 : Set KKKK=INITYP (LIJ) , where LIJ ranges from 1 through INTTMX which is the maximum number of different initial network methods to be applied. KKKK ranges from 1 through 6. Go to block 9. 122 Block 9 : If KKKK=1, then call PUSHIN and BANDB to find an initial network by the branch-and-bound method. Go to block 16. Block 10 : If KKKK=2, then call NORNET to find an initial network by Gimpel's algorithm. Go to block 15. Block 11 ; If KKKK= 3, then call THRLEV to find an initial network by the three- level network method. Go to block 15. Block 12 : If KKKK=4, then call UNIVSA to find an initial network by the uni- versal NOR network method. Go to block 15. Block 13 : If KKKK=5, then call TISON to get a two-level or three-level initial network by Tison's method. If there exist level restriction and fan-in/ fan-out restrictions, then call TISLEV to get a level-restricted network based on the two-level or three-level network just obtained. Call SETEX and then go to block 15. Block 14 : If KKKK=6, then call EXNT to read in the configuration of a network which may be found by any other method. Go to block 15. Block 15 : Call PUSHIN and go to block 16 . Block 16 : Update the values of NR and NRN2. NR is the total number of gates and external variables. NRN2 is the size (number of rows times number of columns) of the truth table for all gates and external variables. Go to block 17. Block 17 : Call OUTPUT, SUBNET and PVAUE to set up the network configuration for the network configuration for the initial network. Go to block 18. Block 18 : Call TRUTH and CKT to print out the truth table and the network con- figuration for the initial network. Go to block 19. Block 19 : Update the value of MSTIME. Go to block 20. Block 20 : Check whether or not the specified computation time limit for the cur rent problem is to expire. If not, then go to block 21 to continue the 123 execution; otherwise punch the intermediate results for the current pro- blem and go back to block 2. Block 21 : Set an initial value for BSTCST (200000 is used) which keeps the best cost of the networks during the processes. Set FI=FO=FOX=FOO=100. FI, FO, FOX and F00 will be used as the fan-in/fan-out restrictions. Also set ITER=0, where ITER is used to count the number of times that the TT-sequence is exe- cuted. Go to block 22. Block 22 : Increase ITER by one and check whether ITER is greater than ITRMAX or not, where ITRMAX is the number of times that the specified TT-sequence is to be executed. GDCST (used to store the best cost found after each applica- tion of the TT-sequence) and NEWCST (used to store the cost found after each application of the transduction subroutine or the transformation subroutine) are initiated to the value COST which is the cost of the initial network. Go to block 23. Block 23 : Check if BSTCST > GDCST or not. If this is true, then BSTCST is ' changed to GDCST (this means that a better network is obtained), store the network configuration of the better network for later use, and go to block 24. Otherwise go to block 24. Block 24 : Call UNNECE to remove some obviously redundant connections from the initial network. Go to block 25. Block 25 : Decode the array SEQE which contains the information about the control sequence. The type of the transduction subroutines (TSDTYP) and the number of execution times (ST2) are calculated in this block. If all specified transduction subroutines have been applied, go to block 30; otherwise go to block 26. Block 26 : Set TMPCST=NEWCST, where TMPCST is used to remember the best cost after the selected transduction subroutines are called in block 27 ST2 times. Go 124 to block 27. Block 27 : Call the selected subroutine according to TSDTYP, and go to block 28. Block 28 : Check whether the specified computation time limit is to expire or not. If it is, then punch the intermediate results and go to block 2. Otherwise go to block 29. Block 29 : Check whether the selected transduction subroutine has been executed ST2 times or not. If so, then print the truth table and the network con- figuration of the network just found and go to block 25. Otherwise, check whether NEWCST < TMPCST or not, where NEWCST is the cost of the network just obtained. If it is true, then go to block 26. Otherwise go to block 25. Block 30 : This block is reached when all specified non-fan- in/non-fan-out re- stricted transduction subroutines have been applied. Set FI=TFI,F0=TF0, F0X=TF0X and F00=TF00 and go to block 31. Block 31 : Call JEFF to transform the network into fan-in/fan-out restricted form. Go to block 32. Block 32 : Print the truth table and the network configuration for the network just obtained. Go to block 33. Block 33 : GDCST is then set to NEWCST, the cost of the network obtained in block 31. Check whether or not the specified computation time limit is to expire. If so, then punch the intermediate results and go to block 2. Otherwise go to block 34. It is now ready to do the fan-in/fan-out restricted transduc- tion. Block 34 : Decode the array SEQE to find the type of the transduction subroutine (FIFOTP) and the number of execution times (ST4) . If all specified transduc tion subroutines have been applied, then go to block 42; otherwise go to block 35. 125 Block 35 : Set OLDCST to the value NEWCST, where OLDCST is used to store the net- work cost each time a "better network" (with lower cost) is obtained after applying the transduction subroutines. Go to block 36. Block 36 : Call the selected transduction subroutine and go to block 37. Block 37 : Print the truth table and the network configuration and then go to block 38. Block 38 : Check whether or not the specified computation time is to expire. If so, then punch the intermediate results and go to block 2. Otherwise go to block 39. Block 39 : Check whether or not the selected transduction subroutine has been executed ST4 times or not. If it is, then go to block 41. Otherwise go to block 40. Block 40 : Check whether NEWCST < OLDCST or not. If this is true, then a network with better cost is obtained. Go to block 35. Otherwise go to block 41. Block 41 : Check whether NEWCST < GDCST or not. If it is, then replace GDCST by NEWCST and go to block 34. Otherwise go to block 34. Block 42 : This block is only reached from block 34. It checks whether the TT- sequence has been applied ITRMAX times or not. If ITRMAX=99 (this means that the TT-sequence will be repeatedly applied until there is no further improve- ment in cost), then go to block 44. Otherwise check wither or not ITER, the number of times that the TT-sequence is executed, is less than ITRMAX. If it is, then go to block 23. Otherwise check whether the specified control sequence is for the fan- in/fan-out restricted and level-restricted problems. If it is, then go to block 45. Otherwise replace BSTCST by GDCST and store the corresponding network configuration, and go to block 6. Block 43 : This block can only be reached from blocks 2, 3, 4 and 5 when data cards are needed but the end of a file is encountered. At this point, the 126 ( START J S10NAL - READ IN MEAD. FUNC, PARM. SEQC, PUNC, AND TLIM READ N,M,A,B, * UC, TFI, TFO, TFOX TFOO , I.REST .NEPMAX .RERUN SET THE DEFAULT VALUES FOR THESE PARAMETERS, IF THE USER DOESN'T SPECIFY THEM. PRINT ALL THESE PARAMETERS . I READ CONTROL SEQUENCE * CARDS, CODE THEM AND STORE THEM IN THE PROPER ARRAYS (a) Initialization Fig. 4.2-3 Detailed flowchart for the control subroutine MAIN, If there is no data card then it will jump to I 9 I to terminate the p abnormally. ^^ roblem V 127 [a KKKK - INTTYP (LIJ »> I CALL PUSHIN NR * N + R NRN2 «- NR * N2 I 17 CALL OUTPUT CALL SUBNET CALL PVALUE CALL TRUTH AND CALL CKT TO PRINT THE TRUTH TABLE AND THE NETWORK 1 I 19 I UP-DATE MSTIME I (b) Initial network step. 128 SET INITIAL VALl't FOR 8STCSI - 200000 SET I - FO - FOX - FOO - 100 ITER • CALL UNNECE DECODE ARRAY SEQE TO FIND THE TRANSDUCTION PRiw.RAM TYPE TSDTYP AND THE II OF ITERATIONS ST2 ll II * , * \ \ II 1 PROCI II „ i t \ t ♦ II MINI2 II II SUBSTI II II RDTCNT II 1 1 CTMERC II II PROCV II II PRIIFF II II PROC 1 V II II PROCCE II * * ♦ ♦ ♦ ♦ ♦ (c) Non-fan-in/non-fan-out restricted transduction step. 129 30 l_ FI = TFI , F0 = TFO FOX = TFOX, FOO = TFOO 31 CALL JEFF 32 PRINT TRUTH TABLE AND NETWORK ~1 33 L CDCST ■*- NEWCST YES PUNCH INTERMEDIATE RESULTS NO ^ J (d) Fan-in/fan-out restricted transformation step, 130 41 PRINT Till. SUMMARY | ' ' ( STOP J (e) Fan- in/fan-out restricted transduction step, 131 YES NO FEASIBLE NETWORK NO NO k? FEASIBLE NETWORK IS FOUND w LIJ *■ w (f) Control flow for considering the level restriction. FifL ^ . 2 - .3 Detailed flowchart for the control subroutine MAIN, 132 current run is finished, so print the summary table and then stop. Block 44 : Check whether GDCST < BSTCST or not. If it is, then go to block 23. Otherwise go to block 6. Block 45 : This block gives the control flow for problems with both fan- in/fan-out restrictions and level-restriction. Details about the control flow is ex- plained already in this section and hence is omitted here. 4. 3 Overlay structured program Overlay structured programming is used when the total memory needed for the program and data exceeds the maximum main storage available. Before explainin; what an overlay structured program is and how to design an overlay structured pro- gram, the following concepts are introduced first. Ordinarily, the preparation for executing a source program can be illus- trated in Fig. 4.3.1. The input to the language translator is a source module ; the output from the language translator is an object module . Before an object module can be executed, it must be processed by the linkage editor. The output of the linkage editor is a load module . The source module can be any program written in symbolic languages like assembly languages, ALGOL, COBOL, FORTRAN, PL/1, APL, etc. The language translator can be an assembler or a compiler. An object module is in relocatable format in unexecutable machine code. A load module is also re- locatable, but in executable machine code. SOURCE MODULE OBJECT MODULE LANGUAGE TRANSLATOR LOAD MODULE LINKAGE n\ ^ I > editor / .' ' u Fig. 4.3.-1 Preparing a load module for execution, 133 Any module is composed of one or more control sections . A control sec- tion is a unit of coding (instructions and data) that is, in itself, an entity. All elements of a control section are loaded and executed in the order specified by the programmer. A control section is, therefore, the smallest separately re- locatable unit of a program. For example, a FORTRAN program may contain many subroutines (including the subroutine MAIN), each of which is a control section. In processing object and load modules, the linkage editor assigns con- secutive relative addresses to all control sections and resolves all references between control sections. Object modules produced by several different language translators can be used to form one load module. Ordinarily, when a load module produced by the linkage editor is executed, all of the control sections of the module remain in main storage throughout execu- tion. The length of the load module is, therefore, the sum of the lengths of all of the control sections. When the main storage space is large enough, this is the most efficient way to execute a program. However, if a program approaches the limit of the main storage available, the programmer should consider using the over- lay facilities of the linkage editor before rewriting the program. When the link- age editor overlay facility is requested, the load module is structured so that, at execution time, certain control sections are loaded only when referenced. The way in which an overlay module is structured depends on the relation- ships among the control sections within the module, and two control sections which do not have to be in storage at the same time can overlay each other. They can be assigned the same load addresses and are loaded only when referenced. Control sections are grouped into segments . The control sections required all the time are grouped into a special segment called the root segment . This segment remains in storage throughout execution of an overlay structured program. All other control sections which can be overlayed are grouped into segments 134 separately. When a particular segment is to be executed, any segments between it and the root segment must also be in storage. For example, assume that a program contains seven control sections (see Fig. 4.3.2), A through G, and exceeds the amount of maximum storage available for its execution. Before the program is rewritten, it is examined to see whether or not it can be placed into an overlay structure. Assume that the re- lationships among control sections are shown in Fig. 4. 3-2 (a). In Fig. 4. 3-2 (a), an arrow from control section i to control section j means that control section j receives control from control section i (or in FORTRAN, subroutine j is called by subroutine i) . Since control sections A and B appear in each indepen- dent control group, they can be placed in the root segment. Control section C, F and G are in three separate segments, and control sections D and E are in one segment. The overlay structure for this example is shown in Fig. 4.3-2(b). The total length of this overlay structured program is the length of the longest path of the above overlay structure. The overlay structure shown in Fig. 4.3-2(b) is called the single-region overlay structure. Usually, if a control section appears in several paths in Fig. 4.3-2(b), it is desirable to place that control section in the root segment. However, the root segment can get so large that the benefits of overlay structure are lost. So the multiple-region overlay structure is introduced. For example, Fig. 4.3-3(a) shows a single-region overlay structure. As can be easily seen, control sections H and I are controlled (or called) by control sections F and G. We can place control sections H and I in the root segment. But this will make the root segment longer than necessary (H and I are not used in the path A+B-+C+D+E). Fig. 4.3-3(b) shows the multiple-region overlay structure; in it, control sections H and I are overlayed in region 2. Control sections H and I can be placed in the main storage only when control section F or G is in 135 I B I C I I B I C I I B I Fig. 4.3-2(a) This program contains seven control sections which are grouped as three independent control section groups B i i Fig. 4.3-2(b) Single-region overlay structure A B 136 Y722ZZZZ CZZZ3 Ez2zi 77ZZZZZZZ2Z> H Z2Z2 Fig. 4.3-3(a) Control sections H and I appear in more than one path "s A " ROOT : SEGMENT 1 REGION 1 B C - SEGMENT 2 G -SEGMENT 5 D F -SEGMENT 4 - - SEGMENT -> - E 3 *v — I ■ SEGMENT 7 REGION 2 H > •SEGMENT 6 J _ Fig. 4. 3-3 (b) Multiple-region overlay structure 137 the main storage. In the NETTRA system, only single-region overlay structure is used. Table 4.3-1 gives the size of each subroutine. The total length of these subroutines is much greater than the storage available (400 K bytes in decimal normally ). Fig. 4.3-4 shows the single-region overlay structure for the NETTRA system. The length of the longest path in Fig. 4.3-4 is 366 K bytes (in decimal) * It can be extended to 500 K on special request. 138 Table 4. 3-1 Memory sizes of all subroutines included in the NETTRA system Type of Subroutines Memory Size (Bytes) Hexadecimal Decimal MAIN 94D8 38,104 COMMON DATA AREA 2EDD8 192,232 I/O SUPPORTING SUBROUTINES AABC 27,068 BANDB et al 6970 26,992 UNIVSA 57E 1,406 THRLEV 10DA 4,314 TISON et al 10450 66,640 TISLEV et al 15CC 5,580 TANT et al 1AF80 110,432 EXNT 6D6 1,750 JEFF et al 428E 17,028 PROCIP (0) 1854 6,268 PROCIP (I) E3C 3,644 PDTCNT CD4 3,284 PROCI E32 3,634 PRIFF & PROCIV et al D8D8 55,512 GIMERG 7144 29,252 PROCV et al A224 41,508 PROCCE et al DF30 57,138 PARMP & OPTTYP * 1042 4,162 , — . — 1 *OPTTYP is an 1/0 supporting subroutine not called by MAIN very often, 139 PROCCE PROCV GTMERO ft M CO PRIIFF and PROCIV JEFF EXNT TANT TISON T IS LEV THRLEV INIVSA BANPB CD -P W EH EH CD -p O > CO H ?H o g •H M CD I CD H bO (3 •H CO i CO •H 140 5. Statistics and Experimental Results The IBM 360/75J is used to run experiments for testing the NETTRA system. It is easy to see from Fig. 4.2-1 that we can design an infinite number of control sequences to solve problems under fan-in/fan-out restric- tions. Each control sequence consists of one or more initial network sub- routines and a TT-sequence, and each TT-sequence consists of the fan-in/fan- out restricted transformation subroutine and one or more transduction sub- routines. For any initial network derived by some initial network subroutine, the TT-sequence and each transduction subroutine in the TT-sequence can be applied as many times as we like. If we apply the same TT-sequence on different initial networks the same number of times, or if we apply different TT-sequences on the same initia network the same number of times, then we will usually obtain different result Therefore a choice of an appropriate control sequence is an important problem- Many experiments are made in order to find out the influence of ini- tial network subroutines on the final results and the general tendency of ef- fectiveness and efficiency of the transduction subroutines. The results of experiments are given in this chapter. We can find out how to design appro- priate control sequences from these results. Besides, four optional control sequences (OPTION 1 through OPTION 4) are provided for those who are not interested in knowing the details about how to specify a control sequence. OPTION 1 is designed to produce a near-optimal network with very good cost, though the computation time spent by this control sequence may be very long. 142 V / 1 / \ / ■ ■ i n \ 1 \ 7 w o \ / \ / M \ / \ \ / iH vO H o m \ / CO oo \ / \ \ / CO m H m \ / \ / \ \ / M +■ \ / \/ \ w H \J v v V ^ \ x I I H H CO O M o CM M A / \ CO O M M A A A CO o CM M W § r-~- M in o\ 00 r^ H • r^ r-« r^. r^ r^ r^ r^ > M M W H 3 3 H CM O LO m CM M O v£3 m M> H O O O o o> 00 O 00 00 o CO M M M O O O M O O M O O m m r^ CM 00 m M CM \D o CM CM CM M CM M CM CM CM CM a r-^ CM LO I s *. m m r^- r^ o> O^ co 00 co CM o> OS M H r^ H 25 i=> W LT> LO co o M m m o CM r-^ H o o o M o M o M o O CO CO CO CO co co co co CO co co O CO CO CO co CO CO co co CO CO o co co CO co co co co CO CO co iJ fc< CO < 2 o MOO H ^ a H H H i is PJ PJ M S S v£> 00 CO o P4 CO n o < PJ Pn M Ph <3" r~~ o u Pn Q CO Ph / pj / LO Pn M CM PJ M co o> vT> o o / s / o> Q < m 00 00 vO o O M / H / CM Q 00 v£> CO 00 CO 00 vO r^ pj / • * • • • • • • • • O PJ M CN CO - 00 CTi o S Q M / / := a '• / fo >3 / pj S Y s — ' Po O • c d CO cO -o II C •u o cu Pd o 00 <1) .r, co 4-1 O •H o 4J s + c c OJ CO pi o o X ti CD •H SO O 4-1 -o •H H M =3 ^ II H 0) ■u B !-i CO •H O O M Ph O 141 OPTION 2 is designed to produce a network with a reasonably good cost in a reasonably short time. OPTION 3 is designed to produce any network in a very short time; in this case, how good the cost of the network is not im- portant. OPTION 4 is a special control sequence designed for producing feasible networks for problems under both fan-in/fan-out and level re- strictions. 5. 1 Comparison of Initial Network Methods In order to find out the influence of initial networks on the final results after applying the same TT-sequence the same number of times, ten 5- variable single-output functions are used to do experiments. First, the ini- tial networks obtained by the five initial network methods are shown in Table 5.1-1. In Table 5.1-1, the given functions are shown in the first column in hexadecimal representation. The cost of a network is defined as 1000 x R + C where R is the number of gates and C is the number of connections in the net- work. Only uncomplemented external variables are permitted as inputs. It is observed that subroutine UNIVSA is the least time-consuming one whereas subroutine TANT is the most time-consuming one. Subroutine TANT can- not produce any result within 1 minute execution for most functions. The reason is that subroutine TANT aims at finding "optimal three-level" networks; it becomes very time-consuming when the number of gates in a network exceeds approximately 10. Subroutine TISON usually produces networks with very good costs, although these networks are always three-level networks (or two-level networks if both complemented and uncomplemented external variables are permit- ted as inputs). Subroutine THRLEV also produces three-level networks, but the * The results derived by TISLEV will be shown in Section 5.3. 143 costs of networks derived by THRLEV are usually higher than those by TISON. Networks obtained by surbroutine BANDB are not restricted to be three-level only, and they usually have reasonably good costs. Table 5.1-1 only gives some ideas how the initial networks obtained by different methods look like and how much computation time different methods spend. It does not show the influence of the initial networks on the final results after applying the control sequences. So some other experiments are made. Since subroutine TANT is too time-consuming, it is not included in later experiments. For the transduction subroutines which can treat problems under fan- in/fan-out restrictions , the control sequences corresponding to the flowchart shown in Fig. 5.1-1 are applied. Each control sequence consists of four ini- tial network subroutines and a TT-sequence, and each TT-sequence consists of subroutine JEFF and one of the following 8 transduction subroutines: MINI2, SUBSTI, RDTCNT, PROCI, GTMERG, PRIIFF, PROCIV and PROCCE . Starting from the initial network derived by one of the subroutines UNIVSA, THRLEV, BANDB, and TISON, we will repeatedly apply the selected transduction subroutine under no fan- in/fan-out restrictions until there is no further improvement in the cost. We will then apply subroutine JEFF to transform the network into fan-in/fan- out restricted form. Again we will repeatedly apply the same transduction subroutine under fan-in/fan-out restrictions until there is no further im- provement in the network cost. The selected TT-sequence will also be applied repeatedly until there is no further improvement in the cost. The fan- in/fan-out restrictions for the experiments are set as FI = FO = FOX = F00 = 4. Costs of the resulting networks and computation Only subroutine PROCV cannot treat problems under fan- in/fan-out restrictions 144 START D CALL ONE OF THE SUBROUTINES : UNIVSA BANDB, THRLEV & TISON TO OBTAIN AN INITIAL NETWORK CALL THE TRANSDUCTION SUBROUTINE X UNDER NO FAN- IN /FAN-OUT RESTRICTIONS CALL THE FAN- IN /FAN-OUT TRANSFORMATION SUBROUTINE JEFF CALL THE TRANSDUCTION SUBROUTINE X 1 " UNDER FAN- IN FAN-OUT RESTRICTIONS STOP ) Fig. 5.1-1 Flowchart for the experiments for finding out the influence of initial networks. These loops will be repeatedly applied until there is no further improvement in the network cost . 145 times are shown in Table 5.1-2 through Table 5.1-9. Since the same 10 func- tions as in Table 5.1-1 are used, only the function numbers are shown. The cost of the best network for each function is marked with circles. In Table 5.1-2, the number of best networks obtained by starting from initial networks obtained by UNIVSA, THRLEV, BANDB and TISON are 1, 1, 4 and 5, respectively. This means that the initial networks obtained by BANDB and TISON are "desir- able" for the transduction subroutine MINI2, i.e., if MINI2 is used in the experiments following the flowchart shown in Fig. 5.1-1 to simplify the initial network obtained by BANDB or TISON, then we will usually obtain better results. In Table 5.1-3, the networks derived by BANDB and UNIVSA are more desirable for the transduction subroutine SUBSTI. In Table 5.1-4 and Table 5.1-5, the networks obtained by BANDB and TISON are more derivable for the transduction subroutines RDTCNT and PROCI. For transduction subroutines GTMERG, PRIFF and PROCIV, networks obtained by BANDB are more desirable. For the transduction subroutine PROCCE, networks obtained by UNIVSA, BANDB or TISON are more desir- able. Table 5.1-10 gives the number of best results obtained by starting from different initial networks and then applying different transduction subroutines, It is easy to see that the initial networks obtained by subroutine TISON are more desirable for the transduction subroutines realizing pruning procedures (including MINI2, RDTCNT and PROCI). For the transduction subroutines which realize the transduction procedures based on gate merging, gate substitution and connectable and disconnectable functions (including SUBSTI, GTMBERG, PRIIFF and PROCIV), networks obtained by BANDB are more desirable. The last row in Table 5.1-10 gives the total number of best networks obtained by starting one of four initial networks, i.e., the sum of the numbers of best methods in each column in Table 5.1-10. It shows that the initial networks obtained by sub- routine BANDB are in general more desirable for applying transduction 146 Table 5.1-2 Results for the experiments shown in Fig. 5.1-1-1. The transduction subroutine MINI2 is used. \\^ INITIAL \ \^ NETWORK COST \ ^ s \. & \funct.^\ TIME \ NO. ^\ UNIVSA THRLEV BANDB TISON H O CJ o H W Z 1 23052 29059 22051 C11051J 2 30063 34065 20071 ( 21050 ) 3 20044 23045 35089 I 17041 ) 4 18038 18038 18045 ( 15037 ) 5 23050 25049 23059 C 15038 ) 6 18047 15033 ( 13035 ) ( 13035) 7 23052 24054 21050 ( 17046 ) 8 19043 17039 20043 C 16044 ) 9 22051 33060 (17045 ) 22054 10 21044 28057 15037 C 14039 ) 1 COMPUTATION TIME (CS)* 1 133 114 165 82 2 172 165 206 90 3 140 97 358 65 4 120 69 116 65 5 125 107 166 64 6 89 55 105 64 7 131 108 132 94 8 112 70 122 95 9 146 145 132 74 10 129 135 128 67 * CS = Centiseconds 147 Table 5.1-3 Results For l ho experiments shown in Ki^. 5.1-1-1 The transduction subrout ine SUBSTI is used. \. INITIAL \ \. NETWORK \funct / s X. DIME \ NO. \\ UNIVSA THRLEV BANDB TISON NETWORK COST 1 22051 23053 22051 ( 16044 ) 2 27060 26057 24064 ( 21050) 3 15037 33089 17041 ( 14039 ) 4 18045 15037 C 15034 ) C 15034 ) 5 21048 19043 20057 C 15038 ) 6 14041 15033 ( 11033 ) ( 11033 ; 7 20050 20050 21050 C 16044 > 8 17041 17039 20043 ( 16044 ) 9 22051 22048 22054 ( 17045 ) 10 16040 24052 13029 ( 13037 ) n J H ~* o H H -i H 5 I 204 203 240 196 2 297 265 317 189 3 134 152 518 120 4 206 154 142 101 5 227 203 167 103 6 120 71 159 88 7 185 179 147 188 8 202 103 128 163 9 255 236 140 188 10 184 199 154 100 ' CS = Centist iconds 148 Table 5.1-4 Results for the experiments shown in Fig. 5.1-1-1. The transduction subroutine RDTCNT is used. \\. INITIAL \ ^>s. NETWORK COST \ ^\ & \FUNCT.^\^ TIME \ NO. \^ \ \ UNIVSA THRLEV BANDB TISON NETWORK COST 1 29057 28056 22051 ( 20052 ) 2 35065 34064 26065 C 21050) 3 22044 21043 23051 C 17041) 4 18038 18038 18045 ( 15037 ) 5 24050 25049 19048 C 15038 ) 6 13037 17043 15033 C 12033 ) 7 24053 25053 21050 C 17042 ) 8 18038 15037 20043 ( 14040 ) 9 29056 33060 22054 C 17045 ) 10 26049 29057 15039 C 14039 ) | - - ■ - - - - COrfPLTATION TIME (CS)" 1 305 175 245 101 2 340 216 324 95 3 211 136 491 84 4 255 81 137 85 5 205 146 248 65 6 170 80 161 65 7 227 161 182 113 8 238 98 165 114 9 302 195 165 98 10 277 183 147 74 * CS = Centiseconds 149 Table 5.1-5 Results for the experiments shown in Fi^;. 5.1-1-1. The transduction subroutine PROCI is used. \^ INITIAL \ \. NETWORK \FUNCT /\. TIME \ NO. ^\ \ \ UNIVSA THRLEV BANDB TISON 1 23052 27054 22051 C 20052J 2 30061 34065 26065 ( ?msn) 3 20044 21043 23051 C 17041 ) 4 16037 18038 18045 H en C 15037 ) o u 5 23050 25049 19048 Ui C 15038', o 6 15037 17043 15033 H ( 13033J 2 7 26057 25053 21050 C 17042 ) 8 15036 14040 20043 C 14035 ) 9 23052 33060 22054 C 17045 ) 10 23050 29057 15039 ( 14039 ) 1 743 185 224 87 2 720 217 322 99 K^ 3 382 162 486 76 CJ 4 618 77 127 70 2 H H 5 264 144 226 60 IS O H 6 470 71 156 69 < H 7 458 149 176 117 o 8 659 83 154 115 9 690 209 157 83 10 664 205 151 84 >'c CS = Centise iconds 150 Table 5.1-6 Results for the experiments shown in Fig. 5.1-1-1. The transduction subroutine GIMERG is used. \\. INITIAL \ ^\. NETWORK COST \ ^ S \. & \FUNCT.^\^ TIME \ NO. \^ UNIVSA THRLEV BANDB TISON H CO o U s o "-> H W z 1 20049 22053 ( 19049 ) 22051 2 28063 23057 C 19050 ) 3 23062 ( 15038 ) ( 15038 ) 17041 4 18045 ( 15034 ; C 15034 ) 15037 5 21048 19046 20057 ( 15038 ) 6 11033 11033 ( 10029 ) 15033 7 22053 18045 ( 16044 ) 21051 8 15036 16044 ( 14035 ) 14037 9 22051 23052 ( 17045 ) 22054 10 16040 23052 ("13037 ) 14039 1 ■■■ ■ - COMPUTATION TIME (CS)" 1 415 499 361 314 2 759 643 545 260 3 255 228 664 180 A 324 242 208 152 5 364 382 254 144 6 155 106 186 153 7 405 352 151 309 8 334 186 154 177 9 500 538 209 318 10 280 556 191 143 * CS = Centiseconds 151 Tabic 5. J -7 Results for the experiments shown in FLg. 5.1-1-1 The transduction subroutine PRIIFF is used. Nv INITIAL \ ^N. NETWORK \FUNCT . >v TIME \ NO. ^\ \ \ UNIVSA THRLEV BANDB TISON 1 19047 20049 17041 ( 14037 ) 2 19045 20050 21050 C 17040 ) 3 13036 17041 ( 13034 ) ( 13034 ) A 13033 17037 15037 H C 13031 ') O u 5 15040 14037 15038 \4 ( 13036 ) O 6 11033 11033 12027 |2 H (J.0026 ) ^ 7 17043 15040 17039 C 14039 ) 8 16039 13033 14037 C 11030) 9 19045 19045 20047 ( 16035) 10 16039 16041 14039 C 13032 ) /-> CO U W H H Z o H H < H P 1 1186 469 545 458 2 1882 593 488 330 3 872 389 1009 445 4 1383 322 362 150 5 846 628 487 165 6 769 207 243 153 7 1026 490 367 515 o u a 1091 325 330 240 1 9 1448 421 602 639 10 1251 567 309 138 * CS = Centiseconds 152 Table 5.1-8 Results for the experiments shown in Fig. 5.1-1-1. The transduction subroutine PROCIV is used. \\^ INITIAL \ \. NETWORK LJOST \ X. & NFUNCT.^n. TIME \ NO. ^\ UNIVSA THRLEV BANDB TISON H CO o u i4 3 o ►3 H z 1 17044 18044 17041 C 14039 ) 2 17042 17045 18041 C 17039 ) 3 15034 17044 C 13034 J C 13034 ) 4 15035 17037 15037 C 14036 ) 5 14037 14036 15038 ( 13032 J 6 11033 11033 15033 C 11031 ) 7 16044 16044 13034 ( 11033 ) 8 11030 12030 14030 C 11029 ) 9 18044 17043 17044 ( 15040 J 10 16039 14039 14039 ( 13034) 1 COMPUTATION TIME (CS) 1 3139 2287 2323 2162 2 3296 2900 2842 3708 3 1674 1391 2677 1179 4 2789 3019 3573 849 5 3662 1775 2220 891 6 1091 809 1082 781 7 1969 1762 1466 3205 8 1534 1236 1385 2143 9 3115 2174 2426 2870 10 3711 1518 1177 772 * CS = Centiseconds 153 Table 5.1-9 Results for the experiments shown in Kig. 5.1-1-1. The transduction subroutine PROCCE is used. \\. INITIAL \ ^\^ NETWORK OST \ ^\^ TIME \ NO. ^\ UNIVSA THRLEV RANDB TISON 1 17043 20051 18045 H en O u & o *— * H W z C 16043) 2 17046 16044 16047 C 16043) 3 12037 14035 13035 ( 11033 ) A 13038 15037 C 12034 ) ( 12034 ) 5 15034 15038 13039 ( 13032 ) 6 10031 10031 12029 C 9027 ) 7 16044 13039 16044 ( 13036 ) 8 13032 12030 13032 C 12029 J 9 15041 17044 17045 ( 14034 ) 10 15041 14039 14039 C 14037 J * u w H z o H H «| H o 1 2663 3795 2046 6690 2 3410 2563 3067 8134 3 1273 1479 2860 3513 4 1150 853 935 1697 5 4778 1921 2973 2704 6 781 573 1039 1195 7 2196 1855 1525 4027 8 2437 2424 1406 1477 9 4570 4154 2407 6288 10 1508 3494 1749 1233 v< CS = Centis( sconds 154 Table 5.1-10 Total number of best methods obtained by starting from one of four initial networks and applying one of eight transduction sub- routines. Transduction Subroutine Applied Initial Network Subroutine Applied UNIVSA THRLEV BANDB TISON MINI2 1 1 4 5 SUBSTI 3 2 5 2 RDTCNT 1 4 5 PROCI 1 1 3 5 GTMERG 3 2 6 1 PRIIFF 2 2 7 PROCIV 3 3 5 PROCCE 4 1 3 3 Total Number of Best networks 18 11 37 21 I 55 procedures than the initial networks obtained by any other initial network sub- routine. Table 5.1-11 Average computation time for finding initial networks by different initial network subroutines UNIVSA THRLEV BANDB TISON 4.4 cs 7.5 cs 77.8 cs 29.6 cs The average computation time for finding initial networks is shown in Table 5.1-11. It is obtained by adding up the computation time in each column in Table 5.1-1 and then dividing the sum by 10. The average computation time for the experiments shown in Fig. 5.1-1 is given in the upper half of Table 5.1-12, it is obtained by adding up the computation time in each column in each table of Table 5.1-2 through Table 5.1-9 and then dividing the sum by 10. The percentage of average computation time for finding initial networks is given in the lower half of Table 5.1-12. These results indicate that the transduction subroutines which realize the transduction procedures based on connectable and disconnectable functions and error-compensation are usually more time-consuming than other transduction subroutines; in other words, the computation time for finding initial networks is only a very small fraction of the total computation time when these transduction subroutines are applied in the experiments. From the previous experimental results and analyses, we get the follow- ing conclusions: (1) The costs of the initial networks do not have direct relationship with the final results; i.e., starting from initial networks with lower costs do not imply that the corresponding networks also have lower 156 Table 5.1-12 Average computation time for the experiments in Fig. 5.1-1 TRANSDUCTION SUBROUTINE USED AVERAGE COMPUTATION TIME / 10 FUNCTIONS (CS) UNIVSA THRLEV BANDB TISON MINI2 129.7 106.5 163.0 76.0 SUBSTI 201.4 176.5 211.2 143.6 RDTCNT 232.5 147.1 225.4 89.4 PROCI 500.4 150.2 233.6 86.0 GTMERG 379.1 373.2 292.3 215.0 PRIIFF 1175.5 441.1 474.2 323.3 PROCIV 2598.0 1887.1 2115.1 1856.0 PROCCE 2476.6 2311.1 2000.7 3695.8 TRANSDUCTION SUBROUTINE USED PERCENTAGE OF COMPUTATION TIME FOR FINDING INITIAL AVERAGE NETWORK (%) UNIVSA THRLEV BANDB TISON MINI 2 3.39 7.04 47.73 38.94 SUBSTI 2.18 4.25 36.84 20.61 RDTCNT 1.89 5.09 34.51 33.10 PROCI 0.88 4.99 33.30 34.42 GTMERG 1.16 2.01 26.62 13.76 PRIIFF 0.37 1.70 16.41 9.16 PROCIV 0.17 0.40 3.68 1.59 PROCCE 0.18 0.32 3.89 0.80 157 costs after applying the transduction procedures. Sometimes the final results are more influenced by the network configurations rather than the costs of the initial networks. More specifically speaking, Table 5.1-1 shows that the initial networks obtained by Tison's method usu- ally have lower costs than those obtained by other methods. But Table 5.1-10 shows that starting from the initial networks obtained by the branch-and-bound method, better final results can usually be obtained. This is because the initial networks obtained by the branch-and-bound method are usually multiple-level networks, and hence are more suit- able for the transduction procedures to reconfigure. The initial net- works obtained by Tison's method are restricted to be two-level or three-level, and hence are more difficult to reconfigure, even though they have lower costs. The initial networks obtained by three-level network method are also restricted to be two-level or three-level; since they usually have higher costs than the initial networks ob- tained by Tison's method, the corresponding final results are worse. The initial networks obtained by the universal network method are multiple-level, but they usually contain too many gates and connec- tions and hence are more difficult to simplify. (2) The computation time spent in finding initial networks is much shorter than that in applying the transduction and transformation subroutines. This is especially true when those sophisticated trans- duction subroutines, such as PRIIFF, PROCIV and PROCCE, are applied. 5. 2 Comparison of Transduction Procedures The results obtained in Table 5.1-2 through Table 5.1-9 can also be used for analyzing the effectiveness and the efficiency of the transduction procedures. Table 5.2-1 through Table 5.2-4 are rearrangements of the costs 158 of Table 5.1-2 through Table 5.1-9, which are more convenient for us to com- pare the transduction procedures. In each table, one of four initial network subroutines is used to obtain networks, and then different transduction sub- routines are applied (according to the flowchart in Fig. 5.1-1) to simplify the initial networks. Best results for each function are marked with circles. In Table 5.2-1, if subroutine PROCIV or subroutine PROCCE is applied, then we can obtain 5 or 6 best networks, respectively. In Table 5.2-2, cor- responding to subroutines PROCIV and PROCCE, we can get 4 and 6 best results, respectively. In Table 5.2-3, we can obtain 5, 2 and 3 best results corres- ponding to subroutines PRIIFF , PROCIV and PROCCE, respectively. In Table 5.2-4 the situation is very interesting. For Function 4 and Function 10, we can get best results no matter what transduction subroutines are involved. But in general, subroutine PROCCE is still more effective. Since the initial networks obtained by subroutine TISON are based on the minimum sums, they usually do not have redundant connections . Only those complex transduction procedures, like PRIIFF, PROCIV and PROCCE, can significantly reconfigure and simplify the net- works. Table 5.2-5 gives the number of best results that we can get if certain, transduction procedures are applied. The last row in Table 5.2-5 gives the total number of best results obtained by each transduction subroutines (i.e., it is the sum of numbers in each column) . This shows that in general sub- routines PROCCE, PROCIV and PRIIFF are more desirable to use in deriving near- optimal solutions. Another interesting statistic is the "average cost" obtained corres- ponding to each transduction subroutine. It is derived by adding up the num- bers of gates and the numbers of connections separately in each column of each * This is also true even after applying the fan- in/ fan-out restricted transforma- tions. /""> r*y •\ , -^ ~N f> w CO mo CO sH u u LJ L> W r\ n r> -> 3 > <-J L> ^> CO m m0 c_> o Pi Pi i— 1 m o o CN M o PL, o 00 rH o> en O r*» H en o en rH VO en O <3- r^ en o rH u en rn o rH rH sf sf o rH o en O CN rH rH rH sr o vO rH o Pd w s CO o CN CN m O en CN 00 en O m en o m H vD o rH en en o rH rH m sr o 00 rH en o m rH CN m O en CM CM m o en CN M o o Pi m o CN m *£> o en en st o rH CN 00 en O 00 rH sf O m CN en en o en rH en m o in CN en o m rH O vO O en en m o CN H u H m o 00 CN o en o rH CN CO en O 00 rH o m CN en O en rH en m o m CN en o m rH O o en en m O ON CN rH H en PQ en en m o en CN m o CN r> en O m H St en o m H en o CTi rH en en o rH rH o m o o CN ON en o rH 00 sf o CN CN CN m o CM CN M i— i ON m o CJN CN m \o o h» 00 ON o rH f-"^ ^ W C_> o o fa fa m r> LO oo ON r>« NO o LO ON H U o Pi fa /">, ,^\ ON LO fa r^ O NO rH r^ nO ON o LO CN M ro LO CO rn CO CN CO oo 0O OO M O O O o o O O o o O fa m NO LO » CO nO O r^ !3 m NO -< cd c o X. u CO 01 u o LW CO 01 X) • 3 0) w ,c 4-J ^ M u O o 3 IIH -i a> X c W /^-Nj f~\ ^~N s~>i (_) m en in r-» CN CT\ o 1— 1 r"N _ s~\. r~\ ^H H ^J r~\ r~N i— i u o PS Ph rH O rH r^- CO en o en -J- CT\ m m in m m rH o CN LH m H LP) m ■o- en en en m H m m r^ 00 <7\ o z c/yv. < / O PS Ph / M W H/ H « / <-> £ / ^ E / t> S / w 163 en en C QJ o C ■H ■H 4-1 4-1 CO 3 (3 O •H u ,fl X> B 3 o DQ o d 4-) c •H cu 4-J u o OJ 3 4-1 "O IW en ■H C T3 rO M >. +J ,Q T3 X) G 01 CU c •H en cd 0) 4-1 C & •H O 4-J 3 CO M U U X> o 3 & en 4-J OJ ^ c U O 4-1 & en 4-J OJ QJ ,fi g 4-1 rH O Cfl •H U 4-J 01 •H ,o c •H 53 <4-l o m I CN m CO w c_> o o CN Pi CN P4 > 1— 1 CJ o m Pi Pm O Pi g o O o CN CN H O M U o o o O CN CN Pi P-I H S CJ> H o o O CN CN H H CO PQ o o o CN CN P CO CN H S o o o CN CN H S P / a w w / o a H / M H P / H H P-i / U P PL,/ P O w p PQ 53 o NUMBER ESULTS i-i Pi 5 CO fc Pi \ TR^ ITIAL^ TWORK BROUT : § s PQ H H TOTAL BEST / a h p K H S". W 164 table in Table 5.2-1 through Table 5.2-4 and then dividing the sums by 10. These results are shown in Table 5.2-6. From this table and the average com- putation time shown in the upper-half of Table 5.1-12, the general tendency of effectiveness and efficiency of each transduction subroutine (or procedure) can be determined. This is shown in Fig. 5.2-1. Notice that so far we have not compared subroutine PROCV with other transduction subroutines. The reason is that subroutine PROCV was originally designed under no fan- in/fan-out restrictions. Since its performance is not very impressive, it is not modified for treating problems under fan-in/fan-out restrictions. The experiments shown in Fig. 5.2-2 are made to compare sub- routine PROCV with subroutines RDTCNT, PROCI and SUBSTI. Table 5.2-7 through Table 5.2-10 give the experimental results. The fan-in/fan-out restrictions are specified as FI = FO = FOX = FOO = 4, and the previous ten 5-variable functions are used. In Table 5.2-7, it is observed that the results obtained by using subroutine PROCV in the experiments are much worse than those by other three transduction procedures; also the computation time is much longer. This is because that subroutine PROCV realizes the transduction procedures based on gate substitution, and each gate (except the output gates) in a universal net- work realizes only one minterm and therefore no gate can substitute for any other gates. For Functions 2, 4 and 10, the results are not fan-in/fan-out re- stricted; because the maximum number of gates allowed in a network in the NETTRA system is 60-n, where n is the number of external variables, and for these problems more than 60-n gates are needed to transform the network into fan-in/fan-out restricted form. For initial networks derived by other three initial network subroutines. 165 •H CO 3 > 43 x) 3 0) 3 to •H CU CO 3 4-1 «H 43 O 3 O -K U CO X 4-> 3 CO CO O o ^J U cu o 60 & CO 4-1 u cu CU C 4 m ON CN m rH f~- o\ st O en r^. en r-«. st r^ o Pi Ph rH m rH en iH en rH en > st ro r- o O rH m rH H U st r^ m oo O Pi P-. <-\ en r-i en rH en rH en Pn H ^d oo -cr 00 St r~- ^o oo en § rH st rH O CN v£> ■H r-» st 00 oo r^ 00 en Pi CN r» en rH cn rH en CN ^D en oo st ON st o> 00 en H Q Pi CN r^ O CN vD H w 00 O C/D PQ <3 < in > PQ S3 ^ I 3 g; > r4 P o 3 °y 1 1 M S3 Pi H 5J en H H / < H H M H Pi C3 o o :s Pi H PQ W 3> 13 C/3 £3 H PQ H cn a • O rH •H rH 4_i a) o o cu 3 4= m-i 3 O -H U " CU >^ 43 rH S CU 3 > G -H 4-1 cu a oo cu co a w CO ai cu > w co cu CO 4= & 4J O u 3 S-i 3 cu CO o CU rH 4-1 CO T3 oo 3 CO J-l cu 43. e 3 3 U cu & 3. 3 3 •H cu 3 00 3 3 O V4 4= CU CO > 3 CU U CU 3 42 H 166 RDTCNT MINI 2 PROCI SUBSTI GTMERG PRIIFF PROCIV PROCCE Less effective More effective MINI2 RDTCNT SUBSTI PROCI GTMERG PRIIFF PROCIV PROCCE Less time-consuming More time-consuming Fig. 5.2-1 General tendency of effectiveness and efficiency of the trans- duction subroutines which can treat fan-in/fan-out restrictions. 167 START I CALL ONE OF THE INITIAL NETWORK SUBROUTINES UNIVSA, THRLEV, BANDB and TISON SELECT ONE OF THE TRANS- DUCTION SUBROUTINES UNDER NO FAN- IN /FAN-OUT RESTRICTIONS AND CALL IT CALL JEFF STOP Fig. 5 . 2-2 Experiments for comparing subroutine PROCV with subroutines RDTCNT, PROCI and SUBSTI. These loops will be repeatedly applied until there is no further improvement in the cost. 168 Table 5.2-7 Results for experiments shown in Fig. 5.2-2, Initial network subroutine UNIVSA is used. \ l-l H > s oo CTi CN H H en CN m o m oo CN H H m H H CN CN O as H H CN O CN CN o m Fn m vD Fn pH Fn O CO 00 00 oo v£> CN CN o CM CM O ON 00 o 1 < CO > M -i X w D ■u [fl H 3 -M W S-i OJ o u :■■ 4-1 H cu n3 C 4-' C .-i (U nj 6 •H 'H jj >-i ■H 0) C a. m X UJ CO 2 H CO O O NO H H H H H H o CM 00 CM 00 CNI o NO co NO co m co CO CO m 00 CN| m o o o ON on CO o on nO oo o CM CO CO ON CO m CM CO CM o CO NO CM CM CO H H CM m CM m NO CM CO CM ON r-i nO nO CM 0O CM H H O 00 CM CO 00 00 CO CM CO r-. 00 m NO on NO CO oo co NO H H NO m m oo CM CO CO no nO H H m H H on CM o o NO m CM O CM O H H ON CM o r-i O NO m CM o CM o co H H CM O O nO CM O CM CO CM O o no m CM O CM O CM H H CM CM O o CM o CM m CM O ON CM O m co o m CM o CM ON o ON m m o o ^3" ON CM o m m O co On CO CM O O m CM o CM m CM O CM m CM o CM m CM © CM H H CM CM o o CM O CM NO CM O CM CM O co o m oo NO 00 NO o NO 00 M co H ON CO w u o o o co Fn NO m CM o CM i-> M > 5 Xi OJ cfl 3 3 •u w ti rH •H 3 ^ +J w i-i G QJ o o y> s u 4_) s-x i-H d- NO ON CM CO o ON ON o CO 178 en c o • •H ~ i u Q) u en a - ~ <4-4 en •H 0> H XI > n W •H H u g nl X > H CO oo CM o CO CM CO O co o ON CM co o co o ON 00 o CM m CM 00 00 CM m CM 00 CM 00 o 00 m CM CM o o CM CM o o CM CM O O m < Q ON m o CM ON o CO oo o CM in vO CM ON CO 00 m ON m in o oo Pn ON 00 CM o co 00 CM CO CO CM o CM O CM CM O CM o CO CM CM O CM CM O o CO 00 00 00 ON CM CM CM co o> o ON m co ON CM CM O CM CM O ON oo o ON CM CM o ON CM CM O ON CM CM O ON CO ON < 179 w C o • •H T3 4-1 (U O t/5 C 3 3 «4-( 05 •H 0) iH •s > 5 W T 1 ^ Vj a! cd S f S 13 W 3 at 4J 0) 3 iH ti 3 ^! •H W M 4-1 CM CM CM o o -3- oo CO o co CO co m o CM CO o 00 CM o CM On CO m CO 00 00 ON 00 00 CO CM m oo ON oo CM m CM CO 00 on o 00 r^ -* CM co CM m m CM m o CM CM m m o CM co oo m CM oo on o o CM CO CM o -3- CO CM CO m CM O CM O CM <1" CM O CM CM O CM m CM o CM m CM O CM CM O o CM O CM CO CM o m CM o CM m CM o CM CM CM O o CM o CM O CO o m CO o m CM o co a\ o o CM CM o CM CM O O CM o CO CM o CO CO o m CM O CO on o o CM CM O m 00 vO 00 o 00 PQ ON CO w o m O O co v£> < u PQ 3 Fn 00 -3- 00 w on 00 00 m o ON CM o o CM 180 to c o • •r-l X) 4-J 0) CJ 7) C 3 D IM Cfi •H 0) i— 1 -O > « w •H ,-) >-i Pi rfl PC > H o 4-1 >-4 5 C 4-1 G r-\ V U rd C ^-^ 4-' C -H QJ a) e -h •H 4-) >-i -H a> c O- M V- W on m m vO H H H H H H m H H CN H H H H nO H H in H H H H ol H H CN H H H H CN ON on m m CNI CN o On pq cj> o nO ON on oo o m NO ON 1^ CN O CN O CN CN 1-^ oo NO nO NO m oo oo CN O On CN o on m CN o 00 CN CN o m o nO o 00 NO o 00 NO o 00 o •J- 00 On m oo NO CN ON O ON on m oo m on ON 00 CN O CN O on o njO o ON CN on O m o on o pq -l 3 4-1 «H Qi CT3 e 4-' c rH 0) Cfl e ■H •H 4-J M ■H 0) C CX H X w CO u 2 H O o M0 H H m H H H H co H H CM H H H H M3 H H m H H H H H H cm H H H oo CO CM m CO CM CM CM co co CM. O On CM o m CM M0 00 O m 00 mo m on o CO oo ON 00 m oo o on m o o\ CO CO ON on M0 ON ON M0 m on m M0 CM CM CM o co CM ON CO 00 CM CM O CO 00 CM 00 00 ON M0 m o r-. ON 00 CM o 00 CM MO MO M0 CO M0 CM O 00 CM o m m CM CM CO CM M0 00 CM O ON 00 O ON o CO o o CM CM o CM O CM o o m CM o CO CM o CO o CM o o o 00 M0 CM o CO ON o 00 CM CM o co o CM o o o 00 ON CM o m ON o oo CM O co < W Pn M0 Pn CM M0 M0 00 o CM < m m MO Pn O CO 00 M0 00 ON in CM co CM M0 CM o iH CM O ON CM o CM CM O ON CM CM o ON 00 o ON On M0 00 00 r-i M0 m mo cm o ON M0 PQ ON < 182 CO c o • •H XI 4-1 PQ H 4-i M 3 O O U-i 5-i /■ — s rO T3 U) 3 CO ■u to 3 rH c 3 ^ •H to u ■U CU G C >-i 3 o 4-1 o i— 1 0i N_^ to c 4-' C rH OJ rs B -H •H jj V-i -H OJ C O. M X w tn u H CO O CJ> H H UO H H H H co H H CM H H H H O CO CO CN o> oo CO H H H H co H H CM H H H r*H oo CO CM CO co CN o 00 00 o oo oo LO oo co CO co co v£> m o o m CM m oo •o- m oo o CO o 00 o m m oo oo O m m oo oo CM 00 co o rH m CM o ON 00 o> o vO CM CO CM o o CT\ O ON m CM o CO m CM o CO o CO o CM CM o o o CM o CO CM o m CM o CO o CM o CM o CM CM o m 00 -3- o 00 PQ co rH ON co w CJ) o o o co Pn o CM o o^ PQ <: Pn 00 m m CM CM CM co CM rH CM rH CM O ON 00 v© r^ CM in m m CM CO .H CM O o CM O o 00 w o> O CM 183 (U C •H 4J c o c_> 03 c o • •H XI ■U QJ CJ UT c 3 IU CO •H OJ H -O pq 0) Q •H > PQ ~ st a) c m •r-l 4-1 Vj 3 O O 14-1 S-i X 03 3 4-1 01 H 3 ^ W M -< M ccj H > X> «_• .— 1 0) Cti C 4-' C r-i 0) cd E -H •H 4-1 l-i -H (U c a, m * u U W H CO O c_> nO H H m H H H H H H H H H H vO H H m H H H H cn H H H H H CN O •vT CN o CN as oo PQ CN LO 00 0> ^D O 00 <£> O CO vC o oo vj3 O co o o CN co cn co CN 00 CO CO CO CN m o o ro co ON CN o 00 o o r->. co o O CO 187 Table 5.3-6 Numbers of best networks obtained by different combina- tions of initial network subroutines and TT-sequences INITIAL NETWORK SUBROUTINE TT-SEQUENCE TT1 TT2 TT3 TT4 TT5 TT6 UNIVSA 13 12 15 20 22 27 THRLEV 12 13 16 21 21 26 BANDB 15 16 21 25 18 21 TISON 8 9 19 25 23 24 188 M i u 0J '-4 3 4-1 .H u iH c iH OJ OJ > ■H o 4-1 •H 4^ c X C "H dJ ,fl ■H U-l — i u CJ J3 c '/. 4-J 3 c 1*4 ,d ■H u X ■U ■H u 03 -3 0! c 3 a ■H X 'H s c >-. m o 14-1 T3 OJ n aj x. -a c 4-1 a ■H c C3 -a OJ 4-J c 3 J=> 03 cr O 03 (0 OJ 4-1 1 1-4 ^H H 03 3 H cn in 3 o 'X CO 03 •H OJ 4-1 3 •H «H C 4J •H 3 O U-4 U O XI 3 C O •H 4-1 CO c •H e o u 03 OJ u c 0) 3 cr OJ 03 03 I Ai H ^ H O 4-J C OJ CO C 4-1 4-» 03 03 OJ O PQ C_) C_> CO 03 03 DJ CJ c c o 4-1 4-1 03 03 OJ O pa c_> u PM vD CM" 00 pa v_5 kO m vO PQ in en ^_^ H P-4 W u w cc CM m PQ C* > w H H H o> CM a> en PQ PQ cn S5 o ^> C/3 H H H H H H CM H H O o cn PQ PQ H H H co o 189 be derived if either TT-sequence TT4 or TT-sequence TT6 is applied. These re- sults mean that in order to get results with very good costs, the combinations of BANDB-TT4 or BANDB-TT6 are more desirable. Table 5.3-8 Number of overall best results obtained when a specific initial network subrou- tine is applied INITIAL NETWORK SUBROUTINES INVOLVED No. of overall best results derived UNIVSA 16 THRLEV 13 BANDB 22 TISON 7 Table 5.3-9 Number of overall best results obtained when a specific initial network TT- sequence is applied TT-SEQUENCE APPLIED No. of overall best results derived TT1 13 TT2 14 TT3 17 TT4 24 TT5 20 TT6 24 Another interesting statistic is the average cost per function for dif- ferent combinations of initial network subroutines and TT-sequences . This is shown in Table 5.3-10. Again, we find from this table that the combination of BANDB and TT4 produces the best average cost, and the combinations involving BANDB and/or TT4 or TT6 usually produce networks with better average costs. 190 Table 5.3-10 Average costs per function for different com- binations of initial network subroutines and TT-sequences INITIAL NETWORK SUBROUTINE TT-SEQUENCE TT1 TT2 TT3 TT4 TT5 TT6 UNIVSA 9.60 ^ /20.47 9.73 /20.40 9.10 /19.77 8.97 /19.47 8.73 /19.33 8.30 /18.63 THRLEV 9.87 /20.40 9.90 /20.47 9.37 /20.17 8.87 /19.57 8.77 /19.23 8.47 /18.67 BANDB 8.98 /18.50 8.80 /18.17 8.60 /18.47 8.00 /17.80 8.67 /18.63 8.33 /18.10 TISON 9.83 /18.50 9.47 /19.43 9.77 /19.83 9.17 719.13 9.20 719.00 8.93 /18.87. * R av/ The average cost is expressed as C , where R av and C av are the average number of gates and connections, respectively. So far the analyses are all for costs. For comparing computation times, other two tables are shown below. Table 5.3-11 gives the average com- putation time per function for different combinations of initial network sub- routines and TT-sequences. Besides, we can get the ratio of computation times by using the time spent by the combination UNIVSA and TT1 as the base. This result is shown in Table 5.3-12. Table 5.3-11 Average computation time per function in centiseconds for different combinations of initial network subroutines and TT-sequences. INITIAL NETWORK SUBROUTINE TT-SEQUENCE TT1 TT2 TT3 TT4 TT5 TT6 UNIVSA 30.01 215.43 199.17 307.80 338.33 284.13 THRLEV 76.13 183.57 220.90 290.77 317.50 256.27 BANDB 75.57 158.00 175.33 232.23 255.40 256.30 TISON 73.33 181.07 184.33 274.33 288.97 245.37 191 Table 5.3-12 Rate of computation times. The time spent by the combina- ion UNIVSA and TT1 is used as the base. INITIAL NETWORK SUBROUTINE TT-SEQUENCE TT1 TT2 TT3 TT4 TT5 TT6 UNIVSA 1 7.18 6.64 10.26 11.28 9.47 THRLEV 2.54 6.12 7.36 9.69 10.58 8.54 BANDB 2.51 5.27 5.84 7.74 8.51 8.54 TISON 2.44 6.03 6.14 9.14 9.62 8.17 Table 5.3-11 and Table 5.3-12 indicate that TT-sequence TT1 is less time- consuming than other TT-sequences whereas TT-sequences TT4, TT5 and TT6 are more time-consuming . The experimental results for 5-variable functions are analyzed in a similar manner. Table 5.3-13 through Table 5.3-16 give network costs and com- putation times. The best results for each function are marked with circles in each table. The numbers of best networks obtained by different combinations of initial network subroutines and TT-sequences are given in Table 5.3-17. The overall best results and the combinations of initial network subroutines and TT-sequences from which the overall results are derived are given in Table 5.3-18. Again, the number of overall best results obtained when a specific initial network subroutine and a specific TT-sequence is applied are given in Table 5.3-19 and Table 5.3-20, respectively. 192 (/) c o • •H T3 4-1 11 a tn c 3 3 H-l CO •H a) i-i 43 < •H > M crj T, r> u m -i 5 4-1 .-i 1) crj c ■u' t I— 1 QJ cd g •H •H 4-1 M •H a) C CX M K W co rH I ro in rH m H vO r^ m 00 in r~- CN 00 CN vO CO H CN 00 CN m O -cr 00 CN n in E-t rH - m r-^ O en CO co cr n CN r^ o r^~ in ^"* CN v© co in CO n o VJO rH 00 CO CO H CN CN rH rH CN rH rH CN rH 3% ON m CN CN rH ^o CO in CN 00 1— 4 co rH co 00 ON co CN On CN f~* m en ON CO in ON o 00 m H 00 r-^ M3 vO rH r~- O in co rH H rH sf r^. 00 rH ^£> ON o CN O rH rH rH rH rH rH r-4 ON ON ro m CN r>- r^- CN r>. rH H rH o\ 00 rH V7 \7 rH rH \J rH V — 7 v7 rH /o\ ON /md\ in /co\ A ' rH /o\ /Ol \y \^/ \y vy A ro vO m CN fcA /CA CO CN O CO / — =3- 1 » CO in m rH 1 vol CO m vO rH rH rH rH rH rH \7 rH rH rH r~- CN -d- m rH rH in rH CN ON H H Pn w W < ON PQ Pn vO UNCTI EXADE i-> .1) O in a 3 o U-l in ■H 01 rH rO > nj W •H £ (d 3 > i H m 0) o rH u H 3 o O iw M XI U) 3 u in H a -Y in l-i OJ o U 3 i-j rH H on ^o r-H CM CM en VO 00 CM 00 H CM CM r-H CM r-H r-H en CM -3- r^ O r-H en ^O 00 ON r^ vO O ^"\ H on CM r-» m CM m ON ON m CM CO H r-H en 00 in m CM r^» m r-~ \o CM rH r-\ rH rH rH rH rH rH rH w / <*"-< /I- 1 - m/cj -a E-f X / pl - / vO 00 en O m en Q o <: w Pn rH Pm ■ rH CM O 00 \0 en 00 en 00 PQ r*» O / 1 U- o u M W <3 CJ> vO w vO 00 fe m Q w U/H C/ fe VO (i< la W < ON PQ K vO / H / | m 0) o c rH •1-1 JJ >-i 3 O o >4-l >-l ,Q ^ to V-i OJ o ^1 3 4-J r-l OJ rcj a ■u' & H CU CT3 G •rl •H JJ >-i •H CU C CU H X w I CI in H -Q cd H to u H CO O C_) NO H H in H H H co H H CNl H H nO H H m H H H co H H CM H H H O CM on O CM m 00 00 oo no oo m oo oo oo CO o m ON O -d- co co no o on 00 o m m CO on CO m o 00 CN o m on o co m CO o o NO CM 00 00 00 o CM nO 00 CO o CO H r-i CO 00 m CM CN CM 00 m CN o CM O ON st CO CO o nO o ND oo CN m nO in CM ON o ON Csl m o NO m oo CO nO CO o CO CO o co CM m NO 00 V3" ON O o CO co co NO CM ON CM CO o m oo m oo oo oo NO in oo on co co nO CM ON no ON nO m ON NO t-H CO O ON ON CM o CM O 00 CO CO o CN CO o co CO o CM ON CO o m CO o CM m co o CM CM CO o co CO o CM 00 o 00 o CO o co CO o NO CN O o CM co O O NO co o co 00 CO o m O m o On CM CO o co o CO NO CN O o CM co o o NO CO o co nO m On CM < Pn 00 t-H Pn P P U NO < CO Pn H < 00 NO Pn o CN m NO W H m Pxl PQ CO vO W ON m CO o i-H 00 00 00 < o NO p co NO CO Pn ON -3- o Pn ON o 00 m pq oo oo NO CM O co ON m CO co o NO co ON o co •o- o o o o < P NO o pp P Pn PQ On m NO co NO oo NO CO m m ON CM w CO o H pa NO 195 tfl C o • ■H •a ■u d [fl (3 3 3 IH a •H i H LH QJ n C rH •H (J M 3 O O U-I M -Q 0] 3 4-1 CD H 3 Jd Efl M 0) O H 3 u H CD ct) C 4_' c rH 01 cd 6 •rH •H J-J U ■H (U C O- M X w NO CO m 0) rH H to H to o NO H m H H H H m H H CM H H no H H m H H H H co H H cm H H H NO on NO ON oo CM O CM nO O co oo CM CM nO CM CM ON 00 CO 00 o CO CO co CO 00 m CO o OO ON r-l NO ON co CO oo CO ON CO rH m LT) CO CO NO 00 00 o nO co CO NO f-«. ON CO CM CM CO ON ■vJ- O CO co NO 00 NO 00 NO CM NO o 00 CO LT) ON CM o CM CM CO O CM ON o NO 00 CO CM NO o ON CM CM U~\ O CM "J- CO o o CO CM [^» ON CM NO co NO CM o CM o CM o o CM o CM o NO m o CM CM O m o o NO CM o ON o r-- CM o CM co o- o ON o m o rH CM O CM o CM ON CO O NO rH m ON CM < Pn -d- oo rH Pn P P NO CO Pn rH < 00 NO Pn CO o CM NO w w m W CO NO w ON co o rH 00 CO 00 < o NO p CO NO CO Pn ON o Pn ON o CO u-i PQ 00 00 o m CO NO m CM O m CM m o m m ON NO 197 The average cost per function for different combinations of initial network sub- routines and TT-sequences is shown in Table 5.3-21. From the previous tables for analyzing network costs for 5-variable functions, we get the similar conclu- sions as in 4-variable case; that is, the combinations of BANDB-TT4, BANDB-TT5, or BANDB-TT6 usually produce networks with very good costs. Table 5.3-19 Numbers of overall best results obtained when a specific initial network subroutine is applied. INITIAL NETWORK SUBROUTINE NO. OF OVERALL BEST RESULTS OBTAINED UNIVSA 2 THRLEV 3 BANDB 6 TISON T able 5.3-20 Numbers of overall best results obtained when a specific TT-sequence is applied. TT-SEQUENCE NO. OF OVERALL BEST RESULTS OBTAINED TT1 1 TT2 2 TT3 3 TT4 4 TT5 5 TT6 6 Table 5.3-21 198 Average cost per function for different combinations of initial network subroutines and TT-sequences. INITIAL NETWORK SUBROUTINE TT-SEQUENCE TT1 TT2 TT3 TT4 TT5 TT6 UNIVSA 15.6 /38.7 14.8 /37.0 14.6 /37.8 13.6 /37.1 14.2 /37.3 14.8 /38.4 THRLEV 16.1 /39.1 14.8 /36.9 14.8 /38.2 14.0 /37.0 14.0 /35.9 13.8 /36.3 BANDB 13.7 /35.7 13.9 /35.5 12.8 /35.4 12.8 /34.7 13.6 /38.4 13.6 /36.1 TISON 16.6 MO. 8 15.7 /39.0 16.5 /42.2 15.5 /39.9 15.6 /39.4 15.7 /39.4 Average numbers of gates and connections are shown by upper and lower figures, respectively, in each cell. The computation time is analyzed in Table 5.3-22 and Table 5.3-23. Table 5.3-22 shows the average computation times for different combinations of initial network subroutines and TT-sequences whereas Table 5.3-23 gives the ratios by using the time spent by UNIVSA and TT1 as the base. Again, we get the similar conclusions as the 4-variable case: TT1 is the least time-consuming TT-sequence whereas TT5 and TT6 are usually more time-consuming than other TT-sequences. Table 5.3-22 Average computation times in centiseconds for different combinations of initial network sub- routines and TT-sequences. INITIAL NETWORK SUBROUTINE TT-SEQUENCE TT1 TT2 TT3 TT4 TT5 TT6 UNIVSA 342.2 1030.0 1411.3 1735.4 2270.7 1966.3 THRLEV 299.8 914.2 1287.4 1639.7 1834.1 1542.0 BANDB 341.3 709.9 765.6 1205.0 1683.7 1426.7 TISON 209.9 862.6 758.6 1181.4 1335.8 1467.6 Table 5.3-23 199 Ratios of computation times. The time spent by the combination of UNIVSA and TT1 is used as the base. INITIAL NETWORK SUBROUTINE TT-SEQUENCE TT1 TT2 TT3 TT4 TT5 TT6 UNIVSA 1 3.01 4.12 5.07 6.64 5.75 THRLEV 0.88 2.67 3.76 4.79 5.36 3.41 BANDB 0.99 2.07 2.21 3.51 4.92 4.17 TISON 0.61 2.52 2.22 3.45 3.90 4.29 After analyzing the effectiveness and efficiency of each TT-sequence, we have some ideas on how to specify a control sequence to solve given problems under fan- in/fan-out restrictions. But for the users who are not interested in the details about how to specify control sequences, three control sequences pro- vided in the NETTRA system can be used. These control sequences are called con- trol sequences OPTION 1, OPTION 2 and OPTION 3. Users only need to specify the type of these options. The details about setting up data cards for using the NETTRA system is explained in [13]. The contents of three control sequences are listed in Table 5.3-24. OPTION 1 is a control sequence which can usually produce networks with very good costs (TT-sequence TT4 is used) , OPTION 2 is a control sequence which can pro- duce networks with reasonably good costs in a reasonably short computation time (TT-sequence TT3 is used) , and OPTION 3 is a control sequence which can produce networks in a very short time. Some practical problems are used to test these built-in control sequences. Table 5.3-25 shows the results. Apparently, these results satisfy our requirements. For Su-Nam's multiple-output incompletely specified example, the network obtained by the NETTRA system using the control sequence OPTION 1 consists of 6 levels, 15 gates and 29 connections, while the 200 original result obtained by Su and Nam consists of 6 levels, 25 gates and 42 connections [39]; i.e., remarkable reduction in the cost has been obtained. Table 5.3-24 Contents of three built-in control sequences TYPE OF CONTROL SEQUENCE TYPE OF INITIAL NETWORK SUBROUTINES TYPE OF TT-SEQUENCE NO. OF TIMES THAT TT-SEQUENCE IS GOING TO BE EXECUTED OPTION 1 UNIVSA, THRLEV and BANDB TT4 oo OPTION 2 BANDB TT3 oo OPTION 3 UNIVSA TT4 1 For the 3-variable odd parity function and the three-variable even parity func- tion, control sequences OPTION 1 and OPTION 2 can derive networks with 8 gates and 16 connections and 7 gates and 16 connections, respectively. These net- works are optimal under the specified restrictions. The optimality of these results is proved by the integer programming logic design program based on the branch-and-bound method [25], It is known that for the four-variable odd and even parity functions, the optimal networks under the specified restrictions have 10 gates and 29 connections and 10 gates and 24 connections, respectively [18]. Control sequences OPTION 1 and OPTION 2 produce the optimal result for the 4-variable odd parity function. For the one-bit full adder, control sequence OPTION 1 produces the optimal network under the specified restrictions in 6.50 seconds. The optimality of this network is proved by the integer programming logic design program based on the implicit enumeration method, spending 154.34 seconds [25], and also by the integer programming logic design program based on the branch-and-bound method, spending 14.80 seconds. 201 Table 5.3-25 Results for testing three built-in control sequences PROBLEMS RESTRICTIONS OPTION 1 OPTION 2 OPTION 3 COST TIME (CS) COST TIME (CS) COST TIME (CS) 3-VAR. ODD PARITY FUNCTION FI = FO = FOX = FOO = 3 * UC ONLY 8016 839 8017 110 10020 73 3-VAR. EVEN PARITY FUNCTION 7017 718 7016 139 10021 42 4-VAR. ODD PARITY FUNCTION FI = FO - FOX = FOO = 4 UC ONLY 10029 6316 10029 1096 13033 323 4-VAR. EVEN PARITY FUNCTION 12040 5577 12036 767 14033 455 5-VAR. ODD PARITY FUNCTION FI = FO = FOX = FOO = 5 UC ONLY 18044 28499 18054 5871 22053 4427 5-VAR. EVEN PARITY FUNCTION 16041 49013 21061 21886 28072 2641 1-BIT FULL ADDER 8023 650 9018 183 9025 37 2-BIT FULL ADDER 16042 24514 18043 6680 23062 2646 2-BIT MULTIPLIER 12025 2826 12025 885 12027 146 SU-NAM's EXAMPLE FI = FO = FOX = FOO = 2 C 1 AND UC 15029 11931 30047 3264 18032 404 UC: uncomplemented external variables C: complemented external variables t 202 Only problems under fan-in/ fan-out restrictions are tested above. Next let us test problems under both fan-in/fan-out and level restrictions. A control sequence OPTION 4 is provided to treat problems according to the flowchart shown in Fig. 4.2-2. Control sequence OPTION 4 consists of initial network subroutine TISLEV and five transduction subroutines, as shown in Table 5.3-26. In this case, each transduction subroutine is applied under both fan-in/fan-out and level restrictions. Table 5.3-26 Contents of the control sequence OPTION 4 INITIAL NETWORK SUBROUTINE TT-SEQUENCE NO. OF TIMES OF APPLICATION OF TT-SEQUENCE TISLEV SUBSTI °°, GTMERG °°, PRIIFF », PROCIV °°, PROCCE °° 1 Each transduction subroutine in this TT-sequence is to be ap- plied under fan- in/fan-out and level restrictions, and each transduction subroutine will be applied repeatedly until there is no further improvement in the cost. It was mentioned in Chapters 2 and 4 that the approach shown in Fig. 4.2-2 does not guarantee that a network satisfying the given restrictions can be obtained even if there do exist feasible networks. However, the experi- mental results in Table 5.3-27 and Table 5.3-28 show that this approach is reasonably good. In Table 5.3-27, ten 4-variable functions are tested; the fan- in/fan-out restrictions are set as FI = FO = FOX = F00 = 3, the maximum 203 number of level permitted (denoted by LEVLIM) is 4 and 5, and only uncomple- mented external variables are permitted as inputs. When LEVLIM = 4, seven feasible networks are obtained; and when LEVLIM = 5, feasible networks are obtained for all functions. In Table 5.3-28, ten 5-variable functions are tested; the fan-in/fan-out restrictions are set as FI = FO = FOX = F00 = 4, the maximum number of levels permitted is 4 and 5, and both complemented and uncomplemented external variables are permitted as inputs. When either LEVLIM = 4 or LEVLIM = 5, we obtain feasible networks for all functions. The results obtained for 10 5-variable functions are also compared with the results obtained by the integer programming logic design program based on the branch-and-bound method in Table 5.3-29. The integer programming logic design program based on the branch-and-bound method cannot produce any optimal networks within two minutes. It only produces two intermediate net- works; and for Function 7 the intermediate result is even worse than the re- sult obtained by the control sequence OPTION 4. 204 Table 5.3-27 Experimental results for testing the control se- quence OPTION 4 FUNCTION (4-VAR.) ■ FI = FO = FOX = FOO = 3; uncomplemented inputs only LREST - 4 LREST = 5 COST TIME (CS) COST TIME (CS) 1 . 4AF1 8021 167 8021 182 2. FBFE 8014 111 8014 123 3. ABCE * 7017 504 7017 274 4. 2D8B 13026* 922 13026 405 5. 9DA5 7018 116 6015 117 6. 5F12 7013 95 7013 85 7. F1F4 7014 85 7014 84 8. 6830 11021 288 8019 225 9. 9048 14026* 687 14026 425 10. EA9B 9019 167 9019 183 These results are not level-restricted 205 Table 5.3-28 Experimental results for testing the control sequence OPTION 4 FUNCTION (5-VAR.) complemented and FI = FO = FOX = FO0 = 3; uncomplemented inputs LEVLIM = 4 LEVLIM = 5 COST TIME (CS) COST TIME (CS) 1. 4FA295F6 19043 928 17041 2660 2. A6CDDF18 16040 996 15036 957 3. FF68A153 13033 1257 14034 1173 4. 1EE65240 12030 577 12030 716 5. 9E63BE75 16036 1251 16036 1077 6. 0A888103 11026 504 9021 375 7. 49F363CD 14033 1641 12030 1738 8. 8B5809F0 11028 756 10026 595 9. BFD6C6DA 14036 4485 14036 2494 10. C6E7103E 13034 1199 13032 1602 206 Table 5.3-29 Comparison between the NETTRA system based on the branch-and-bound method using OPTION 4 and the program RESTRICTIONS ^V COST FUNCTI0NS\ X & (HEX) \TIME LREST = 4 FI = FO = FOX = FOO = 3; complemented and uncomplemented inputs RESULTS BY THE TRANSDUCTION PROGRAM THE RESULTS BY BRANCH-AND-BOUND METHOD COST & TIME (CS) COST & TIME (CS) 1. 4FA295F6 19043 928 CS s \ NO RESULTS AFTER TWO MINUTES 2. A6CDDF18 16040 996 CS 3. FF68A153 13033 1257 CS 4. 1EE65240 12030 577 CS 5. 9E63BE75 16036 1251 CS INTERMEDIATE RESULTS 14038 12000 CS 6. 0A888103 11026 504 CS NO RESULTS AFTER TWO MINUTES 7. 49F363CD 14033 1641 CS INTERMEDIATE RESULTS 15039 12000 CS 8. 8B5809F0 11028 756 CS > NO RESULTS AFTER TWO MINUTES 9. BFD6C6DA 14036 4485 CS 10. C6E7103E 13034 1197 CS 207 6. Conclusions In this paper, the organization of the entire NETTRA system is intro- duced. Many experiments have been made to find out the effectiveness of the NETTRA system. The current version of the NETTRA system can design near optimal, multiple-output, multi-level and loop-free NOR (NAND) -gate networks under fan- in/fan-out restrictions and/or level restriction. The problem size can be up to five external variables and ten output functions; each function may be com- pletely or incompletely specified and both complemented and uncomplemented ex- ternal variables or only uncomplemented external variables are allowed as in- puts. Since all programming variables in the current version of the NETTRA system are 4-character integers, the system can be modified to treat problems with larger problem size by using 2-character integers as programming variables. The experimental results given in this paper indicate that the NETTRA system is very effective in finding near-optimal solutions for the given pro- blems. For switching functions with very few number of gates (around 9 through 12 gates) , the NETTRA system can often produce networks which are really opti- mal. For the switching functions with many gates, the NETTRA systen cam pro- duce networks with reasonably good costs in a short time that usually the integer programming logic design programs based on the branch-and-bound method and the implicit enumeration method cannot get any feasible solution. Comparing with other methods such as transformation methods, the NETTRA system is generally much more powerful. Hence the NETTRA system appears to be a very useful and powerful tool for logic design of large NOR (NAND) networks. 208 The explanation of how to use the system is given in the programming manual [13]. The network transduction program NETTRA-E3 is not included in the NETTRA system because this program requires too much core storage. Since this program realizes the "multiple-path" application of the error-compensation pro- cedures, it usually produces very good results if enough computation time is allowed. How to use this program is detailed in [21]. 209 References [1] Culliney, J.N. , "Program manual: NOR network transduction based on connectable and disconnectable conditions (Reference manual of NOR network transduction programs NETTRA-G1 and NETTRA-G2)," UIUCDCS-R- 75-698, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., Feb. 1975. [2] Culliney, J.N. , H.C. Lai, and Y. Kambayashi, "Pruning procedures for NOR networks using permissible functions (Principles of NOR network transduction programs NETTRA-PG1, NETTRA-P1, and NETTRA-P2) , UIUCDCS- R-74-690, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., Nov. 1974. [3] Cutler, R.B., et al, "TISON-VERSION 1: A program to derive a minimal sum of products for a function or set of functions which may not be completely specified," to appear as Report. Department of Computer Science, University of Illinois, Urbana, 111. [4] Davidson, E.S., "An Algorithm for NAND Decomposition of Combinational Switching Systems", Ph.D. dissertation, Department of Electrical Engineering and Coordinated Science Laboratory, Univ. of Illinois, Urbana, 111., 1968. [5] Dietmeyer, D.L. , and Y.H. Su, "Logic design automation of fan-in limited NAND networks," IEEETC , Vol. C-18, No. 1, Jan. 1969. [6] Ellis, D.T., "A synthesis of combinational logic with NAND or NOR elements," IEEE Trans., vol. EC-14, pp. 701-705, Oct. 1965. [7] Gimpel, J.F., "The minimization of TANT networks," IEEE Trans., vol. EC-16, pp. 18-36, Feb. 1967. [8] Hellerman, L. , "A catalog of three-variable OR-INVERT and AND-INVERT logical circuits," IEEE Trans., vol. EC-12, pp. 198-223, June 1963. [9] Hohulin, K.R., "Network transduction programs based on connectable and disconnectable conditions with fan-in and fan-out restrictions (A des- cription of NETTRA-G1-FIF0 and NETTRA-G2-FIF0) ," UIUCDCS-R-75-719, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., April 1975. 10] Hohulin, K.R., and S. Muroga, "Alternative methods for solving the c-c table in Gimpel 's algorithm for synthesizing optimal three level NAND networks," UIUCDCS-R-75-720, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., April 1975. 11] Hu, K.C., "NOR(NAND) network design; error-compensation procedures for fan- in/fan-out restricted networks (NETTRA-E1-FIF0 and NETTRA-E2-FIF0) ," Report No. UIUCDCS-R-77-847, Dept. of Computer Science, University of Illinois, Urbana, 111. 210 [12] Hu, K.C., "Level-restricted NOR network transduction procedures," Report No. UIUCDCS-R-77-849, Dept. of Computer Science, University of Illinois, Urbana, 111. [13] Hu, K.C., "Programming manual for the NOR network transduction system," to appear as Report. Dept. of Computer Science, University of Illinois, Urbana, 111. [14] Kambayashi, Y. , and J.N. Culliney, "NOR network transduction procedures based on connectable and disconnectable conditions (Principles of NOR network transduction programs NETTRA-G1 and NETTRA-G2)," to appear as Report. Dept. of Computer Science, University of Illinois. [15] Y. Kambayashi, H.C. Lai, J.N. Culliney and S. Muroga, "NOR network transduction by error compensation (Principles of NOR network transduc- tion programs NETTRA-E1, NETTRA-E2, and NETTRA-E3)," to appear as Report, Dept. of Computer Science, Univ. of Illinois, Urbana, 111. [16] Kambayashi, Y. , H.C. Lai, and S. Muroga, "Transformation of NOR networks," to appear as Report. Department of Computer Science, University of Illinois, Urbana, 111., [17] Kambayashi, Y. , and S. Muroga, "Network transduction based on permissible functions (General principles of NOR network transduction NETTRA pro- grams)," UIUCDCS-R-7 6-804, Dept. of Computer Science, University of Illinois, June 1976. [18] Lai, H.C, "A study of current logic design problems, part II," Ph.D. thesis, 1976. [19] Lai, H.C, "Program manual: NOR network transduction by generalized gate merging and substitution (Reference manual of NOR network trans- duction programs NETTRA-G3 and NETTRA-G4)," UIUCDCS-R-75-714, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., April 1975. [20] Lai, H.C. and J.N. Culliney, "Program manual: NOR network pruning pro- cedures using permissible functions (Reference manual of NOR network transduction programs NETTRA-PG1, NETTRA-P1, and NETTRA-P2) , UIUCDCS-R- 74-686, Dept of Computer Science, Univ. of Illinois, Urbana, 111., Nov. 1974. [21] Lai, H.C. and J.N. Culliney, "Program manual: NOR network transduction by error-compensation (Reference manual of NOR network transduction programs NETTRA-E1, NETTRA-E2, and NETTRA-E3)," Report No. UIUCDCS-R-75- 732, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., June 1975. [22] Lai, H.C. and Y. Kambayashi, "NOR network transduction by generalized gate merging and substitution (Principles of NOR network transduction programs NETTRA-G3 and NETTRA-G4)," UIUCDCS-R-75-728, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., June 1975. .'I I Lee, H. and E.S. Davidson, "A transform for NAND network design," IEEE Trans., vol. C-21, pp. 12-20, Jan. 1972. Legge, J.G., "The design of NOR-networks under fan-in and fan-out constraints (A program manual for FIF0TRAN-G1)" , Report No. 661, Department of Computer Science, University of Illinois, Urbana, 111., June 1974. Liu, T.K., K.R. Hohulin, L. Shiau and S. Muroga, "Optimal one-bit full adders with different types of gates," IEEE Transactions on Computers, Vol. C-23, No. 1, January 1974, pp. 63-70. McCluskey, E.J. and T.C. Bartee, "A survey of switching circuit theory," McGraw-Hill, New York, 1962. McCluskey, E.G., "Logical design theory of NOR gate networks with no- complemented inputs," Proc . 4th Ann . Symp . on Switching Circuit Theory and Logical Design , pp. 137-148, 1963. Maley, G.A. and J. Earle, The Logical Design of Transistor Digital Computers , Englewood Cliffs, N. J. : Prentice Hall, 1963. Muroga, S. , "Logical design of optimal digital networks by integer pro- gramming," Chapter 5 in Advances in Information Systems Science , Vol. 3, edited by J.T. Tou, Plenum Press, pp. 283-348, 1970. Muroga, S., Threshold Logic and Its Applications , Chapter 14, Wiley- Interscience, 1971. Muroga, S., Logic design and switching theory, class notes, Dept . of Computer Science, Univ. of Illinois, Urbana, 111. Muroga, S. and T. Ibaraki, "Logical design of an optimum network by integer linear programming - Part I," Report No. 264, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., July 1968. Muroga, S. and T. Ibaraki, "Logical design of an optimum network by integer linear programming - Part II," Report No. 289, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., Dec. 1968. Muroga, S. and T. Ibaraki, "Design of optimum switching networks by integer programming," IEEE Trans., Vol. C-21, pp. 573-582, June 1972. Nakagawa, H.C. Lai and S. Muroga, "Pruning and branching methods for designing optimal networks by the branch-and-bound method," Report No. 471, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., Aug. 1971. Also International Journal of Computer and Information Sciences, Sept. 1974. Nakagawa, T. and S. Muroga, "Comparison of the Implicit Enumeration Method and the Branch-and-Bound Method for Logical Design", Report No. UIUCDCS-R-71-455, Department of Computer Science, University of Illinois, Urbana, 111., June 1971. 212 [37] Nakagawa, T. and H.C. Lai, "A branch-and-bound algorithm for optimal NOR networks (The algorithm description)," Report No. 438, Dept. of Computer Science, University of Illinois, Urbana, 111., April 1971. [38] Plangsiri, B. , "NOR network transduction procedures: "Merging of Gates" and "Substitution of Gates" for fan-in and fan-out restricted networks (NETTRA-G3-FIF0 and NETTRA-PG1-FIF0) , " Report No. UIUCDCS-R-74-688, Dept. of Computer Science, University of Illinois, Urbana, 111. Dec. 1974. [39] Su, Y.H. and C. W. Nam "Computer-aided synthesis of multiple output multi-level NAND networks with fan- in and fan-out constraints", IEEE Trans. Comput . , Vol. C-20, December 1971. [40] Tison, P., "Generalization of consensus theory and application to the minimization of Boolean functions," IEEE Tec, August 1967, pp. 446-456. [41] Torng, H.C, Theory and Logic Design , Addison-Wesley , pp. 112-126, 1972. [42] White, B.E., "Efficient realization of Boolean functions by pruning NAND trees," September 1969, Lincoln. Lab. Report. BIBLIOGRAPHIC DATA SHEET .in J Subt itle 1. Report No. UIUCDGS-R-77-88 1 ? 3. R<< ipient'i Accession Nm. 4. T, NOR NETWORK TRANSDUCTION SYSTEM (Principles of the NETTRA System) 5. Report Dste August 1977 f. Author(s) K.C. Hu 8- Performing Organization Rept. No. ). Performing Organization Name and Address Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 61801 10. Project/Task/Work (Inn No. 11. Contract /Grant No. NSF DCR73-03421 12. Sponsoring Organization Name and Address National Science Foundation 1800 G Street, N.W. Washington, D.C. 20550 13. Type of Report & Period Covered Technical 14. 15. Supplementary Notes 16. Abstracts The network transduction programs, including NETTRA-PG1, -PI, -P2, -Gl, -G2, -G3, -G4, -El, and -E2 are combined as a large program system named the NETTRA system (NETwork TRAnsduction system). The NETTRA system can design near-optimal, multiple-output, multi-level and loop-free NOR(NAND) networks under fan-in/ fan-out restrictions and/or level restriction. Given function(s) may be completely or incompletely specified and both complemented and uncomplemented external variables are permitted as inputs. The user can specify the control sequence (the types of the initial network methods and the types and the order of the transduction procedures to be applied) to solve his problem. Besides, four control sequences are provided for the users who are not in- terested in the details of how to specify the control sequence. Facilities for treat- ing unfinished jobs due to the expiration of computation time are also provided by the system. 17. Key Words and Document Analysis. 17a. Descriptors Logic design, logic circuits, logic elements, programs (computer) 17b. Identifiers /Open-Ended Terms Computer-aided design, transduction procedures, transformations, near-optimal networks, optimal networks, permissible functions, CSPF, fan-in, fan-out, level, NOR, NAND, NETTRA system, integer programming logic design 17c. COSATl Field/Group 18. Availability Statement Release Unlimited 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 217 22. Price ORM N T1S-35 (10-70) USCOMM-DC 40329-P71 DCftifiHZ 1 1979