Method and apparatus for measuring congestion in a partitioned region

A method of placing circuit modules in a region of an integrated circuit (“IC”) layout, said IC layout having a plurality of circuit elements, wherein a plurality of nets represent interconnections between said circuit elements, each net defined to include a set of circuit elements, the method comprising:

• a) partitioning the IC region into several sub-regions, wherein a plurality of line paths exist between said sub-regions;
• b) for each particular net, identifying the set of sub-regions containing the circuit elements of the particular net,
• c) for each particular net, identifying the probabilities of said line paths being used by one or more connection graphs that represent the topology of interconnect lines necessary for connecting the set of sub-regions identified for the particular net;
• and
• d) computing a placement congestion cost for said region based on the identified probabilities.

A method of placing circuit modules in a region of an integrated circuit (“IC”) layout, said IC layout having a plurality of circuit elements, wherein a plurality of nets represent interconnections between said circuit elements, each net defined to include a set of circuit elements, the method comprising:

• a) partitioning the IC region into several sub-regions, wherein a plurality of edges exist between said sub-regions;
• b) for each particular net, identifying the set of sub-regions containing the circuit elements of the particular net;
• c) for each particular net, identifying a set of edges intersected by at least one connection graph that represents the topology of one or more interconnect lines necessary for connecting the set of sub-regions identified for the particular net;
• and
• d) computing a placement congestion cost for said region based on the identified set of edges.

A method of placing circuit modules in a region of an integrated circuit (“IC”) layout, said IC layout having a plurality of circuit elements, wherein a plurality of nets represent interconnections between said circuit elements, each net defined to include a set of circuit elements, the method comprising:

• a) partitioning the IC region into several sub-regions, wherein a plurality of line paths exist between said sub-regions;
• b) for each particular net, identifying the set of sub-regions containing the circuit elements of the particular net;
• c) for each particular net, identifying a set of line paths used by at least one connection graph that represents the topology of one or more interconnect lines necessary for connecting the set of sub-regions identified for the particular net;
• and
• d) computing a placement congestion cost for said region based on the identified set of line paths.