Incremental logic synthesis system for efficient revision of logic circuit designs

• US 5,436,849 A
• Filed: 02/09/1993
• Issued: 07/25/1995
• Est. Priority Date: 02/09/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Drumm, Anthony D.
• Primary Examiner(s): Trans, Vincent N.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/015,567
• Time in Patent Office: 896 Days
• Field of Search: 364/488, 364/489, 364/490
• US Class Current: 716/106
• 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

An apparatus and method for incremental logic synthesis that transforms a revised technology-independent electronic digital circuit design into a revised technology-dependent design deviating as little as possible from the original technology-dependent design. The incremental synthesis procedure includes a forward sweep technique where nodes in the revised technology-independent model and the original technology-dependent design are compared to see if they map the same logical function of the inputs common to both designs. A backward sweep technique compares nodes in the revised technology-independent model to the unrevised technology-dependent design to see which outputs common to both map the same logical node functions. Portions of the revised technology-independent model with the same logical function as corresponding parts of the unchanged technology-dependent design are progressively eliminated, reducing the revised technology-independent design to an "increment" that is then conventionally synthesized and merged with the unchanged technology-dependent design to yield the revised technology-dependent design having only the minimal necessary revisions.

Claims

1. A method for performing incremental logic synthesis of a revised technology-dependent digital circuit design model M₂₂ from a revised technology-independent digital circuit design model M₁₂ and an unrevised technology-dependent digital circuit design model M₂₁, each said model including one or more digital logic functions having one or more inputs and one or more outputs, each said model having one or more boundary nodes to each of which are mapped one or more of said inputs and outputs, said models M₁₂ and M₂₁ sharing a first set of one or more said boundary nodes designated as Boolean inputs and a second set of one or more said boundary nodes designated as Boolean outputs, said method comprising the computer-executable steps of:

(a) performing one or more steps from a group consisting essentially of the following three unordered steps of;

(a.1) performing an exclusion procedure including the ordered steps of

(a.1.1) selecting one or more of said Boolean outputs to form an output group such that the logical function of said Boolean inputs in said model M₂₁ represented by each member of said output group is identical to the logical function of said Boolean inputs in said model M₁₂ represented by said each member, and

(a.1.2) deleting from said revised technology-independent design model M₁₂ each said digital logic function and each said input that maps only into said output group;

(a.2) performing one or more times a forward sweep procedure including the ordered steps of

(a.2.1) selecting one or more first pairs of said nodes to form a forward sweep group such that each said first node pair includes a first node in said model M₁₂ and a second node in said model M₂₁ where said first and second nodes represent identical logical functions of said Boolean inputs except for complimentary operators,

(a.2.2) redesignating as new inputs in said revised technology-independent design model M₁₂ each said first node member of said forward sweep group, and

(a.2.3) deleting from said revised technology-independent design model M₁₂ each said digital logic function and each said input that maps only into said new inputs;

(a.3) performing one or more times a backward sweep procedure including the ordered steps of

(a.3.1) selecting one or more second pairs of said nodes to form a backward sweep group such that each said second node pair includes a third node in said model M₁₂ and a fourth node in said model M₂₁ where each said Boolean output represents a logical function of said third nodes and said Boolean inputs in said model M₁₂ that is identical to the logical function of said fourth nodes and said Boolean inputs in said model M₂₁ at said each Boolean output except for complimentary operators,

(a.3.2) redesignating as new outputs in said revised technology-independent design model M₁₂ each said third node member of said backward sweep group, and

(a.3.3) deleting from said revised technology-independent design model M₁₂ each said digital logic function and each said output to which are mapped only said new outputs;

(b) synthesizing a new technology-dependent design model increment having a logical function equivalent to the portion of said model M₁₂ remaining after completion of said performing step (a); and

(c) merging said new technology-dependent design model increment with said unrevised technology-dependent design model M₂₁ to form said revised technology-dependent design model M₂₂.

2. The method of claim 1 wherein said performing step (a) is applied to said remaining portion of model M₁₂ and said new technology-dependent design model increment from said synthesizing step (b).

3. The method of claim 2 wherein said merging step (c) comprises the ordered steps of:

(c.1) disconnecting from the digital logic functions in said unrevised technology-dependent design model M₂₁ each said node belonging to said output group from said performing step (a.1) and each said node belonging to said backward sweep group from said performing step (a.3);

(c.2) connecting each input in said new technology-dependent design model increment to the node in said unrevised technology-dependent design model M₂₁ that is paired to said each input in said forward sweep group; and

(c.3) connecting each output in said new technology-dependent design model increment to a node in said unrevised technology-dependent design model M₂₁ that is paired to said each output in said backward sweep set.

4. The method of claim 3 wherein said selecting step (a.2.1) comprises the ordered steps of:

(a.2.1.1.) labeling each said node of said models M₂₁ and M₁₂ with a first bit vector representing the set of said inputs mapped to said each node;

(a.2.1.2) selecting one or more third pairs of said nodes having identical said first bit vectors, such that each said third node pair includes one said node from said model M₁₂ and one said node from model M₂₁ ; and

(a.2.1.3) selecting said forward sweep group from said one or more third node pairs.

5. The method of claim 4 wherein said selecting step (c.1) comprises the ordered steps of:

(a.3.1.1) labeling each said node of said models M₁₂ and M₂₁ with a second bit vector representing the set of said outputs into which said each node is mapped;

(a.3.1.2) selecting one or more fourth pairs of said nodes having identical said second bit vectors, such that each said third node pair includes one said node from said model M₁₂ and one said node from said model M₂₁ ; and

(a.3.1.3) selecting said backward sweep group from said one or more fourth node pairs.

