No abstract available.

Article Free AccessA resynthesis approach for network optimization Authors: Kuang-Chien Chen Fujitsu America Inc. Fujitsu America Inc.View Profile , Yusuke Matsunaga Fujitsu Labs. Ltd., Japan Fujitsu Labs. Ltd., JapanView Profile , Saburo Muroga University of Illinois University of IllinoisView Profile , Masahiro Fujita Fujitsu Labs. Ltd., Japan Fujitsu Labs. Ltd., JapanView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991Pages 458–463https://doi.org/10.1145/127601.127712Published:01 June 1991Publication History 11citation196DownloadsMetricsTotal Citations11Total Downloads196Last 12 Months13Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The logic networks that can be put on a single chip continues to grow in size and complexity. There is thus an increasing need for designers to rely on the assistance of computer-aided design tools to provide a fast design turnaround and reduce design errors. Logic design (or logic synthesis) is one major step in the ASIC VLSI design cycle in which automation is playing an increasingly important role in recent years. In this thesis, we describe an algorithm, SYLON-REDUCE, that can be used in automated logic synthesis tools for the logic optimization of MOS networks. Most existing logic synthesis algorithms divide logic synthesis into a technology-independent logic synthesis and optimization phase and a technology-mapping phase. This, however, may yield suboptimal final networks. In contrast to this two-phase design approach, SYLON-REDUCE uses a technology-specific approach for the logic optimization of multi-level combinational MOS networks. Given an initial MOS network, SYLON-REDUCE resynthesizes each cell in the network and produces an area- or delay-optimized network which contains only cells that satisfy the same technology constraints or belongs to the same technology library as the cells in the initial network. SYLON-REDUCE uses the concept of permissible functions for more effective optimization. Extensive experimental results demonstrate the effectiveness of SYLON-REDUCE, which generally produces better results than other existing algorithms, including those that employ a two-phase design approach. To make SYLON-REDUCE applicable to a wider range of large, complex networks, we use a windowing scheme for repeated local optimization of these large networks. This scheme also enables the algorithm to optimize the delay of these networks effectively. Experimental results prove this to be a viable approach. Furthermore, SYLON-REDUCE is useful for further improvement of MOS technology-mapped networks. It will also be particularly useful in cell generation or full custom design environments.

For the automated design of PLAs (programmable logic arrays) with a minimum size, computationally efficient procedures are needed that can minimize functions of a large number of variables. For such minimization procedures, excessively long processing time and an excessively large memory requirement are major problems to overcome. An absolute minimization procedure is presented for standard PLAs with reduced computation time and memory space. The improvement achieved by this procedure, which is based on the decomposition of ratio sets, is mainly due to the detection of all essential prime implicants during the derivation of inclusion functions and to the merger of two procedures previously published by R.B. Cutler and S. Muroga (1987) into one efficient procedure.>

This paper presents a timing optimization algorithm SDLR (acronym of SYLON-DREAM Level-Reduction), which is used in the SYLON-DREAM logic synthesizer for speeding up combinational multi-level networks. In SDLR, gates on critical paths are identified and their level numbers counted from the inputs of the network are maximally reduced by a level-reduction procedure. Gates which are not on the critical paths are processed by an area reduction procedure to reduce network area without increasing its maximum depth. SDLR uses the concept of permissible functions in both level and area reduction procedures, and it can directly process networks consisting of simple gates or negative gates (i.e., MOS cells). Experimental results obtained for benchmark functions show that SDLR is an effective algorithm which can reduce network delay with no or minimal area increase.

An algorithm, SYLON-REDUCE, that uses the concept of permissible functions to optimize an MOS network directly is presented. SYLON-REDUCE uses a more coherent, algorithmic approach, adapting the MOS cell synthesis procedure of algorithm DIMN, to resynthesize the cells in the network. Better networks can be obtained for most functions. It is shown that technology-specific synthesis and optimization can produce better results than dividing synthesis into technology-independent and technology-mapping phases.>

