Circuit design approximation

A circuit design, responsive the input signals, may be obtained and processed. The circuit design may define connections between combinational elements, memory elements, and input signals. Identification of cut-off points may be performed with respect to predetermined combinational logic input signals. The cut-off points may be connections whose values are not dependant on the value of the predetermined combinational logic input signals. An approximated circuit design may be synthesized by relaxing the logic associated with the cut-off points. Based on the approximated circuit design, processing may be performed. In some exemplary embodiments, a clock gating function of a memory element may be determined by approximating the circuit design with respect to the output signal of the memory element. The clock gating function may be determined based on the approximated circuit design and introduced to the circuit design, with or without additional refinement.

TECHNICAL FIELD

The present disclosure relates to circuit design, in general, and to over-approximation of a circuit design useful for the design of the circuit, in particular.

BACKGROUND

When a circuit design is being designed, automatic or semi-automatic processes, such as determining a clock gating function to be used with respect to a memory element, such as for example a flip-flop or a latch, may be utilized. However, as the circuit design may include a large number of signals that are logically connected to each other by combinational logic, performing various computations may be a hard task.

Traditionally, a use of a Binary Decision Datagram (BDD) may be used to enable automatic simplification of complex binary functions represented by the signals of the circuit design. Another option is to represent the logic and a corresponding desired attribute as a Boolean Satisfaction Problem, and use a SAT solver to determine whether the attribute is satisfied of the logic. In some cases, an All-SAT may be used to determine a set of states in the design that hold the desired attribute. Though these approaches enable processing the circuit design, they do not scale well enough, and given design that has many memory units, input signals and/or complex combinational logic, the sizes of the BDDs may be too large to be retained in the memory of a computerized device and the SAT may not provide an answer within a reasonable time. These problems are an aspect of the state-space explosion problem which refers to the fact that the number of distinct states represented by such a circuit design is too high for a computerized device to process. As each signal multiplies the number of states, it can be understood that the size of the state space is exponential in the number of signals/memory units. Therefore, the state-space explosion problem may be a significant problem with regards to automatic or semi-automatic processing of the circuit design.

BRIEF SUMMARY OF THE INVENTION

One exemplary embodiment of the disclosed subject matter is a computer-implemented method performed by a processor, the method comprising: obtaining a circuit design, the circuit design is responsive to input signals, the circuit design defines connections between combinational elements, memory elements, and input signals; selecting one or more combinational logic input signals of the circuit design; identifying at least one cut-off point in the circuit design with respect to the selected combinational logic input signals, wherein value of the cut-off point is defined as a combinational function of a set of combinational logic input signals, the set of combinational logic input signals does not comprise any of the selected combinational logic input signals; and approximating the circuit design by defining an approximated circuit design, wherein the approximated circuit design is retained in a storage device, wherein in the approximated circuit design the at least one cut-off point is defined as a value of a new input signal.

Another exemplary embodiment of the disclosed subject matter is a computerized apparatus having a processor and a memory device, the computerized system comprising: a circuit design obtainer operative to obtain a circuit design, the circuit design is responsive to input signals, the circuit design defines connections between combinational elements, memory elements, and input signals; a combinational logic input signal selector operative to select one or more combinational logic input signals of the circuit design; a cut-off point identifier operative to identify at least one cut-off point in the circuit design with respect to the selected combinational logic input signals, wherein value of the cut-off point is defined as a combinational function of a set of combinational logic input signals, the set of combinational logic input signals does not comprise any of the selected combinational logic input signals; and a circuit design approximator operative to define an approximated circuit design based on the circuit design, wherein in the approximated circuit design the at least one cut-off point is connected to a simple input signal instead of to the combinational function to the input signals.

Yet another exemplary embodiment of the disclosed subject matter is a computer program product comprising: a non-transitory computer readable medium; a first program instruction for obtaining a circuit design, the circuit design is responsive to input signals, the circuit design defines connections between combinational elements, memory elements, and input signals; a second program instruction for selecting one or more combinational logic input signals of the circuit design; a third program instruction for identifying at least one cut-off point in the circuit design with respect to the selected combinational logic input signals, wherein value of the cut-off point is defined as a combinational function of a set of combinational logic input signals, the set of combinational logic input signals does not comprise any of the selected combinational logic input signals; a fourth program instruction for approximating the circuit design by defining an approximated circuit design, wherein the approximated circuit design is retained in a storage device, wherein in the approximated circuit design the at least one cut-off point is defined as a value of a new input signal; and wherein the first, second, third and fourth program instructions are stored on the non-transitory computer readable media.