6. The method of claim 1 wherein said merging step (c) comprises the ordered steps of:

(c.1) disconnecting from the digital logic functions in said unrevised technology-dependent design model M₂₁ each said node belonging to said output group from said performing step (a.1) and each said node belonging to said backward sweep group from said performing step (a.3);

(c.2) connecting each input in said new technology-dependent design model increment to the node in said unrevised technology-dependent design model M₂₁ that is paired to said each input in said forward sweep group; and

(c.3) connecting each output in said new technology-dependent design model increment to a node in said unrevised technology-dependent design model M₂₁ that is paired to said each output in said backward sweep set.

7. The method of claim 1 wherein said selecting step (a.2.1) comprises the ordered steps of:

(a.2.1.1) labeling each said node of said models M₂₁ and M₁₂ with a first bit vector representing the set of said inputs mapped to said each node;

(a.2.1.2) selecting one or more third pairs of said nodes having identical said first bit vectors, such that each said third node pair includes one said node from said model M₁₂ and one said node from model M₂₁ ; and

(a.2.1.3) selecting said forward sweep group from said one or more third node pairs.

8. The method of claim 1 wherein said selecting step (a.3.1) comprises the ordered steps of:

(a.3.1.1) labeling each said node of said models M₁₂ and M₂₁ with a second bit vector representing the set of said outputs into which said each node is mapped;

(a.3.1.2) selecting one or more fourth pairs of said nodes having identical said second bit vectors, such that each said third node pair includes one said node from said model M₁₂ and one said node from said model M₂₁ ; and

(a.3.1.3) selecting said backward sweep group from said one or more fourth node pairs.

9. A system for performing incremental logic synthesis of a revised technology-dependent digital circuit design model M₂₂ from a revised technology-independent digital circuit design model M₁₂ and an unrevised technology-dependent digital circuit design model M₂₁, each said model including one or more digital logic functions having one or more inputs and one or more outputs, each said model having one or more boundary nodes to each of which are mapped one or more of said inputs and outputs, said models M₁₂ and M₂₁ sharing a first set of one or more said boundary nodes designated as Boolean inputs and a second set of one or more said boundary nodes designated as Boolean outputs, said system comprising:

reduction means for identifying and limiting the revision of said model M₂₁ needed to obtain said model M₂₂, said reduction means including one or more elements from a group consisting essentially of exclusion means, forward sweep means and backward sweep means,

said exclusion means including

first selection means for selecting one or more of said Boolean outputs to form an output group such that the logical function of said Boolean inputs in said model M₂₁ represented by each member of said output group is identical to the logical function of said Boolean inputs in said model M₁₂ represented by said each member, and

first deletion means for deleting from said revised technology-independent design model M₁₂ each said digital logic function and each said input that maps only into said output group,

said forward sweep means including

second selection means for selecting one or more first pairs of said nodes to form a forward sweep group such that each said first node pair includes a first node in said model M₁₂ and a second node in said model M₂₁ where said first and second nodes represent identical logical functions of said Boolean inputs except for one or more complimentary operators,

first deletion means for redesignating as new inputs in said revised technology-independent design model M₁₂ each said first node member of said forward sweep group, and

second deletion means for deleting from said revised technology-independent design model M₁₂ each said digital logic function and each said input that maps only into said new inputs, and

said backward sweep means including

third selection means for selecting one or more second pairs of said nodes to form a backward sweep group such that each said second node pair includes a third node in said model M₁₂ and a fourth node in said model M₂₁ where each said Boolean output represents a logical function of said third nodes and said Boolean inputs in said model M₁₂ that is identical to the logical function of said fourth nodes and said Boolean inputs in said model M₂₁ at said each Boolean output except for complimentary operators,

second designation means for redesignating as new outputs in said revised technology-independent design model M₁₂ each said third node member of said backward sweep group, and

third deletion means for deleting from said revised technology-independent design model M₁₂ each said digital logic function and each said output to which only said new outputs are mapped;

logic synthesis means for producing a new technology-dependent design model increment having a logical function equivalent to the portion of said model M₁₂ remaining after any operation of said reduction means; and

merger means for merging said new technology-dependent design model increment with said unrevised technology-dependent design model M₂₁ to form said revised technology-dependent design model M₂₂.

10. The method of claim 9 wherein said merger means comprises:

disconnection means for disconnecting from the digital logic functions in said unrevised technology-dependent design model M₂₁ each said node belonging to said output group and each said node belonging to said backward sweep group;

first connection means for connecting each input in said new technology-dependent design model increment to the node in said unrevised technology-dependent design model M₂₁ that is paired to said each input in said forward sweep group; and

said connection means for connecting each output in said new technology-dependent design model increment to a node in said unrevised technology-dependent design model M₂₁ that is paired to said each output in said backward sweep set.

11. The method of claim 9 wherein said second selection means comprises:

labeling means for labeling each said node of said models M₂₁ and M₁₂ with a first bit vector representing the set of said inputs mapped to said each node;

fourth selection means for selecting one or more third pairs of said nodes having identical said first bit vectors, such that each said third node pair includes one said node from said model M₁₂ and one said node from model M₂₁ ; and

fifth selection means for selecting said forward sweep group from said one or more third node pairs.

12. The method of claim 9 wherein said third selection means comprises:

labeling means for labeling each said node of said models M₁₂ and M₂₁ with a second bit vector representing the set of said outputs into which said each node is mapped;

fourth selection means for selecting one or more fourth pairs of said nodes having identical said second bit vectors, such that each said third node pair includes one said node from said model M₁₂ and one said node from said model M₂₁ ; and

fifth selection means for selecting said backward sweep group from said one or more fourth node pairs.