SYLON-DREAM, a logic network synthesizer which consists of SYLON-DREAM-INI for designing initial networks and SYLON-DREAM-MIN for further optimization, is presented. Unlike the networks designed by other approaches, those designed by SYLON-DREAM consist of MOS cells satisfying given constraints on the maximum number of series and parallel transistors. Such networks can be easily realized by a cell generator or mapped to the gates in existing cell libraries.>

Based on the new concept of permissible functions, a heuristic procedure to design logic networks with as few gates as possible, without guaranteeing the minimality of designed networks, is developed. This procedure, which is drastically different from conventional logic-design procedures, is called the transduction method, because an initial network designed by any conventionally known logic-design method is first transformed into a different network configuration and then reduced to a simpler network by calculating permissible functions at the outputs of gates and connections throughout the network.>

A heuristic algorithm for assigning input variables to the decoders of a decoded-programmable logic array (PLA) is presented. In this algorithm, the number of inputs to each decoder is not restricted to two and the area overhead incurred by using multi-input decoders is considered in the cost function. Experimental results show that the areas of multi-input decoded-PLAs designed by this algorithm are smaller in many cases than those of decoded-PLAs with two-input decoders or standard PLAs.>

If a logic gate in a logic network of MOS transistors expresses a negative function, which is a logic function that can be expressed as the complement of a disjunctive form of only noncomplemented variables, it is called a negative gate. An algorithm, DIMN, for the design of a MOS logic network with a minimum number of negative gates and irredundant connections among negative gates for a completely specified function was published by the authors in 1985. DIMN is extended here to the case of an incompletely specified function, and an example is given.>

Some new concepts in switching theory are pre sented. One of these is called an "abridged minterm base." We can use an abridged minterm base instead of the minterm expansion in conventional absolute minimization procedures. Since an abridged minterm base almost always has much fewer minterms than are in the minterm expansion, we can derive an abridged minterm base for many functions for which it is impossible to derive the minterm expansion. This paper also introduces the concept of generalized inclusion function Q(f) and its decomposition theorem Q(g)·Q(h) = Q(g V h). The theorem is very useful.

Design of logic networks, in single-rail input logic, with a minimum number of NOR gates for parity functions of an arbitrary number of variables is described. This is partly based on minimum networks for parity functions of a small number of variables which are designed by the integer programming logic design method. Although it is generally difficult to design minimum networks for functions of an arbitrarily large number of variables, we have previously designed minimum networks for adders of an arbitrary number of variables. The minimum networks for parity functions of an arbitrary number of variables discussed in this paper is another case. Many unique properties of minimum NOR networks for parity functions are shown. Minimum networks with NAND gates for parity functions can be easily obtained from those with NOR gates because of duality relationship between NAND and NOR.

When we design networks with NOR or NAND gates which are implemented with bipolar and MOS transistors, wired logic is usually allowed. The usage of wired logic reduces the network cost and possibly improves the speed because of shorter delays on wired logic than on a gate. Typical logic functions performed by wired logic are AND and OR, which are called wired-AND and wired-OR, respectively. Properties of networks with NOR gates and wired-AND (or wired-OR) are discussed. Some of these properties are used in developing synthesis procedures of optimum networks by the integer programming logic design method. For all three-variable functions, the optimum networks with NOR gates and wired-OR's, designed by this synthesis approach, are shown.