DETAILED DESCRIPTION

One technical problem dealt with by the disclosed subject matter is to approximate a circuit design. Another technical problem is to determine an approximated circuit design useful for automatic or semi-automatic processing of the circuit design. Yet another technical problem is to determine clock gating function of a circuit design. Yet another technical problem is to perform processing on the circuit design such as logic optimization, false path analysis, or the like.

One technical solution is to approximate the circuit design by relaxing combinational logic that is not affected by signals of interest. Another technical solution is to identify cut-off points in the circuit design and to produce the approximated circuit design as the same circuit design aside from “cutting” the logic behind the cut-off points. “Cutting” the logic may be performed by replacing the combinational function representing the value at the cut-off point with a new input signal. Yet another technical solution is to traverse the connections of the circuit design, beginning from a predetermined connection towards the origin of the value of the connection, and identifying which connection is a potential cut-off and which is a non-cut-off point. The traversal may be performed until a combinational logic input signal is detected. A combinational logic input signal is a signal that is used as an input to determine a value of the connection in a cycle. For example, a combinational logic input signal may be an input signal to the circuit design. As another example, a combinational logic input signal may be an output signal of a memory element. A determination regarding a connection being a cut-off point may be with respect to a set of one or more combinational logic input signals. In some exemplary embodiments, the set of one or more combinational logic input signals may be selected online, may be predetermined, may be selected by a user, or the like. Yet another technical solution is to determine a combinational clock gating function of a memory element by determining cut-off points from the connection to the memory element (i.e., the signal setting the value of the memory element) with respect to the output signal of the memory element. The clock gating function may be applied on the circuit design. Yet another solution is to refine the determined clock gating function by introducing the combinational function that was removed during approximation of the circuit design.

One technical effect of utilizing the disclosed subject matter is to enable automatic and semi-automatic processing of the circuit design. By approximating the circuit design, the adverse effects of the state-space explosion problem may be reduced. Another technical effect is determining an exact clock gating function by processing the approximated circuit design. The clock gating function may be exact in the sense that in every cycle in which there is a clock gating opportunity, the function may provide a proper indication. Refining the clock gating function may be performed in order to simplify the clock gating function and determine constant value of the function or its sub-functions. Yet another technical effect is to provide a maximal cut-off point in the circuit design, so that if an additional connection in the approximated circuit design is disconnected and replaced with a new input signal, than an effect of the selected combinational logic input signal may be hidden.

Herein below, the disclosed subject matter is explained in particularity regarding computation of a clock gating function. However, the disclosed subject matter is not limited to this particular processing of a circuit design. Additional processes may be applied on the approximated circuit design, such as for example logic optimization, sensitivity analysis of the circuit design to a particular signal, false path analysis and similar processes applicable to the circuit design and/or verification.

Referring now toFIG. 1showing a computerized environment in which the disclosed subject matter is used, in accordance with some exemplary embodiments of the subject matter.

A computerized environment100may comprise a design approximator110. The design approximator110may be configured to obtain a circuit design, such as provided by a user140. The circuit design may be provided in a descriptive language such as Hardware Description Language (HDL), Verilog, SystemC, or the like. The design approximator110may generate an approximated circuit design in accordance with the disclosed subject matter,

A design processor120may be operative to process a circuit design. The design processor120may process the approximated circuit design for an improved feasibility and/or efficiency. The design processor120may perform a predetermined processing such as determination and addition of a Clock Gating (CG) function, optimization analysis, false path analysis and the like. In some exemplary embodiments, the design processor120may perform several processes. The design processor120may perform automatic or semi-automatic processing of the circuit design. In some exemplary embodiments, in response to processing the approximated circuit design, an additional processing, such as refining, may be performed prior to applying the output to the circuit design.

