Back to results
US 8,136,077 B2Granted
Timing-optimal placement, pin assignment, and routing for integrated circuits
AssigneeSynopsys, Inc.
InventorsLarry E. McMurchie, Kenneth S. McElvain, Kenneth R. McElvain
Life of this patent
Estimating the term…
Abstract
Techniques for timing-optimal placement, pin assignment, and routing for integrated circuits are described herein. According to one embodiment, a list of paths providing implementation possibilities is constructed. A means is provided for removing paths from the list as well as a means for committing paths to the implementation if such paths are required for making the circuit implementation valid. Paths with worst case attributes are iteratively removed from the list until all paths in the list are committed to the implementation. Other methods and apparatuses are also described.
Claims23
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.
10 more elements
A non-transitory, machine-readable storage medium storing instructions which when executed by a machine, cause the machine to perform a 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 a 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;
- 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.
10 more elements
A system for designing an integrated circuit, the system comprising:
- a processor;
- and
- a memory for storing instructions which when executed from the memory, cause the processor to perform a method for designing an integrated circuit, the method including:
- 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 a 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;
- 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.
12 more elements
An apparatus for designing an integrated circuit, comprising:
- means for providing a circuit netlist having a subset of cells, signals, pins, and connections between pins;
- means for 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;
- means for providing implementation possibilities for implementing the circuit netlist as a list of possible paths, each path including a sequence of connected resources;
- means for providing an attribute and corresponding value for each path in the list of possible paths;
- means for removing paths from the list of possible paths that make the circuit implementation invalid;
- means for committing paths to remain in the list of possible paths if such paths are required for making the circuit implementation valid;
- means for identifying a 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
- means for iteratively removing, committing and identifying paths until all paths are committed;
- 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.
10 more elements
Dependencies are inferred from the claim text.