Methods for allocating circuit design portions among physical circuit portions

• US 5,787,009 A
• Filed: 02/20/1996
• Issued: 07/28/1998
• Est. Priority Date: 02/20/1996
• Status: Expired due to Term

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Pedersen, Bruce B.
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US08/603,222
• Time in Patent Office: 889 Days
• Field of Search: 364/488-491, 364/578, 235/150
• US Class Current: 716/125
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Partitioning of a circuit design to facilitate economical implementation of that circuit in a physical circuit that is made up of two or more physical subcircuits is improved by starting with two different, conventionally produced partitions of the design and combining selected features of those two starting partitions to produce a final partition that is better than either of the starting partitions.

Claims

1. A method of implementing an electrical circuit design in a physical circuit which includes a plurality of physical subcircuits, said circuit design including a plurality of circuit elements and a plurality of connections between said elements, said method comprising the steps of:

partitioning said circuit design into a first plurality of design subcircuits, each of which is implementable in a respective one of said physical subcircuits;

partitioning said circuit design into a second plurality of design subcircuits, each of which is implementable in a respective one of said physical subcircuits, said first and second pluralities being different from one another;

identifying each connected component in each of said design subcircuits, a connected component being any subplurality of said elements which are within said design subcircuit and which are all connected to one another by one or more of said connections which extend only to elements in said subplurality and which connections are therefore also part of said connected component;

for each connected component in each of said first and second pluralities, performing the following substeps (a) through (d) for said connected component;

(a) identifying as adjacent connected components all connected components in the other of said first and second pluralities that have at least one element in common with said connected component;

(b) determining as a first number the number of said connections which are part of said connected component;

(c) determining as a second number the number of said connections which are part of said adjacent connected components and which are also connected to at least one element of said connected component, said connections in said second number being referred to as adjacent connections; and

(d) determining whether said first or second number is predominant, and if said first number is predominant, then deleting said adjacent connections from said adjacent connected components, with consequent modification of the elements and connections which are part of said adjacent connected components;

combining the connected components which remain in said first and second pluralities after performance of the preceding steps to produce a plurality of combined connected components;

for each combined connected component, including said combined connected component in an associated modified design subcircuit along with other combined connected components and elements that are not part of any combined connected component to the extent that the resulting modified design subcircuit can be implemented in a respective one of said physical subcircuits; and

implementing each of said modified design subcircuits in said respective one of said physical subcircuits.

2. The method defined in claim 1 wherein said step of performing substeps (a)-(d) is repeated for all of said connected components until no further adjacent connections are being deleted as a result of performance of substep (d).

3. The method defined in claim 1 wherein said including step comprises the steps of:

for each combined connected component, performing the following substeps (e) through (i);

(e) identifying as first related connected components the connected components that remain in said first plurality and that have at least one element in common with said combined connected component;

(f) determining as a third number the number of connections that are part of any of said first related connected components and connect to but are not part of said combined connected component;

(g) identifying as second related connected components the connected components that remain in said second plurality and that have at least one element in common with said combined connected component;

(h) determining as a fourth number the number of connections that are part of any of said second related connected components and connect to but are not part of said combined connected component; and

(i) determining whether said third number or said fourth number predominates, and if said third number predominates, then deleting from said connected components that remain in said second plurality the connections that account for said fourth number, with consequent modification of the elements and connections which are part of said second related connected components, or if said fourth number predominates, then deleting from said connected components that remain in said first plurality the connections that account for said third number, with consequent modification of the elements and connections which are part of said first related connected components; and

combining the connected components which remain in said first and second pluralities after performance of the preceding steps to produce a plurality of modified combined connected components which take the place of said combined connected components in steps performed subsequently.

4. The method defined in claim 1 wherein said including step comprises the step of:

for each combined connected component, performing the following substep;

for each connection that is not part of any combined connected component but that is connected to said combined connected component, determining whether said combined connected component together with that connection and all other combined connected components and elements to which that connection connects can be implemented in a respective one of said physical subcircuits, and if so, then modifying said combined connected component to include said connection and said other combined connected components and elements to which that connection connects.

5. The method defined in claim 1 wherein said including step comprises the step of:

bin-packing said combined connected components and elements that are not part of any combined connected component into said modified design subcircuits.

6. The method defined in claim 3 wherein said including step further comprise the step of:

for each combined connected component that results from the performance of the steps of claim 3, performing the following substep;

for each connection that is not part of any combined connected component but that is connected to said combined connected component, determining whether said combined connected component together with that connection and all other combined connected components and elements to which that connection connects can be implemented in a respective one of said physical subcircuits, and if so, then modifying said combined connected component to include said connection and said other combined connected components and elements to which that connection connects.

