Behavioral Synthesis of Circuits Including High Impedance Buffers

This invention relates generally to the design of electronic circuits and more particularly to the automated design of integrated circuits by means of behavioral synthesis tools.

The motivation for automation of integrated circuit design is the ever increasing complexity of integrated circuits. Since 1960 the number of gates on an integrated circuit chip has doubled approximately every two years. Currently, it is not unusual for a single integrated circuit chip to include hundreds of thousands of gates. Behavioral synthesis tools are emerging to help integrated circuit designers to deal with this complexity.

A behavioral synthesis tool typically comprises a behavioral synthesis program running on a general purpose digital computer. Ideally, the behavioral synthesis program takes a user's description of a circuit's behavior and then produces a corresponding circuit structure. By "behavior" it is meant that a user does not have to describe the structural components of a circuit but rather what the circuit does and how it operates. This user's description is written in a hardware description language (HDL) such as VERILOG (a trademark of Cadence, Inc.) or the public domain language VHDL. The VHDL hardware description language is specified by the IEEE as VHDL standard version 1076B which was released in 1987.

In FIG. 1, a prior art routine for producing integrated circuit masks from a hardware description language is shown. A behavioral synthesis program 10 typically includes a net expression routine 12 (sometimes called a level one synthesis routine) and a structure synthesis routine 14 (sometimes called a level two synthesis routine). The behavior of an integrated circuit (I.C.) is coded into a hardware description language and is received by the net expression routine 12 which produces a series of net expressions as illustrated by the single net expression in FIG. 1A. A net expression is a parse graph or tree which defines the output of a circuit solely in terms of its input signals. Examples of net expressions include: "IN1+IN2+CARRY"; "(e2)?e1:e2;" and "C." These net expressions are input into the structure synthesis routine 14 which produces gate-level descriptions of the I.C. circuitry. Behavioral synthesizers incorporating net expression routines and structure synthesis routines are commercially available from Synopsis, Inc.

The gate-level descriptions provided by a behavioral synthesis program 10 can be further processed in a chip compiler program 16 which produces device-level descriptions of the circuitry and in a mask layout program 18 which will use the device-level descriptions produced by the chip compiler to produce production-worthy integrated circuit masks. Chip compiler programs and mask layout programs are commercially available from VLSI, Inc. of San Jose, Calif.

A problem with prior art behavioral synthesis programs is that they cannot directly synthesize the circuit structure for a high impedance buffer. As a result, integrated circuit designers had to manually specify the structure, data inputs and control inputs for every high impedance buffer they wished to design into the circuit. This is illustrated in FIGS. 1 and 1B where the high impedance structures 20 and inputs D(data) and C(control) must be manually entered into the structure synthesis routine 14 by the circuit designer.

This step of manually entering the high impedance structure and inputs into the structure synthesis routine partially defeats the purpose of the behavioral synthesizer program, which is to free the integrated circuit designer from gate-level design work. Despite the disadvantages of manually specifying high impedance structures and control signals, designers of behavioral synthesis programs have not previously supported the synthesis of high impedance structures due to the complexities of handling high impedance states within the net expression routine.

The present invention automatically generates high impedance structures and input signals when high impedance states are specified in a hardware description language. The clear advantage of this capability is the further automation of the integrated circuit design process.

Rather than developing the control expressions for high impedance structures directly from the hardware description language, the present invention preferentially takes the output of the net expression routine and runs it through a high impedance structure and control expression routine (HI-Z routine). Within the HI-Z routine, the net expressions are analyzed for high impedance states, and high impedance structures and control expressions are automatically generated when appropriate. The net expressions, the high impedance structures, and the high impedance control expressions are input into the structure synthesis routine for automatic gate-level synthesis.

The present invention therefore allows an integrated circuit designer to specify high impedance states at the hardware description language level thereby saving time and reducing the complexity of the circuit design task. Because the invention preferentially operates on the net expressions provided by the net expression routine, its implementation efficient and relatively straight-forward.

These and other advantages of the present invention will become clear to those skilled in the art upon a study of the detailed description of the invention and of the several figures of the drawings.

FIG. 1 is a block diagram of a prior art method for generating integrated circuit masks including a behavioral synthesis program, chip compiler program, and a mask layout program;

FIG. 1A is an example of a prior art output of the Net Expression Routine at point 1A in FIG. 1;

FIG. 1B illustrates the prior art manual input into the Structure Synthesis Routine at point 1B in FIG. 1;

FIG. 2 is a block diagram of an improved Behavioral Synthesis Program including a High Impedance Structure and Control Expression Routine (HI-Z routine);

FIG. 2A is an example of an output of the Net Expression Routine at a point 2A in FIG. 2;

FIG. 2B illustrates an output of the HI-Z routine at a point 2B in FIG. 2;

FIG. 3 is a block diagram of the internal processes of the HI-Z routine shown in FIG. 2; and

FIG. 4 is a block diagram of the internal processes of the FINDHIZEXPR routine shown in FIG. 3.