In some exemplary embodiments, the design approximator110and/or the design processor120may be computerized devices, implemented by software, hardware, firmware, combination thereof, or the like.

In some exemplary embodiments, a user140may utilize a Man Machine Interface (MMI)145, such as a terminal, a display, a keyboard, an input device or the like. The user140may provide the circuit design, review the approximated circuit design, assist in semi-automatic processing performed by the design processor120, review output of the design processor120, or the like. The user140may select “interesting” combinational logic input signals that are not to be cut out of the approximated circuit design. The user may determine from which connection in the circuit design the cut-off points determination is performed.

Referring now toFIG. 2Ashowing a diagram of a circuit design, in accordance with some exemplary embodiments of the disclosed subject matter

A circuit design200comprises a memory element210, such as for example a flip-flop. The memory element210has an input connection215and an output signal240. The value in the input connection215, and therefore the value set in the memory element210in each cycle, originates from input signals202and from the output signal240. The input signals202and the output signal240are considered combinational logic input signals. The value of input connection215is determined by AND gate220, having two input connections222and224. The value of connection222is determined by a combinational logic205, which is based on some of the input signals. The value of the connection224is determined by an OR gate230. The value of the OR gate230is based on the value in connections232and234. The value of connection234is the value of the output signal240. The value of connection232is determined by a combinational logic207, which is based on input signals. In some exemplary embodiments, the combinational logics205and207may be based on the same input signals, different input signals, or a combination thereof. The combinational logics205and207may comprise combinational elements, such as AND gate, OR gate, XOR gate, Multiplexer, Arithmetic Logic Unit (LGU) or the like.

Referring now toFIG. 2Bshowing a diagram of an approximated circuit design, in accordance with the disclosed subject matter.

In some exemplary embodiments, the circuit design200may be approximated to circuit design250. The approximation may be performed for the purpose of determining a combinatorial CG function for the memory element210. For the purpose of determining the combinatorial CG function, CG opportunities are determined in case the value of connection215is the same as the combinational logic input signal in the output signal240. Therefore, approximation may be performed starting from the connection215so that affects of the output signal240are propagated.

It will be noted that the values of connections222and232are determined by combinational logic which is not affected by the output signal240. Therefore, the connections222and232may be considered as cut-off points in the circuit design200. In the approximated circuit design250, the value of the corresponding connections:260and270is determined using an input signal. In some exemplary embodiments, the potentially complex computations associated with the combinational logics205,207is relaxed and abstracted to a simple input signal. Computation of the CG function based on the approximated circuit design250may be computationally easier.

In some exemplary embodiments, identification of the cut-off points may be performed by performing a Depth First Search (DFS) on the circuit design, starting from the connection216. In some exemplary embodiments, the DFS may be performed on a DAG structure corresponding to the circuit design200, so that a node is a connection having a value (e.g., the connection215, the output signal240, the input signals202, and so forth).

Referring now toFIG. 2Cshowing a schematic depiction of corresponding DAG data structure of the circuit design200, in accordance with some exemplary embodiments of the disclosed subject matter. Each node of the DAG is annotated with the corresponding connection number in the circuit design200. The root is the connection215. A node corresponding to a combinational logic input signal may be a leaf. A first node is a son of second node in case there is a direct connection from the first node to the second node, so that the value of the first node affects the value of the second node. For example, a node corresponding to connection234is a son node of the node corresponding to connection224(but not vice versa). In some exemplary embodiments, the connection234may be merged into the connection240.

In some exemplary embodiments, the DFS may a post-order DFS so that leaves of the DAG are processed prior to their corresponding parent nodes. By iterating over the DAG, non-cut-off points and potential cut-off points may be marked. A leaf that is not one of the selected “interesting” combinational logic input signals (e.g., in this case any leaf other than240) may be marked as a potential cut-off point. The “interesting” combinational logic input signals may be marked as non-cut-off points. A non-leaf node may be marked as a potential cut-off point in case all of its children nodes are potential cut-off nodes.

In this specific example node222and its children nodes may be marked as potential cut-off points. Node232and its children nodes may be too marked as potential cut-off nodes. Maximal cut may be determined by selecting two cut-off points: nodes222and232. As an outcome of cutting in the selected cut-off points all additional potential cut-off points are also removed from the approximated circuit design.

