×

Method and apparatus for accurate crosspoint allocation in VLSI area routing

  • US 6,519,751 B2
  • Filed: 03/31/2000
  • Issued: 02/11/2003
  • Est. Priority Date: 03/31/2000
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method comprising:

  • defining a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of successive boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal;

    selecting from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary;

    selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary;

    repeating the selecting from a successive boundary for each successive boundary until a successive boundary of the last area is reached;

    for each preceding boundary having more than one lowest-cost node, changing, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from the lowest-cost node of the successive boundary to the preceding boundary; and

    identifying a signal route through the selected lowest-cost nodes.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×