JP3204285B2 - Method for increasing operating speed of logic circuit with embedded latch - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION The present invention relates to an FPGA (Field Pr
ogrammable Gate Array) suitable for use as a circuit for constituting a related operating speed fast method latch embedded logic circuits of.

[0002]

2. Description of the Related Art The operating speed of a logic circuit is determined by its synchronous clock frequency, and the upper limit thereof is a path which causes the maximum delay of a combinational circuit portion existing between each latch in the logic circuit (hereinafter referred to as a critical path). ) Is the reciprocal of the delay value. In order to increase the operation speed without changing the processing function of the designed logic circuit, a new latch may be inserted into the combinational circuit part so as to reduce the delay. However, in order not to change the processing function of the logic circuit other than the clock response delay, the latches must be inserted so that the number of latches is the same for all paths between the input and output terminals of the logic circuit. As a method based on the above-mentioned idea, for example, Nakata et al., “A method of inserting a latch preserving logic in a synchronous circuit”, IEICE Transactions A, Vol.
J75-A, No. 12, PP. 1849-1858, December 1992 (hereinafter referred to as Document 1), a latch insertion method has been proposed.

[0003]

However, in recent years, in logic circuit design, the work of allocating, arranging, and wiring circuits to individual components has been performed by computer aided design (Computer Aided).
Design: CAD) tools are often used, but if the work is redone with some circuit changes, the overall configuration changes significantly. For this reason, not only the part intended by the designer but also the delay of other combinational circuit parts greatly change. Therefore, conventionally, it is not a simple operation to insert a latch only for the purpose of increasing the operation speed. Furthermore, since the conventional method does not consider restrictions on the insertion location and the number of latches inserted, if the number of latches that can be used in advance and the insertion location are limited due to the circuit configuration, it is not possible to simply apply could not.

In a conventional insertion method for increasing the operating speed of a designed logic circuit, a number of new latches are finally inserted in each combinational circuit portion existing in the logic circuit. I can't know for sure. For this reason, when the insertion position of the latch is limited due to the circuit configuration, the conventional method cannot be applied. In addition, in a normal circuit configuration, it is necessary to add a clock supply wiring for the inserted latch, which necessitates rearrangement of components and a change in other wiring, and consequently another part. A critical path sometimes occurred. The present invention has been made in view of the above-described problems, and after a logic circuit using an FPGA or the like is designed, a latch may be inserted into a basic circuit for the purpose of increasing the operation speed.
And to provide a <br/> operating speed fast method latch embedded logic circuits other parts are not affected.

[0005]

According to the first aspect of the present invention, there is provided a multi-input, one-output combination circuit, and a latch connected to an output of the combination circuit. A circuit having a plurality of basic circuits each including a selection means for selecting and outputting any one of the output of the combinational circuit and the output of the latch, and having a predetermined function by setting a wiring between the basic circuits. In the logic circuit, the basic circuit is set as a node, the wiring between the basic circuits is set as an edge, all inputs of the logic circuit are set as start nodes, and all outputs of the logic circuit are set as end nodes. A first step of reducing a loop existing in the directed graph to one node and connecting an edge connected to a node in the loop to a reduced node. A third step of defining a starting node as a set A, a fourth step of redefining a set of all nodes that can be directly reached from a node belonging to the set A by an edge as a set A, and a set A A step of checking whether or not a terminal node is included in the set A. A node using a latch or a node that can reach a node belonging to the set A via a latch or an edge belonging to the set A A sixth step of checking whether or not there is a node that can be reached via another node in the set A; and, in the sixth step, a corresponding node from the set A A seventh step of deleting and adding a node directly reachable by an edge from the deleted node to the set A; and checking whether or not the set A includes a terminal node. If there is no corresponding node in the sixth step, if there is no corresponding node, the ninth step is to add the set A to the set Y and return to the fourth step. In the step or the eighth step, when the end node is included in the set A, the latch is inserted into all the nodes belonging to the set Y.

[0006]