In some exemplary embodiments, a different approximation may be performed. The approximation may be performed with respect to other/additional combinational logic input signals. The identification of the cut-off point may be performed from a different connection other than the215connection.

In some exemplary embodiments, a tree data structure, which is a private case of a DAG, may be used.

Referring now toFIGS. 2D and 2Eshowing corresponding diagram of the circuit design and the approximated circuit design to which a Clock Gating function is introduced, in accordance with some exemplary embodiments of the disclosed subject matter. A Clock Gating (CG) function may be determined based on the approximated circuit design, and a corresponding circuit portion290may be synthesized and introduced to the approximated circuit design (FIG. 2D). The circuit portion290may be utilized in the circuit design as well (FIG. 2E), by manipulating the wiring connections to the circuit portion290. In some exemplary embodiments, the circuit portion290may be simplified in view of the constraints of combinational logic that was omitted in the approximated circuit design.

Referring now toFIG. 3showing a block diagram of an apparatus, in accordance with some exemplary embodiments of the disclosed subject matter.

In some exemplary embodiments, a circuit design obtainer310may be configured to obtain the circuit design. The circuit design may be obtain in an electronic form. The circuit design may be defined using a descriptive language such as HDL, Verilog, SystemC, or the like. The circuit design obtainer310may utilize the I/O module305to obtain the circuit design. The circuit design may be obtained from a user, such as140ofFIG. 1, a file, a remote storage, or the like. In some exemplary embodiments, the circuit design may at least one memory element. In some exemplary embodiments, the circuit design may define connections between combinational elements, memory elements, and/or signal inputs.

In some exemplary embodiments, a combinational logic input signal selector320may be configured to select one or more combinational logic input signals of the circuit design. In some exemplary embodiments, approximation of the circuit design may be determined with respect to the selected one or more combinational logic input signals. The selection may be manual, automatic, or semi-automatic. The selection may be inputted by a user, such as140ofFIG. 1, may be performed based on rules, commands or parameters, such as for example selection of an output signal of a memory element to which CG function is to be determined. In some exemplary embodiments, the selected combinational logic input signal may be240ofFIG. 2A.

In some exemplary embodiments, a cut-off point identifier330may be operative to identify at least one cut-off point in the circuit design with respect to the selected combinational logic input signals. In some exemplary embodiments, a value of in a connection in the circuit design may be formulated as a combinational function of combinational logic input signals. The cut-off point may be characterized in having its value be determined by a combination function that does not comprise any of the selected combinational logic input signals.

In some exemplary embodiments, a connection selector335may be operative to select a connection of the circuit design. Identification performed by the cut-off point identifier330may be performed from the selected connection. The selection may be manual, automatic, or semi-automatic. The selection may be inputted by a user, such as140ofFIG. 1, may be performed based on rules, commands or parameters, such as for example selection of an input connection to a memory element to which CG function is to be determined. In some exemplary embodiments, the selected combinational logic input signal may be215ofFIG. 2A.

In some exemplary embodiments, a connection traverser340may be configured to traverse nodes of the circuit design. The connection traverser340may be utilized by the cut-off point identifier330. The connection traverser340may traverse connections of the circuit design starting from a selected connection, such as selected by the connection selector335, and downstream towards the combinational logic input signals. The connection traverser340may be configured to traverse a DAG data structure corresponding to the circuit design. The traversal may be performed until combinational logic input signals, such as input signals and/or output signals of memory elements are encountered.

In some exemplary embodiments, the connection traverser340may be configured to mark potential cut-off points and/or non-cut-off points during traversal. In some exemplary embodiments, a combinational logic input signal in the set of combinational logic input signals selected by the combinational logic input signal selector320is a non-cut-off point. Any other combinational logic input signal is a potential cut-off point. Any connection that is not a combinational logic input signal is a potential cut-off point if its value is determined based only on combinational logic input signals not in the set of combinational logic input signals selected by the selector320. Using the marking, a determination may be made with regards to each connection by checking only its direct connections: in case any of them is a non-cut-off point, the connection is a non-cut-off point, and in case all of them are potential cut-off points, the connection is too a potential cut-off point.

