Timing driven placement

A method for determining placement of circuit elements, comprising the steps of:

• describing said circuit in logical form, said logical block form containing a plurality of logical blocks interconnected by a plurality of nets;
• describing a physical space within which to design an integrated circuit;
• partitioning said logical block form into a plurality of segments, each of said segments containing a plurality of logical blocks, each of said segments connected to other segments by global nets;
• partitioning said physical space into a plurality of precincts;
• randomly assigning each of said segments to one of said precincts;
• generating path equations, said path equations representing delays on said global nets as a function of said segments assignment to said precincts;
• determining slack from said path equations;
• optimizing said slack, said slack optimization interchanging a plurality of segments between said assigned precincts, said slack optimization utilizing said path equations to measure said slack, said measurement expressed in a cost function, said cost function efficiently evaluating timing and wiring changes in said circuit design from said segment interchanges, said slack optimization minimizing said cost function, said slack optimization indicating a final assignment of said segments to said precincts when said slack is optimized;
• and
• placing said segments into said precincts indicated by said final assignment.

A method for determining placement of circuit elements comprising the steps of:

• assigning logic blocks to a plurality of segments, said segments interconnected by a plurality of nets;
• calculating slack associated with said plurality of nets;
• selecting a plurality of critical nets based on slack;
• evaluating a plurality of logic block moves between said segments for each of said critical nets, said evaluation determining a new net slack for each of said moves;
• selecting a move for each critical net which provides the largest improvement in slack;
• and
• making said selected block move when said new net associated with said block move has a larger slack than said critical net slack.

A method for determining placement of circuit elements comprising the steps of:

• assigning logic blocks to a plurality of precincts, said precincts interconnected by a plurality of nets;
• calculating slack associated with each of said plurality of nets;
• identifying a plurality of critical nets based on said slack;
• evaluating a plurality of logic block moves between precincts for each of said critical nets, said evaluation determining a new slack for each of said moves;
• selecting a block move for each critical net which provides the largest improvement in slack;
• and
• making said selected block move when said new net associated with said block move has a larger slack than said critical net slack.

A method for determining placement of circuit elements comprising the steps of:

• assigning logic blocks to a plurality of precincts, said precincts interconnected by a plurality of nets;
• calculating slack associated with each of said plurality of nets;
• sorting said plurality of nets by a slack;
• evaluating a plurality of logic block moves between precincts for each of said plurality of nets to determine capacitance and wiring cost;
• selecting a block move for each net which provides the lowest cost;
• and making said selected block move when said capacitance associated with said move is not increased on a critical net.

A method for determining placement of circuit elements comprising the steps of:

• assigning logic blocks of said circuit elements to a plurality of precincts, said precincts interconnected by a plurality of nets, said nets interconnect a plurality of logic blocks, said precincts forming a circuit;
• optimizing said logic block placement within said precincts, said optimization placing logic blocks associated with critical nets within said precincts;
• and
• optimizing said precinct placement in said circuit to enhance wiring, said precinct placement optimization overlapping precinct edges.

A method for determining placement of circuit elements, comprising the steps of:

• describing said circuit elements in logical block form, said logical block form containing a plurality of logical blocks interconnected by a plurality of nets;
• describing a physical space within which to design an integrated circuit;
• partitioning said logical block form into a plurality of segments, each of said segments containing a plurality of logical blocks, each of said segments connected to other segments by global nets;
• calculating slack associated with said plurality of global nets;
• selecting a plurality of critical nets from said global based on slack;
• evaluating a plurality of logic block moves between said segments for each of said critical nets, said evaluation determining a new net slack for each of said moves;
• selecting a move for each critical net which provides the largest improvement in slack;
• making said selected block move when said new net associated with said block move has a larger slack than said critical net slack.
• partitioning said physical space into a plurality of precincts;
• initially assigning each of said segments to one of said precincts;
• generating path equations, said path equations representing delays on said global nets as a function of said segments assignment to said precincts;
• determining slack from said path equations;
• optimizing said slack, said optimization interchanging a plurality of segments between said assigned precincts, said optimization utilizing said path equations to measure said slack, said measurement being expressed in a cost function, said cost function efficiently evaluating timing and wiring changes in said circuit design, said optimization minimizing said cost function, said optimization indicating a final assignment of said segments to said precincts when said slack is optimized;
• placing said segments into said precincts indicated by said final assignment;
• moving at least one logic block on a net between precincts connected by the net, said movement improving slack associated with said net, and
• moving at least one logic block between precincts when said move does not increase capacitance on said net and when said move improves precinct wiring.

A system for placing circuit elements, comprising:

• a database means for storing a description of a circuit, said description containing placement information of a plurality of logic blocks within said circuit, said logic blocks interconnected by nets;
• a logical partitioning means for separating said plurality of logic blocks into a plurality of segments, said segments interconnected by global nets;
• a path equation generation means for generating path equations representing delays on said global nets;
• a slack determining means for determining slack from said path equations and said circuit description;
• a global placement means for optimizing said slack;
• and
• a circuit migration means for physically placing said plurality of logic blocks in said circuit.

A system for placing circuit elements, comprising:

• a data base storage means for storing an assignment of logic blocks to a plurality of precincts, said precincts interconnected by a plurality of nets;
• a calculating means for calculating slack associated with each of said plurality of nets;
• a first selection means for selecting a plurality of critical nets based on said slack;
• an evaluation means for evaluating a plurality of logic block moves between said plurality of precincts for each of said critical nets, said evaluation determines a new net slack for each of said moves;
• a second selection means for selecting a logic block move for each critical net which provides the largest improvement in slack;
• and
• a movement means for making said selected move when said new net associated with said selected move has a larger slack than said critical net slack.

A system for placing circuit elements, comprising:

• a data base storage means for storing an assignment of logic blocks to a plurality of precincts, said precincts interconnected by a plurality of nets;
• a calculating means for calculating slack associated with each of said plurality of nets;
• a sorting means for sorting said nets by slack;
• an evaluation means for evaluating a plurality of logic block moves between precincts for each of said plurality of nets to determine capacitance, timing cost, and wiring cost;
• a selection means for selecting a block move for each net which provides the lowest wiring cost;
• and
• a movement means for making said selected block move when said capacitance on critical nets associated with said move is not increased.