Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2001-02-09
2002-08-06
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S038000
Reexamination Certificate
active
06429681
ABSTRACT:
BACKGROUND OF THE INVENTION
Programmable logic devices (PLDs) are integrated circuit devices with configurable logic networks linked together by programmable interconnection resources. The configurable logic networks may include device elements such as logic cells (e.g., look-up tables (LUTs) or product term logic), memory cells, and input-output cells. Registers (e.g., D-type flip-flops) may be associated with one or more of the device elements. The registers hold and transfer data signals (i.e., variables) between the device elements during device operation.
The device elements of a conventional PLD are often architecturally organized into blocks of programmable logic (e.g., gate arrays), blocks of input-output cells, and blocks of memory (e.g., random access memory (“RAM”)), etc. Groups of these blocks may make up larger blocks (i.e., “super-regions”) that are arranged, for example, in an X-Y array. The programmable interconnection resources of the PLD are organized as rows and columns of conductors for selectively routing signals to, from, and between the logic, input-output, and memory blocks. See, for example, Cliff et al. U.S. Pat. No. 5,550,782, Cliff et al. U.S. Pat. No. 5,689,195, and Jefferson et al. U.S. patent application Ser. No. 09/266,235, filed Mar. 10, 1999, all of which show PLD architectures developed by Altera Corporation of San Jose, Calif.; but other examples of architectures with which the present invention can be used include those developed by other PLD manufacturers such as Xilinx, Inc., also of San Jose, Calif.
Complex logic functions (circuits), as desired, may be implemented in present-day PLDs. The logic functions are implemented by interconnecting a select configuration of device elements according to a suitable circuit design. Conventional circuit design techniques for synthesis of logic functions may be used to generate a suitable circuit design. The circuit design may be characterized by a corresponding configuration file (i.e., a netlist) that specifies the placement and interconnection of selected device elements. PLDs usually have a large number of device elements that have identical functionality (e.g., AND gates) and which may be used interchangeably. Therefore, several possible circuit designs (i.e., configurations of device elements) may yield the same desired logic function.
The circuit design which is implemented is, usually, optimized for circuit performance. A measure of circuit performance is data signal propagation delay. This delay depends, inter alia, on the length of interconnection and on the number of registers between device elements traversed by data signals. A figure of merit of circuit delay performance is the length (in units of time) of the longest register-to-register delay path (“the critical path”) in the circuit.
Critical path length may be minimized using “re-timing” techniques for optimizing circuit designs. These techniques address the problem of optimal placement and interconnection of device elements by repositioning registers along the path of data signals. Registers associated with logic cells are repositioned from the cells' output to input or vice versa, so that the critical path is as short as possible (see, De Micheli Giovanni, Synthesis and Optimization of Digital Circuits, McGraw-Hill, Inc., 1994, Chapter 9, TK7874.65 D4). Local network topology as well as overall architecture of a PLD determine the efficacy of re-timing optimization of circuit designs that can be implemented in the PLD.
The local network topology may impede the repositioning of registers. For example, moving a register through a multiple fan-in logic cell requires duplicating the register at each fan-in input. However, positioning a register on an input of the multiple fan-in logic cell may be precluded by the presence of an already existing register on the input. As another example, moving a register to an output of a multiple fan-out source logic cell may change the latency (i.e., the number of cycles for execution) of the other outputs of the source logic cell.
Additionally, the architecture of a PLD itself may restrict possibilities for repositioning registers. For example, the PLD architecture may partition the device into a hierarchy of regions and require use of long interconnections between the regions (see, for example, Jefferson et al. U.S. patent application Ser. No. 09/266,235, filed Mar. 10, 1999). Some circuit designs must use device elements in different regions. For these designs, repositioning of registers along the data path between the device elements in different regions cannot reduce critical path length below the length of a long interconnection that must be used.
A further drawback of re-timing optimization, irrespective of local topology and PLD architecture, is that any significant changes in the number of registers make simulation and verification of circuit designs computationally expensive.
Consideration is now being given to ways of enhancing programming logic device architectures to increase flexibility in re-timing optimization of circuit designs.
SUMMARY OF THE INVENTION
In accordance with the present invention, programmable logic device architectures are enhanced by additionally providing one or more registers (“re-timing registers”) associated exclusively with interconnection resources. These re-timing registers are not associated with any individual device element such as a logic cell, memory cell, or an input-output cell, and are in addition to registers that are conventionally associated with individual device elements.
PLDs with a hierarchical architecture may have segments of interconnection conductors buffered at hierarchical partition boundaries. For these PLDs, the provided re-timing registers are placed in parallel to segmentation buffers. Additionally, programmable links are provided to enable data paths between disconnected segments of conductors. The data paths are enabled through the re-timing registers bypassing the segmentation buffers. Re-timing optimization of circuit designs can utilize positioning of re-timing registers on interconnection conductors, independent of local circuit topology. Long interconnections between regions across the partition boundaries are enabled with only short segments of the interconnection conductors contributing to register-to-register path lengths.
Further features of the invention, its nature and various advantages will be more apparent from the accompanying drawing and the following detailed description.
REFERENCES:
patent: 5550782 (1996-08-01), Cliff et al.
patent: 5689195 (1997-11-01), Cliff et al.
patent: 6107825 (2000-08-01), Lane et al.
patent: 6215326 (2001-04-01), Jefferson et al.
patent: 6272655 (2001-08-01), Hecht et al.
U.S. Patent applicaton No. 09/266,235, Jefferson et al., filed Mar. 10, 1999.
Giovanni De Micheli,Synthesis and Optimization of Digital Circuits, McGraw-Hill, Inc., New York, 1994, Chapter 9, pp. 441-503.
Aldridge Jeffrey C.
Altera Corporation
Fish & Neave
Tan Vibol
Tejwani Manu J.
LandOfFree
Programmable logic device routing architecture to facilitate... 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 logic device routing architecture to facilitate..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable logic device routing architecture to facilitate... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2876205