Abstract:
A circuit comprising a programmable routing network, a logic array configured to generate a plurality of product terms in response to one or more of a plurality of input signals from said programmable routing network, a plurality of look-up tables each configured to receive a logical combination of at least two of said product terms and a plurality of macrocells each configured to generate an output in response to one or more of said look-up tables.

Description:
This is a continuation of U.S. Ser. No. 09/087,654, filed May 30, 1998, now U.S. Pat. No. 6,201,408. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to programmable logic devices generally and, more particularly, to a programmable logic device architecture that may improve functionality over look-up table based or product-term based programmable logic devices and that may provide for the efficient implementation of user-programmable logic designs resulting in implementations that may require less area and may provide increased performance. 
     BACKGROUND OF THE INVENTION 
     Field programmable gate arrays (FPGAs) typically consist of arrays of programmable macrocells (or arrays of clusters of programmable macrocells) and a programmable routing network. The programmable routing network is used to route signals between macrocells, between clusters of macrocells, and between the I/Os and macrocells. FPGA macrocells may contain one or more look-up tables (LUTs), a flip-flop, one or more programmable multiplexers, and control logic for flip-flop control signals, as well as carry chain and cascade chain logic. 
     Referring to FIG. 1, one conventional FPGA macrocell  10  is shown comprising a look-up table  12 , a look-up table  14 , a look-up table  16 , a number of configuration multiplexers  18   a - 18   n,  a flip-flop  20 , and a flip-flop  22 . The FPGA macrocell  10  is sometimes referred to as a logic element, a logic cell, a programmable function unit, a configureable logic block or other similar name. 
     Referring to FIG. 2, a portion of a typical FPGA  30  is shown made up of a number of FPGA macrocells  10   a - 10   n.  Programmable routing channels ( 34   a - 34   n ) are located between the FPGA macrocells  10   a - 10   n  and can be used to propagate signals from one of the macrocell  10   a - 10   n  to another and between input/output (I/O) and the macrocells  10   a - 10   n.  FIG. 3 illustrates a routing matrix  40  that can be implemented to produce the inputs to the various macrocells  10   a - 10   n.    
     Logic functions are implemented in FPGA macrocell  10  by using (i) synthesis and technology mapping software to map logic into the macrocells, (ii) placement software to determine where to place logic within the array, and (iii) routing software to route the necessary signals in the programmable routing network. 
     Referring to FIG. 4, another macrocell  50  in accordance with conventional methods shown. The macrocell  50  generally comprises a look-up table  52 , a flip-flop  54 , output multiplexers  56   a  and  56   b,  a carry chain logic  58 , flip-flop control logic  60  and a clock select multiplexer  62 . FIG. 5 illustrates a clustered logic block  51  comprising macrocells  50   a - 50   n  and a local programmable routing network. FIG. 6 illustrates an array of clustered logic blocks  51   a - 51   n  illustrating a portion of an FPGA along with an associated routing network. 
     Presently, complex programmable logic devices (CPLD) may contain a programmable routing network, multiple blocks comprising a product term array, a product term matrix, a number of OR-gates, and macrocells. The macrocells are comprised of a programmable flip-flop, programmable multiplexers, and sometimes an XOR gate or carry logic. 
     Logic functions are implemented in the CPLD by using synthesis and technology mapping software to map logic to the product-term array and associated macrocells. Partitioning and placement software is used to determine where to place logic within the CPLD. 
     Some conventional approaches have defined the terms FPGA and CPLD in different ways. In general, the distinction between FPGAs and CPLDs is blurring as both devices move to higher densities. For illustrative purposes, FPGAs will be considered to use LUTs as the basic building-block for implementing logic, and CPLDs will be considered to use product terms (e.g., programmable AND-OR planes) as the basic building block for implementing logic. 
     Some disadvantages of the LUT-based macrocell are that a LUT can only implement functions of up to the number of inputs to the LUT (usually between 3 and 5, inclusive). Complex functions usually must be implemented using a number of macrocells. Some commonly required functions cannot be efficiently implemented in just one macrocell. Functions requiring multiple macrocells utilize the macrocells inefficiently, wasting logic, routing resources, and die area, while degrading the performance of the implemented circuit. 
     One disadvantage of product-term based CPLDs with macrocells (e.g., where the input to a macrocell is an OR function of multiple product terms) is that some functions (e.g, a multiple input XOR function) often cannot be implemented efficiently in AND-OR logic. Arithmetic functions such as adders, subtractors, comparators, and parity trees are examples of functions that are not implemented efficiently with AND-OR logic. 
     SUMMARY OF THE INVENTION 
     The present invention concerns a programmable device architecture that may improve functionality over look-up table based or product-term based programmable logic devices and that may provide for the efficient implementation of user-programmable logic designs resulting in implementations that may require less area and may provide increased performance. A product-term array (either fully or partially populated) may be placed in front of a number of LUT-based macrocells, utilizing the available routing wires as wordlines to form the product terms. The present invention takes advantage of existing routing to do more than just route signals from one point to another by allowing logic to be implemented in the same die area. The result is logic implementations that may require fewer total macrocells, fewer levels of macrocells, and fewer point-to-point nets (because logic density increases). The present invention may apply to FPGAs comprising an array of macrocells and to FPGAs comprising an array of clustered macrocells. The present invention may also be used with CPLDs by replacing or supplementing the product term matrix, OR gates, and macrocells with LUT-based macrocells. The present invention may be used to implement logic functions in fewer macrocells than may be implemented in either LUT-based macrocells or product-term based macrocells alone. 
     The objects, features and advantages of the present invention include providing a product-term array with a look-up table-based macrocell in a FPGA or a CPLD that improves the area efficiency in implementing user designs as well as the speed of operation of the user designs. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other objects, features and advantages of the present invention will be apparent from the following detailed description and the appended claims and drawings in which: 
     FIG. 1 is a block diagram of a conventional FPGA macrocell; 
     FIG. 2 is a block diagram of a number of FPGA macrocells and routing channels; 
     FIG. 3 is a block diagram showing the inputs and programmable connections to the macrocells; 
     FIG. 4 is a block diagram of another conventional approach to implementing a FPGA; 
     FIG. 5 is a diagram showing the clustering of the macrocells of FIG. 4; 
     FIG. 6 is an array of clustered logic blocks illustrating a portion of an FPGA along with an associated routing network; 
     FIG. 7 is a block diagram of a preferred embodiment of the present invention; 
     FIG. 8 is a more detailed block diagram of the macrocell of FIG. 7; 
     FIG. 9 is a block diagram illustrating how the present invention may be used with clustering of macrocells; 
     FIG. 10 is an alternate embodiment of the present invention; 
     FIG. 11 illustrates the present invention as compared to the conventional approach of FIG. 3; and 
     FIG. 12 illustrates the present invention compared to the conventional approach of FIG.  6 . 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring to FIG. 7, a block diagram of a circuit  100  illustrating a preferred embodiment of the present invention is shown. The circuit  100  comprises a product term array  102  and a macrocell  104 . The product-term array  102  may be a fully or partially populated AND-type gate array. The macrocell  104  may be implemented as a LUT-based macrocell with one or more LUTs. A number of outputs  106   a - 106   n  of the product term array  102  may be presented to a number of inputs  108   a - 108   n  of the macrocell  104 . The outputs  106   a - 106   n  may be presented to one or more of the inputs  108   a - 108   n  to macrocell  104  (e.g., the data inputs). A programmable routing network (not shown) provides the inputs to the product term array  102 . The macrocell  104  is preceded with product terms from the product term array  102 . 
     Referring to FIG. 8, a more detailed diagram of the macrocell  104  is shown. The LUT-based macrocell  104  is shown having product terms as the inputs  108   a - 108   n  from the product-term array  102  (shown in FIG.  7 ). The macrocell  104  comprises a LUT  112 , a flip-flop  114 , and output multiplexer  116 . The LUT  112  may be implemented, in one example, as a four-input LUT. The flip-flop  114  may be implemented, in one example, as a D-type flip-flop. However, other variations of the LUT  112  and the flip-flop  114  may be implemented accordingly to meet the design criteria of a particular implementation. The output multiplexer  116  may select either a registered output  117  or a combinational output  118  from the LUT  112 . In one example, the LUT  112  may be split into two smaller LUTs having fewer inputs to produce two functions of the same variables. This may be used, in conjunction with a configuration multiplexer  120 , to implement a carry chain for fast adders and subtractors. Additional configuration multiplexers  122 ,  124  and  126  may be used to select the appropriate reset, preset, and clock signals. The width of the multiplexers  120 ,  122 ,  124  and  126  is shown for illustrative purposes only, and may each be implemented as multiplexers of varying widths. Although the LUT  112  has four data inputs  127   a - 127   n,  the macrocell has five data inputs (i.e.,  108   b - 108   f ). In one example, two of the macrocell inputs (e.g., inputs  108   c  and  108   f ) are presented to a gate  128  which may have an output presented to one of the LUT inputs (e.g., input  127   n ). The gate  128  may be implemented, in one example, as an XOR gate. The gate  128  may be used to aid the efficient implementation of counters since the macrocell  104  is preceded by a product-term array  102 . 
     Referring to FIG. 9, a diagram illustrating a logic block incorporating the present invention in the context of an FPGA comprising a cluster of macrocells  104   a - 104   n.  A number of signals X and Y from a programmable routing network  130  may be presented to the cluster of macrocells  104   a - 104   c  through the product-term array  102 . The signals X and Y generally serve as the wordlines to the product-term array  102 . The product terms may then be distributed to the inputs of the macrocells  104   a - 104   n.  The signals X and Y may be selected using software that may comprise a medium that stores a series of instructions. For one embodiment, the software may be stored in a RAM including SRAM, DRAM or other types of RAM memory. The software may be accessed by a microprocessor, a microcontroller, etc. 
     The preferred embodiment illustrates that the five logic inputs to each of the macrocells  104   a - 104   n  in the cluster may be fed by product terms  132   a - 132   n.  In one example, each of the product terms  132   a - 132   n  may represent a number (e.g., 5) of product terms. However, a larger or smaller number of product terms may be implemented at each output  132   a - 132   n  in order to meet the design criteria of a particular implementation. The product terms  132   a - 132   n  may be used simply to route a signal into one of the macrocell inputs (which is the extent of the flexibility of the conventional approaches discussed in the background) or to implement logic functions such as logical AND, NAND, or NOR. By creating the product terms in the product-term array  102 , the present invention may more efficiently implement functions of more variables and greater complexity, which may result in less required area and higher performance. The higher performance may be achieved despite the additional delay imposed by the product term array  102  since fewer levels of macrocells may be necessary to implement functions. Thus, the delay for a logic implementation using the present invention may be substantially better than the delay for a logic implementation using the conventional approaches due to multiple macrocell delays and the associated routing delays required to use multiple macrocells. 
     The following examples illustrate how the present invention provides improvements over conventional approaches. Consider the macrocell of FIG. 8 without the product terms. A simple design, which is used frequently in many (or most) designs, is a 4-to-1 multiplexer. This implementation is very area inefficient because, when implemented using convention approaches, it requires the area of three macrocells plus the associated routing for implementation. The propagation delay of this implementation is large, the result of two levels of logic and routing. 
     Consider a 4-bit counter with synchronous clear, load, and enable implemented in the macrocell of FIG.  8 . Without the product terms, each counter bit would require two macrocells compared to one macrocell with the product terms. Thus the present invention provides substantial performance and area efficiency gains. 
     The advantages to preceding a LUT-based macrocell with product terms used as inputs to the macrocell include improved performance and area efficiency. The present invention provides these advantages because it may implement functions of more variables and of greater complexity than conventional methods of using LUT-based macrocells or product-term arrays alone. Fewer levels of macrocells are required to implement many functions. This improves performance since multiple levels of macrocells are avoided. Area savings are gained by the use of fewer macrocells and routing. 
     Referring to FIG. 10, an alternate implementation of a circuit  100 ′ is shown. The circuit  100 ′ illustrates a product term matrix  140  placed after the product term array  102 , but before a cluster of the macrocells  104 . The product term matrix  140  may be used to distribute (e.g., steer or share) the product terms among the cluster of the macrocells  104 . 
     Referring to FIG. 11, the present invention is shown compared to the routing of FIG.  3 . The routing of the conventional approach of FIG. 3 may be replaced by a product-term array (e.g., FIG. 11) in order to accomplish the desired objective of this invention (i.e., preceding LUT-based macrocells with product term arrays). The product-term array  102  may be partially or fully populated. The product-term array  102  may be fully populated by providing the true and complement of every signal that is received as an input. Alternatively, the product term array  102  may be partially populated by providing a mechanism for allowing some inputs to propagate in both true and complement form and others in only true or complement form. In addition, some signals in the routing channel will serve as inputs to the array, while others will bypass the array altogether. One example of a partially populated array may be found in co-pending application Ser. No. 09/046,960 filed on Mar. 24, 1998, which is hereby incorporated by reference in its entirety. 
     The result of the circuit  100 ′ is an improved macrocell that combines a normal macrocell with product terms that are created in the routing channels. As with the previous embodiment, the circuit  100 ′ may be modified by creating a partially-populated or fully-populated AND array. 
     Referring to FIG. 12, a comparison is shown compared to the circuit of FIG.  5 . The inputs to the cluster of macrocells form the wordlines to a product term array  102 . Each data input to a macrocell, in turn, is a product term output. The result is an improved cluster of macrocells that combines the prior macrocell with a product term array to provide substantial improvements in area and performance. 
     A related application of the principle of this invention is to implement a product term array in the channels of the FPGA of FIG.  11 . The inputs to the cluster of logic blocks are themselves product terms. 
     While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the spirit and scope of the invention.