Reduction of logic and delay through latch polarity inversion

A method for reducing logic and delay within a logic structure that includes searching logic structures to be analyzed, finding a plurality of latches within a logic structure to be analyzed, determining if any respective latches of the plurality of latches have sufficiently positive slack within an input and output path thereof and optionally excluding the respective latches from being analyzed, determining if there is at least one remaining latch to be analyzed, and determining whether inverters are disposed within an input path and an output path of the at least one remaining latch. The method further includes obtaining logic functions of the input path and output path of the at least one remaining latch when inverters are found, modifying the logic functions using DeMorgan's Theorems, determining whether timing violations exist with the modified logic functions, and annotating hardware description language based on the modified logic functions when no timing violations exist.

BACKGROUND

The present invention relates generally to integrated circuits, and more specifically, to a method of automation of logic synthesis and implementation for reducing logic and delay through latch polarity inversion.

In synchronous logic designs, latches or flip-flops are the sequential blocks that synchronize the logic flow. Due to the complexity of logic designs, the logic flows are written in hardware description languages (HDL) such as very-high-speed integrated circuit “VHSIC” (VHDL), and then synthesized into digital logic circuits. The synthesis process includes inserting logic between the latches to implement logic functions using inverters and/or other logic gates. A combinational synthesis process is repeated for all logic functions within the design. The signal polarity of each logic function is correctly implemented within the latch boundaries however maintaining signal polarity across latch boundaries may lead to inefficient use of inverters and/or logic gates, thereby causing extra path delay and circuit power.

SUMMARY

The present invention provides a method of analyzing a synthesized design and improving the handling of cross latch polarity by removing and/or re-synthesizing gates before and after a latch such that the function logic stays the same while reducing the number of logic gates, path delay and circuit power.

The present invention automatically searches through the synthesized logic to identify patterns of logic that can be implemented by a reduced number of inverters, logic gates and latches in reversed polarity. Based on the results of the search, the following on step can be applied to remove the extra logic (i.e., optionally excluding some latch paths). The present invention also provided a method of physical design changes to meet the cycle time and slew requirements, the algorithm of automatic back annotation which including writing back a file that describes the modified latch structure, the latch polarity changes to the designs in HDL, as well as a re-synthesizing the logic using the back-annotated HDL thus eliminating the need for extra logic gates.

According to one embodiment of the present invention, a method for reducing logic and delay within a logic structure is provided. The method includes searching logic structures to be analyzed, finding a plurality of latches within a logic structure to be analyzed, determining if any respective latches of the plurality of latches have sufficiently positive slack within an input and output path thereof and optionally excluding the respective latches from being analyzed, and determining if there is at least one remaining latch to be analyzed. The method further includes determining whether inverters are disposed within an input path and an output path of the at least one remaining latch, obtaining logic functions of the input path and output path of the at least one remaining latch when inverters are found, modifying the logic functions using DeMorgan's Theorems, determining whether timing violations exist with the modified logic functions, and annotating hardware description language based on the modified logic functions when no timing violations exist.

A computer program product capable of performing the above-mentioned method is also provided.

DETAILED DESCRIPTION

According to an embodiment of the present invention, a method for reducing logic and delay within a logic structure is provided where a logic structure is analyzed and changes may be made to a selected logic structure based on DeMorgan's Theorems to reduce the number of inverters, logic gates and/or latches in reversed polarity Reversed polarity in binary/Boolean logic means to invert the binary value, for example, the reversed polarity of logic “1” means logic “0” and vice versa. According to an embodiment of the present invention, logic represents a sequence of connected logic gates with or without inverters in between the logic gates as obtained from logic synthesis. A level within logic represents one logic gate. DeMorgan's Theorems indicate that any logical binary expression remains unchanged if changes are made such that all variables are changed to their complements, all AND operations are changed to OR operations or vice versa and by taking the complement of the entire logic expression. According to the present invention, an existing logic structure that has completed logic synthesis, placement and routing is provided. It is assumed that the logic structure meets all timing requirements except for slack. That is, there are no slew violations on any of the signals within the logic structure. Slack is defined as “required arrival time minus actual arrival time” in circuit delay. A logic structure fails to meet slack when a delay on a path between any two latches of the logic structure is higher than desired for that path. Therefore, a positive or more slack is better than less slack. Thus, the method according to an embodiment of the present invention reduces the path delay through logic redesign around a latch including latch inversion as mentioned above. Therefore, the path(s) delay(s) before and after a latch are reduced through logic simplification such that new gates have less delay than the existing implementation of the logic structure.

