Abstract:
The described embodiments relate to the general area of Field Programmable Gate Arrays (FPGAs), and, in particular, to the architecture and the structure of the building blocks of the FPGAs. Proposed logic units, as separate units or a chain of units, which are mainly comprised of look-up tables, multiplexers, and latches, implement different mathematical and logical functions. Having two outputs, the embodiments of the logic unit can operate in a split mode and perform two separate logic and/or arithmetic functions at the same time. Chains of the proposed logic units, wherein every other unit is clocked by one of the two half clock cycles and utilizes local interconnections instead of traditional routing channels, add to efficiency and speed, and reduce required real estate.

Description:
TECHNICAL FIELD  
       [0001]     This invention relates to the general area of Field Programmable Gate Arrays (FPGA) In particular, it relates to the architecture of FPGA building blocks, arrays of modularized blocks, and their interconnection resources.  
       BACKGROUND  
       [0002]     A digital logic circuit, generally formed as a cascade of separate logic functions, is a circuit that produces a digital output as a result of some logical operation on its digital inputs. Digital logic circuits are typically implemented on various types of integrated semiconductor chips. One widely known type of integrated chip is the Application Specific Integrated Circuit (ASIC), which is a custom-made integrated chip. Each ASIC is manufactured to implement a specific digital logic circuit.  
         [0003]     Programmable chips are another type of integrated chips, but differ from ASICs because of their ability to implement any number of different complex digital logic circuits by configuring the underlying integrated chip. The programmable integrated chips are less costly, usually in a limited volume, than ASICs because a large number of similar integrated chips may be manufactured from a single design, which can later be configured to implement a wide variety of digital logic circuits. For this reason the cost of design and manufacturing is distributed over a large number of integrated chips.  
         [0004]     An FPGA is one type of programmable integrated chips. The FPGA can either be permanently programmed by the user, such as in U.S. Pat. No. 4,758,745 by El Gamal, et al., or can be temporarily programmed by the user, as described in U.S. Pat. No. 4,870,302, by Freeman.  
         [0005]     Typically, an FPGA consists of an array of modularized logic units and interconnection resources. It is an array of uncommitted gates with uncommitted wiring channels. Each logic unit can be programmed to implement a particular logic function. Various digital circuits may be implemented to execute desired functions by programming a number of logic blocks and interconnecting them using interconnection resources. In other words, to implement a particular circuit function, the circuit is mapped into the array and the wiring channels and appropriate connections are programmed to implement the necessary wiring connections that form the circuit function. A gate array circuit can be programmed to implement virtually any set of functions.  
         [0006]     Of utmost importance in designing an FPGA is the topology of the logic units and the interconnection resources since different FPGA architecture provides different performance characteristics. Also, the programming of a gate array and the mapping of a desired functionality onto it depend upon the topology of the gate array. If the logic units of the gate array are high-level blocks, such as counters, parity generators, and the like, then the amount of programming required is limited to the interconnections among these large- or coarse-grain units.  
         [0007]     If, on the other hand, the logic units of the gate array are low-level blocks, such as gates, latches, and the like, then the amount of programming is significantly higher, because these smaller, or fine-grain, units need to be interconnected to affect the higher-level functions. In some designs the use of the fine-grain units results in higher circuit densities because the desired functions can be implemented more efficiently with small low-level units rather than with larger high-level units whose high-level functionality is useless in the particular circumstances.  
         [0008]     A highly complex logic unit may be able to perform a large number of complex operations, but if a relatively simple operation is desired, much of the functionality and semiconductor real estate will be wasted. At the same time, a logic unit consisting of basic logic gates requires extensive wiring to perform sophisticated operations. In other words, some complex designs cannot be efficiently embodied in a fine-grain gate array because the amount of interconnection required among the low-level units exceeds the capacity of the gate array.  
         [0009]     The traditional implementations of the FPGA logic element units have predominantly focused on a single logic element producing a combinatorial function with arithmetic, sequential, and register packing capabilities. With such architecture, and in many applications, many of the capabilities of an FPGA logic element may remain unused. Various architectures have been proposed to optimize the tradeoffs among circuit building blocks, routing efficiency, performance limits, and the like. There is a need for logic units or a cluster of logic units that optimizes flexibility and functionality of the FPGAs. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]      FIG. 1  is a schematic circuit diagram of an FPGA logic unit, in accordance with an embodiment of the invention.  
         [0011]      FIG. 2  depicts a logic head while operating as a 4-input look-up table (LUT 4 ), in accordance with another embodiment of the invention.  
         [0012]      FIG. 3  depicts a logic head while operating as a LUT 4  in a register packing mode, in accordance with another embodiment of the invention.  
         [0013]      FIG. 4  depicts a logic head in a split combinational mode, in accordance with yet another embodiment of the invention.  
         [0014]      FIG. 5  depicts a logic head in a split mode while employing D-latches, in accordance with yet another embodiment of the invention.  
         [0015]      FIG. 6  illustrates a fast processing path configuration, wherein the logic head is in a split mode with D-latches, in accordance with an alternative embodiment of the invention.  
         [0016]      FIG. 7  illustrates a fast processing path configuration, wherein the logic head is in a LUT 4  mode with D-latches, in accordance with an alternative embodiment of the invention.  
         [0017]      FIG. 8  illustrates a fast processing path configuration, wherein the logic head is in a split mode with combinational logic and D-latches, in accordance with another alternative embodiment of the invention.  
         [0018]      FIG. 9  illustrates a fast processing path configuration, wherein the logic head is in a split mode with D-latches and both of the split parts are members of one path, in accordance with an alternative embodiment of the invention. 
     
    
     DETAILED DESCRIPTION  
       [0019]     Various embodiments of the invention will now be described. The following description provides specific details for a thorough understanding and enabling description of these embodiments. One skilled in the art will understand, however, that the invention may be practiced without many of these details. Additionally, some well-known structures or functions may not be shown or described in detail, so as to avoid unnecessarily obscuring the relevant description of the various embodiments.  
         [0020]     The terminology used in the description presented below is intended to be interpreted in its broadest reasonable manner, even though it is being used in conjunction with a detailed description of certain specific embodiments of the invention. Certain terms may even be emphasized below; however, any terminology intended to be interpreted in any restricted manner will be overtly and specifically defined as such in this Detailed Description section.  
         [0021]     The described embodiments illustrate significant performance enhancement by split-mode dual combinatorial capabilities, combined synchronous control logic, independent and fully swappable outputs, dividable D flip-flop, and a fast data processing path based on such possibilities.  
         [0022]     The present invention relates to the general area of Field Programmable Gate Arrays (FPGAs), and, in particular, to the architecture of the logic units that are the building blocks of the FPGAs, hereinafter called “logic heads,” and the cascade of such logic heads. A cascade of the proposed logic heads does not require traditional channel-based routing resources and, as such, improves efficiency in several areas. In the detailed description provided below, different embodiments of the proposed logic head are disclosed, and some of their functional capabilities are illustrated. In addition, some of the advantages of cascading logic heads are described, and a few of the functional capabilities of such cascades will be presented.  
         [0023]     In an embodiment illustrated in  FIG. 1 , a logic head  100 , which is a function unit of an FPGA, comprises: 
        two 3-input look-up tables (LUT 3 ):  101  and  102 ;     six inputs: IP- 1 -IP 6 , where three of the inputs are shared between the two LUT 3 s;        
 
         [0026]     four control signals: clock (CLK), synchronous reset (Syn_Rst), asynchronous reset (asynchronous_Rst), and synchronous load (Sload);  
         [0027]     two outputs: OP 1  and OP 2 ;  
         [0028]     two D-latches:  112  and  114 ;  
         [0029]     two dynamic (standard) multiplexers:  107  and  108 ;  
         [0030]     seven hard-wired (programmable) multiplexers:  103 ,  104 ,  105 ,  109 ,  110 ,  116 , and  118 ;  
         [0031]     one inverter:  111 ; and  
         [0032]     a number of switches (not shown for clarity of the figures).  
         [0033]     The LUT 3  look-up tables are universal function generators and not necessarily limited to 3-inputs as shown in the logic diagrams. The two D-latches are triggered by opposite clock levels, and if combined together, they can form an edge-triggered D flip-flop. Without requiring channel-based or any external routing resources, required by most traditional FPGAs, a fast data processing path can be formed by directly linking the logic heads.  
         [0034]     The logic function of each logic head is determined by the content of its look-up table and the appropriate routing of its internal signals. As illustrated by the embodiments of this invention, each logic head can operate in a split mode, and perform two separate functions in parallel or in series. Each logic head can also perform 2-bit arithmetic functions, and while in a cascading chain the logic heads perform multiple other functions. A cascading chain of logic heads improves logic efficiency in addition to significantly enhancing the performance without requiring traditional channel-based routing resources.  
         [0035]     On the other hand, the logic units of most of the prior art FPGAs require 4-input look-up tables, dedicated carry logic, and multiple registers, which make them more complicated while performing the same or fewer functions. A few of the presently available commercial logic unit structures use 3-input look-up tables to implement logic functions, as indicated in U.S. Pat. No. 6,476,636 by Jung-Cheun Lien and U.S. Pat. No. 6,236,229 by Zvi Or-Bach. Also, regarding the cascading techniques, some prior arts include Altera&#39;s 10K family, which uses an AND gate, and Xilinx Virtex-architecture, which uses dedicated 2-to-1 multiplexers.  
         [0036]     The embodiments of the present invention have expanded the flexibility of the logic units by, among other advantages, providing for split-mode dual combinatorial capabilities, which are supported by the two independent logic head outputs, and by the possibility of the formation of cascading logic chains, which employ dynamic multiplexers.  
         [0037]     The two LUT 3 s of each logic head can implement a LUT 4  with the help of a 2-to-1 dynamic multiplexer. The two LUT 3 s can also produce two LUT 3 s, two LUT 2 s, or one LUT 3  and one LUT 2 , in parallel. The registered or the non-registered outputs of the two LUT 3 s, LUT 2 s, LUT 4 , or some of the inputs of the logic head can be routed to either of its two outputs, OP 1  or OP 2 . Feeding back one or both of the outputs helps implement additional functionality such as counting, accumulating, finite state machines, or multi-level random logic. The provided D-latches, in addition to serving the logic head or its neighboring logic heads, may be used along with the D-latches of other logic heads to form a register chain.  
         [0038]     In the following paragraphs, different embodiments of the invention will demonstrate how a logic head is programmed to implement any mentioned function. In the figures, the internal signal flow of the logic head, related to its function, is illustrated with a broken line. Based on these examples, and their associated figures, a person of ordinary skill in the relevant art will be able to program and configure such circuits and control or hard-wire, the multiplexers, to perform a desired function mentioned herein. (Hereinafter “hard-wiring” of a multiplexer will be referred to as “programming” the multiplexer.)  
         [0039]      FIG. 2  depicts a logic head while operating as a 4-input look-up table (LUT 4 ), in accordance with another embodiment of the invention. Each LUT 3   101  and  102  has 23 memory bits. The two of them together are capable of addressing 2(23) or 24 data bits, which is the same as the number of possible combinations of a 4-input logic gate. Therefore, to use the logic head of  FIG. 2  as a 4-input logic gate, IP 1 , IP 2 , IP 3 , and IP 6  are chosen to be the inputs to the logic gate, and multiplexers  103 ,  104 , and  105  are programmed so that LUT 3 s  101  and  102  both receive IP 1 , IP 2 , and IP 3  as their inputs. In this way IP 6  is used to control multiplexer  107  and choose between LUT 3   101  and LUT 3   102  outputs. In short, this arrangement makes  24  memory bits available and addressable by IP 1 , IP 2 , IP 3 , and IP 6 , while each LUT 3  can be used separately to implement 1-, 2-, or 3-input logic gates.  
         [0040]     In the arrangement of  FIG. 2 , the desired outcome of all the logic combinations in which IP 6 =0 must be stored in one LUT 3  and the ones with IP 6 =1 must be stored in the other LUT 3 . If the non-registered version of the output of multiplexer  107 , which is effectively the output of the desired “4-input logic gate,” is needed, it can be furnished at OP 1  and/or OP 2  by merely programming multiplexers  116  and/or  118 , respectively.  
         [0041]     If the registered version of the output of multiplexer  107  is desired, appropriate control of multiplexer  108 , by Sload and Syn_Rst lines, routes the multiplexer  107  output to multiplexers  109  and  110  and from multiplexers  109  and  110 , by appropriate programming, to D-latch  112  and/or  114 . Programming of multiplexers  116  and/or  118  will make the latched outputs of D-latch  112  and/or  114  available at OP 1  and/or OP 2 . Proper programming of multiplexers  109 ,  110 ,  116 , and  118  will route the output of the D-latch  114  through the D-latch  112  before it appears at OP 1  and/or OP 2 . With this arrangement the logic head is a LUT 4  combined with a D flip-flop.  
         [0042]      FIG. 3  depicts a logic head while operating as a LUT 4  in a register packing mode, in accordance with another embodiment of the invention. In this embodiment the output of LUT 4  may be available at OP 1  and/or OP 2  by programming multiplexers  116  and/or  118 . The LUT 4  output may also become available at OP 1  and/or OP 2  after going through the D flip-flop formed by D-latches  112  and  114 , when multiplexers  108 ,  109 ,  110 ,  116 , and  118  are appropriately controlled and programmed. In this embodiment the mentioned D flip-flop can be separately used by a signal entering the logic head at IP 5  input, while the LUT 4  is also independently utilized. Such separate usage of LUT 4  and D flip-flop also requires programming of the same mentioned multiplexers.  
         [0043]      FIG. 4  depicts a logic head in a split mode, with both of its LUT 3 s available in parallel as unregistered combinational logic. Using IP 1 , IP 2 , and IP 3  as inputs to LUT 3   101 , and IP 4 , IP 5 , and IP 6  as inputs to LUT 3   102 , both LUT 3 s can be employed separately, and by programming multiplexers  116  and  118 , the outputs of LUT 3   101  and LUT 3   102  can be available at OP 1  and OP 2 , respectively. The above explanation enables a person of ordinary skill in the appropriate art to also use either or both of the LUT 3 s as LUT 2 s.  
         [0044]      FIG. 5  depicts a logic head in a split mode, with both of its LUT 3 s available in parallel, in latched form. In this embodiment, using IP 1 , IP 2 , and IP 3  as inputs to LUT 3   101 , and IP 4 , IP 5 , and IP 6  as inputs to LUT 3   102 , both LUT 3 s can be utilized separately. The output of LUT 3   101  can be available at OP 1  after going through multiplexer  109 , D-latch  112 , and multiplexer  116 , while the output of LUT 3   102  can be available at OP 2  after going through multiplexer  110 , D-latch  114 , and multiplexer  118 , if multiplexers  109 ,  110 ,  116 , and  118  are appropriately programmed. The above explanation enables a person of ordinary skill in the appropriate art to also use either or both of the LUT 3 s as LUT 2 s.  
         [0045]     The embodiment illustrated in  FIG. 6  is an example of a fast processing path with two cascaded logic heads in a split mode, representing an n th  and an (n+ 1  ) th  stages of a cascade chain. Each stage of such chain latches the outputs of the corresponding two LUT 3 s for half a clock cycle. In the arrangement of  FIG. 6 , every other stage of the chain latches during every other half cycle of the clock.  
         [0046]     For example, stage n latches during the high-level half cycle of the clock (clock-high) and stage (n+1) latches during the low-level half cycle of the clock (clock-low).  
         [0047]     The top row cascade chain of  FIG. 6 , comprising all  101  LUT 3 s, is functionally separate from the bottom row cascade chain, which comprises all  102  LUT 3 s. In this embodiment D-latch  112  switches its place with D-latch  114  from one stage to the next. For example, at stage n, LUT 3   101  is in communication with D-latch  112  and LUT 3   102  is in communication with D-latch  114 , while at stage (n+1) LUT 3   101  is in communication with D-latch  114  and LUT 3   102  is in communication with D-latch  112 .  
         [0048]     In this embodiment the outputs of the two D-latches  112  and  114  of any stage can be connected to any of the three inputs of the corresponding LUT 3  of the next stage. For example, the output of the D-latch  112  of stage n can be connected to IP 1 , IP 2 , or IP 3  of the LUT 3   101  of stage (n+1) and the output of the D-latch  114  of stage n can be connected to IP 4 , IP 5 , or IP 6  of the LUT 3   102  of stage (n+1). This embodiment is possible through appropriate programming of multiplexers  109 ,  110 , 116 , and  118 .  
         [0049]     In an alternative embodiment, similar to the one shown in  FIG. 6 , at every stage LUT 3   101  remains in communication with D-latch  112  and LUT 3   102  remains in communication with D-latch  114 ; however, the combination of LUT 3   101  and D-latch  112  switches its place with the combination of LUT 3   102  and D-latch  114  from one stage to the next. In this embodiment the output of the D-latch  112  of stage n can be connected to IP 4 , IP 5 , or IP 6  of the LUT 3   102  of stage (n+1) and the output of the D-latch  114  of stage n can be connected to IP 1 , IP 2 , or IP 3  of the LUT 3   101  of stage (n+1). This embodiment is possible through appropriate control and programming of multiplexers  109 ,  110 ,  116 , and  118 .  
         [0050]     The embodiment illustrated in  FIG. 7  is an example of a fast processing path with two cascaded logic heads each operating in LUT 4  mode, representing an n th  and an (n+1) th  stages of a cascade chain. Each stage of such chain latches the outputs of the corresponding LUT 4  for half a clock cycle. In the arrangement illustrated in  FIG. 7 , every other stage of the chain latches during every other half cycle of the clock. For example, stage n latches during the high-level half cycle of the clock (clock-high) and stage (n+1) latches during the low-level half cycle of the clock (clock-low).  
         [0051]     In this embodiment every other stage uses D-latch  112  and the remaining in-between stages use D-latch  114 . In this embodiment the output of the employed D-latch of any stage can be connected to any of the four inputs of the corresponding LUT 4  of the next stage. For example, the output of the D-latch  112  of stage n shown in  FIG. 6  can be connected to IP 1 , IP 2 , IP 3 , or IP 6  of the LUT 4  of stage (n+1). This embodiment is possible through appropriate programming of multiplexers  108 ,  109 , and  118  at every other stage and  108 ,  110 , and  118  at the remaining in-between stages.  
         [0052]      FIG. 8  illustrates a fast processing path arrangement, similar to the one in  FIG. 6 , where LUT 3 s are replaced by any combinational logic and the logic heads, in effect, are used for their D-latches only. To use a logic head for its D-latches only, LUT 3   101  can be programmed so that the output of the LUT 3   101  follows one of its inputs, for example, IP 1 , and LUT 3   102  can be programmed so that its output follows one of its inputs, for example, IP 4 . With such arrangement, the output of the combinational logics depicted in  FIG. 8  can be tied to IP 1  and IP 4  and in effect the combinational logics replace the LUT 3 s. The multiplexer programming requirements of this embodiment are similar to those of the embodiments described in relation to  FIG. 6 .  
         [0053]     In yet another embodiment shown in  FIG. 9 , both parts of a split logic head are members of the same cascade chain. The two parts of any logic head participating in the chain can either be consecutively arranged or reside separated from each other within the chain.  FIG. 9  depicts two logic heads whose parts are consecutively arranged. One of the advantages of this embodiment is that most of the multiplexers of all logic heads are programmed the same and each logic head is fully utilized within the same chain.  
         [0054]     In general, among other functions, a single or a cascade of logic heads can be utilized as: 
    a LUT 4 ;     combinational logic and sequential elements used separately and simultaneously;     two LUT 3 , with or without latched outputs;     a 4-to-1 Multiplexer;     a 4-to-2 cross switch, where any one input of 4 can go to either of the two outputs;     multiple logic heads that can be chained to form: 
        a wide-input multiplexer;     a long register chain;     a long pipelined data path with the help of fast carry-chain;     a wide-input logic function, including random logic.    
       
 
         [0065]     Unless the context clearly requires otherwise, throughout the description and the claims, the words “comprise,” “comprising,” and the like are to be construed in an inclusive sense, as opposed to an exclusive or exhaustive sense; that is to say, in the sense of “including, but not limited to.” Additionally, the words “herein,” “above,” “below,” and words of similar import, when used in this application, shall refer to this application as a whole and not to any particular portions of this application. Where the context permits, words in the above Detailed Description using the singular or plural number may also include the plural or singular number respectively. When the claims use the word “or” in reference to a list of two or more items, that word covers all of the following interpretations of the word: any of the items in the list, all of the items in the list, and any combination of the items in the list.  
         [0066]     The above detailed description of embodiments of the invention is not intended to be exhaustive or to limit the invention to the precise form disclosed above. While specific embodiments of, and examples for, the invention are described above for illustrative purposes, various equivalent modifications are possible within the scope of the invention, as those skilled in the relevant art will recognize. Also, the teachings of the invention provided herein can be applied to other systems, not necessarily the system described above. The elements and acts of the various embodiments described above can be combined to provide further embodiments.  
         [0067]     All of the above patents and applications and other references, including any that may be listed in accompanying filing papers, and U.S. patent application Ser. No. 10/883,901 filed Jul. 2, 2004, titled “LOGIC CELL FOR FIELD PROGRAMMABLE GATE ARRAY,” AND U.S. patent application Ser. No. 10/916,232 filed Aug. 11, 2004, titled “FIELD PROGRAMMABLE GATE ARRAY LOGIC UNIT AND ITS CLUSTER,” are incorporated herein by reference. Aspects of the invention can be modified, if necessary, to employ the systems, functions, and concepts of the various references described above to provide yet further embodiments of the invention.  
         [0068]     Changes can be made to the invention in light of the above Detailed Description. While the above description details certain embodiments of the invention and describes the best mode contemplated, no matter how detailed the above appears in text, the invention can be practiced in many ways. Therefore, implementation details may vary considerably while still being encompassed by the invention disclosed herein. As noted above, particular terminology used when describing certain features or aspects of the invention should not be taken to imply that the terminology is being redefined herein to be restricted to any specific characteristics, features, or aspects of the invention with which that terminology is associated. In general, the terms used in the following claims should not be construed to limit the invention to the specific embodiments disclosed in the specification, unless the above Detailed Description section explicitly defines such terms. Accordingly, the actual scope of the invention encompasses not only the disclosed embodiments, but also all equivalent ways of practicing or implementing the invention under the claims.  
         [0069]     While certain aspects of the invention are presented below in certain claim forms, the inventors contemplate the various aspects of the invention in any number of claim forms. For example, while only one aspect of the invention is recited as an embodied in computer-readable medium, other aspects may likewise be embodied in a computer-readable medium. Accordingly, the inventors reserve the right to add additional claims after filing the application to pursue such additional claim forms for other aspects of the invention.