Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Circuit simulation
Reexamination Certificate
1998-10-27
2001-06-05
Teska, Kevin J. (Department: 2763)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Circuit simulation
C703S002000, C716S030000, C340S870030, C307S112000, C326S041000
Reexamination Certificate
active
06243664
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to programmable logic devices and more particularly to providing maximum routability of input signals in a programmable interconnect matrix having less than full connectability.
BACKGROUND OF THE INVENTION
Various programmable logic architectures are known, including, for example, the programmable logic device (“PLD”), the programmable logic array (“PLA”), and programmable array logic (“PAL™”). Wherein there are many differences between the various architectures, each of the PLD, PLA, and PAL architectures typically includes a set of input conductors directly coupled as inputs to an array of logical AND gates (“product term array”), the outputs of which, in turn, act as inputs to another portion of the logic device.
The product term array is often fully programmable, which typically results in 1) each logical AND gate of the product term array having as many inputs as there are input conductors, 2) an array of programmable switches or elements that allow a programmer to selectively enable and disable the use of each input conductor as an input term for each logical AND gate, and 3) a multiplicity of conductors each of which is routed from one programmable element to one input of a logical AND gate. The total number of programmable elements is typically equal to the number of input conductors multiplied by the number of logical AND gates, and each input conductor is capable of being connected to each logical AND gate. A fully programmable product term array has “full connectability” because each input condutor of the product term array can be coupled to each logical AND gate of the product term array.
For complex programmable logic devices (“CPLDs”), wherein the set of input conductors and the set of logical AND gates to which they connect are both quite large compared to prior PLDs, PALs™, and PLAs, maintaining the full connectability of the product term array for each input conductor becomes impractical. First, to maintain full connectability, the size of the input field of each logical AND gate in the product term array must increase for each input conductor that is added. Second, the addition of a single input conductor requires the addition of a number of programmable elements equal to the total number of logical AND gates, one for each logical AND gate. Third, the total number of conductors that are routed from the programmable elements to the AND gates increases as the number of programmable elements increases. All of these consequences of attempting to maintain full connectability for CPLDs result in a large increase in die space for the product term array without a proportionate increase in functionality over the less complex PLD.
One solution is to interpose a connection circuit that is not fully connectable between the set of input conductors and the product term array of a logic block, wherein the inputs of the connection circuit are coupled to the input conductors of the CPLD and the outputs of the connection circuit are coupled to the inputs of the product term array of a logic block. One such connection circuit is associated with each CPLD logic block and provides unique connection between CPLD inputs and the product term array inputs of the associated logic block. Typically, this connection circuit allows only a subset of the CPLD inputs to be connected to the product term array inputs.
Early CPLDs implement this connection circuit as a programmable, fully populated cross-point matrix similar to that used in a fully programmable product term array. Each input conductor of the connection circuit is connected to a number of programmable elements equal to the number of output conductors of the connection circuit, wherein each programmable element is capable of providing a unique connection between the input conductor and one of the output conductors. This connection circuit guarantees a route for every possible combination of input signals up to the total number of output conductors of the front end connection, regardless of the ordering of the combination. A fully populated cross-point matrix may thus be said to have “full connectability,” wherein the term “connectability” denotes the ability of the connection circuit to connect an input conductor of the connection circuit to the output conductors of the connection circuit. A “fully connectable” connection circuit is one that can connect every input conductor to every output conductor.
This early approach is very inefficient. First, the number of programmable elements required for each connection circuit is equal to the total number of CPLD input conductors, n
in
, multiplied by the number of output conductors, n
out
, for the connection circuit, wherein n
out
is typically equal to the number of input terms for the product term array of the associated logic block. As a CPLD typically implements two or more connection circuits, this approach requires large amounts of die area.
Second, of the n
in
programmable elements connected to any one of the n
out
output conductors, only one of the programmable elements is ever programmed, regardless of the input signals selected for routing through the connection circuit. Otherwise, two or more input signals may be shorted together. Thus, the maximum number of programmable elements that are ever used to route any combination of input signals through a fully populated cross-point matrix is n
out
. This means that the maximum percentage of programmable elements that are used for any one connection circuit is equal to (1
in
). Therefore, the amount of die space required to implement the fully connectable cross-point matrix is excessive in light of underutilization of the programmable elements. The inefficiency of this early approach is only emphasized when the number n
in
of CPLD inputs increases.
An alternative connection circuit provides full connectability while requiring less “connectivity” than the fully populated cross-point matrix. The term “connectivity” refers to the total number of programmable elements provided by a connection circuit. This alternative connection circuit uses a number n
out
of n
in
:1 multiplexors, wherein the output of each multiplexor is connected to an output conductor of the connection circuit. As each multiplexor requires only (log n
in
/log2) programmable elements, the total number of programmable elements (the connectivity) for a fully connectable multiplexor array is reduced to n
out
multiplied by (log n
in
/log2). Wherein this results in some savings of die space over the fully connectable cross-point matrix, the die space requirements are still excessive, especially when the number n
out
of CPLD input signals increases.
To further reduce the amount of semiconductor die area needed for a connection circuit, the connectivity of the connection circuit may be further reduced by providing even fewer programmable elements. This reduction in connectivity results in connection circuits that are not fully connectable, which means that every input conductor of the connection circuit cannot be connected to every output conductor of the connection circuit. The level of connectability for a connection circuit is related to the level of “routability” of the connection circuit. For purposes of discussion, the term “routability” denotes the probability that the connection circuit can provide a route for any given combination of input signals from the input conductors to the output conductors of the connection circuit. The routability of a connection circuit tends to increase with the connectability of the connection circuit.
Because every input conductor can no longer be connected to every output conductor, the number of “routes” through the connection circuit for a particular combination of input signals may be reduced when compared to fully connectable connection circuits. So long as a connection circuit provides at least one route for every combination of n input signals, the connection circuit is “fully routable” or “100% routable.” If no route can be provided for a particular combination of
Borzin Shiva Sorooshian
Douglass Stephen M.
Graf W. Alfred
Nazarian Hagop A.
Neuman Darren
Cypress Semiconductor Corporation
Frejd Russell W.
Teska Kevin J.
Wagner , Murabito & Hao LLP
LandOfFree
Methods for maximizing routability in a programmable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for maximizing routability in a programmable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for maximizing routability in a programmable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444161