FIG. 1is a diagram illustrating an input and output path of a latch within a logic structure that can be implemented within an embodiment of the present invention. As shown inFIG. 1, the input path1includes logic at an input of a latch2and an output path3including logic is disposed at an output of the latch2.FIG. 2is a diagram illustrating an example of the input path shown inFIG. 1that can be implemented within embodiments of the present invention.FIG. 3is a diagram illustrating an example of the output path shown inFIG. 1that can be implemented within embodiments of the present invention.

As shown inFIG. 2, the input path1includes logic gates4and5and an inverter6disposed between the logic gates4and5. As shown inFIG. 3, the output path3includes logic gates7and8and an inverter9disposed between the logic gates7and8.

According to an embodiment of the present invention, the logic function at the input path1and the logic function at the output path3can be changed based on DeMorgan's Theorems in the case of an inverted latch. Further, all of the logic gates are placed and physically connected. Additional details regarding the input and output paths1and3will be described below with reference to the method for reducing logic and delay in a logic structure shown in the flowchart inFIG. 4.

FIG. 4is a flowchart illustrating a method for reducing logic and delay within a logic structure that can be implemented within embodiments of the present invention. As shown inFIG. 4, in operation300, a logic structure to be analyzed is provided. From operation300, the process moves to operation302where a plurality of latches within the logic structure are found. That is, according to an embodiment of the present invention, all of the latches within the logic structure are found. From operation302, the process moves to operation304where it is determined whether any latches of the plurality of latches found have sufficiently positive slack in an input path and output path of the latch since these latches already meet the timing constraints. Upon determination, the specified latches having positive slack in both input and output paths are optionally excluded from analysis. From operation304, the process moves to operation306, where it is determined whether there are any remaining latches to be analyzed. At operation306, if it is determined that there is at least one remaining latch, the process continues to operations308and309where the at least one remaining latch is analyzed. According to an embodiment of the present invention, each remaining latch is analyzed one at a time, until there are no remaining latches to be analyzed. According to an embodiment of the present invention, the remaining latches may be ordered based on an amount of slack, for example, starting with the latch having the worst slack.

At operation308, an input path of the remaining latch is traced backwards from the input at the latch to find any inverters. In operation309, an output path of the remaining latch is traced forward from the output at the latch to find any inverters. According to an embodiment of the present invention, the operations performed in operations308and309are independent tasks which may be performed simultaneously or sequentially. From operations308and309, the process moves to operation310, where it is determined whether any inverters are found. If it is determined that no inverters are found in operation310, the process returns to operation306to determine whether there are any remaining latches to be analyzed and the process begins again if it is determined in operation306that there is at least one remaining latch to be analyzed. On the other hand, when it is determined that inverters are found in operation310, the process moves to operations312and313where the logic functions at the input (e.g., Foriginal(x)) and output (e.g., Goriginal(x)) of the remaining latch are obtained.

Referring back toFIGS. 2 and 3, as shown inFIG. 2, Foriginalrefers to the logic function from the input of the inverter6through the logic gates5at the input path1to the input at the latch2(e.g., a latch being analyzed). As shown inFIG. 3, the Goriginalrefers to logic function from the output of the latch2(e.g., a latch being analyzed) through the logic gates7to the output of the inverter9of the same latch2. Referring back toFIG. 4, from operations312and313the process moves to operations314and315.

