Placement of objects with partial shape restriction
AssigneeXilinx, Inc.
InventorsSrinivasan Dasasathyan, Guenter Stenz, Sudip K. Nag, Jason H. Anderson
Life of this patent
Estimating the term…
Abstract
Application of network flow techniques to constrained optimization problems is disclosed. The present of constrains may lead to infeasible solutions. The infeasible solutions can be removed by an iterative process of changing the structure of the network and/or the associated parameters. Specific applications of the invention to the placement of tristate buffers and clocks in integrated circuits are disclosed.
Claims26
A method for placing a design onto an integrated circuit, said design comprising plural sets of electronic components and said integrated circuit being associated with a grid, said method comprising:
- generating a global placement solution for said design;
- setting up a flow network of said electronic components using said global placement solution;
- obtaining a flow solution for said flow network;
- if said flow solution is infeasible based on at least one of a geographical restriction of each electronic component in a set and a overlap restriction on said sets, modifying said network to discourage said infeasible solution and repeating said obtaining step.
A method for placing a design onto an integrated circuit, said design comprising plural sets of electronic components and said integrated circuit being associated with a grid, each of said electronic components in a set being geographically restricted, said method comprising:
- generating a global placement solution for said design;
- setting up a flow network of said electronic components using said global placement solution;
- obtaining a flow solution for said flow network;
- if said flow solution is infeasible, modifying said network to discourage said infeasible solution and repeating said obtaining step;
- and
- wherein said grid has a plurality of rows, each of said electronic components in at least one of said sets is restricted to a row, and said flow network comprises a plurality of sources associated with said electronic components, a plurality of sinks associated with said rows, and a plurality of edges connecting some of said sources to some of said sinks, and wherein at least one edge is associated with an initial cost related to said global placement solution and a row under consideration.
Dependencies are inferred from the claim text.