According to the present invention, a combination circuit having multiple inputs and one output, a latch connected to the output of the combination circuit, and a selection circuit for selecting and outputting one of the output of the combination circuit and the output of the latch The basic circuit constituted by the means constitutes a logic circuit, and a latch is inserted so that the number of newly inserted latches is equal in any of a plurality of propagation paths existing from the beginning to the end of the logic circuit. A portion is selected, and an output is selected by the selection means so that a latch is inserted into an output of the corresponding basic circuit.

[0007]

An embodiment of the present invention will be described below with reference to the drawings. A. 1. Configuration FIG. 1 shows a configuration of a basic circuit 1 which is a basic logic circuit used in one embodiment of the present invention. This basic circuit 1 has an input I
1, I2... In and an output X. All inputs I1,
I2... In are connected to a combinational circuit 2 having multiple inputs and one output.
It is connected to one input of a selector 4 having two inputs. The output of the latch 3 is connected to another input of the selector 4. Further, the output of the selector 4 is connected to the output X of the basic circuit 1. In the basic circuit 1, whether the output of the combinational circuit 2 is the direct output X,
Whether the latch 2 is inserted between the output X and the output of the combinational circuit 2 can be switched by the selector 4. The select signal line for this switching and the clock supply line of the latch 3 are wired in advance, and the wiring does not become a critical path. All the logic circuits can be designed with the basic circuit 1 of FIG. 1 as a unit.

B. Circuit Graph In a logic circuit using a plurality of the basic circuits 1 described above, in order to increase the operating speed, the logic circuit is formed into a circuit graph in the present invention. The circuit graph will be described below with reference to FIGS. A logic circuit designed as a configuration as shown in FIG. 2 can be expressed as a directed graph in which the basic circuit 1 in FIG. 1 is set as one node and the wiring between the basic circuits 1 is an edge as shown in FIG. it can. Since then
A diagram as shown in FIG. 3A is called a circuit graph. FIG.
Nodes a to i shown by circles in (a) represent the basic circuit 1 in FIG. Here, nodes e and f shown by solid circles are
This is the basic circuit 1 in which the latch 3 side is selected by the selector 4 shown in FIG.
Is called a latch node. Nodes s and t are dummy nodes, which are connected to all input terminals and output terminals of the logic circuit, respectively. All the input terminals of the logic circuit are one dummy node, which is the node s in FIG. Similarly, all the output terminals are one dummy node and are the node t in FIG.

When a loop exists in a logic circuit, the loop is reduced to one node, and the edge connected to each node in the loop is connected to the reduced node. Deform. For example, FIG.
In the circuit graph of (1), the nodes c, e, and h form a loop. FIG. 3B shows a reduced circuit graph. In FIG. 3B, the node L is the node c in FIG.
The nodes composed of e, h, and h are contracted nodes, and edges E1, E2, E3, and E4 are newly generated. Note that the loop is always 1 due to the nature of the logic circuit.
One includes a latch node. Therefore, a node generated by reducing the loop is indicated by a black circle as a latch node.

C. Latch Insertion Method Hereinafter, a flow chart shown in FIG. 4 shows a method of determining which basic circuit 1 to insert a latch in order to increase the operation speed in a logic circuit using a plurality of basic circuits 1 according to the present invention. This will be described with reference to FIG. FIG. 5 shows a case where this method is applied to the circuit graph of FIG.
This will be described with reference to FIG. At the time of latch insertion, as shown in Reference 1, in order to guarantee the original circuit operation, the number of latches newly inserted for all paths from node s to node t on the circuit graph Must be identical. This latch insertion method satisfies the above-mentioned restrictions. Also,
The term "child of a node" here refers to any node that can be directly reached by an edge emanating from the node,
"Descendants of a node" refers to all nodes that can be reached from that node via edges and other nodes. In addition, offspring include children.

