Methods for allocating circuit elements between circuit groups

• US 5,341,308 A
• Filed: 05/17/1991
• Issued: 08/23/1994
• Est. Priority Date: 05/17/1991
• Status: Expired due to Term

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Mendel, David W.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/702,001
• Time in Patent Office: 1,194 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/125
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Circuit partitioning methods are enhanced by more accurately accounting for circuit nets which include connections external to the circuit being partitioned. The user can also prohibit movement of any circuit element or cell which the user does not want to have moved. The user can also prevent splitting of any net or set of cells which the user does not want to have split. The balance requirement of prior art methods is modified to allow circuit element moves which imbalance the partition. However, balance is ultimately restored by further circuit element moves.

Claims

1. A method of fabricating an electrical circuit which includes two subcircuits and at least one circuit node which is not in either of said subcircuits, each of said subcircuits including a plurality of circuit elements, each of said circuit elements requiring predetermined electrical connections to predetermined others of said circuit elements, and at least some of said circuit elements requiring predetermined electrical connections to said node, said method including the step of placing the circuit elements in the circuit so that the circuit elements are divided between the subcircuits, said placing step comprising a preliminary trial phase in which at least some of said circuit elements are moved between said subcircuits in an effort to reduce a variable which indicates the number of said electrical connections which must extend between said subcircuits, said preliminary trail phase of said placing step comprising the steps of:

identifying all circuit elements which require an electrical connection to said node;

after performing said identifying step and each time a circuit element which was identified in said identifying step is a first of the circuit elements identified in said identifying step to move from a subcircuit which previously contained all of said circuit elements identified in said identifying step to the other of said subcircuits, increasing said variable by approximately half the amount that said variable is increased when a circuit element connected only to other circuit elements in one of said subcircuits is moved to the other of said subcircuits; and

after performing said identifying step and each time a circuit element which was identified in said identifying step is moved to a subcircuit which previously contained all other circuit elements identified in said identifying step, decreasing said variable by approximately half the amount that said variable is decreased when a circuit element connected only to other elements in said subcircuits is moved to a subcircuit which contains all of the other circuit elements to which that circuit element is connected.

2. A method of fabricating an electrical circuit which includes two subcircuits, each of said subcircuits including a plurality of circuit elements, each of said circuit elements requiring predetermined electrical connections to predetermined others of said circuit elements, said method including the step of placing the circuit elements in the circuit so that the circuit elements are divided between the subcircuits, said placing step comprising a preliminary trial phase in which at least some of said circuit elements are moved between said subcircuits in an effort to reduce a variable which indicates the number of said electrical connections which must extend between said subcircuits, said preliminary trial phase of said placing step comprising the steps of:

initially placing said circuit elements in said subcircuits and designating at least one of said circuit elements as locked in the subcircuit in which that circuit element is initially placed;

after performing the preceding step, moving a circuit element which is not designated as locked from one of said subcircuits to the other in an effort to reduce said variable;

after performing the preceding step, designating as locked the circuit element which was moved during performance of the preceding step; and

repeating the two preceding steps as a continuation of said effort to reduce said variable.

3. A method of fabricating an electrical circuit which includes two subcircuits, each of said subcircuits including a plurality of circuit elements, each of said circuit elements requiring predetermined electrical connections to predetermined others of said circuit elements, said method including the step of placing the circuit elements in the circuit so that the circuit elements are divided between the subcircuits, said placing step comprising a preliminary trail phase in which at least some of said circuit elements are moved between said subcircuits in an effort to reduce a variable which indicates the number of said electrical connections which must extend between said subcircuits, said preliminary trial phase of said placing step comprising the steps of:

collectively identifying a subplurality of said circuit elements which are all in one of said subcircuits as a master circuit element;

after performance of the preceding step, treating said master circuit elements as a circuit element during performance of the succeeding steps;

moving a circuit element from one of said subcircuits to the other in an effort to reduce said variable; and

repeating the preceding step using different ones of said circuit elements as a continuation of said effort to reduce said variable.

4. The method defined in claim 3 wherein each of said circuit elements has an associated weight value which is used to ensure that the aggregate weights of the circuit elements in each of said subcircuits conform to a predetermined balance requirement, and wherein said step of treating said master circuit element comprises the step of:

computing a weight value for said master circuit element as the sum of the weight values of the circuit elements in said subplurality of circuit elements.

5. The method defined in claim 3 wherein circuit elements which are connected to one another are identified as a net, wherein data is maintained for each net which includes a reference to each circuit element in that net, and wherein said step of treating said master circuit element comprises the step of:

for each net containing one of the circuit elements in said subplurality, replacing said reference to said one of said circuit elements with a reference to said master circuit element.

6. A method of fabricating an electrical circuit which includes two subcircuits, each of said subcircuits including a plurality of circuit elements, each of said circuit elements requiring (1) predetermined electrical connections to predetermined others of said circuit elements, and (2) an associated portion of an overall circuit resource, and wherein said overall circuit resource must be divided between said subcircuits in accordance with a predetermined ratio range, said method including the step of placing the circuit elements in the circuit so that the circuit elements are divided between the subcircuits, said placing step comprising a preliminary trial phase in which at least some of said circuit elements are moved between said subcircuits in an effort to reduce a variable which indicates the number of said electrical connections which must extend between said subcircuits without causing the resulting division of said overall circuit resource between said subcircuits to be outside said predetermined ratio range, said preliminary trail phase of said placing step comprising the steps of:

(a) identifying a circuit element which has not yet been moved from one subcircuit to the other and which can be moved to the other subcircuit without producing a division of said overall circuit resource between said subcircuits which is outside of said ratio range, and if there is no such circuit element, then identifying a circuit element which has not been moved from one subcircuit to the other subcircuit even through moving the identified circuit element will produce a division of said overall circuit resource between said subcircuits which is outside of said ratio range;

(b) after the preceding step, moving the identified circuit element from said one subcircuit to said other subcircuit;

(c) after the preceding step, recomputing said number;

(d) after the preceding step, clearing any list of circuit element moves which may have to be reversed and skipping step (e) if either of the following conditions is satisfied;

(i) the value of said number computed in step (c) is less than any previously computed value and the division of said overall circuit resource between said subcircuits is within said predetermined ratio range, or (ii) the value of said number computed in step (c) is approximately equal to the smallest previously computed value of said number and the division of said overall circuit resource between said subcircuits is closer to said predetermined ratio range than said division was for the last accepted move;

(e) after the preceding step, adding to the list of circuit element moves which may have to be reversed the circuit element move performed in step (b);

(f) repeating the preceding steps while step (a) can be performed; and

(g) after step (a) can no longer be performed, reversing any circuit element moves in the list of circuit element moves which may have to be reversed.

7. The method defined in claim 6 wherein in each performance of step (a) the circuit element identified is the circuit element which will produce the greatest decrease in said number when that circuit element is moved from said one subcircuit to said other subcircuit.