2.5-D graph for multi-layer routing
AssigneeSun Microsystems, Inc.
InventorsZhaoyun Xing, Russell Kao
Life of this patent
Estimating the term…
Abstract
A routing graph (e.g., a 2.5-D graph) and a method for generating same is provided for more efficient multiple-layer path searching and routing. Subgraphs are generated for each layer, and then are combined (e.g., through via connections) into a single, multi-layer graph. The resulting 2.5-dimensional graph may be used in VLSI routing, for example, which commonly includes multiple routing layers in a given design space. Each subgraph corresponds to a layer of circuitry and includes segments based on segments from other layers and intersection points of all such segments. Methods of generating subgraph layers are disclosed
Claims24
A method of building a multi-layer graph for greater than two dimensional integrated circuit routing, the method comprising:
- generating a plurality of subgraphs, each of the plurality of subgraphs corresponding to each of a plurality of layers of circuitry, each of the plurality of subgraphs including a plurality of segments based on information from other layers of circuitry;
- and
- combining all of the plurality of subgraphs into a single, multi-layer graph.
A method of routing through a route space including a plurality of route layers, the method comprising the steps of:
- generating a subgraph for each of the routing layers, each subgraph corresponding to a routing layer and including a plurality of route segments based on information from the corresponding routing layer and a plurality of route segments based on information from other routing layers;
- and
- generating a multi-layer route graph, the multi-layer route graph including a plurality of the generated subgraphs.
A product for receiving routing data regarding a multi-layer routing problem and for generating a multi-layer graph to facilitate resolution of the routing problem, the product comprising:
- a first module for generating a plurality of subgraphs, each of the plurality of subgraphs corresponding to each of a plurality of layers of the routing data, each of the plurality of subgraphs including a plurality of segments based on information from other layers of the routing data;
- and
- a second module for combining all of the plurality of subgraphs into a single, multi-layer graph.
A 2.5-D graph for use in multi-layer, integrated circuit routing, the graph comprising:
- a first subgraph corresponding to a first circuit layer, the first subgraph including a set of routing segments selected using information from the first circuit layer and at least one other circuit layer;
- and
- a second subgraph corresponding to a second circuit layer, the second subgraph including a set of routing segments selected using information from the second circuit layer and at least one other circuit layer.
Dependencies are inferred from the claim text.