# US 7,610,573 B1 · Implementation of alternate solutions in technology mapping and placement

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,610,573 B1
- Document ID: US7610573B1
- Status: Granted
- Kind: B1
- Application number: 11/881,307
- Filed: 2007-07-26
- Granted: 2009-10-27
- Earliest claimed: 2007-07-26
- Assignees: Xilinx, Inc.
- Inventors: Vi Chi Chan; Tetse Jang; Sridhar Krishnamurthy; Kevin Chung
- Web page: https://patentgrep.com/patent/US7610573B1

## CPC

- G06F 30/34: for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
- G06F 2111/06: Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method of implementing a circuit design within a target integrated circuit (IC) can include, during technology mapping of the circuit design, determining a plurality of implementations of at least one sub-circuit of the circuit design and placing the circuit design on the target IC using a primary implementation of the plurality of implementations of the sub-circuit. The primary implementation of the sub-circuit can be selectively replaced with an alternate implementation of the sub-circuit selected from the plurality of implementations of the sub-circuit. The placed circuit design, including either the primary implementation or the alternate implementation of the sub-circuit, can be output.

## Claims

### Claim 1

A computer-implemented method of implementing a circuit design within a target integrated circuit (IC), the method comprising:
executing a program on a computer system, wherein execution of the program causes the computer system to perform operations including:
during technology mapping of the circuit design, determining a respective plurality of implementations of a plurality of sub-circuits of the circuit design;
retaining each respective plurality of implementations;
for each sub-circuit having the respective plurality of implementations, selecting a primary implementation from the retained respective plurality of implementations;
placing the circuit design on the target IC using each primary implementation of each sub-circuit having the respective plurality of implementations;
after the placing, identifying a portion of the circuit design that does not conform to a design constraint;
selecting from the identified portion the sub-circuit having a respective plurality of implementations;
selecting a respective alternate implementation of the selected sub-circuit from the retained respective plurality of implementations;
replacing the primary implementation of the selected sub-circuit with the selected alternate implementation, wherein determining the respective plurality of implementations comprises determining the respective plurality of implementations for each of the plurality of sub-circuits of a selected region of the circuit design, and wherein replacing the primary implementation comprises replacing each primary implementation of each sub-circuit of the selected region with a respective alternate implementation of the sub-circuit; and
outputting the placed circuit design after the replacing.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the selected sub-circuit comprises a plurality of nodes of the circuit design, and wherein determining the respective plurality of implementations comprises:
mapping a first group of nodes of the selected sub-circuit to at least one lookup table forming the primary implementation; and
mapping a second group of nodes of the selected sub-circuit to at least one lookup table forming the alternate implementation, wherein the first group of nodes is not equal to the second group of nodes.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein the identifying the portion of the circuit design that does not conform to the design constraint comprises:
performing a timing analysis upon the placed circuit design;
identifying a critical path of the circuit design; and
wherein the selected sub-circuit comprises a node of the critical path.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3, further comprising accepting the alternate implementation of the selected sub-circuit according to a further timing analysis of the placed circuit design comprising the alternate implementation of the selected sub-circuit.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, further comprising:
during the technology mapping, generating a circuit description that specifies the respective pluralities of implementations of the sub-circuits; and
providing the circuit description specifying the pluralities of implementations to a placer.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein determining the respective plurality of implementations comprises:
determining an implementation for one or more of the plurality of sub-circuits comprising slice logic; and
determining another implementation for the one or more of the plurality of sub-circuits comprising non-slice logic.

### Claim 7 (depends on 6)

The computer-implemented method of claim 6, wherein determining the respective plurality of implementations further comprises determining an implementation comprising a combination of slice logic and non-slice logic.

### Claim 8

A computer program product, comprising:
a computer-usable storage medium having computer-usable program code that implements a circuit design within a target integrated circuit (IC), the computer-usable medium comprising:
computer-usable program code that, during technology mapping of the circuit design, determines a respective plurality of implementations of a plurality of sub-circuits of the circuit design;
computer-usable program code that retains each respective plurality of implementations;
computer-usable program code that, for each sub-circuit having the respective plurality of implementations, selects a primary implementation from the retained respective plurality of implementations;
computer-usable program code that places the circuit design on the target IC using each primary implementation of each sub-circuit having the respective plurality of implementations;
computer-usable program code that after the placing, identifies a portion of the circuit design that does not conform to a design constraint;
computer-usable program code that selects from the identified portion a sub-circuit having the respective plurality of implementations;
computer-usable program code that selects a respective alternate implementation of the selected sub-circuit from the retained respective plurality of implementations;
computer-usable program code that replaces the primary implementation of the selected sub-circuit with the selected alternate implementation; and
computer-usable program code that outputs the placed circuit design, wherein the computer-usable program code that determines the respective plurality of implementations comprises computer-usable program code that determines the respective plurality of implementations for each of the plurality of sub-circuits of a selected region of the circuit design, and wherein the computer-usable program code that selectively replaces the primary implementation comprises computer-usable program code that replaces each primary implementation of each sub-circuit of the selected region with a respective alternate implementation of the sub-circuit after the replacing.

### Claim 9 (depends on 8)

The computer program product of claim 8, wherein the selected sub-circuit comprises a plurality of nodes of the circuit design, and wherein the computer-usable program code that determines a plurality of implementations comprises:
computer-usable program code that maps a first group of nodes of the selected sub-circuit to at least one lookup table forming the primary implementation; and
computer-usable program code that maps a second group of nodes of the selected sub-circuit to at least one lookup table forming the alternate implementation, wherein the first group of nodes is not equal to the second group of nodes.

### Claim 10 (depends on 8)

The computer program product of claim 8, wherein the identifying the portion of the circuit design that does not conform to the design constraint comprises:
computer-usable program code that performs a timing analysis upon the placed circuit design; and
computer-usable program code that identifies a critical path of the circuit design;
wherein the selected sub-circuit comprises a node of the critical path.

### Claim 11 (depends on 10)

The computer program product of claim 10, further comprising computer-usable program code that accepts the alternate implementation of the selected sub-circuit according to a timing analysis of the placed circuit design comprising the alternate implementation of the selected sub-circuit.

### Claim 12 (depends on 8)

The computer program product of claim 8, wherein the computer-usable program code that determines the respective plurality of implementations comprises at least one of computer-usable program code that determines an implementation for one or more of the plurality of sub-circuits comprising slice logic, computer-usable program code that determines an implementation for the one or more of the plurality of sub-circuits comprising non-slice logic, or computer-usable program code that determines an implementation for the one or more of the plurality of sub-circuits comprising a combination of slice logic and non-slice logic.