Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-02-28
2004-05-18
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C713S002000, C713S100000, C707S793000, C707S793000, C709S221000, C709S222000, C703S016000
Reexamination Certificate
active
06738961
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the data structures for representing an electronic circuit, and more particularly, the invention relates to a computer readable medium and a method of describing data structures for representing an electronic circuit as a routing-resource graph.
2. Background Information
Programmable Circuit Arrays (“PCA”) can be programmed to define desired routing paths. A field programmable gate array (“FPGA”) is a PCA comprising configurable logic elements and a programmable routing network. The routing network and logic elements exhibit a regularity, such as a tiling of a small number of different types of subcomponents creating large mosaics of regular programmable structure. A user's design can be mapped onto an FPGA by selecting and configuring appropriate logic elements and interconnecting them, along with FPGA inputs and outputs, using the routing network and a suitable programming of the routing network which has been derived using a “router.”
An exemplary routing structure has horizontal and vertical lines representing wires or metal traces within the FPGA capable of carrying signals throughout the FPGA chip. At the intersection of a horizontal and vertical line, a programmable switch “x” can be configured to either connect the wires represented by the underlying horizontal vertical lines (“closed”) or to leave them unconnected (“open”). Inputs and outputs to the FPGA are represented as small squares, and configurable function units are represented as labeled rectangles. Closing appropriate switches will create an effective circuit within the FPGA, interconnecting desired inputs, outputs (i.e., squares) and functions units (i.e., rectangles). A a single “cell” or “tile” (composed of a function unit, several wire segments, and switches) can be replicated and abutted many times to create the FPGA.
To create a router that is independent of any specific FPGA architecture and usable for multiple FPGA targets, a routing-resource graph, or similar structure, is used to represent the routing network within the FPGA. As referenced herein, a “routing-resource graph” is any structural representation wherein a node is used to represent a wire, input, output, or pin on a logic block; a directed edge is used to represent a unidirectional switch (e.g. a programmable buffer) and a pair of directed edges are used to represent a bidirectional switch (e.g. a pass transistor). As referenced herein, a routing-resource graph can be used to represent an arbitrary routing architecture, such that a general-purpose router can configured independent of any particular FPGA architecture. After creating a routing-resource graph for a desired FPGA target, a general purpose router can route a user's design onto the FPGA. A routing-resource graph can also map onto object-oriented programming, allowing the use of instances of a “Switch” class and a “Wire” class to represent the routing network in an FPGA.
A routing-resource graph can require large memory. For example, an FPGA can have hundreds of thousands or wires, and tens of millions of switches, and these numbers will only increase as technology advances. Representing such a current FPGA with a straightforward resource-routing graph implementation can several gigabytes or more of memory.
It is known to exploit the regularity of a routing architecture to trade-off computation for memory. For example, consider the routing of a signal from a horizontal wire H
0
starting in cell (
0
,
0
) to a desired target vertical wire Vf. From a switch table, a router can deduce that there are two switches in the current cell (
0
,
0
) potentially connecting to vertical wires V
0
and V
1
. By calling a first function (i.e., a first method call) for the first switch, the router finds that the first switch leads to a wire Va, and by calling the first function for the second switch, the router finds that the second switch leads to a wire Vb, neither of which is the desired target vertical wire Vf. The router proceeds along wire H
0
to the next cell to the right, (
1
,
0
), taking into account any twist in the horizontal wire bus between the two cells (
0
,
0
) and (
1
,
0
). In cell (
1
,
0
), the same wire thus has the local name H
1
. Again by calling the first function, the router can discover that the second switch within cell (
1
,
0
) leads to the desired target wire Vf.
A compute based approach is an effective alternative to the resource routing graph, and is used in the JRoute code supplied with the JBits system offered by Xilinx. The advantage is that much less memory is needed to represent the switched connectivity. For example, instead of the 54 instances of Switch data structures used in a typical routing-resource graph, a small switch table plus some easily written functions will suffice. Memory savings can be more dramatic in an FPGA comprising tens of thousands of cells. However, the internal structures of the FPGA have to be exposed to the router so that it can be used to navigate the routing network. A router written at this level can not be easily adapted to a different FPGA architecture.
SUMMARY OF THE INVENTION
The present invention relates to efficiently representing an electronic circuit array as a routing-resource graph using reduced memory (e.g., use of a Flyweight Design Pattern with a computation based approach).
In accordance with an exemplary embodiment of the present invention, a computer readable medium containing a computer program is provided for representing an electronic circuit, which has been segmented into plural blocks, as a routing-resource graph that includes a first wiring data structure with first switch information and a first wire identity information to identify a first wire across a first plurality of blocks, a second wiring data structure with the first switch information and a second wire identity information to identify a second wire across a second plurality of blocks, and a first switch data structure associated with the first and second wiring data structures for identifying a third wire connected to the first wire with a switch as a function of the first wire identity information and wire information from the first switch data structure.
In accordance with another exemplary embodiment of the present invention, a method for representing an electronic circuit as a routing-resource graph includes defining a plurality of blocks each having a regular sub-array of switches and wires, defining a first wiring data structure with first switch information and first wire identity information to identify a first wire, defining a second wiring data structure with first switch information and second wire identity information to identify a second wire, and defining a first switch data structure having wire information and associated with the first and second wiring data structures for identifying wires respectively connected to the first and second wires by a switch as a function of wire identity information and the wire information.
REFERENCES:
patent: 5519629 (1996-05-01), Snider
patent: 5598346 (1997-01-01), Agrawal et al.
patent: 5640327 (1997-06-01), Ting
patent: 5659484 (1997-08-01), Bennett et al.
patent: 5740069 (1998-04-01), Agrawal et al.
patent: 5761729 (1998-06-01), Scales
patent: 5835751 (1998-11-01), Chen et al.
patent: 5850537 (1998-12-01), Selvidge et al.
patent: 5959871 (1999-09-01), Pierzchala et al.
patent: 5960446 (1999-09-01), Schmuck et al.
patent: 6052688 (2000-04-01), Thorsen
patent: 6086631 (2000-07-01), Chaudhary et al.
patent: 6099583 (2000-08-01), Nag
patent: 6128770 (2000-10-01), Agrawal et al.
patent: 6317804 (2001-11-01), Levy et al.
patent: 6360191 (2002-03-01), Koza et al.
patent: 6536018 (2003-03-01), Chisholm et al.
patent: 6584601 (2003-06-01), Kodosky et al.
patent: 2002/0157066 (2002-10-01), Marshall et al.
patent: 2003/0028852 (2003-02-01), Thurman et al.
patent: 2003/0088843 (2003-05-01), Mehrotra et al.
patent: 319232 (1989-06-01), None
patent: 2149989 (1985-06-01), None
patent: WO 9833182 (1998-07-01),
LandOfFree
Computer readable medium and a method for representing an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer readable medium and a method for representing an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer readable medium and a method for representing an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207026