The present invention comprises a behavioral synthesis tool which, as mentioned previously, includes both a behavioral synthesis program and a hardware platform upon which it operates. The hardware platforms may be, and preferably are, general purpose digital computers such as engineering workstations, minicomputers and mainframe computers. Alternatively, the hardware platforms may be custom designed digital computers which incorporate some or most of the behavioral synthesis program into the hardware of the system.

Prior art behavioral synthesis programs were described with reference to FIGS. 1, 1A and 1B. In FIG. 2, a behavioral synthesis program 10 constructed in accordance with the present invention is shown in high-level, block diagram form. The net expression routine 12 is similar to that found in the prior art, as is the structure synthesis routine 14. A high impedance structure and control expression routine, hereafter referred to as HI-Z routine 22, is not known in the prior art either as an independent routine or as an integral portion of a behavioral synthesis program.

As seen in FIG. 2, HI-Z routine 22 has an input signal 2A comprising a series of net expressions such as the net expression for "A" shown in FIG. 2A. The output signal 2B of HI-Z routine 22 (as illustrated in FIG. 2B) includes the specifications of a tri-state or high impedance buffer 24, a series of net expressions such as the net expression "A" and a series of high impedance control expressions such as the high impedance control expression "B". Structure synthesis routine 14 uses the net expressions, control expressions and high impedance buffer structures to automatically synthesize circuits having high impedance buffers.

The HI-Z routine 22 is shown in grater detail in FIG. 3. In a first step 26, the HI-Z routine 22 passes a net expression from input signal 2A to a FINDHIZEXPR routine, which will be discussed in greater detail with reference to FIG. 4. The routine 26 issues an output enable expression OENEXPRA or signal 28. In a conditional step 30, OENEXPRA is analyzed to determine whether all binary digits of this expression are zero, i.e., whether the output enable expression OENEXPR is a null. As used herein, "null" means any pattern or code indicating that there are no high impedance states whatsoever in the associated net expression. Conveniently, the present invention uses an all zeros expression as a null, but it could equally well use an all ones expression as a null or some other pattern or code to indicate nullity.

If the net expression is not a null, the net expression with which OENEXPR is associated includes at least one high impedance state, and the high impedance buffer structure 24 must be created in a step 32. Also within step 32 the high impedance control expression B is assigned the value of the output enable expression OENEXPR.

If the output enable expression OENEXPRA has been determined to be a null in step 30, or if step 32 has already been performed, a determination is made in a conditional step 34 whether there are any more net expressions to be processed. If there are, the HI-Z routine 22 is repeated, beginning from step 26. If all net expressions have been processed, the HI-Z routine has completed its task, and the routine returns control to the structure synthesis routine 14 for level two synthesis.

In FIG. 4 the routine FINDHIZEXPR 26 is shown in detail. Routine FINDHIZEXPR 26 is recursive, i.e. it can call itself recursively and without limitation. The first step within routine FINDHIZEXPR 26 is a conditional step 38 which examines a net expression for operations which never produce a high impedance state. Examples of such operations include addition, multiplication, greater-than, less-than, etc. If the net expression contains only operations which would never produce a high impedance state, the output enable expression OENEXPR is set to,, null in a step 40 and the call to routine FINDHIZEXPR 26 is terminated in a return step 42.

If, in conditional step 38, it is determined the net expression does include operations which can produce at least one high impedance state, the net expression is examined in a conditional step 44 to determine whether this net expression is a "net only" net expression, such as A=C. If this expression is a net only net expression, OENEXPR is set equal to a null expression in step 40 and control is returned the calling routine in step 42.

If the next expression is not found to be a net only expression in step 44, the net expression is examined in a conditional step 46 to determine whether the net expression is a "value only" expression, such as A=011ZZ010. If this next expression is a value only expression, a conditional step 48 determines whether this net expression produces one or more high impedance states within the net expression. If not, the expression OENEXPR is set to null in step 40 and control is returned to the calling routine in step 42. If the net expression is a value only expression with at least one high impedance state, step 50 causes OENEXPR to manifest the high impedance state produced by the net expression. By way of example, one way that OENEXPR can reflect the high impedance states of the net expression is to set the bits of OENEXPR equal to "1" wherever the net expression indicates a high impedance state and equal to "0" elsewhere. In this example, for the net expression A =011ZZ010, the expression OENEXPR created by step 50 would be B=OENEXPR=00011000. Of course, there are other ways by which OENEXPR may manifest the high impedance states of the net expression, such as setting corresponding equal to "0" to indicate a high impedance state in the net expression and equal to "1" elsewhere.

If this net expression is not found to be a value only expression in step 46, it has been effectively determined this next expression is composed of two or more sub-expressions. For example, for expression A=IN1+IN2, the sub-expressions are A.sub.1 =IN1 and A.sub.2 =IN2 where A=A.sub.1 +A.sub.2. A.sub.1 and A.sub.2 can, in turn, have their own sub-expressions. Each of these sub-expressions is analyzed in turn by recursively calling routine FINDHIZEYPR 26 in a recursive call step 52. Once all sub-expressions and their sub-expressions have been analyzed, they are combined in a combinational step 54 according to their expression type to create OENEXPR, after which control is returned to the calling routine in return step 42.

