Method to improve routability in programmable logic devices...

Details Method to improve routability in programmable logic devices... Method to improve routability in programmable logic devices...

2001-06-27

2002-10-15

Tokar, Michael (Department: 2819)

Electronic digital logic circuitry

Multifunctional or programmable

Having details of setting or programming of interconnections...

C326S039000, C326S041000

Reexamination Certificate

active

06466050

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a method for improving the success of signal routing during the physical synthesis of programmable logic devices.
BACKGROUND OF THE INVENTION
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 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.
Complex Programmable Logic Devices (“CPLDs”) are large scale PLDs that, like all programmable architectures, are configured to the specific requirements of an application by programming. A typical programmable logic device consists of one or more logical clusters, each containing one or more logic blocks, one or more memory modules, and an internal bus to carry signals, all connected by one or more Programmable Interconnect Matrices (“PIMs”). In some CPLDs, high level channels connect the clusters to each other and to external devices. The connections made in a PIM are determined by routing software.
The signals that need to route to a Logic Block PIM are determined by the desired configuration of the device and the logic inside the logic block. Some of these signals are carried in the top-level horizontal and vertical routing channels that surround the cluster. There are channel-to-cluster PIMs connecting the routing channels to the cluster internal bus. Conventional routing software routes these signals through the channel-to-cluster PIMs, which sends these signals onto a particular set of wires in the cluster bus. Then the routing software routes through the Logic Block PIMs to send the signals into the logic blocks toward their final destination.
Routing of the input set to the output set through a PIM can be defined as a “Maximum Bipartite Matching” problem, and use a standard network-flow based solution. See, for example, the reference entitled “Introduction to Algorithms” by Cormen, Leiserson and Rivest, 1990 p. 600, which is incorporated herein as background.
The operation of a conventional routing process can best be visualized by reference to conventional art
FIGS. 1
,
2
and
3
.
FIG. 1
illustrates a schematic representation of a logical cluster and associated PIMs. Signals
308
, carried in channel
206
, are selected and routed through channel-to-cluster PIM
205
into cluster
201
, then routed by logic block PIM
204
into logic block
255
.
The logical operation of a conventional process is illustrated by conventional art
FIGS. 2 and 3
. Source node
301
represents the set of input signals and input node array
303
represents the arrangement of signals at the PIM input. Note that a PIM is represented here as the combination of input node array set
303
, interconnect matrix
305
and output node array set
306
. Pathways are determined through interconnect matrix
305
from input to output. The resultant connection graph is illustrated by FIG.
3
. The signal present at input node
313
has been successfully routed to output node
316
and the signal present at input node
343
has been successfully routed to output node
336
via pathways
402
.
The conventional processes used in the routing software route the signals through a PIM with each signal being routed to exactly one output. In a typical CPLD, the routing software first routes the “upstream” channel-to-cluster PIM
205
(FIG.
1
), then the “downstream” Logic Block PIM
255
. Logic block PIM routing is limited to routing a given set of signals represented only once in the set of wires as determined by the routing of the channel-to-cluster PIMs.
In the conventional art, there can be many routing failures because the limited routing resources are not always able to provide a path for all required signals. Typical routing failures occur in routing the Logic Block PIMs inside the cluster. This is due to the nature of the interconnection pattern of the PIM. A given set of signals, each on a particular wire, might not be able to be routed through a PIM since a routing solution for one signal, due to its location in the input set, may use routing resources necessary to the only routing solution available to another signal in the set. The set of input wires the signals occupy are fixed by the routing of the Channel-To-Cluster PIMs. Routing of Channel-To-Cluster PIMs is done without knowing whether Logic Block PIMs downstream can route or not, and this cannot be known at the time the channel-to-cluster PIM is routed. Hence, there is always some probability in the conventional art that a routing solution in the upstream PIM,
205
, will induce a routing failure in the downstream PIM,
255
. What is required, then, is a method for routing signals in the interconnect matrices of programmable logic devices that reduces the occurrence of routing failures.
SUMMARY OF THE INVENTION
A method and system thereof are described herein for routing signals through interconnect matrices in a programmable logic device such that downstream routing failures can be reduced. In one embodiment, the invention is used to improve routing in complex programmable logic devices or CPLDs, however, the invention can be applied to other programmable devices and routing resources.
In routing a set of signals through an upstream interconnect matrix or PIM, the novel method determines a set of high priority signals. The process routes a set of original signals through the upstream PIM so that all signals are routed once and only once. Then the process routes the high priority signals (as many as possible) such that they are duplicated at the output of the upstream PIM. In routing the upstream PIM, the method uses an augmented Maximum Bipartite Matching process (maximum flow) in one embodiment where some signals (high priority signals) are routed twice. Specifically, the high priority signals are re-introduced to existing input nodes of the graph and then path finding steps are performed to locate forward paths through the upstream PIM to additional output nodes, represented in the graph, for the duplicate signals. These duplicated high priority signals are then sent to the input array of the downstream interconnect matrix along with the originally routed signals.
The downstream interconnect matrix can then route the originally routed signals or the duplicate signals depending on position in the input array set and the available routing resources. The method also uses a technique for preventing the simultaneous routing of duplicate signals through the downstream interconnect matrix and ensuring that one, and only one, copy of any signal arrives at the destination output array. Specifically, for each duplicate signal, a virtual node is inserted in a graph between the source node and the input nodes, where the virtual node ensures that each duplicate signal is routed only once. Then, forward paths are determined through the graph to output nodes for each unique signal. Signals are routed once, and only once, this way. The routing failures attendant to conventional routing are thus reduced significantly, if not eliminated.
In one embodiment, the method comprises the steps of selecting highest priority original signals for duplication, routing all signals once through a first interconnect matrix and then routing the duplicated signals through unused pathways remaining in the first interconnect matrix. Then the method includes the steps of routing the signal outputs resulting from the first interconnect matrix through a second interconnect matrix. This second routing comprises the steps of routing all signal outputs, allowing both original and duplicate through the second interconnect matrix and each successfully routed signal is then prevented from being

Affiliated with

Also associated with

Rating

Method to improve routability in programmable logic devices... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method to improve routability in programmable logic devices..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method to improve routability in programmable logic devices... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2995868