Back to results
US 2010/0146473 A1Published application
Routing system
AssigneeSTMicroelectronics Pvt. Ltd.
InventorsHimanshu Srivastava, Jyoti Malhotra
Life of this patent
Estimating the term…
Abstract
A process for shortest path routing in computer-aided designs (CAD) is performed using an incremental graph traversal technique. This technique searches the shortest path routing trees in a graph by path exploration limited only to an incremented search region thereby reducing run time complexity. Graph traversal begins in the incremented search region, and propagates successive changes thereafter.
Claims12
A computer-aided-design system comprising a routing module, said routing module comprising:
- a search region identifying module;
- and
- an incremental graph traversal routing module.
A method for computer-aided-design, said method comprising:
- identifying a search region with a first module of a computer aided design system;
- and
- processing an incremental graph traversal routing with a second module of the computer aided design system.
A method, comprising:
- identifying a bounding box as a search region;
- performing graph traversal within the search region using a source-sink routing path estimator to find a shortest path for a given net of a source sink list according to a shortest path algorithm by identifying a source sink routing path;
- determining by a routing processor whether the shortest path has been found;
- if so, then completing routing for a net;
- if not, incrementing the search region according to a defined factor of an increment index;
- and
- performing graph traversal again using the source-sink routing path estimator but only in the incremented search region and not in the previous region.
4 more elements
Dependencies are inferred from the claim text.