This paper first discusses the symmetric property of the minimal covering problem in terms of group theory and then the use of this property in the branch-and-bound method for solving the problem. Computational results on solving sample problems are shown to demonstrate the improvement of computational efficiency of the branch-and-bound method by the utilization of the symmetric property. The sample problems contain the minimal sum derivation of symmetric switching functions, as an application to the design of minimal programmable logic arrays (PLA's). It is shown that when the minimal covering problem derived for the given switching function has symmetric permutations, the given switching function may not be symmetric; although when the given switching function is symmetric, the minimum covering problem obtained from the function is symmetric. The branch-and-bound method based on the symmetric property can be applied not only to symmetric switching functions but also to switching functions which are not symmetric, if the corresponding minimal covering problems have symmetric permutations. The method can be also applied to minimal covering problems which arise outside the minimal sum derivation problems for switching functions.

An n-bit parallel binary adder consisting of NOR gates only in single-rail input logic is proved to require at least 17n + 1 connections for any value of n. Such an adder is proved to require at least 7n + 2 gates. An adder that attains these minimal values is shown. Also, it is concluded that some of the parallel adders with the minimum number of NOR gates derived by Lai and Muroga have the minimum number of connections as well as the minimum number of gates, except for the two modules for the two least significant bit positions.

logic networks of carry–save adders such as high-speed multipliers, multioperand adders, and double-rail input parallel adders are designed based on the parallel adders with a minimum number of NOR gates discussed in [1]. After a discussion of the derivation of carry–save adder modules (CSAM's) by the integer programming logic design method, general design procedures are illustrated with example networks. Compared to conventional networks of carry–save adders, the derived networks of carry–save adder modules (NOCSAM's) have the advantages of fewer gates, fewer connections, and faster operation. In particular, the parallel adder of NOR gates in double-rail input logic obtained has six gates and 15½ connections per stage, whereas the previously known best design under the same condition requires six gates and 17 connections per stage with the same carry propagation delay.

This correspondence presents the results of the synthesis of optimal feed-forward networks of just AND and OR gates for representative functions of the 222 n-p-n-equivalence classes into which all functions of four or fewer variables can be categorized. (Optimality here means minimization of the number of gates as the primary objective and minimization of the number of connections as the secondary objective, regardless of the number of levels. No fan-in or fan-out restriction is imposed.) Based on these results, instructions are given for obtaining optimal networks for desired functions of four or fewer variables which are not representative functions. The branch-and-bound computer program ILLOD-(AND-OR-B) was used to obtain the optimal networks presented.

A theorem about conditionally eliminable prime implicants presented by Chang and Mott1is shown to be incorrect by counterexample.

An algorithm for finding a minimal irredundant disjunctive form representation for an incompletely specified multiple-output switching function presented by P. Tison1is shown to be incorrect by counterexample and corrected.

Parallel binary adders of n bits long in single-rail input logic which have a minimum number of NOR gates are derived in this paper. The minimality of the number of NOR gates is proved for an arbitrary value of n. Also, it is proved that the adders must be a cascade of basic modules and that there exist many different types of basic modules. These adders have fewer gates and shorter net gate delays (or fewer connections) than the widely used carry-ripple adders which are a cascade of one-bit full adders. Design procedures of such adders are described, based on the integer-programming logic design method. There are many solutions but adders with few connections and those with few net gate delays (all these adders have the minimum number of gates) are shown as important examples. Altbough these adders are designed with NOR gates, the results in this paper are applicable to adders with NAND gates by duality conversion.

Based on the intuitive observation that smaller numbers of gates and connections would usually lead to a more compact network on an integrated circuit (IC), a monotonically increasing function of gate count and connection count is concluded to be a reasonable cost function to be minimized in the logical design of a network implemented in IC. Then it is shown that all minimal solutions of such a cost function always can be found among the following: minimal networks with a minimal number of gates as the first objective and a minimal number of connections as the second objective; minimal networks with a minimal number of connections as the first objective and a minimal number of gates as the second objective; and minimal networks which are associated with the above two types of minimal networks. All three of these types of minimal networks of NOR gates, as an example, are calculated by logical design programs based on integer programming, for all functions of 3 or less variables and also some functions of 4 variables which require 5 or less NOR gates. According to the computational results, for the majority of the functions the first type of minimal networks is identical to the second type, and for no function were networks of the third type found to exist.

Optimal networks with thirty different types of restrictions are listed for the one-bit fuli adder. Optimality is derined as the minimization of the number of gates under different restrictions.

Optimal networks consisting of NOR-OR gates (each gate produces the NOR and/or the OR of its inputs) are tabulated for all Boolean functions of three variables. Optimality is defined as minimizing first the number of gates and then the number of interconnections. The optimal networks were synthesized for each Boolean function by using an integer programming synthesis technique.

The design of optimal logic networks is formulated as integer programming (IP) problems. This formulation has the following advantages over other methods of logic design. 1) General feed-forward networks can be dealt with rather than two-level or three-level networks usually treated in conventional switching theory. 2) Network restrictions such as fan-in and fan-out restrictions are easily incorporated. 3) Various gate types such as NOR, NAND, AND-OR combination, NOR-AND combination, and those gates with NOR-OR dual outputs can be treated. 4) Various objectives such as the number of gates and the number of connections are minimized. 5) Incompletely specified functions can be handled without additional difficulty. 6) The formulation can be extended to multiple-output networks. To solve the resulting IP problems, the implicit enumeration method of integer programming is found to be suitable. An IP code ILLIP (Illinois Integer Programming Code) is implemented based on the implicit enumeration by incorporating some new gimmicks such as pseudounderlining. Then the ILLIP is used to solve the IP problems for logical design by making use of the inherent structure of our problems. Various optimal networks are derived by a computer as follows: optimal NOR networks and optimal NOR-AND networks for all functions of up through three variables, one-bit adders with various gate types, and others. These results indicate the computational feasibility of the integer programming approach.

