Method to efficiently reduce the number of connections in a circuit

• US 5,257,201 A
• Filed: 08/14/1989
• Issued: 10/26/1993
• Est. Priority Date: 03/20/1987
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Trevillyan, Louise H., Berman, Charles L.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/394,247
• Time in Patent Office: 1,534 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/200, 364/900, 364/578, 395/140, 395/141
• US Class Current: 716/103
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist

Abstract

A provided logic circuitry implementation in a given technology includes n signals and m nodes. A final logic circuitry implementation is produced therefrom which is the functional equivalent of, and contains fewer connections than, the provided logic circuitry implementation. A given one of the n signals is first processed, and global information is computed for this signal. A graphical representation of connections between the m nodes is derived from the computed global information. A list of nodes that form a cut-set is produced from the graphical representation, and an optimized logic circuitry implementation is provided as a function thereof. Each of the remaining ones of the n signals are processed sequentially, as above, to form successive optimized logic circuitry implementations, with the processing of the nth signal resulting in the final logic circuitry implementation.

Claims

1. A method of operating a computer to take a provided network configuration including n signals and m nodes and producing therefrom a final network configuration which is the functional equivalent of, and contains fewer connections than, said provided network configuration, said method comprising the steps of:

computing global information relative to a given one of said n signals;

generating a derived graphical representation of connections between said m nodes from said computed global information;

deriving from said derived graphical representation of connections a list of nodes that separates a source node from a sink node, and providing a reduced number of connections between said nodes in an intermediate network configuration as determined from the derived list of nodes; and

repeating the above steps for each of the remaining ones of said n signals, with the completion of the repetition of steps providing the reduced number of connections in said final network configuration.

2. A method of operating a computer to take an original circuit configuration of logic devices including n signals and m nodes and producing therefrom a new circuit configuration which is the functional equivalent of, and contains fewer connections than, said original circuit configuration, said method comprising the steps of:

computing global information relative to a given one of said n signals;

generating a derived graphical representation of connections between said m nodes from said computed global information;

deriving from said derived graphical representation of connections a list of nodes to which said given one of said n signals should be connected, and providing a reduced number of connections in an intermediate circuit configuration as determined from the derived list of nodes; and

repeating the above steps sequentially for each of the remaining ones of said n signals, with the connections in said original circuit configuration being replaced with a reduced number of connections in said intermediate circuit configuration, with the completion of the nth sequential repetition of steps resulting in a new reduced set of connections in said new circuit configuration.

3. A method of operating a computer to take a provided logic circuitry implementation in a given technology, which circuitry includes n signals and m nodes and producing therefrom a final logic circuitry implementation which is the functional equivalent of, and contains fewer connections than, said provided logic circuitry implementation, said method comprising the steps of:

(a) taking a given one of said n signals and computing global information relative thereto;

(b) generating a derived graphical representation of connections between said m nodes from said computed global information;

(c) deriving from said derived graphical representation of connections a list of nodes that separates a source node from a sink node, and providing a reduced number of connections in an intermediate logic circuitry implementation as determined from the derived list of nodes; and

(d) repeating steps (a) thru (c) sequentially for each of the remaining ones of said n signals, with the completion of the nth sequential repetition of steps providing the reduced number of connections in said final logic circuitry implementation.

4. A method of operating a computer to take a provided logic circuitry implementation in a given technology, which circuitry includes n signals and m nodes, and producing therefrom a final logic circuitry implementation which is the functional equivalent of, and contains fewer connections than, said provided logic circuitry implementation, said method comprising the steps of:

(a) taking a given one of said n signals and computing global information relative thereto;

(b) generating a derived graphical representation of connections between said m nodes from said computed global information;

(c) deriving from said derived graphical representation of connections a list of nodes that separates a source node from a sink node;

(d) providing a reduced number of connections in an intermediate circuitry implementation as a function of the derived list of nodes; and

(e) repeating steps (a) thru (d) sequentially for each of the remaining ones of said n signals, with the completion of the nth sequential repetition of steps (a) thru (d) resulting in the reduced number of connections in said final logic circuitry implementation.

5. The method of claim 4, wherein step (d) includes the steps of:

(1) getting a node from the derived list of nodes of said derived graphical representation, and getting the corresponding node in said provided logic circuitry;

(2) determining if said given one of said n signals is connected to the node gotten in step (1), if not connect it, and if so connected go to step (3);

(3) determining if there are more nodes in the derived list of nodes, if there are more nodes in the derived list of nodes repeat steps (1) and (2), if there are no more nodes in the derived list of nodes go to step (4);

(4) getting a sink node of said given one of said n signals in said provided logic and getting the corresponding node in said derived graph;

(5) determining if said sink node is in said derived list of nodes, if said sink node is not in said derived list disconnect it, if said sink node is in said derived list go to step (6);

(6) determining if there are more sink nodes in said provided logic circuitry, if there are more sink nodes, repeat steps (4) and (5), if there are not more sink nodes, said intermediate logic circuitry implementation is complete.

6. The method of claim 4, wherein step (b) includes the steps of:

(1) selecting a node in said derived graph;

(2) determining if the selected node has more than one input edge, if if does not go to step (4), if it does go to step (3);

(3) splitting the selected node into two new nodes, and copying the input edges from the selected to the first new node, and building an edge between the first new node and the second new node, and copying the out-edge of the selected node to the second new node, and associate the selected node with the second new node;

(4) determing if there are more nodes in the derived graph, if there are more nodes go to step (1), if there are not more nodes go to step (5);

(5) select an edge from the derived graph;

(6) determining if the to-node of the edge is a legal connection point, if so assign a capacity to the edge which describes the desirability of having a connection of the given signal at this point, if not assigning an infinite capacity to the edge;

(7) determining if there are more edges in the derived graph, if there are more edges return to step (5), if there are not more edges go to step (7);

(8) applying a max-flow/min-cut analysis to the derived graph, and deriving therefrom a list of nodes to which said given one of said n signals should be connected.

7. A method of operating a computer to tab an original network configuration having an original set of connections, and including at least one signal and m nodes and producing therefrom a new network configuration which is the functional equivalent of, and contains fewer connections than, said original network configuration, said method comprising the steps of:

determining which of said m nodes comprise FRONTIER nodes for said one signal in said original network configuration;

determining a new set of a reduced number of connections which generates the same set of FRONTIER nodes for said one signal; and

replacing the original set of connections in said original network configuration with said new set of a reduced number of connections for producing said new network configuration having a reduced number of connections.

8. A method of operating a computer to take an original logic circuit implementation in a given technology having an original set of connections, and including n signals and m nodes and producing therefrom a new logic circuit implementation which is the functional equivalent of, and contains fewer connections than, said original logic circuit implementation, said method comprising the steps of:

(a) determining which of said m nodes comprise FRONTIER nodes for a given one of said n signals in said original logic circuit implementation;

(b) determining a different set of a reduced number of connections which generates the same set of frontier nodes for said given one of said n signals;

(c) replacing the original set of connections in said original circuit with said different set of a reduced number of connections for producing an intermediate logic circuit implementation; and

repeating steps (a) through (c) for each of the remaining ones of said n signals, which said intermediate logic circuit implementation being replaced by the reduced number of connections in said new logic circuit implementation.