In some exemplary embodiments, a post order DFS module345may be utilized by the connection traverser340to determine an order of traversal. The DFS module345may provide a traversal order of a post-order DFS.

In some exemplary embodiments, a circuit design approximator350may be configured to define an approximated circuit design, in accordance with the disclosed subject matter. The approximated circuit design may be the same as the circuit design except for “cutting” connections at the cut-off points and replacing them with fresh input signals. Such approximation may be viewed as modifying a combinational function defining the value of the connection with a value of an unconstrained input signal. For example, in case the cut-off point is defined by a connection to an AND gate which is connected to an input signal (i1) and an OR gate that is connected to two input signals (i2, i3), then the value may be defined by the following combinational function: i1(i2i3). In the approximated circuit design the value may be defined by a fresh and unconstrained input signal (i′1).

In some exemplary embodiments, a CG function determinator360may be configured to determine a CG function with respect to a memory element of the approximated circuit design. The CG function may a combinatorial CG function, a sequential CG function, or the like. The CG function may be indicative of a cycle in which there is a CG opportunity in the approximated circuit design. The CG function may be applicable to the circuit design. A combinational logic may be synthesized based on the CG function. The synthesized combinational logic may be introduced to the circuit design. The input to the synthesized combinational logic may be the signals applicable to the CG function. In case the replacement input signal introduced at the cut-off point is used, a connection from the original combinational logic at the cut-off point may be used. Thereby, the CG function determined based on the approximated circuit design is used on the circuit design as is. In some exemplary embodiments, the CG function is an exact CG function. A CG function, determined using a predetermined algorithm on the approximated circuit design, may be said to be exact with respect to the predetermined algorithm, in case that no CG opportunity that would have been discovered by applying the predetermined algorithm on the circuit design is missed due to the predetermined algorithm being applied on the approximated circuit design. In other words, the exact CG function, derived from the approximated circuit design, may cover all CG opportunities (discoverable by the use of the predetermined algorithm) in the circuit design. In some exemplary embodiments, the exact CG function does not comprise CG opportunities that are incorrect when applied on the circuit design.

In some exemplary embodiments, some of the CG opportunities that are feasible in the approximated circuit design, may not be feasible in the circuit design, due to combinational logic relaxed in the approximated circuit design. In some exemplary embodiments, a CG function refiner370may be configured to refine the CG function by introducing the relaxed combinational logic into the CG function and simplifying the CG function. In some exemplary embodiments, after refinement, the CG function may be a constant (e.g., zero in case none of the CG opportunities are feasible), or may be simplified, such as to enable a more efficient combinational logic representation.

In some exemplary embodiments, a BDD module380may be operative to manipulate BDD variables. The BDD module380may be utilized by the CG function determinator360and/or CG function refiner370.

In some exemplary embodiments, a fresh BDD variable for each combinational logic input signal of the approximated circuit design may be introduced. A BDD variable representative of the value of the connection selected by the connection selector335may be computed using the fresh BDD variables. A BDD of a CG function may be determined using any method known in the art. Each BDD variable in the BDD of the

CG function that corresponds to a cut-off point may be replaced with a BDD variable  representative of the relaxed combinational logic.

In some exemplary embodiments, a SAT solver382may be operative to manipulate SAT problems and provide a satisfying assignment to the SAT problem. The SAT solver382may be an all-SAT solver. Using the SAT solver382, CG opportunities in the approximated circuit design may be determined. The SAT solver382may further be used to refine the CG function, such as verifying satisfiability when the relaxed combinational logic is re-introduced.

In some exemplary embodiments, the apparatus300may comprise a processor302. The processor302may be a Central Processing Unit (CPU), a microprocessor, an electronic circuit, an Integrated Circuit (IC) or the like. The processor302may be utilized to perform computations required by the apparatus300or any of it subcomponents.

In some exemplary embodiments of the disclosed subject matter, the apparatus300may comprise an Input/Output (I/O) module305. The I/O module305may be utilized to provide an output to and receive input from a user, such as140ofFIG. 1.