According to an embodiment of the present invention, operations312and313are independent tasks which may be performed simultaneously or sequentially similar to that of operations308and309. Similarly, operations314and315may also be performed simultaneously or sequentially. In operation314, the logic function at the input (i.e., Foriginal(x)) is optimized using DeMorgan's Theorems where the complement Fnew=Foriginal(x)′ of the Foriginal(x) is obtained. That is, the new (i.e., modified) logic function Fnewis the complement of the existing logic function. According to an embodiment of the present invention, the total gate delay of Fnewis less than that of Foriginal(x). In operation315, the logic function at the output (i.e., Goriginal(x)) is optimized using DeMorgan's Theorems where the new (i.e., modified) logic function (i.e., Gnew) at the output of the inverter9(as depicted inFIG. 3) considering that the output of the latch is now inverted. According to an embodiment of the present invention, the logic function Gnew=Goriginal; therefore, this logic function remains the same as before optimization. From operations314and315, the process moves to operation316, where it is determined whether the new logic function at the input is equal to the complement of the original logic function at the input and whether the new logic function at the output is equal to the original logic function at the output. If it is determined that one or both cases are false in operation316, process returns to operation306where it is determined whether there is another remaining latch to be analyzed. If it is determined that there is a remaining latch the process begins to analyze the remaining latch. If it is determined that both cases are true in operation316, the process moves to operation318where it is determined whether the physical implementation of the new logic functions at the input and output paths meet desired specifications. From operation318, the process moves to operation320where the previous logic functions at the input and output of the latch are removed.

Next, a determination of placement position is made based on a bounding box of the input and output pins of a gate to be placed. According to an embodiment of the present invention, the gate is placed in a nearest location of a center of the bounding box. According to an embodiment of the present invention, this process is automatically repeated starting with the gates directly connecting to the latch and tracing backwards and forwards on the gates of the new logic function until the input and output of the latch are reached and the new logic functions are inputted, routed and connected. From operation320, the process moves to operation322where affected gates may be optimized due to physical properties of the new logic functions. According to an embodiment of the present invention, optimization of the new gates includes adjusting a power level of the new gates to adjust the sizes thereof based on the new logic functions. From operation322, the process moves to operation324where it is determined whether there are any slew failures on all affected signals. From operation324, the process moves to operation326where it is determined whether there are any timing violations. In operation326, testing is performed to determine whether there are any timing violations. If it is determined that there are timing violations in operation326the process moves to operation328where the previous state of the latch within the logic structure is restored in both the input path and output path. According to an embodiment of the present invention, the restoration of the state of the latch includes bringing the original gates into their original places and restoring the original routes. From operation328, the process returns to operation306where it is determined whether there is a remaining latch to be analyzed.

On the other hand, if it is determined that there are no timing violations, the process returns back to operation306, to determine if there are any remaining latches to be analyzed. If it is determined that there is at least one remaining latch to be analyzed, the process begins again at operations308and309. If it is determined that there are no more remaining latches to be analyzed in operation306, the process moves to operation330where it is determined whether any of the latches in the logic structure have been inverted. If it is determined that any of the latches have been inverted, the process moves to operation332, the VHDL is back annotated with the logic changes made. That is, after all latches of the critical latches have been visited, the latches inverted due to optimization are identified. According to an embodiment of the present invention, a VHDL description of the inverted latches is created and merged back into the original VHDL description of the logic structure analyzed. The new VHDL will drive logic simulation to create new test patterns for testing the logic structure and tools that perform design checking between layout implementations and the logic structure description. According to another embodiment, a resynthesizing operation may be performed where the logic is resynthesized using back-annotated HDL thus using the back-annotated HDL as an input for logic synthesis again instead of modifying the already synthesized logic.

