# US 6,732,349 B1 · Method and apparatus for improving PIP coverage in programmable logic devices

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

- Number: US 6,732,349 B1
- Document ID: US6732349B1
- Status: Granted
- Kind: B1
- Application number: 10/231,900
- Filed: 2002-08-29
- Granted: 2004-05-04
- Earliest claimed: 2002-08-29
- Assignees: Xilinx, Inc.
- Inventors: Richard Yachyang Sun; Sandor S. Kalman; Sudip K. Nag
- Web page: https://patentgrep.com/patent/US6732349B1

## CPC

- G01R 31/318516: {Test of programmable logic devices [PLDs]}
- G01R 31/31704: {Design for test; Design verification (concerning scan tests G01R31/318583; computer-aided design G06F30/00)}
- G06F 30/394: Routing (G06F30/396 takes precedence)
- G01R: MEASURING ELECTRIC VARIABLES; MEASURING MAGNETIC VARIABLES (indicating correct tuning of resonant circuits H03J3/12)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Routing algorithms can be modified to increase the number of programmable interconnect points (PIPs) used in a routing pattern. A file is set up to store information on whether a PIP has been covered. The cost of a node can be decreased by a predetermined value if two nodes are connected by an uncovered PIP. In another embodiment, a file is set up to store a count for each PIP. The count is increased each time the PIP is used in a routing. The cost of a node can be increased by multiplying a predetermined value and the count of a PIP associated with the node.

## Claims

### Claim 1

A method for increasing the number of covered programmable interconnect points in a routing, comprising:
setting up a file that stores information indicating whether a programmable interconnect point has been covered;
accepting a value; and
routing a plurality of nodes, including a step of expanding from a first node to a second node, comprising:
determining whether the first and the second nodes are connected through an uncovered programmable interconnect point;
applying a modified cost to the second node if the first node and a second node are connected through an uncovered programmable interconnect point, the modified cost is related to the value; and
performing routing using the modified cost.

### Claim 2 (depends on 1)

The method of claim 1 wherein the modified cost is substantially equal to cost of the first node plus base cost of the second node minus the value.

### Claim 3 (depends on 1)

The method of claim 1 wherein the modified cost is substantially equal to cost of the second node if the cost of the second node is smaller than cost of the first node plus base cost of the second node minus the value.

### Claim 4

A method for increasing the number of covered programmable interconnect points in a routing, comprising:
setting up a file that stores information indicating whether a programmable interconnect point has been covered;
accepting a value;
accepting a routed pattern;
ripping up one signal from the routed pattern; and
routing a plurality of nodes associated with the signal, including a step of expanding from a first node to a second node, comprising:
determining whether the first and the second nodes are connected through an uncovered programmable interconnect point;
applying a modified cost to the second node if the first node and a second node are connected through an uncovered programmable interconnect point, the modified cost is related to the value; and
performing routing using the modified cost.

### Claim 5 (depends on 4)

The method of claim 4 wherein the modified cost is substantially equal to cost of the first node plus base cost of the second node minus the value.

### Claim 6 (depends on 4)

The method of claim 4 wherein the modified cost is substantially equal to cost of the second node if the cost of the second node is smaller than cost of the first node plus base cost of the second node minus the value.

### Claim 7

A method for increasing the number of covered programmable interconnect points in a routing, comprising:
setting up a file that stores a count for each the programmable interconnect points;
accepting a value;
performing a routing run of the design, comprising:
for each of the nodes reached in the routing run, calculating a new cost by adding to a base cost a term equal to a product of the value and the count for one of the programmable interconnect points associated with the node; and
routing using the new cost; and
updating the file at the end of the routing run.

### Claim 8 (depends on 7)

The method of claim 7 wherein the updating step increases the count of each visited programmable interconnect point by a predetermined number.

### Claim 9 (depends on 7)

The method of claim 7 wherein the performing step is repeated more than one time, and the file is updated after more than one routing run.