First, only the node s is defined as an element of the set A (step S1). At this point, it is assumed that the set Y of target nodes into which a new latch is to be inserted is not defined. Next, children of all nodes in the set A are searched, and all nodes that are children of the elements of the set A are set
(Step S2). In FIG. 5, nodes a, b, and L that are children of node s are redefined as elements of set A. Next, if the element of the newly defined set A includes the terminal node t, the set Y
, All the nodes which are the elements of the set A are additionally defined, and the process ends (step S3). On the other hand, in the processing of step S3, if the element of the set A does not include the terminal node t, for all the nodes that are the elements of the set A, the node is a latch node or the descendant of the node is a set. Check whether it is an element of A (step S
4).

If the element of the set A checked in the process of step S4 is a latch node, or if the descendant is an element of the set A, this node is temporarily set as a node n and the node n is set as the node A of the set A. Node n
Are added to the elements of the set A (step S5). FIG.
In, since node L is a latch node, it is deleted from the elements of set A, and nodes i and j, which are children of node L, are added to the elements of set A instead. Although node b is a child of node L, it is already an element of set A. Here, if the terminal node t is included in the elements of the set A, all the nodes that are the elements of the set A are additionally defined in the set Y, and the processing is terminated (step S6). If not included, the process returns to step S4. On the other hand, if all the nodes that are the elements of the set A are not the latch nodes and the descendants are not the elements of the set A in the processing of the step 4, all the nodes that are the elements of the set A are additionally defined to the set Y (step S7), returning to step S2. In FIG. 5, the set A = {a, b, i, j} (nodes indicated by double circles in FIG. 5) has no descendant relationship with each other and is not a latch node. ).

Next, in FIG. 6, as elements of the set A,
The nodes d, g, k and l (the nodes of the double circle in FIG. 6) which are the children of the nodes a, b, i and j are redefined (step S2). Although node f is a child of node b, nodes g and k, which are children of node f, are defined as elements of set A because they are latch nodes. Further, in FIG. 7, since the nodes g, k and l are descendants of the node d, the node d is deleted from the set A, and the node f which is a child of the node d is a latch node as described above. (Step S5). Therefore, as a result, the set A = {g, k, l}
(The node of the double circle in FIG. 7). Next, in FIG.
Since the node 1 is a descendant (child) of the node k, the node k is deleted from the elements of the set A. At this time, since the nodes g and l, which are the elements of the set A, both have the child as the terminal node t, this set A = {g, l} (the double circle node in FIG. 8) It is additionally defined in the set Y as a broken line C) (step S6).

At the end of the flowchart shown in FIG.
The node that is an element of the set Y is a target node into which a new latch is inserted. In the circuit graph shown in FIG. 3B, nodes connected by two broken lines B and C in FIG. , A node into which a latch should be inserted.
Note that a specific latch insertion operation is performed by selecting the selector 4 of the basic circuit 1 of FIG. 1 corresponding to each node on the circuit graph.
By switching to the one to which the latch 3 is connected.

In the above description, it has been assumed that the basic circuit 1 shown in FIG. 1 having a multi-input / one-output combinational circuit therein is used as one node. However, the present invention can be applied to a circuit configuration using other basic circuits as a unit as long as a circuit graph as shown in FIG. 3 can be created. Examples thereof are shown in FIGS. 9 and 11
Shows a basic circuit 11 and a basic circuit 21 having different configurations each having a configuration of multiple inputs and two outputs. In FIG. 9, the basic circuit 11 has two combinational circuits 2a and 2b having a common input. In this configuration, two basic circuits 1 of FIG. 1 are prepared and inputs are shared. Therefore, when creating a circuit graph, two nodes 15a and 15b may be created as shown in FIG.

The basic circuit 22 shown in FIG. 11 is different from the basic circuit of FIG.
One output is in the form. In this case, FIG.
As shown in FIG. 2, the nodes on the circuit graph may be configured so that two outputs are output from one node 25. However, in this case, the latches 3a and 3b in FIG. 11 are either simultaneously used or not used, and the selectors 4a and 4
b must always be controlled synchronously. Further, the latch insertion position of the basic circuit 11 or 21 described above depends on the combinational circuit 2a, 2b or 22
However, even if a latch insertion position is provided for the input, the same can be handled on the circuit graph.

[0017]

