Patent ID: 8136077

Claim:
A machine-implemented method for designing an integrated circuit, the method comprising: providing a circuit netlist having a subset of cells, signals, pins, and connections between pins; providing an implementation architecture to implement the circuit netlist, the implementation architecture having resources including a subset of cell sites, pin sites, and routing resources; providing implementation possibilities for implementing the circuit netlist as a list of possible paths, each path including a sequence of connected resources; providing an attribute and corresponding value for each path in the list of possible paths; removing paths from the list of possible paths that make the circuit implementation invalid; committing paths to remain in the list of possible paths if such paths are required for making the circuit implementation valid; identifying an uncommitted path from the list of possible paths with a worst-case value for the attribute and removing that path from the list of possible paths; and iteratively removing, committing and identifying paths until all paths are committed by using a computer; wherein a valid circuit implementation is specified by the following conditions: completeness, which requires each cell in the netlist to be assigned to at least one cell site, each in to be assigned to at least one in site and each signal to be assigned one or more resources; and satisfaction of constraints between paths, which requires that only one cell to be assigned to a cell site, only one pin to be assigned to a pin site, and only one signal to be assigned to a resource.