Sweepline triangulation for spanning graphs

Patent metadata

Field	Value
Publication number	US-11734486-B2
Application number	US-202117467631-A
Country	US
Kind code	B2
Filing date	Sep 7, 2021
Priority date	Sep 7, 2021
Publication date	Aug 22, 2023
Grant date	Aug 22, 2023

Abstract

Aspects of the invention include systems and methods for implementing a sweepline triangulation technique to optimize spanning graphs for circuit routing. A non-limiting example computer-implemented method includes receiving an unrouted net having a plurality of elements. The elements can include pins, vias, and wires. A sweepline is passed across the unrouted net until the sweepline intersects an element of the plurality of elements. In response to the sweepline intersecting the element, the sweepline is stopped and one or more nodes on the sweepline and one or more previous nodes are identified. A connectivity graph is built from the one or more nodes and the one or more previous nodes. The connectivity graph includes one or more arcs and one or more guides. A minimum spanning tree is built by removing one or more guides from the connectivity graph and the unrouted net is routed based on the minimum spanning tree.

First claim

What is claimed is:

1. A computer-implemented method for circuit routing, the method comprising:
receiving an unrouted net comprising a plurality of elements, wherein the elements comprise pins, vias, and wires;
passing a sweepline across the unrouted net until the sweepline intersects an element of the plurality of elements;
in response to the sweepline intersecting the element, stopping the sweepline and identifying one or more nodes on the sweepline and one or more previous nodes;
building a connectivity graph from the one or more nodes and the one or more previous nodes, the connectivity graph comprising one or more arcs and one or more guides;
building a minimum spanning tree by removing one or more guides from the connectivity graph; and
routing the unrouted net based on the minimum spanning tree.

2. The computer-implemented method of claim 1 further comprising, for each node on the sweepline:
defining an upper sweepline triangle and a lower sweepline triangle;
tagging each previous node in the upper sweepline triangle with a first indicator; and
tagging each previous node in the lower sweepline triangle with a second indicator.

3. The computer-implemented method of claim 2 further comprising removing any node with both the first indicator and the second indicator.

4. The computer-implemented method of claim 1 , wherein the previous nodes correspond to a previous location of the sweepline.

5. The computer-implemented method of claim 1 , wherein the sweepline intersects the element at a first location; and, further comprising, passing the sweepline to a second location.

6. The computer-implemented method of claim 1 , wherein a guide represents an open between a first node and a second node in the connectivity graph.

7. The computer-implemented method of claim 1 , wherein an arc is created between two adjacent nodes of a wire segment and between a top pad and a bottom pad of a via.

8. A system comprising a memory having computer readable instructions and one or more processors for executing the computer readable instructions, the computer readable instructions controlling the one or more processors to perform operations comprising:
receiving an unrouted net comprising a plurality of elements, wherein the elements comprise pins, vias, and wires;
passing a sweepline across the unrouted net until the sweepline intersects an element of the plurality of elements;
in response to the sweepline intersecting the element, stopping the sweepline and identifying one or more nodes on the sweepline and one or more previous nodes;
building a connectivity graph from the one or more nodes and the one or more previous nodes, the connectivity graph comprising one or more arcs and one or more guides;
building a minimum spanning tree by removing one or more guides from the connectivity graph; and
routing the unrouted net based on the minimum spanning tree.

9. The system of claim 8 further comprising, for each node on the sweepline:
defining an upper sweepline triangle and a lower sweepline triangle;
tagging each previous node in the upper sweepline triangle with a first indicator; and
tagging each previous node in the lower sweepline triangle with a second indicator.

10. The system of claim 9 further comprising removing any node with both the first indicator and the second indicator.

11. The system of claim 8 , wherein the previous nodes correspond to a previous location of the sweepline.

12. The system of claim 8 , wherein the sweepline intersects the element at a first location; and, further comprising, passing the sweepline to a second location.

13. The system of claim 8 , wherein a guide represents an open between a first node and a second node in the connectivity graph.

14. The system of claim 8 , wherein an arc is created between two adjacent nodes of a wire segment and between a top pad and a bottom pad of a via.

15. A computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by one or more processors to cause the one or more processors to perform operations comprising:
receiving an unrouted net comprising a plurality of elements, wherein the elements comprise pins, vias, and wires;
passing a sweepline across the unrouted net until the sweepline intersects an element of the plurality of elements;
in response to the sweepline intersecting the element, stopping the sweepline and identifying one or more nodes on the sweepline and one or more previous nodes;
building a connectivity graph from the one or more nodes and the one or more previous nodes, the connectivity graph comprising one or more arcs and one or more guides;
building a minimum spanning tree by removing one or more guides from the connectivity graph; and
routing the unrouted net based on the minimum spanning tree.

16. The computer program product of claim 15 further comprising, for each node on the sweepline:
defining an upper sweepline triangle and a lower sweepline triangle;
tagging each previous node in the upper sweepline triangle with a first indicator; and
tagging each previous node in the lower sweepline triangle with a second indicator.

17. The computer program product of claim 16 further comprising removing any node with both the first indicator and the second indicator.

18. The computer program product of claim 15 , wherein the previous nodes correspond to a previous location of the sweepline.

19. The computer program product of claim 15 , wherein the sweepline intersects the element at a first location; and, further comprising, passing the sweepline to a second location.

20. The computer program product of claim 15 , wherein a guide represents an open between a first node and a second node in the connectivity graph.

Assignees

• IBM

Inventors

• Pandey Diwesh
• Tellez Gustavo Enrique

Classifications

• G06F30/394 Primary

  Routing (G06F30/396 takes precedence) · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title