Method to improve routability in programmable logic devices via prioritized augmented flows

Abstract

A method and system 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 method determines a set of high priority signals. In routing the upstream PIM, the method uses a Maximum Bipartite Matching process in one embodiment to route the original signals once. The duplicated high priority signals are then routed and sent to the input array of the downstream interconnect matrix along with the originally routed signals. From the originally routed signals and the duplicate signals, the downstream interconnect matrix routes each unique signal once and only once depending on 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.