In some exemplary embodiments, the apparatus300may comprise a storage device307. The storage device307may be a hard disk drive, a Flash disk, a Random Access Memory (ROM), a memory chip, or the like. In some exemplary embodiments, the storage device307may retain program code operative to cause the processor302to perform acts associated with any of the subcomponents of the apparatus300.

Referring now toFIG. 4showing a flowchart diagram of a method in accordance with some exemplary embodiments of the disclosed subject matter.

In step400, a circuit design may be obtained. The circuit design may be obtained by a circuit design obtainer, such as310ofFIG. 3.

In step410, one or more combinational logic input signals may be selected. The combinational logic input signals may be selected by a combinational logic input signal selector, such as320ofFIG. 3.

In step420, a circuit design may be traversed. The circuit design may be traversed by a connection traverser, such as340ofFIG. 3. Traversal order may be determined by a post-order DFS module, such as345ofFIG. 3.

In step430, iteration over nodes of the circuit design may commence. Iteration may be performed in respect to nodes of a DAG data structure corresponding to the circuit design.

In step440, a determination whether a node is a combinational logic input signal may be performed. Combinational logic input signals (e.g., leaves of the DAG) may be processed in step450. Other nodes may be processed in step445.

In step445, direct child nodes of the traversed node may be inspected to determine whether all nodes are potential cut-off points or not. Potential cut-off points may be nodes marked as potential cut-off points and/or combinational logic input signals that are not comprised by the set of combinational logic input signals selected in step410.

In the case that the node corresponds to a combinational logic input signal (i.e., a leaf node in the DAG data structure), in step450a determination whether or not the combinational logic input signal is amongst the set of combinational logic input signals selected in step410.

Based upon the determinations in steps450and/or445, the node may be marked as either a potential cut-off point or as a non-cut-off point in steps460,465. Marking may be performed by retaining a data structure indicative of the marking. The marking may be performed using a Boolean variable.

In step470, iteration to the next node, according to a determined order, such as a post-order DFS. In case there are no additional nodes to iterate over, step480may be performed.

In step480, one or more cut-off points may be selected so as to provide a maximal cut-off in accordance with the disclosed subject matter. In some exemplary embodiments, a set of cut-off points provides a maximal cut-off in case that any additional constraint that may be relaxed by cutting it out of the circuit design is affected by at least one of the selected combinational logic input signals. In some exemplary embodiments, the cut-off points are selected as the highest level in the corresponding DAG representation of the circuit design. In case all the parent nodes of a potential cut-off node are also potential cut-off node, the potential cut-off node is not selected as a cut-off point, as its associated constraints may be relaxed by selecting its parents as cut-off points.

It will be noted that a maximal cut-off is a syntactic notion in the disclosed subject matter and not semantic. For example, XORing the value of a selected combinational logic input signal with itself may provide a constant zero value. Therefore, such a constraint may be simplified and an additional combinational logic may be potentially cut off the approximated circuit design. However, such a determination is a semantic determination. In some exemplary embodiments, additional processes, methods and/or algorithms may be applied to identify tautologies, constants and other semantic notions. After the circuit design is simplified the disclosed subject matter may be applied to provide for a syntactic maximal cut-off in the simplified circuit design.

In step485, an approximated circuit design may be determined. The approximated circuit design may be synthesized based on the circuit design, where combinational logic leading to a cut-off point is omitted from the approximated circuit design and replaced with a new and unconstrained input signal. The approximated circuit design may be generated, synthesized, or otherwise determined by a circuit design approximator, such as350ofFIG. 3.

In step490, the approximated circuit design may be processed in a manual, semi-automatic, or automatic process. In some exemplary embodiments, the processing may be a determination of a CG function, such as performed by a CG function determinator, such as360ofFIG. 3. Other processing that may be performed may include logic optimization, false path analysis and the like. Additional processing associated with circuit design and/or verification may be performed.

In step495, an output of the processing of step490may be applied to the circuit design. In some exemplary embodiments, the CG function may be applied to the circuit design. In some exemplary embodiments, refinement, simplification, or similar operation may be performed prior to applying the output. For example, the CG function may be refined, such as by a CG function refiner370ofFIG. 3.