In this paper we develop an algorithm to design a switching network using only gates which represent negative functions. The number of gates in the network is minimized under the conditions that 1) the network consists of two levels, and 2) no fan-in restriction on each gate is imposed.

The number of threshold functions of eight variables is counted by ILLIAC II, the computer of the University of Illinois. Sets of optimum weights of majority elements realizing these functions also are investigated. Actually, canonical positive self-dual threshold functions of nine variables are investigated instead of directly investigating threshold functions of eight variables because it is easier to deal with them. The number and optimum weights of threshold functions of eight variables are easily obtained from these functions of nine variables and their realization.

For reduced finite Moore automata corresponding to regular expressions which are finite sums of expressions of the form E+HΣ*G (E,H,G are finite events and Σis the set of inputs) it is shown that an arbitrary change of the initial state or of the set of final states results in an automaton belonging to the same class. The transition graphs corresponding to the single inputs in definite and reverse-definite automata are investigated.

Properties of self-dual threshold functions are discussed because of the importance of self-dual functions in threshold logic. Since any threshold function can be easily converted into or reduced from a positive self-dual threshold function, we will not lose generality in discussion by exploring the properties of positive self-dual threshold functions. First functions generated by additively or subtractively merging two variables of a positive self-dual threshold function are discussed. Expansions of a positive self-dual threshold function with respect to two variables are then shown, and the generation of functions based on them is discussed. The concepts of strongly asymmetrical selfdual threshold functions and its degree are introduced, and the relation of all self-dual threshold functions of fewer variables with strongly asymmetrical ones is shown. The above discussion enables the classification of threshold functions and the relation between threshold functions of n variables and those of more variables to be better seen.

A lower bound on the number of threshold functions and a lower bound on the maximum of minimum weights of a threshold element are derived from a recursively constructed family of threshold elements. All threshold functions of n variables are difficult to construct for a general value of n, but it is shown that a large number of them can be constructed recursively from threshold functions of fewer variables. Schemes of such generation and related proper ties are discussed. Threshold functions generated in this way are so numerous that they constitute a constructive proof of a good lower bound on the number of threshold functions. By a similar procedure, we can derive a lower bound on the maximum of minimum weights of a threshold element. In this paper, discussion is limited to self-dual threshold functions, but this does not sacrifice generality, because any threshold function can be derived from a self-dual threshold function by assigning 1 or 0 to a certain variable.

Features of a large-scale digital computer with novel logical elements, the parametrons, are described. The machine, which is located at Musashino City, Tokyo, was named the MUSASINO-1, and has been in almost continuous operation since its completion in the spring of 1957. Primarily for scientific uses, it does arithmetic operations in parallel, and has a fast access memory of ferrite cores with nonrectangular hysteresis curve. Maintenance experience has indicated its extreme stability and low incidence of faults.

The capacity of a noisy continuous channel is discussed in both cases where the signal transmitted over the channel is expressible by a process with mutually independent random variables and where it is expressible by a Markov process. Unlike discrete channels, continuous channels impose certain restrictions on transmitter power in general. In the case of a continuous channel under disturbance of additive noise, a theorem on the capacity in terms of channel parameters is obtained and applied. Then in the general case of a Markov process a general procedure to calculate the capacity is shown.