Programmable interconnect matrix architecture for complex...

Details Programmable interconnect matrix architecture for complex... Programmable interconnect matrix architecture for complex...

1998-01-20

2002-04-09

Chin, Wellington (Department: 2664)

Multiplex communications

Pathfinding or routing

Through a circuit switch

C340S870030, C370S380000, C326S038000, C326S039000, C326S041000

Reexamination Certificate

active

06370140

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to programmable logic devices and, more particularly, to a routing architecture for such devices.
BACKGROUND
Various programmable logic architectures are known, including, for example, programmable logic devices (“PLDs”), programmable logic arrays (“PLAs”), complex programmable logic devices (“CPLDs”), field programmable gate arrays (“FPGAs”) and programmable array logic (“PAL”). Although there are differences between these various architectures, each of the architectures typically includes a set of input conductors directly coupled as inputs to an array of logic gates (e.g., a product term array made up of logical AND gates), the outputs of which, in turn, act as inputs to another portion of the logic device.
For complex programmable logic devices, wherein the number of input conductors and the number of logical AND gates to which they connect are both quite large compared with other programmable logic architectures, maintaining full connectability of the product term array for each input conductor becomes impractical for several reasons. 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 logical AND gates increases as the number of programmable elements increases. All of these consequences of attempting to maintain full connectability for CPLDs results in a large increase in die space for the product term array without a proportionate increase in functionality over a less complex PLD.
One solution to this dilemma 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, or multiple numbers of logic blocks, and provides a 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 implemented 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 in each programmable element is capable of providing a unique connection between the input conductor and one of the output conductors. Such a 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. The 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.
Such early approaches were rather inefficient. For example, 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.
Further, 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 signal 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 0.1

in
. Therefore, the amount of die space required to implement the fully connectable cross-point matrix is excessive in light of the under utilization of the programmable elements. The inefficiency of such early approaches 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 multiplexers, wherein the output of each multiplexer is connected to an output conductor of the connection circuit. As each multiplexer requires only log n
in
/log 2 programmable elements, the total number of programmable elements (the connectivity) for a fully connectable multiplexer array is reduced to n
out
multiplied by log n
in
/log 2. This results in some savings of die space over the fully connectable cross-point matrix, however, the die space requirements are still excessive, especially when the number n
out
of CPLD inputs 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. Here, the term routability denotes the probability that the connection circuit can provide a route (or signal path) for any given combination of input signals from the input conductors to the output conductors of the connection circuit. The routability of the connection circuit tends to increase with the connectability of the connection circuit.
Because every input conductor can no longer be connected to an output conductor, the number of routes through the connection circuit for a particular combination of input signals may be reduced when compared to the fully connectable connection circuits. So long as the connection circuit provides at least one route for every combination of input signals, the connection circuit is fully routable or 100% routable. If no route can be provided for a particular combination of input signals, the connection circuit is not fully routable. Fully connectable connection circuits have maximum routability as they provide a route for every permutation of input signals.
Connectivity for a multiplexer array is reduced by reducing the width of the input field for each multiplexer such that the number of input conductors that are coupled to each multiplexer is less than the total number of input conductors for the connection circuit. So long as each input signal is provided with at least one chance to route, that is, each input conductor is connected to at least one multiplexer, a successful routing for a particular logic function can be achieved regardless of the routability of the connection circuit. For such a constrained multiplexer, providing a route for a particular logic function may

Affiliated with

Also associated with

Rating

Programmable interconnect matrix architecture for complex... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Programmable interconnect matrix architecture for complex..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable interconnect matrix architecture for complex... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2833109