Abstract:
An arithmetic logic unit (ALU) cell, having a narrow pitch for straightforward cascading and integration with a memory array or similar device, also able to efficiently perform AND, NAND, OR, NOR, XOR, XNOR, INVERT, SET and CLEAR operations, and ripple carry addition. The ALU has particular utility in a multiport random access memory (RAM) based multiprocessor.

Description:
FIELD OF THE INVENTION 
     This invention generally relates to CMOS arithmetic logic unit (ALU) design, and more precisely relates to a narrow ALU cell that can be easily cascaded and connected in parallel to bit lines of an integrated memory array circuit, without expanding pitch of said array. 
     BACKGROUND OF THE INVENTION 
     A multiprocessor, disclosed in application &#34;Multiport RAM Based Multiprocessor,&#34; inventor Ward D. Parkinson et al, file date Mar. 9, 1989, here incorporated by reference, requires a narrow ALU cell for efficient integration. To make the multiprocessor as small as possible (which is highly desirable), each ALU cell can be no wider than one or two bit lines in the RAM array. 
     The present invention includes a narrow ALU cell design useful for the above application. 
     SUMMARY OF THE INVENTION 
     A preferred embodiment of the invention includes an ALU cell having a narrow pitch, so that a cascade of such ALU cells can be connected in parallel to bit lines of a memory array. The preferred embodiment performs AND, NAND, OR, NOR, XOR, XNOR, INVERT, SET, CLEAR, and ripple carry addition. Multiplication and other functions can be performed by sequentially stepping the ALU through one or more of its operations. 
     Because The preferred embodiment includes simple transistor circuitry, fast operation times are possible. 
     The inventive ALU cell has a small enough pitch such that a plurality of them can be cascaded and integrated with a memory array or similar device, making possible a memory based microprocessor, while retaining the small bit line pitch of said array. 
     Such an ALU cell allows on-chip processing, thus eliminating a data transfer bottleneck between memory and the ALU cell. 
     A plurality of primary logic operations are simultaneously generated, therefore having equal processing times. These primary operations are invertible, said inversion adding approximately one gate delay. These primary operations include operations required for ripple carry addition, so that a sum bit and a carry bit are generated nearly simultaneously, thus increasing ripple carry addition speed. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows simple implementations of AND and OR operation. 
     FIG. 2 shows AND, NAND, OR, NOR, XOR, and XNOR implementations. 
     FIG. 3 shows a schematic of a preferred embodiment of the invention. 
     FIG. 4 contains a table detailing ripple carry addition. 
     FIG. 5 shows a layout of the preferred embodiment. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     As shown in FIG. 1, logic operations AND and OR may be accomplished by simple circuits 11 and 12. Circuit 11 is a field effect transistor (FET) or equivalent device, with inputs X and Y, and output Z, the output Z and one of the inputs (here shown as X) each on an active electrode of the FET 11. If X, Y, and Z are limited to logic high or low levels (also called 1 and 0), it is evident that Z is high only when both X and Y are high. This is an AND operation. Circuit 12 is commonly referred to as a wire OR. If Z&#39;, Y&#39;, or both are active (said active state can be high or low), the Z&#39; is in an active state. A necessary wire OR condition is that if an input is not active, then it must be disconnected (high impedance), or very weakly biased. Unless otherwise noted, all arithmetic expressions herein represent Boolean logic. For example, &#34;+&#34; denotes an OR operation, not addition. 
     Following these concepts, AND, NAND, OR, NOR, XOR, and XNOR operations each can be implemented as shown in FIG. 2. Notice that each implementation includes two FETs of the same conductive type, input A controlling one, and input A* controlling the other, so that an output node is driven high or low by only one activated FET at a time, the other FET being deactivated (off). 
     Of these implementations, XOR, NAND, and NOR are used with advantage to create a narrow pitch ALU cell, shown in FIG. 3. Transistors Q1-Q20 and inverters A1-A3 are connected as shown. Q1-Q17 and Q19-Q20 are n-channel, and Q18 is p-channel. Nodes A, A*, B, B*, CIN, and CIN* are data inputs, &#34;*&#34; denoting inversion. Nodes ALL0S, ALL1s, XOR, NAND, NOR, SUM, INV1, INV2, and EN are control inputs. Only one node of nodes XOR, NAND, and NOR is held high at one time. Only one node of nodes SUM, INV1, and INV2 is held high at one time. Nodes ALUOUT and ALUOUT* are data outputs. EN high enables the ALUOUT* output. ALL0S and ALL1S are normally held low. 
     A layout corresponding to the preferred embodiment is shown in FIG. 5. 
     The preferred embodiment pitch is about twice the bit line pitch of a dynamic random access memory (DRAM) array. The preferred embodiment can be easily integrated with said array by alternating bit lines, odd bit lines connecting to ALU cells on one side of the array, and even bit lines connecting to ALU cells on an opposing side. It should be noted that other arrangements may be made with the equivalent effect, such as alternating every two bit lines instead of every one. If the array pitch is wide enough, such as with a static random access memory (SRAM) or other larger pitched array, cascaded ALU cells may be integrated along one side of the array. It should also be noted that an ALU cell or a cascade of ALU cells may be integrated with a device that is not a memory array. 
     A XOR B Is equivalent to (A)(B*)+(A*)(B). As shown in FIG. 3, Q1 embodies term (A)(B*), and Q2 embodies term (A*)(B). The terms are wired ORed at node 21. When node XOR is high, A XOR B (the value of node 21) passes through Q3 to node 20. Notice that by using A in one term and A* in the other, only one term drives wire OR 21 at a time, the non-driving term being hi-Z. This technique is used for all wire ORs in the preferred embodiment. 
     A NOR B is equivalent to (A)(A*)+(A*)(B*). Q4 embodies term (A)(A*), and Q5 embodies (A*)(B*). The terms are wire ORed at node 22. When node NOR is high, A NOR B (the value of node 22) passes through Q6 to node 20. 
     A NAND B is equivalent to (A)(B*)+(A*)(A*). Q7 embodies term (A)(B*), and Q8 embodies term (A*)(A*). The terms are wire ORed at node 23. When node NAND is high, A NAND B (the value of node 23) passes through Q9 to node 20. 
     Ripple carry addition in the preferred embodiment is now disclosed, looking first at carry-out generation, then at sum generation. As shown in the Table of FIG. 4, when a carry-in bit CIN is low, a carry-out bit COUT can be generated by operation A AND B. When CIN is high, COUT can be generated by operation A OR B. In the preferred embodiment, when input CIN is high, Q10 passes inverted carry-out bit A NOR B from node 22 to output COUT*. When input CIN is low, input CIN* is high, allowing Q11 to pass inverted carry-out bit A NAND B from node 23 to output COUT*. Inverter A1 with helper pullup Q18 generates COUT from COUT*. Q18 pulls up COUT* to a full rail level, so the carry bit voltage does not degenerate as it is rippled through cascaded ALU cells. Q18 also reduces power required by inverter A1. 
     Also as shown in the table of FIG. 4, a sum bit S can be generated by a parity function of the bits A, B, and CIN. This can be implanted with the function A XOR B XOR CIN. During an addition in the preferred embodiment, node XOR is held high, allowing Q3 to pass A XOR B from node 21 to node 20. Inverter A2 inverts A XOR B and places it on node 25. Q12 and Q13, controlled by CIN* and CIN respectively, then perform (A XOR B) XOR CIN, placing the result on node 24. When node SUM Is high, the value of node 24 (the sum of bits A, B, and CIN) is passed to node ALUOUT. 
     When no sum or inversion is desired, control signal INV12 is held high. This allows the signal on node 20 to pass directly to output ALUOUT. Inversion is accomplished by holding INV2 high instead of INV1. This allows the signal on node 25 (which is inverse to node 20) to pass to output ALUOUT. This inversion, when used with primary operations XOR, NAND, and NOR operations already described, allows generation of XNOR, AND, and OR operations. In each case, the final signal (whether from node 20 or node 25), is also presented to inverter A3, which generates output ALUOUT*. ALUOUT* is desirable when the ALU cell drives a device with differential inputs. Otherwise, ALUOUT*, A3, Q17 and EN may be be necessary. 
     The preferred embodiment can INVERT A in a plurality of ways. One way is to use the fact that if B* is high for A NOR B=(A)(A*)+(A*)(B*), then A NOR B=A*. In the preferred embodiment, B and B* are switchably connected to bit lines in a memory array, which are precharged high during an access cycle (B and B* both high being a null state). Because B* is precharged high, INVERT A can be performed by isolating precharged B and B* from the array (to preserve the precharge), and pulling node NOR high, allowing Q6 to pass inverted A to node 20. Pulling INV1 high then allows inverted A to pass to node ALUOUT through Q15. 
     A second way to perform INVERT A is to pull precharged node B* low by activating Q20 via node ALL1S, then pulling node XOR high. This essentially performs A XOR 1, which inverts A. Pulling INV1 high then allows inverted A to pass to node ALUOUT. 
     A third way to perform INVERT A is to pull precharged node B low by activating Q19 via node ALL0S, then pulling node XOR high. This essentially performs A XOR 0, which passes A through Q3 uninverted to node 20. Pulling node INV2 high then inverts A and places it on node ALUOUT. 
     The preferred embodiment also performs SET on B and B*. If B and B* are precharged high (null state), then activating node ALL1S pulls B* down through Q20, giving the result of B=1 and B*=0, setting B. CLEAR is performed by activating ALL0S on precharged B and B*, pulling B down through Q19, giving the result of B=0 and B*=1, thus clearing B. 
     Any logic operation such as AND, NAND, OR, NOR, XOR, and XNOR can be selected as a primary logic operation of the inventive ALU cell. XOR, NAND, and NOR were chosen as primary operation because NAND and NOR are useful for efficiently generating bit COUT*, and XOR is useful for directly generating a sum bit on node 24. AND, OR, and XNOR can then be generated simply by inverting the chosen primary operations. 
     The reason for generating COUT* and then inverting COUT* to get COUT, rather than generating COUT and the inverting COUT to get COUT*, will now be disclosed. A carry-out bit such as COUT remains low, or has a low to high transition, then staying high. The output of an n-channel FET has a faster high to low transition than low to high. Therefore, for faster overall ripple carry (carry-out generation) using n-channel devices, COUT* (having a high to low transition, if any transition at all) is generated. During an addition, if the carry bit is unchanged, no transition time is necessary and there is no ripple carry delay. If the carry bit undergoes a transition, the circuit is configured to most quickly process the transition. Equivalently, for faster ripple carry using p-channel elements, COUT should be generated and then inverted to obtain COUT*, However, it is well known that n-channel technology is faster than, and therefore preferably to, p-channel technology. The preferred embodiment provides a ripple carry propagation time of one gate delay or less per ALU cell. 
     Although the preferred embodiment includes primary operations XOR, NAND, and NOR, more, fewer, or other operations or functions might also be selected. Simply a pass-through function might be implemented. It should also be understood that this invention can be embodied using p-channel FETs, in a similar fashion as with n-channel FETs. Conceivably, any type of switching device that is appropriate to the application at hand. Although the preferred embodiment uses CMOS technology, other technologies might be chosen. Any of these variations may be made while remaining within the scope of this invention.