An example of a routine FINDHIZEXPR is illustrated in Appendix A. This routine is written in MAINSAIL a PASCAL-like language provided by Xidak, Inc. of Menlo Park, Calif. Lines 1 and 2 are comment lines, while lines 3-10 are the internal variable definitions. In line 12, OENEXPR is set to a one-bit-wide null expression if the net equation is a null. In line 14, the expression OENEXPR is set equal to a null if the net expression is a net only expression. In line 16, value only net expression are set equal to nulls, and in lines 17-19 the bits of OENEXPR are caused to reflect the high impedance states of the value only net expressions by setting the corresponding bits of OENEXPR to 1 whenever a high impedance state is detected in the net expression. Line 20 begins the routine which handles a net expression which may require recursive calls to routine FINDHIZEXPR to analyze the next expression sub-expressions. In lines 24 and 25, the operator "If" in line 20 is analyzed by recursive calls to FINDHIZEXPR to create a sub-control expressions which are combined in line 26 to create OENEXPR. Similarly, the operator "Extract" in line 28 is analyzed by recursive calls to FINDHIZEXPR in line 29 and the sub-expressions are combined to form OENEXPR in lines 30-31; the operator "Decode" in lie 33 is analyzed by a recursive call to FINDHIZEXPR in line 36 and combined to form OENEXPR in line 37; the operator; "Concatenate" in line 39 is analyzed by a recursive call in line 42 and combined to form OENEXPR in line 43; and the operators Shift-Left and Shift-Right in line 45 are analyzed by a recursive call in line 46 and are combined to form OENEXPR in lines 47 and 48. It should be noted that the recursive calls which analyze the sub-expressions may, in turn, create further recursive calls which analyze their own sub-expressions and so forth. In any event, once the net expression has been analyzed according to all of its sub-expressions, the sub-expressions are combined according to their type to form the final output enable expression OENEXPR. Finally, for all next expressions which cannot contain high impedance states, OENEXPR. Finally, for all next expressions which cannot contain high impedance states, OENEXPR is set to a null expression in line 53.

It will be noted that the routines FINDHIZEXPR 26 of FIG. 4 and of Appendix A do not coincide in the order in which the net equations are analyzed. This illustrates the important point that there are many ways to express the same functionality when dealing with software routines. For example, in FIG. 4 it is irrelevant whether the conditional step 38 which looks for high impedance operations is performed before or after the conditional step 44 which looks for net only net expressions. This is, of course, true for all of the routines described herein: the routines are by way of example only, and not limitation.

While this invention has been described in terms of several preferred embodiments, it is contemplated that various alterations and permutations thereof will become apparent to those skilled in the art. It is therefore intended that the appended claims include all such alterations and permutations as fall within the true spirit and scope of the present invention.

Behavioral Synthesis Pro ram: A program running on a digital computer which creates gate-level circuitry from a behavioral description of how the circuit should work.

Behavioral Synthesis Tool: The combination of a behavioral synthesis program and a digital computer.

FINDHIZEXPR routine: A software routine which analyzes net expressions and returns OENEXPR.

HDL: Hardware Description Language. A user of a behavioral synthesis tool inputs the desired behavior of a circuit into the tool by means of a specialized hardware description language.

High Impedance Control Expression: This expression defines the control input to a high impedance buffer. The data input to the high impedance buffer is the associated net expression.

HI-Z routine: This software routine takes a net expression, analyzes it for high impedance states and develops the structure of a high impedance buffer and a high impedance control expression whenever the net expression includes at least one high impedance state.

Level One Synthesis: A software routine which decomposes a series of hardware description language commands into a series of net expressions.

Level Two Synthesis: A software routine which converts a series of net expressions into gate-level circuitry.

Net Expression: An acyclic graph or tree developed from the hardware description language commands which express all circuit outputs solely in terms of their inputs.

Net Only Expression: A net expression containing only another net expression.

Null: As used herein, a condition in the HI-Z routine and the FINDHIZEXPR routine signifying that no high impedance states are associated with a particular net expression.

OENEXPR: Output Enable Expression. This expression is generated by the FINDHIZEXPR routine and becomes the high impedance control expression in the HI-Z routine if it is not a null expression.

Reflect: A first expression is reflected by a second expression if the second expression encodes the high-impedance states of the first expression.

Sub-Control Expression: The control expression associated with a sub-expression.

Sub-Expression: Expressions within other expressions, i.e. an expression within a net expression or within another sub-expression.

Value Only Expression: A net expression including only a value.

VERILOG: A HDL provided by Cadence, Inc.

VHDL: A public domain HDL developed as part of a Very High Speed Integrated Circuit (VHSIC) hardware program and specified by the IEEE.