Optimal buffered routing path constructions for single and multiple clock domains systems
First Claim
1. A method comprising:
- receiving a location of a source node and a location of a sink node; and
in response to receiving the location of the source node and the location of the sink node, generating a minimum-delay routing path from the source node to the sink node, wherein the minimum-delay routing path contains buffers and synchronization elements.
1 Assignment
0 Petitions
Accused Products
Abstract
A method, computer program product, and data processing system for automatically designing routing paths in an integrated circuit is disclosed. The present invention allows for the design of paths that are optimal in terms of the signal delay in circuits that may require registers for signal to travel over multiple clock cycles or in circuits that may contain multiple clock domains.
An integrated circuit die is modeled as a weighted grid graph in which the edges represent wire segments and the weights represent the delays associated with those wire segments. Designing for optimum delay involves finding a shortest path between two vertices in the grid graph using a modified single-source shortest path algorithm. Registers, buffers, and dual-clock domain synchronizers are modeled according to a labeling function that assigns components to selected vertices in the routing path for optimal results.
30 Citations
27 Claims
-
1. A method comprising:
-
receiving a location of a source node and a location of a sink node; and
in response to receiving the location of the source node and the location of the sink node, generating a minimum-delay routing path from the source node to the sink node, wherein the minimum-delay routing path contains buffers and synchronization elements. - View Dependent Claims (2, 3)
-
-
4. A method comprising:
-
establishing a first priority queue and a second priority queue;
extracting a minimum-delay candidate from the first priority queue to be a current candidate, wherein the current candidate represents a current path and a current node;
generating a first at least one new candidate by adding edges to the current path;
pushing the first at least one new candidate to the first priority queue;
generating a second at least one new candidate containing a register at the current node;
pushing the second at least one new candidate to the second priority queue; and
in response to the first priority queue becoming empty, moving candidates from the second priority queue onto the first priority queue. - View Dependent Claims (5, 6, 7, 8, 9)
-
-
10. A computer program product in at least one computer-readable medium comprising functional descriptive material that, when executed by a computer, enables the computer to perform acts including:
-
receiving a location of a source node and a location of a sink node; and
in response to receiving the location of the source node and the location of the sink node, generating a minimum-delay routing path from the source node to the sink node, wherein the minimum-delay routing path contains buffers and synchronization elements. - View Dependent Claims (11, 12)
-
-
13. A computer program product in at least one computer-readable medium comprising functional descriptive material that, when executed by a computer, enables the computer to perform acts including:
-
establishing a first priority queue and a second priority queue;
extracting a minimum-delay candidate from the first priority queue to be a current candidate, wherein the current candidate represents a current path and a current node;
generating a first at least one new candidate by adding edges to the current path;
pushing the first at least one new candidate to the first priority queue;
generating a second at least one new candidate containing a register at the current node;
pushing the second at least one new candidate to the second priority queue; and
in response to the first priority queue becoming empty, moving candidates from the second priority queue onto the first priority queue. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
19. A data processing system comprising:
-
memory;
at least one processor in communication with the memory; and
a set of instructions in the memory, wherein the at least one processor executes the set of instructions to perform acts including;
receiving a location of a source node and a location of a sink node; and
in response to receiving the location of the source node and the location of the sink node, generating a minimum-delay routing path from the source node to the sink node, wherein the minimum-delay routing path contains buffers and synchronization elements. - View Dependent Claims (20, 21)
-
-
22. A data processing system comprising:
-
memory;
at least one processor in communication with the memory; and
a set of instructions in the memory, wherein the at least one processor executes the set of instructions to perform acts including;
establishing a first priority queue and a second priority queue;
extracting a minimum-delay candidate from the first priority queue to be a current candidate, wherein the current candidate represents a current path and a current node;
generating a first at least one new candidate by adding edges to the current path;
pushing the first at least one new candidate to the first priority queue;
generating a second at least one new candidate containing a register at the current node;
pushing the second at least one new candidate to the second priority queue; and
in response to the first priority queue becoming empty, moving candidates from the second priority queue onto the first priority queue. - View Dependent Claims (23, 24, 25, 26, 27)
-
Specification