According to an embodiment of the present invention, the method performed within the flowchart shown inFIG. 4, is not limited to the operations being performed in any particular order and may be varied accordingly. For example, according to an alternative embodiment of the present invention, the process shown in the flowchart ofFIG. 3may be parallelized for speed purposes. That is, latches which do not share logic cones can be optimized by concurrent processes as long as their input and output logic cones do not share the same physical space in order to prevent a gate to be placed in a location by a processor and not seen by the optimization on another processor. According to an embodiment of the present invention, if the parallel processing is being performed, the logic cones are being analyzed and where there is a possibility of two concurrent processes competing for the same physical location, a handshaking mechanism between the processors may be implemented to find open locations. The results of each processor may then be merged into one proposed solution. According to yet another embodiment of the present invention, the method shown inFIG. 4, may be implemented such that the analysis performed on each latch to determine if latch inversion simplification is possible, may be parallelized. That is, operations308through316may be performed simultaneously on all of the latches excluding the latches having positive slack. Thus, according to this embodiment of the present invention, all latches without shared logic may be analyzed concurrently and the proposed solutions resulting from the analysis may be stored within a single processor. Afterwards, the physical implementation (in operation318) of the proposed solutions may be performed sequentially to avoid any potential conflicts of shared physical resources.

FIG. 5is a diagram illustrating an example of a logic structure. As shown inFIG. 5, an example of a logic structure which may be simplified by applying the method shown as shown inFIG. 4is provided. The logic structure100includes a latch path F1to F2which includes a first pair of inverters10and12at an input of a latch14and a second pair of inverters16and18at an output of the latch14. Upon applying the method ofFIG. 4, as mentioned above, path problems between latches are identified based on timing analysis. After review of the list of all the paths that do not meet certain timing requirements, a path is selected to be analyzed. InFIG. 5, during analysis of the selected path, for example, logic structure100, the logic (e.g., the first pair of inverters10and12and the second pair of inverters16and18) connected to an input and output of the latch14are reviewed to determine whether optimal changes may be made to the logic within the selected path. These optimal changes include any changes which will reduce the number of logic gates, path delay and circuit power required within the logic structure100within violating the timing requirements and which improves the logic structure100without compromising the logic function. Upon review of the logic shown inFIG. 5, extra inverters10and18are identified. These inverters10and18are considered unnecessary since the signal polarities are inverted multiple times unnecessarily. For example, if the signal polarity going into inverter10is “0” it is inverted to a “1” at inverter10and then inverted back to “0” by inverter12going through the latch14to be inverted again by inverter16into a “1” and then inverted again to a “0” by the inverter18. Therefore, the logic included in the logic structure100is able to be simplified using DeMorgan's Theorems as described below with reference toFIG. 6without compromising the logic function.

FIG. 6is a diagram illustrating a modified logic structure of the logic structure shown inFIG. 5upon implementing a method shown inFIG. 4. As shown inFIG. 6, the extra inverters10and18shown inFIG. 5have been removed. According to an embodiment of the present invention, the algorithm of the present invention will not remove any inverters (e.g., the inverters10and18) from the paths that potentially can cause early-mode timing violations. As shown inFIG. 6, a modified logic structure105includes a latch path F1to F2which now includes the inverter12, the latch14and the inverter16. According to an embodiment of the present invention, a scan initialization logic and process may require modification based on any changes made to the logic structure100. In addition, additional modifications may need to be made in order to meet delay and slew requirements. Next, a post processing operation is implemented which automatically modifies the logic design in HDL such that the Boolean equivalence check will pass.FIGS. 7 and 8below illustrate another example of a logic structure and a modified version of the logic structure using the method described above. According to an embodiment of the present invention, if there are no inverters at the input or output of the latch14for example, logic subsets may be identified using DeMorgan's Theorems that may be substituted to perform the same logic function.

FIG. 7is a diagram illustrating another example of a logic structure. As shown inFIG. 7, a logic structure200is provided. The logic structure200includes a latch patch from F1to F2that includes a first inverter20and a second inverter22at an input of a two-way NOR gate24. The NOR gate24is positioned at an input of a latch26. A first NAND gate28having a third inverter30at an output thereof along with an output of the latch26are input into a second NAND gate32. A fourth inverter34is provided at an output of the second NAND gate32.

