Abstract:
Embodiments disclosed herein provide sparse adder circuits comprising Ling type propagate and generate circuits and sparse carry circuits to efficiently add first and second operands to one another.

Description:
BACKGROUND 
       [0001]    Processors have arithmetic logic units (ALUS) to perform calculations involving integers. An ALU generally contains a multiplicity of adder circuits to perform the arithmetic calculations by summing two binary operands together. Adders are generally used by the majority of instructions in controlling the operations of a computer system, microprocessor or the like and are usually performance limiting devices in such systems because they form a core of several critical paths in performing instructions and calculations. For example, typical adder circuits can include over 500 logic gates. 
         [0002]    Traditional high performance (e.g., dense tree adder architectures like so-called Kogge-Stone types) use binary carry-merge trees to generate and provide to the summing circuitry a carry signal for each bit. That is, they generate a carry for every two bits summed together for two binary operands. With 64 bit operands, for example, 64 summations and carries are generated—typically in parallel operations. While the time period during which these arithmetic operations are performed is normally extremely fast, unfortunately, such architectures tend to result in large fan-outs requiring large transistors. They also can require wide routing channels for interstage wiring. 
         [0003]    Accordingly, in order to reduce the size and complexity of the carry tree architecture, other architectures are sought such as those providing a limited number of carry bits to the sum generation circuitry (e.g. every 16 th  bit provided to  16 -bit conditional sum generating circuits).  FIG. 1  shows a Manchester carry chain (MCC) implementation, which is an example of such an architecture. Unfortunately, with these architectures, performance may still be impaired due to excessive bottlenecks through carry merge (CM) gate paths to the sum generators. As indicated in the figure, the carry tree has CM gates with up to four transistors in a stack, which as shown, contribute to a critical path having an associated 32 bit RC delay resulting in slower than desired performance. Such high gate stacks may also tend not to scale well with different semiconductor processes. Accordingly, an improved adder architecture is desired. 
     
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0004]    Embodiments of the invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings in which like reference numberals refer to similar elements. 
           [0005]      FIG. 1  is a diagram of a conventional  64 -bit adder circuit with a MCC carry tree architecture. 
           [0006]      FIG. 2  is a general diagram of an adder circuit having a sparse carry tree in accordance with some embodiments. 
           [0007]      FIG. 3  is a more detailed diagram of the adder circuit of  FIG. 2  in accordance with some embodiments. 
           [0008]      FIG. 4  is a block diagram of a computer system having a microprocessor with at least one adder circuit in accordance with some embodiments. 
       
    
    
     DETAILED DESCRIPTION 
       [0009]    Embodiments disclosed herein generally pertain to implementations of adder circuits using sparse tree architectures having dynamic and static complementary metal oxide semiconductor (CMOS) circuits. 
         [0010]      FIG. 2  shows a general diagram of such an adder circuit in accordance with some embodiments. It comprises sparse carry tree circuitry  204  coupled between Ling type group propagate-generate (PG) circuits  202  and sum generator circuits  206 . The operands, A and B, (which are to be added together) are provided at inputs of the Ling circuits, as well as to inputs of the sum generator circuits  206 . The Ling circuits, as is well known in the art (see, e.g., U.S. Pat. No. 5,719,803 to Naffziger entitled, HIGH SPEED ADDITION USING LING&#39;S EQUATIONS AND DYNAMIC CMOS LOGIC), generate carry propagate and generate (PG) terms from the A and B operands. The PG terms are provided to the sparse carry tree circuitry  204 , which generates carry signals for every n th  bit and provides them to the sum generator circuits  206  to generate the sum of A and B. 
         [0011]      FIG. 3  shows a more detailed implementation of a 64-bit adder circuit in accordance with the adder of  FIG. 2 . The Ling circuitry  202  is grouped into four quadrants ( 302 A to  302 D) to handle 16 bits each. Each quadrant includes four Ling circuits, with each circuit generating PG terms for a 4-bit portion of the applied A and B operands. The Ling circuits output 2-way group-generate (GG i =G i +P i G i−1 ) and group-propagate (GP i =P i P i+1 ) signals. In the depicted embodiment, the 4-bit Ling circuits are implemented with domino gates to generate the Ling carry (PG) terms and provide them to the sparse carry tree  204 . In some embodiments, they are pre-charged High and have a worst-case 2-NMOS pull-up evaluation path. 
         [0012]    The generated Ling PG carry terms are then merged using a sparse carry merge scheme to generate intermediate carry terms. In the depicted embodiment, the sparse carry tree  204  comprises five intermediate carry-merge levels (CM 1  to CM 5 ) comprising carry merge gates  306 A-G to  314 A-G, disposed as indicated the arrows generally depict P and G term connections between the CM gates. The gates are configured to generate carry bits for every 8 th  bit (C 7 , C 15  . . . C 55 ) of the 64 bit operands. 
         [0013]    The depicted sparse carry tree  204  uses both domino and static gates to achieve good performance and reduced power consumption. Especially in critical paths, CM gates with no more than 2-high transistor stacks are used. As indicated in the figure, with this architecture, the critical path can be made to have a delay length of only 16 RC bits. Moreover, with this architecture, a reduction in wiring complexity can occur, which permits the use of wider/shielded wires on the few performance-critical inter-stage ‘group generate/propagate’ signals. 
         [0014]    In some embodiments, CM levels CM 1 , CM 3 , and CM 5  comprise domino circuits with 2-high dynamic (e.g., footless) NMOS-stacks (represented as 2N), while levels CM 2  and CM 4  incorporate static gates having 2-high PMOS stacks (represented as 2P). With this configuration, the carry-merge tree has a worst-case evaluation path of 2N-2P-2N-2P-2N in order to generate the carry signals. 
         [0015]    (The term “PMOS transistor” refers to a P-type metal oxide semiconductor field effect transistor. Likewise, “NMOS transistor” refers to an N-type metal oxide semiconductor field effect transistor. It should be appreciated that whenever the terms: “transistor”, “MOS transistor”, “NMOS transistor”, or “PMOS transistor” are used, unless otherwise expressly indicated or dictated by the nature of their use, they are being used in an exemplary manner. They encompass the different varieties of MOS devices including devices with different VTs and oxide thicknesses to mention just a few. Moreover, unless specifically referred to as MOS or the like, the term transistor can include other suitable transistor types, e.g., junction-field-effect transistors, bipolar-junction transistors, and various types of three dimensional transistors, known today or not yet developed.) 
         [0016]    The carry bits from the sparse carry tree  204  are provided to sum generation circuits  316 , which are also coupled to the input operands (A, B), to generate their sum. In some embodiments, conditional sum generation circuits are used. In this embodiment, each 8-bit sum generator is a conditional sum generator that generates conditional sums for its input carry bit being both 0 and 1 while the sparse tree circuitry calculates the carry values for every eighth bit. With this scheme, the non-criticality of the sum-generator permits the usage, for example, of a ripple carry-merge scheme to generate the conditional carries. 
         [0017]    In some embodiments, the 8-bit operand sections and associated conditional carries are XORed together to generate conditional sums in 8-bit sections. Once arriving from the sparse tree circuitry  204 , the carry bits (C 7 , C 15 , . . . C 55 ) then select the appropriate 8-bit conditional sums, e.g., using a 2:1 multiplexer to deliver the final 64-bit sum. In this way, logic traditionally implemented in complex main carry-tree, for example, using expensive parallel prefix logic can instead be implemented in the sparse-tree design using an energy-efficient architecture. Such an approach can result in smaller area, reduced energy consumption and lower leakage. 
         [0018]    With reference to  FIG. 4 , one example of a computer system is shown. The depicted system generally comprises a processor  402  that is coupled to a power supply  404 , a wireless interface  406 , and memory  408 . It is coupled to the power supply  404  (e.g., battery and/or AC adapted supply) to receive from it power when in operation. The wireless interface  406  is coupled to an antenna  410  to communicatively link the processor through the wireless interface chip  406  to a wireless network (not shown). Microprocessor  402  also comprises one or more ALUs  403  with one or more adder circuits configured in accordance with adder circuits disclosed herein. 
         [0019]    It should be noted that the depicted system could be implemented in different forms. That is, it could be implemented in a single chip module, a circuit board, or a chassis having multiple circuit boards. Similarly, it could constitute one or more complete computers or alternatively, it could constitute a component useful within a computing system. 
         [0020]    The invention is not limited to the embodiments described, but can be practiced with modification and alteration within the spirit and scope of the appended claims. For example, it should be appreciated that the present invention is applicable for use with all types of semiconductor integrated circuit (“IC”) chips. Examples of these IC chips include but are not limited to processors, controllers, chip set components, programmable logic arrays (PLA), memory chips, network chips, and the like. 
         [0021]    Moreover, it should be appreciated that example sizes/models/values/ranges may have been given, although the present invention is not limited to the same. As manufacturing techniques (e.g., photolithography) mature over time, it is expected that devices of smaller size could be manufactured. In addition, well known power/ground connections to IC chips and other components may or may not be shown within the FIGS. for simplicity of illustration and discussion, and so as not to obscure the invention. Further, arrangements may be shown in block diagram form in order to avoid obscuring the invention, and also in view of the fact that specifics with respect to implementation of such block diagram arrangements are highly dependent upon the platform within which the present invention is to be implemented, i.e., such specifics should be well within purview of one skilled in the art. Where specific details (e.g., circuits) are set forth in order to describe example embodiments of the invention, it should be apparent to one skilled in the art that the invention can be practiced without, or with variation of, these specific details. The description is thus to be regarded as illustrative instead of limiting.