7. The method defined in claim 6 wherein said including step further comprises the step of:

bin-packing said combined connected components that result from the performance of the steps of claim 6 and elements that are not part of any of said combined connected components into said modified design subcircuits.

8. A method of implementing an electrical circuit design in a physical circuit which includes a plurality of physical subcircuits, said circuit design including a plurality of circuit elements and a plurality of connections between said elements, said method comprising the steps of:

representing said circuit design as a plurality of vertices joined by edges, each of said vertices representing a respective one of said elements and each of said edges representing a respective one of said connections that extend to the elements represented by the vertices joined by said edge;

partitioning said vertices and edges into a first plurality of design subcircuits, each of which is implementable in a respective one of said physical subcircuits;

partitioning said vertices and edges into a second plurality of design subcircuits, each of which is implementable in a respective one of said physical subcircuits, said first and second pluralities being different from one another;

identifying each connected component in each of said design subcircuits, a connected component being any subplurality of said vertices and edges which are entirely within said design subcircuit and which are all joined to one another by those edges;

for each connected component in each of said first and second subpluralities, performing the following substeps (a) through (d);

(a) identifying as adjacent connected components all connected components in the other of said first and second pluralities that have at least one vertex in common with said connected component;

(b) determining as a first number the number of said edges which are part of said connected component;

(c) determining as a second number the number of said edges which are part of said adjacent connected components and which are also joined to at least one element of said connected component, said edges in said second number being referred to as adjacent edges; and

(d) determining whether said first or second number is predominant, and if said first number is predominant, then deleting said adjacent edges from said adjacent connected components, with consequent modification of the vertices and edges which are part of said adjacent connected components;

combining the connected components which remain in said first and second pluralities after performance of the preceding steps to produce a plurality of combined connected components;

for each combined connected component, including said combined connected component in an associated modified design subcircuit along with other combined connected components and vertices that are not part of any combined connected component to the extent that the resulting modified design subcircuit can be implemented in a respective one of said physical subcircuit; and

implementing each of said modified design subcircuits in said respective one of said physical subcircuits.

9. The method defined in claim 8 wherein said step of performing substeps (a)-(d) is repeated for all of said connected components until no further adjacent edges are being deleted as a result of performance of substep (d).

10. The method defined in claim 8 wherein said including step comprises the steps of:

for each combined connected component, performing the following substeps (e) through (i);

(e) identifying as first related connected components the connected components that remain in said first plurality and that have at least one vertex in common with said combined connected component;

(f) determining as a third number the number of edges that are part of any of said first related connected components and that join to but are not part of said combined connected component;

(g) identifying as second related connected components the connected components that remain in said second plurality and that have at least one vertex in common with said combined connected component;

(h) determining as a fourth number the number of edges that are part of any of said second related connected components and join to but are not part of said combined connected component; and

(i) determining whether said third number or said fourth number predominates, and if said third number predominates, then deleting from said connected components that remain in said second plurality the edges that account for said fourth number, with consequent modification of the vertices and edges which are part of said second related connected components, or if said fourth number predominates, then deleting from said connected components that remain in said first plurality the edges that account for said third number, with consequent modification of the vertices and edges which are part of said first related connected components; and

combining the connected components which remain in said first and second pluralities after performance of the preceding steps to produce a plurality of modified combined connected components which take the place of said combined connected components in steps performed subsequently.

11. The method defined in claim 8 wherein said including step comprises the step of:

for each combined connected component, performing the following substep;

for each edge that is not part of any combined connected component but that is joined to said combined connected component, determining whether said combined connected component together with that edge and all other combined connected components and vertices to which that edge is joined can be implemented in a respective one of said physical subcircuits, and if so, then modifying said combined connected component to include said edge and said other component connected components and vertices to which that edge is joined.

12. The method defined in claim 8 wherein said including step comprises the step of:

bin-packing said combined connected components and vertices that are not part of any combined connected component into said modified design subcircuits.

13. The method defined in claim 10 wherein said including step further comprises the step of:

for each combined connected component that results from the performance of the steps of claim 10, performing the following substep;

for each edge that is not part of any combined connected component but that is joined to said combined connected component, determining whether said combined connected component together with that edge and all other combined connected components and vertices to which that edge is joined can be implemented in a respective one of said physical subcircuits, and if so, then modifying said combined connected component to include said edge and said other combined connected components and vertices to which that edge is joined.

14. The method defined in claim 13 wherein said including step further comprises the step of:

bin-packing said combined connected components that result from the performance of the steps of claim 13 and vertices that are not part of any of said combined connected components into said modified design subcircuits.