Methods for partitioning circuits in order to allocate elements among multiple circuit groups

• US 5,659,717 A
• Filed: 07/31/1995
• Issued: 08/19/1997
• Est. Priority Date: 07/31/1995
• Status: Expired due to Term

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Mendel, David W., Tse, John
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): FREJD, RUSSELL WARREN
• Application Number:
  US08/508,401
• Time in Patent Office: 750 Days
• Field of Search: 395/500, 364/148, 364/488, 364/489, 364/490, 364/491, 364/468, 437/250
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Improved circuit partitioning methods are provided which combine the advantage of multiple starting positions of the random initial placement approach with the advantage of optimal starting positions of the greedy initial placement approach, by starting with greedy initial placement and modifying partitioning constraints on subsequent passes so that each pass begins in a new position, In addition, the partitioning goals of interconnection minimization and resource utilization efficiency may be prioritized according to a design goal by manipulating the manner in which partitioning constraints are changed during each partitioning pass. Furthermore a user may adjust the weight of the benefits for eliminating existing interconnections and the weight of the penalties for adding new interconnections in accordance with a design goal.

Claims

1. A method for partitioning a plurality of circuit elements within a plurality of circuit groups, the method of partitioning comprising the steps of:

(a) initially placing the plurality of circuit elements in accordance with a greedy initial placement method subject to at least one partitioning constraint associated with each circuit group of the plurality of circuit groups, and also subject to at least one physical constraint also associated with each circuit group of the plurality of circuit groups;

(b) performing a standard partitioning operation in which a partition cost variable is computed which indicates the number of connections required between each circuit group of the plurality of circuit groups with the objective of reducing the number by moving circuit elements from at least one of the plurality of circuit groups to another of the circuit groups in order to obtain a partition result indicative of the position of each of the plurality of circuit elements, wherein the partition result is associated with the partition cost variable;

(c) comparing the partition cost variable obtained at step (b) with a previously obtained partition cost variable, and storing the partition result obtained at step (b) if its associated partition cost variable is less than the previously obtained partition cost variable;

(d) identifying one or more circuit groups of the plurality of circuit groups that violate one or more of said at least one partitioning constraint, and proceeding to step (g) if no such circuit groups exist;

(e) changing one or more of said at least one partitioning constraint for all circuit groups identified at step (d);

(f) repeating step (a) using one or more of said at least one partitioning constraint changed at step (e); and

(g) returning the partition result stored at step (c).

2. The method of claim 1, wherein said at least one physical constraint comprises a capacity limit indicative of the maximum amount of circuit elements that may be placed into a particular circuit group from the plurality of circuit groups, wherein each of the plurality of circuit groups may have varying capacity limits.

3. The method of claim 2 further comprising the step of:

(h) assigning a first status to the partition result obtained at step (b) if it is determined at step (d) that none of the plurality of circuit groups violate one or more of said at least one partitioning constraint, and assigning a second status to the partition result if it is determined at step (d) that at least one of the plurality of circuit groups violate one or more of said at least one partitioning constraint.

4. The method of claim 3 further comprising the step of:

(i) selecting a value for a multiple pass variable from a first value and a second value, wherein;

if the first value is selected, the partitioning operation of steps (b) thru (g) stops after the first partition result having the first status is obtained, and wherein

if the second value is selected, the partitioning operation of steps (b) thru (g) is repeated until the partition result with the lowest partition cost variable is obtained.

5. The method of claim 2 further comprising the step of:

(j) selecting a partitioning priority from a plurality of design goals, the plurality of design goals comprising;

minimization of the number of connections required between the two circuit groups, and maximization of resource use of the circuit element groups, this step being performed prior to step (a).

6. The method of claim 5 wherein said at least one partitioning constraint changed at step (e) comprises a capacity variable indicative of the maximum amount of circuit elements that may be placed into a particular circuit group, wherein the capacity variable for the particular circuit group must be lower than or equal to the capacity limit for that circuit group.

7. The method of claim 6, wherein the design goal selected at step (j) is the minimization of the number of connections required between the plurality of circuit groups, further comprises the step of:

(k) setting the capacity variable of each circuit group equal to the capacity limit for that circuit group, this step being performed prior to step (a).

8. The method of claim 7 wherein at step (e) the changing of the capacity variable comprises decreasing the capacity variable by a first programmable amount, wherein the total magnitude of the capacity variables for all circuit groups from the plurality of circuit element groups must be less than or equal to the total number of circuit elements in the plurality of circuit elements.

9. The method of claim 8 further comprising the steps of:

determining whether one or more circuit groups of the plurality of circuit groups violate their capacity variable by having a number of circuit elements which exceeds the capacity variable, this step being performed after step (e);

(m) unplacing circuit elements from the circuit group in violation of its capacity variable so that the number of circuit elements remaining in the circuit group is less than or equal to its capacity variable; and

(n) repeating step (a) so that the circuit elements unplaced at step (m) may be placed into one or more circuit groups of the plurality of circuit groups.

10. The method of claim 6, wherein the design goal selected at step (j) is the maximization of resource use of the circuit element groups, further comprising the step of:

(o) setting the capacity variable of each circuit group to a value equal to the capacity limit for that circuit group reduced by a second programmable amount, this step being performed prior to step (a).

11. The method of claim 10 wherein at step (e) the changing of the capacity variable comprises increasing the capacity variable by the first programmable amount, wherein the capacity variable for each circuit group may not exceed the capacity limit for that circuit group.

12. A method for partitioning a plurality of circuit elements between two circuit groups in accordance with the objective of maximizing a gain cost variable, wherein each circuit element comprises a first plurality of pins, wherein a first constraint limits the plurality of pins to its value, wherein the two circuit groups comprise a first plurality of interconnections between one another, wherein a second constraint limits the plurality of interconnections to its value, and wherein when a circuit element is moved from one of the circuit groups to the other of the circuit groups, a gain variable is increased by a first gain modifier for each pin from the plurality of pins which is eliminated during the move, decreased by the first gain modifier for each new pin added to the plurality of pins during the move, increased by a second gain modifier for each interconnection from the plurality of interconnections which is eliminated during the move, and decreased by a second gain modifier for each new interconnection added to the plurality of interconnections during the move, the method for partitioning comprising the steps of:

(a) selecting the second gain modifier;

(b) performing a standard partitioning operation in which an interconnections variable is computed which indicates the number of connections required between the two circuit groups with the objective of reducing the number by moving circuit elements from one of the circuit groups to the other of the circuit groups in order to obtain a partition result;

(c) determining a gain cost variable using the first and the second gain cost modifiers;

(d) determining if the partition result violates both the first and the second constraints, proceeding to step (j) if the partition result violates both the first and the second constraints, and proceeding to step (e) otherwise;

(e) determining if the partition result violates the second constraint, proceeding to step (f) if the partition result violates the second constraint, and proceeding to step (g) otherwise;

(f) discarding the partition result, decreasing the second gain cost modifier via a decreasing function, and returning to step (b);

(g) determining if the partition result violates the first constraint, proceeding to step (h) if the partition result violates the first constraint, and otherwise proceeding to step (i);

(h) discarding the partition result, increasing the second gain cost modifier via an increasing function, and returning to step (b);

(i) returning the partition result obtained at step (b);

(j) notifying a user that a partition is impossible to obtain.