FIG. 8is a diagram illustrating a modified logic structure of the logic structure shown inFIG. 7upon implementing a method as shown inFIG. 4. As shown inFIG. 8, after applying the method shown inFIG. 4, the DeMorgan's Theorems were applied to the logic before and after the latch26. That is, these theorems were applied to the first through fourth inverters20,22,30and34and to the NOR gate24and the first and second NAND gates28and32. As a result, as shown inFIG. 8, the logic structure200has been modified. A modified logic structure205is provided and only includes the second inverter22, the NAND gate28, another NAND gate36, the latch26, and an NOR gate38. As shown inFIGS. 7 and 8, the first, third and fourth inverters20,30and34were removed. The NOR gate24was replaced by an NAND gate36and the NAND gate32was replaced by a NOR gate38. Therefore, the logic function at the input of the latch26changes (i.e., polarity change) however the logic function after the latch26is preserved therefore maintaining the logic integrity of the logic structure200(now modified logic structure205). By applying the method according to an embodiment of the present invention to the logic structure200(as depicted inFIG. 7), the latch patch from F1to F2is reduced, incurring speed improvements thereby reducing logic and delay of the logic structure200.

Thus, according to an embodiment of the present invention, the logic function at the input path is modified such that the modified logic function is a complement of the logic function at the input path prior to being modified and with a reversed latch output polarity the logic function at the output path remains a same logic function as the logic function at the output path prior to being modified.

According to an embodiment of the present invention, intermediate logic points in downstream logic are identified to which the logic simplification process is applied simultaneously before and after the latch. In addition, upstream logic points (before the latch) are identified to allow logic simplification. While the logic function at the input of a latch such as latch26may change, the logic integrity of any other connection of the upstream logic is maintained. For example, the logic function of Fbshown inFIG. 8is preserved.

FIG. 9is a diagram illustrating an apparatus for implementing the method shown inFIG. 4that can be implemented within embodiments of the present invention. As shown inFIG. 9, the method described herein is practiced with a general-purpose computer and the method may be coded as a set of instructions on removable or hard media for use by the general-purpose computer. InFIG. 9, a computer system500has at least one microprocessor or central processing unit (CPU)505. CPU505is interconnected via a system bus510to a random access memory (RAM)515, a read-only memory (ROM)520, an input/output (I/O) adapter525for a connecting a removable data and/or program storage device530and a mass data and/or program storage device535, a user interface adapter540for connecting a keyboard545and a mouse550, a port adapter555for connecting a data port560and a display adapter565for connecting a display device570.

ROM520contains the basic operating system for computer system500. The operating system may alternatively reside in RAM515or elsewhere as is known in the art. Examples of removable data and/or program storage device530include magnetic media such as floppy drives and tape drives and optical media such as CD ROM drives. Examples of mass data and/or program storage device535include hard disk drives and non-volatile memory such as flash memory. In addition to keyboard545and mouse550, other user input devices such as trackballs, writing tablets, pressure pads, microphones, light pens and position-sensing screen displays may be connected to user interface540. Examples of display devices include cathode-ray tubes (CRT) and liquid crystal displays (LCD).

A computer program with an appropriate application interface may be created by one of skill in the art and stored on the system or a data and/or program storage device to simplify the practicing of this invention. In operation, information for or the computer program created to run the present invention is loaded on the appropriate removable data and/or program storage device530, fed through data port560or typed in using keyboard545.

Embodiments of the present invention provide a method for automation of logic synthesis which reduces the number of logic gates, path delay and circuit power required within a logic design. In addition, the present invention prevents any timing violations and automatically changes the polarity of a latch when it is determined that a different latch polarity will improve the logic design without compromising the logic function. Therefore, the present invention provides the advantage of being able to back annotate the VHDL if necessary to reflect any changes in latch polarity.