As described above, according to the present invention,
When increasing the operating speed by inserting a latch into a designed logic circuit using an FPGA or the like, a new critical path is created because no circuit change occurs with the insertion of a new latch. In addition, it is possible to realize a method for increasing the operating speed of a latch-embedded logic circuit , which is not limited by the upper limit of the finite number of latches inserted beforehand in the combinational circuit and the restriction on the insertion position.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating an example of a configuration of a basic circuit according to an embodiment of the present invention.

FIG. 2 is a diagram illustrating an example of a configuration of a logic circuit according to an embodiment of the present invention.

FIG. 3 is a diagram showing a circuit graph of the example of the logic circuit shown in FIG. 2;

FIG. 4 is a flowchart illustrating a latch insertion method for the logic circuit represented by the circuit graph illustrated in FIG. 3;

FIGS. 5 to 8 are diagrams showing how a node into which a latch is inserted is determined in the circuit graph shown in FIG. 3B according to the flowchart shown in FIG.

FIG. 9 is a diagram showing an example of a configuration of a basic circuit having multiple inputs and two outputs in the present invention.

FIG. 10 is a diagram showing a state in which the basic circuit shown in FIG. 9 is converted into a node for expression in a circuit graph.

FIG. 11 is a diagram showing an example of a configuration of a basic circuit with multiple inputs and two outputs in the present invention.

FIG. 12 is a diagram showing a state in which the basic circuit shown in FIG. 11 is turned into a node for expression in a circuit graph.

[Explanation of symbols]

 1 Basic circuit 2 Combination circuit 3 Latch 4 Selector

──────────────────────────────────────────────────続 き Continuing on the front page (72) Kazuhisa Yamada 1-6-1, Uchisaiwaicho, Chiyoda-ku, Tokyo Nippon Telegraph and Telephone Corporation (72) Naohisa Ota 1-1-6 Uchisaiwaicho, Chiyoda-ku, Tokyo Japan Inside Telegraph and Telephone Corporation (56) References Kazuhisa Yamada and 3 others, “Study of communication circuit emulation using multi-FPGA system”, IEICE Technical Report (CS92-77-84), 1993 Vol. 92, No. 429, p. 49-56 Toshiaki Miyazaki and 4 others, "Latch insertion method for high-speed synchronous circuit on FPGA", Information Processing Society of Japan Research Report (93-DA-69), December 16, 1993 93, No. 111, p. 71-77 (58) Field surveyed (Int. Cl. ⁷ , DB name) G06F 17/50

Claims (1)

(57) [Claims] 1. A combination circuit having multiple inputs and one output, a latch connected to an output of the combination circuit, and selection means for selecting and outputting one of the output of the combination circuit and the output of the latch. A logic circuit comprising a plurality of basic circuits to perform a predetermined function by setting wiring between the basic circuits, wherein the basic circuit is a node, the wiring between the basic circuits is an edge, and the logic circuit A first step of making the logic circuit a directed graph, with all inputs of the logic element as a starting node and all outputs of the logic circuit as a terminating node, and reducing a loop existing in the directed graph to one node, A second step of connecting an edge connected to a node in the loop to a reduced node, a third step of defining a start node as a set A, and a node belonging to the set A A fourth step of redefining a set consisting of all nodes that can be directly reached by edges from the set as a set A, and a fifth step of checking whether or not the set A includes a terminal node.
A node using a latch or a node that can be reached via an edge to a node belonging to set A, or a node that can be reached via an edge and another node to set A A sixth step of checking whether or not there is a node corresponding to any of the included nodes; a node in which the corresponding node is deleted from the set A in the sixth step, and a node directly reachable from the deleted node by an edge In the set A, whether the set A includes a terminal node, and if not, return to the sixth step; and return to the sixth step. If there is no node to do, set Y
A ninth step of adding the set A to the set A and returning to the fourth step. In the fifth step or the eighth step, if the set A includes a terminal node, all nodes belonging to the set Y Latch embedding characterized by inserting a latch into a latch
A method for increasing the operating speed of read- only logic circuits.