Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2002-09-25
2004-10-26
Tran, Anh Q. (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S038000, C326S047000
Reexamination Certificate
active
06809551
ABSTRACT:
TECHNICAL FIELD
The present invention relates to programmable logic devices (PLDs), such as field-programmable gate arrays (FPGAs) and complex PLDs (CPLDs). More particularly, the present invention relates to a method of routing signals in a PLD.
BACKGROUND
Non-volatile memory devices, such as EPROM, EEPROM, and Flash EEPROM, store data even after power is turned off. One common application of EEPROMs is in programmable logic devices (PLDs). PLDs are standard semiconductor components purchased by systems manufacturers in a “blank” state that can be custom configured into a virtually unlimited number of specific logic functions. PLDs provide system designers with the ability to quickly create custom logic functions to provide product differentiation without sacrificing rapid time to market. PLDs may be reprogrammable, meaning that the logic configuration can be modified after the initial programming.
One type of PLD is known as a Field-Programmable Gate Array (FPGA). An FPGA is a general purpose device that can be programmed by an end user to perform one or more selected functions. An FPGA typically includes an array of individually programmable logic cells (PLCs), each of which is programmably interconnected to other PLCs and to input/output (I/O) pins via a programmable routing structure to provide the selected function. Examples of such devices are exemplified in U.S. Pat. Nos. 4,642,487; 4,706,216; and 4,758,985.
An FPGA device can be characterized as an integrated circuit that may include four major features:
(1) A user-accessible, configurable memory device, such as SRAM, EPROM, EEPROM, anti-fused, fused, or other, is provided in the FPGA device so as to be at least once-programmable by device users for defining user-provided configuration information. Static Random Access Memory or SRAM is a form of reprogrammable memory that may be differently programmed many times. Electrically Erasable programmable ROM or EEPROM is another example of nonvolatile reprogrammable memory. The configurable memory of an FPGA device may be formed of a mixture of different kinds of memory elements if desired (e.g., SRAM and EEPROM).
(2) Input/Output Blocks (IOBs) are provided for interconnecting other internal circuit components of the FPGA device with external circuitry. The IOBs may have fixed configurations or they may be configurable in accordance with user-provided configuration information.
(3) PLCs are provided for carrying out user-programmed logic functions (e.g., logic gates) as defined by user-provided configuration information. Typically, each of the many PLCs of an FPGA has at least one lookup table (LUT) that is user-configurable to define any desired truth table. A PLC may have other resources such as LUT input signal pre-processing resources and LUT output signal post-processing resources.
(4) An interconnect network is provided for carrying signal traffic within the FPGA device between various PLCs and/or between various IOBs and/or between various IOBs and PLCs. At least part of the interconnect network is typically configurable so as to allow for programmably-defined routing of signals between various PLCs and/or IOBs in accordance with user-defined routing information.
Most FPGAs have these four features, but modern FPGAs tend to be even more complex. For example, many PLCs can be configured together to implement such devices as multipliers or complex microprocessors. For example, U.S. Pat. No. 5,754,459, issued May 19, 1998 to Telikepalli, teaches implementing a multiplier circuit using a number of PLCs in an FPGA architecture. However, implementing a multiplier using PLCs of an FPGA architecture may not only consume valuable PLC resources, but also consume valuable general interconnect resources, which in turn may slow performance of the FPGA device. Consequently, preconfigured, dedicated multipliers have been inserted into some FPGA designs in order to free valuable PLC resources for other functions, such as illustrated in U.S. Pat. No. 6,362,650 to New, et al.
It is therefore desirable to provide a PLD device that can further free valuable PLC resources while increasing overall functionality. Including other dedicated components into the PLD, however, can create routing problems between the PLCs and the dedicated components. Accordingly, it is desirable to provide a method of optimizing routing in a PLD.
SUMMARY
A method of routing input signals in a programmable logic device (PLD) is disclosed. In a PLD having a PLD domain (where data is manipulated on a bit-by-bit basis) and a vector domain (where bits are grouped together and manipulated as multi-bit data units termed words or vectors), input signals from the PLD domain may be routed to the vector domain through an interface. The interface, however, often comprises a limited number of conductors and restricts the amount of data that can be directly transmitted to the vector domain. To overcome this problem, an input switching unit is disclosed that may use PLD-domain resources to route the input signals according to the time periods (or states) in which they operate. The input switching unit may comprise one or more multiplexers that route the input signals in a time-multiplexed manner. Thus, the amount of data that can be transmitted through the interface is maximized.
According to one aspect of the disclosed method, input signals are associated with time periods, and at least a portion of the input signals are grouped into groups of input signals that share a conductor but that use the conductor during mutually exclusive time periods. In one particular implementation of the method, the grouping is accomplished through the creation of one or more data structures. For example, a first data structure may identify the time periods in which the input signals are used. The first data structure may further identify the vector-domain destinations to which the input signals are routed (e.g., inputs of a vector-domain engine). A second data structure may identify usage values for the input signals. The usage values of the input signals may then be used to identify the time periods in which the input signals operate. A third data structure may identify related input signals. Related input signals comprise input signals that are routed to a common vector-domain destination. A fourth data structure may contain data entries identifying the related input signals and the remaining unrelated input signals. The entries of the fourth data structure may further identify combined usage values for the related input signals and usage values for the remaining unrelated input signals. The fourth data structure may then be iteratively compressed by grouping together data entries that identify input signals used during mutually exclusive time periods. A final data structure may then be generated from the compressed fourth data structure.
A PLD having an input switching unit for routing input signals that operate in mutually exclusive time periods is also disclosed. The input switching unit may be designed using the disclosed method.
These and other aspects of the disclosed technology will become apparent from the following detailed description, which makes references to the accompanying drawings.
REFERENCES:
patent: 4642487 (1987-02-01), Carter
patent: 4706216 (1987-11-01), Carter
patent: 4758985 (1988-07-01), Carter
patent: 5197065 (1993-03-01), Calvignac et al.
patent: 5295137 (1994-03-01), Jurkevich
patent: 5754459 (1998-05-01), Telikepalli
patent: 6023742 (2000-02-01), Ebeling et al.
patent: 6262908 (2001-07-01), Marshall et al.
patent: 6275491 (2001-08-01), Prasad et al.
patent: 6289097 (2001-09-01), Gregory et al.
patent: 6362650 (2002-03-01), New et al.
patent: 6363319 (2002-03-01), Hsu
patent: 6538470 (2003-03-01), Langhammer et al.
patent: 2002/0089348 (2002-07-01), Langhammer
Alves et al., “RVC—A Reconfigurable Coprocessor for Vector Processing Applications,” IEEE Com. Soc., pp. 258-259 (1998).
Birkner et al., “High Performance Mulitpliers in QuickLogic FPGAs,” 9 pp, no date.
Chameleon Systems—Your Communication Platform; from
Lattice Semiconductor Corporation
Tran Anh Q.
LandOfFree
Method of optimizing routing in a programmable logic device 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 of optimizing routing in a programmable logic device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of optimizing routing in a programmable logic device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3289122