Patent Publication Number: US-5426743-A

Title: 3-1 Arithmetic logic unit for simultaneous execution of an independent or dependent add/logic instruction pair

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is a continuation of application Ser. No. 07/906,631, filed Jun. 30, 1992, now abandoned, which claims priority and is a continuation in part of the following application: 
     U.S. patent application Ser. No. 07/677,079 filed Mar. 29, 1991, now issued U.S. Pat. No. 5,299,319, by S. Vassiliadis et al, entitled &#34;High Performance Interlock Collapsing SCISM ALU Apparatus&#34;. 
     The prior application also claims priority of the following co-pending U.S. Patent applications: 
     (1) Application Ser. No. 07/519,384 (IBM Docket EN9-90-020), filed May 4, 1990, entitled &#34;Scalable Compound Instruction Set Machine Architecture&#34;, the inventors being Stamatis Vassiliadis et al; 
     (2) Application Ser. No. 07/519,382 (IBM Docket EN9-90-019), filed May 4, 1990, entitled &#34;General Purpose Compound Apparatus For Instruction-Level Parallel Processors&#34;, the inventors being Richard J. Eickemeyer et al; 
     (3) Application Ser. No. 07/504,910 (IBM Docket EN9-90-014), filed Apr. 4, 1990, now issued U.S. Pat. No. 5,051,940, entitled &#34;Data Dependency Collapsing Hardware Apparatus&#34;, the inventors being Stamatis Vassiliadis et al; 
     (4) Application Ser. No. 07/522,291 (IBM Docket EN9-90-012), filed May 10, 1990, now issued U.S. Pat. No. 5,214,763 entitled &#34;Compounding Preprocessor For Cache&#34;, the inventors being Bartholomew Blaner et al; and 
     (5) Application Ser. No. 07/543,464 (IBM Docket EN9-90-018, filed Jun. 26, 1990, entitled &#34;An In-Memory Preprocessor for a Scalable Compound Instruction Set Machine Processor&#34;, the inventors being Richard Eickemeyer et al. 
     (6) Application Ser. No. 07/543,458, (IBM Docket EN9-90-042) filed Jun. 26, 1990, now issued U.S. Pat. No. 5,197,135 entitled &#34;Memory Management for Scalable Compound Instruction Set Machines&#34; with 
     (7) Application Ser. No. 07/619,868 (IBM Docket EN9-90-033) filed Nov. 28, 1990, now issued U.S. Pat. No. 5,301,341, entitled &#34;Overflow Determination for Three-Operand ALUS in a Scalable Compound Instruction Set Machine&#34;, the inventors being Stamatis Vassiliadis et al; and 
     (8) Application Ser. No. 07/642,011 (IBM Docket EN9-90-049) filed Jan. 15, 1991, now issued U.S. Pat. No. 5,295,249, entitled &#34;Compounding Preprocessor for Cache&#34;, the inventors being Bartholomew Blaner et al. 
     (9) Application Ser. No. 677,066, (IBM Docket EN9-90-039, filed Mar. 29, 1991, entitled &#34;System for Compounding Instructions for an Instruction Processor with Different Attributes with Apparatus for Handling Test and Data with Differing Reference Point Information and Backward Compounding Apparatus for Compound Instructions&#34;, the inventors being Eickemeyer et al; and 
     (10) Application Ser. No. 677,685, (IBM Docket EN9-90-040, filed Mar. 29, 1991, now issued U.S. Pat. No. 5,303,356, entitled &#34;System for Preparing Instructions for Instruction Processor and System with Mechanism for Branching in the Middle of a Compound Instruction&#34;, the inventors being S. Vassiliadis et al. 
     These other co-pending applications are not specific to the present invention. 
     This application and the related applications are assigned to International Business Machines Corporation, Armonk, N.Y. The related applications are incorporated by reference. 
    
    
     FIELD OF THE INVENTION 
     This invention relates to the field of computing apparatus and Arithmetic Logic Units (ALUs), and particularly to an interlock collapsing apparatus ALU. 
     BACKGROUND OF THE INVENTION 
     The need to handle interlocks is common in computing apparatus. There are other solutions. However, as architectures progress the different problems invariably arise. A barrier which arose to achieving super scalar performance with RISC processors, such as those developed originally for the IBM RISC/System 6000 (tm) is that interlocks are serialized so that the traditional super-scalar hardware is underutilized. There is a need to increase utilization of the hardware for a system, especially in the superscalar area where a machine attempts to issue more than one instruction in a given machine cycle or the machine attempts to execute interlocked instructions in a single cycle. The present description of a 3-1 computing apparatus has provided the answer. 
     SUMMARY OF THE INVENTION 
     Our architecture which defines instructions that have an &#34;add/logical combinatorial operation&#34; which means combining all four of the following combinations: add-add; add-logical; logical-add; and logical-logical functions, and to an architecture in which two or more disassociated ALU operations are specified by a single interlock collapsing ALUs which responds to the parallel issuance of a plurality of separate instructions (including RISC type instructions), each of which specifies ALU operations, and executes the instructions in parallel in a single machine cycle making the ALU useful in CISC, superscalar, superscalar RISC, etc. type computer designs. 
     In accordance with our invention we have designed a three-to-one ALU which provides a way to execute plural instructions in a given machine cycle and which can execute interlocked instructions in a single cycle. The computing apparatus, the 3-1 ALU has the ability to execute with a 3-1 two&#39;s complement and unsigned number notation a pair of interlocked instructions. The 3-1 ALU has a 3-2 carry save adder (CSA); and a 2-1 control arithmetic logic unit (CALU) coupled for an input from the carry save adder; and a first pre-adder logic block coupled with an output to the control arithmentic logic unit; and a control generator; and a second controlled logic block coupled to receive an input from said control generator and having its output coupled to said control arithmetic logic unit. 
     In the 3-1 ALU we have provided that the output of the pre-adder logical block is combined with a sum from the CSA and a CSA sum control. The control generator has control inputs which it combines with a third operand; and the second controlled logic block combines a half-sum and modified half-sum from the CALU with the output of the control generator to produce controls for the CALU for incorporating post-adder logical functions into the CALU. 
     We also provide bitwise AND, OR, XOR, NOR, NAND, or XNOR functions into the CALU for executing the catogories: 
     Category 2: B+(A LOP Γ) Logical followed by Arithmetic; and 
     Category 3: B LOP (A+Γ) Arithmetic followed by Logical; and 
     Category 4: B LOP (A LOP Γ) Logical followed by Logical. 
     This ALU, when used in conjunction with a regular two-to-one ALU as expected and done in our preferred embodiment allows simultaneous execution of any combination of two independent or dependent arithmetic or logical instruction types. Because the three-to-one ALU has been designed to be fast (considerable faster than two ALUs connected in series) it allows the execution of the two arithmetic or logical instruction types identified above to be executed in one machine cycle without increasing the cycle time. The concept is particularly useful for superscalar, superscalar RISC, and other machines attempting to issue more than one instruction in a given machine cycle or machines that attempt to execute interlocked instructions in a single cycle. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates a our preferred embodiment. This is the logical dataflow for our interlock collapsing 3-1 execution ALU. 
     FIG. 2 shows our preferred ALU in combination with a regular two-to-one ALU. This combination uses the ALU for simultaneous execution of two arithmetic or logical instructions. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In FIG. 1 is shown a high level description of the 3-1 Arithmetic Logic Unit (ALU). All operands to the ALU are fed to a Carry Save Adder (CSA) where, for add type operations, the three operands are reduced to a sum and a carry to be fed to the subsequent Control Arithmetic Logic Unit (CALU) in which a special addition can be performed. In addition, the left and right operands are fed to a first logic block or logic unit, L1, where logical operations are performed when collapsing a dependency between a logic instruction followed by an arithmetic. This logic block handles add functions followed by a logic function, as well as a logic function followed by a logic function. The middle operand is fed to a control generator, along with the ALU control inputs that specify the operation of the CALU, where controls for the CALU are generated. The CALU responds to these controls in such a manner to allow the fast generation of the bitwise logic operations between the middle input and the sum that would result from a regular two-to-one addition. To allow the CALU to perform its operation, a second controlled logic block L2 receives signals H and M from the CALU and produces signals θ and m to allow the generation of these bitwise logic operations between the middle input and the sum from a two-to-one addition. Controlled logic block L2 handles a logic function followed by a add, as well as a logic function followed by a logic function. 
     FIG. 2 demonstrates the use of the 3-1 ALU along with a standard 2-1 ALU to support the simultaneous execution of any combination of two dependent or independent arithmetic or logical type instructions. The 2-1 ALU executes the first of the two issued instructions while the 3-1 ALU executes the second dependent or independent instruction. 
     FIG. 1 shows an overview of the three-to-one ALU being disclosed. Such an ALU designed in compliance with the ESA/370 instruction set is described by the following equations: 
     
         Λ.sub.i =μ.sub.i φ.sub.i+1 +θ.sub.i φ.sub.i+1 +Ξ.sub.SOMi. 
    
     
         θ.sub.i =H.sub.i Ξ.sub.GENi +H.sub.i Ξ.sub.SXMi. 
    
     
         μ.sub.i =M.sub.i Ξ.sub.GENi +M.sub.i Ξ.sub.SXMi 
    
     
         G.sub.i+1.sup.n =G.sub.i+1.sup.n +Ξ.sub.SOMi, 
    
     
         L.sub.i =α.sub.i Ω.sub.OALASL +γ.sub.i Ω.sub.OALASL +α.sub.i γ.sub.i Ω.sub.XOSL +α.sub.i γ.sub.i Ω.sub.XAAL. 
    
     
         Ξ.sub.GENi =Ξ.sub.ADD +Ξ.sub.OR +β.sub.i Ξ.sub.AND +β.sub.i Ξ.sub.XOR 
    
     
         Ξ.sub.SXMi =β.sub.i Ξ.sub.XOR +β.sub.i Ξ.sub.NOR 
    
     
         Ξ.sub.SOMi =β.sub.i Ξ.sub.OR 
    
     
         σ.sub.i =α.sub.i  β.sub.i  γ.sub.i 
    
     
         λ.sub.i =Ω.sub.1 α.sub.i β.sub.i +Ω.sub.2 α.sub.i γ.sub.i +Ω.sub.1 β.sub.i γ.sub.i +Ω.sub.3 β.sub.i-1 
    
     
         H.sub.i =(Ω.sub.4 σ.sub.i +L.sub.i) λ.sub.i+1 
    
     
         G.sub.i =(Ω.sub.4 σ.sub.i +L.sub.i)λ.sub.i+1 
    
     
         T.sub.i =Ω.sub.4 σ.sub.i +L.sub.i +λ.sub.i+1 
    
     where Ω 1 , Ω 2 , Ω 3 , Ω 4 , Ω OALASL , Ω XAAL , Ω XOSL , Ξ ADD , Ξ OR , Ξ NOR , and Ξ XOR  are control signals, φ i , M i , G i   n , and T i   n  are parameters for recursive CLA equations as defined in &#34;Recursive Equations for Hardwired Binary Adders&#34;, Int. J. Electronics, Vol 67, No. 2, pp201-213, and α i , β i , and γ i  are inputs to the ICALU. 
     In the following, it is shown that the above equations describing the ALU perform the functions required for collapsing interlocks for the ALU instructions contained in a RISC instruction sets. For ease of discussion, the MIPs instruction set has been chosen as an example of such an instruction set and is used in the following discussion. The MIPS ALU instructions can be divided into the following six categories: 
     signed arithmetic operations ADDI, ADD, SUB 
     unsigned arithmetic operations ADDIU, ADDU, SUBU 
     signed arithmetic compare SLTI, SLT 
     unsigned arithmetic compare SLTIU, SLTU 
     logical operations NR, OR, XR, NOR 
     load register LR 
     These six instruction categories can be abstracted to two categories: arithmetics and logicals in which arithmetic covers signed arithmetic operations, unsigned arithmetic operations, signed arithmetic compare, unsigned arithmetic compare, and load register while logicals covers logical operations. With this abstraction, consideration of the combinations of the instruction categories indicates that the majority of interlocks can be collapsed by supporting the execution of the following categories of ALU operations in the three-to-one ALU: 
     Category 1: α+β+γ Arithmetic followed by Arithmetic 
     Category 2: β+(α LOP γ) Logical followed by Arithmetic 
     Category 3: β LOP (α+γ) Arithmetic followed by Logical 
     Category 4: β LOP (α LOP γ) Logical followed by Logical. 
     in which α, β, and γ represent the three operands upon which the ALU is to operate, +represents binary addition (and covers signed or unsigned addition, subtraction or comparison since subtraction can be obtained by adding the ones complement of the subtrahend to the minuend and supplying a `hot one` to the adder), and LOP represents one of the bitwise logical operations of OR, AND, EXCLUSIVE-OR, or NOR. 
     First consider the ALU description in light of execution of the first category of ALU operations. For this category, controls are supplied to the ALU as: 
     
         Ω.sub.1 =Ω.sub.2 =Ω.sub.4 =1 
    
     
         Ω.sub.3 =0 
    
     
         Ξ.sub.ADD =1 
    
     
         Ξ.sub.OR =Ξ.sub.AND =Ξ.sub.XOR =Ξ.sub.NOR =0 
    
     
         Ω.sub.OALASL =Ω.sub.XOSL =Ω.sub.XAAL =0 
    
     from which it follows from the above equations that: 
     
         Ξ.sub.GENi =1 
    
     
         Ξ.sub.SXMi =Ξ.sub.SOMi =0 
    
     
         L.sub.i =0 
    
     
         σ.sub.i =α.sub.i  β.sub.i  γ.sub.i 
    
     
         λ.sub.i =α.sub.i β.sub.i +α.sub.i γ.sub.i +β.sub.i γ.sub.i 
    
     
         H.sub.i =σ.sub.i  λ.sub.i+1 
    
     
         G.sub.i =σ.sub.i λ.sub.i+1 
    
     
         T.sub.i =σ.sub.i +λ.sub.i+1 
    
     
         μ.sub.i =M.sub.i (1)+M.sub.i (0)=M.sub.i 
    
     
         θ.sub.i =H.sub.i (1)+H.sub.i (0)=H.sub.i 
    
     
         G.sub.i+1.sup.n =G.sub.i+1.sup.n 
    
     
         Λ.sub.i =M.sub.i φ.sub.i+1 +H.sub.i φ.sub.i+1 +0=M.sub.i φ.sub.i+1 +H.sub.i φ.sub.i+1 
    
     But since σ i  and λ i  represent the sum and carry from a three-to-two CSA, and since φ i  represents the new carry of a two-to-one CLA whose inputs are the sum from the three-to-two CSA added to the carry from the CSA shifted left one bit position, then, making use of the recursive equations for binary adders taught by Vassiliadis, Λ i  becomes the sum, α i  +β i  +γ i  as desired. 
     Next consider the execution of the second category of ALU operations. For this category Ω OALASL , Ω XOAL , and Ω XAAL  are asserted along with the appropriate polarity of the operands to produce the one of the logic functions AND, OR, XOR, NAND, NOR, XNOR between the left and right inputs, α i  and γ i . In addition, the remaining controls are asserted as: 
     
         Ω.sub.1 =Ω.sub.2 =Ω.sub.4 =0 
    
     
         Ω.sub.3 =1 
    
     
         Ξ.sub.ADD =1 
    
     
         Ξ.sub.OR =Ξ.sub.AND =Ξ.sub.XOR =Ξ.sub.NOR =0 
    
     from which it follows from the above equations that: 
     
         Ξ.sub.GENi =1 
    
     
         Ξ.sub.SXMi =Ξ.sub.SOMi =0 
    
     
         L.sub.i =[AND,OR,XOR,NAND,NOR,XNOR] 
    
     
         σ.sub.i =α.sub.i  β.sub.i  γ.sub.i 
    
     
         λ.sub.i =β.sub.i-1 
    
     
         H.sub.i =L.sub.i  λ.sub.i+1 =L.sub.i  β.sub.i 
    
     
         G.sub.i =L.sub.i λ.sub.i+1 =L.sub.i β.sub.i 
    
     
         T.sub.i =L.sub.i +λ.sub.i+1 =L.sub.i +β.sub.i 
    
     
         μ.sub.i =M.sub.i (1)+M.sub.i (0)=M.sub.i 
    
     
         θ.sub.i =H.sub.i (1)+H.sub.i (0)=H.sub.i 
    
     
         G.sub.i+1.sup.n =G.sub.i+1.sup.n 
    
     
         Λ.sub.i =M.sub.i φ.sub.i+1 +H.sub.i φ.sub.i+1 +0=M.sub.i φ.sub.i+1 +H.sub.i φ.sub.i+1 
    
     But since L i , which is (α i  LOPγ i ), and γ i , which is β i-1 , are fed to the two-to-one adder with λ i  shifted left one bit position, a new carry is generated which complies with the new carry for adding β i  +(α i  LOPγ i ). From the recursive equations for binary adders of Vassiliadis, Λ i  is taught to produce the required sum: β i  +(α i  LOPγ i ). 
     Thirdly, consider the execution of the third category of ALU operations. For this category Ω QALASL  is asserted as a logic zero, while Ω XOSL  and Ω XAAL  are both asserted as logic one. The polarity of the third input, Γ, is either positive or negative, respectively, for addition or subtraction between A and Γ. The controls for the CALU indicate one of the bitwise logical functions to be executed by the CALU. In the following example, the EXCLUSIVE-OR function is assumed; therefore, the example demonstrates the operation: B (A+Γ). To execute this function, the remaining controls are asserted as: 
     
         Ω.sub.1 =Ω.sub.3 =Ω.sub.4 =0 
    
     
         Ω.sub.2 =1 
    
     
         Ξ.sub.XOR =1 
    
     
         Ξ.sub.ADD =Ξ.sub.OR =Ξ.sub.AND =Ξ.sub.NOR =0 
    
     From the above setting of the controls along with the expressions specifying the operation of the three-to-one ALU, the results are produced by: 
     
         Ξ.sub.GENi =β.sub.i 
    
     
         Ξ.sub.SXMi =β.sub.i 
    
     
         Ξ.sub.SOMi =0 
    
     
         L.sub.i =α.sub.i  γ.sub.i 
    
     
         σ.sub.i =α.sub.i  β.sub.i  γ.sub.i 
    
     
         λ.sub.i =α.sub.i γ.sub.i 
    
     
         H.sub.i =L.sub.i  λ.sub.i+1 
    
     
         G.sub.i =L.sub.i λ.sub.i+1 
    
     
         T.sub.i =L.sub.i +λ.sub.i+1 
    
     
         μ.sub.i =M.sub.i β.sub.i +M.sub.i β.sub.i 
    
     
         θ.sub.i =H.sub.i β.sub.i +H.sub.i β.sub.i 
    
     
         G.sub.i+1.sup.n =G.sub.i+1.sup.n ##EQU1## 
    
     But since L i  and λ i  represent the sum and carry from a two-to-two addition between A and Γ, and since L i  and λ i  are fed to a two-to-one adder with λ i  shifted left one bit position, and finally since σ i , though fed to the two-to-one adder is deselected by Ω 4  =0, the recursive equations of Vassiliadis teach that M i  φ i+1  +H i  φ i+1  represents the sum, A+Γ. Letting S i  represent the sum A+Γ at bit position i, then: 
     
         S.sub.i =M.sub.i φ.sub.i+1 +H.sub.i φ.sub.i+1 
    
     Substituting S i  into the results from the three-to-one ALU gives: 
     
         Λ.sub.i =β.sub.i S.sub.i +β.sub.i S.sub.i =β.sub.i S.sub.i 
    
     Thus, the result is the bitwise logical EXCLUSIVE-OR between B and S. But S is the sum A+Γ; therefore, the result is: 
     
         Λ=B (A+Γ) 
    
     where in this later expression   represents the bitwise EXCLUSIVE-OR operation and + represents addition. 
     Finally, consider the last category of operations, category four. For this category, the three-to-one ALU is shown to produce the desired results for the bitwise logical operations AND followed by NOR. Thus, the result should be B+(AΓ). The controls to the ALU are: 
     
         Ω.sub.1 =Ω.sub.2 =Ω.sub.3 =Ω.sub.4 =0 
    
     
         Ω.sub.XAAL =1 
    
     
         Ω.sub.OALASL =Ω.sub.XOSL =0 
    
     
         Ξ.sub.NOR =1 
    
     
         Ξ.sub.ADD =Ξ.sub.OR =Ξ.sub.AND =Ξ.sub.XOR =0 
    
     from which the results are produced by: 
     
         Ξ.sub.GENi =0 
    
     
         Ξ.sub.SXMi =β.sub.i 
    
     
         Ξ.sub.SOMi =0 
    
     
         L.sub.i =α.sub.i 0+γ.sub.i 0+α.sub.i γ.sub.i 0+α.sub.i γ.sub.i 1=α.sub.i γ.sub.i 
    
     
         σ.sub.i =α.sub.i  β.sub.i  γ.sub.i 
    
     
         λ.sub.i =0 
    
     
         H.sub.i =(0σ.sub.i +L.sub.i) 0=L.sub.i 
    
     
         G.sub.i =(0σ.sub.i +L.sub.i)0=0 
    
     
         T.sub.i =0σ.sub.i +L.sub.i +0=L.sub.i 
    
     
         μ.sub.i =M.sub.i 0+M.sub.i β.sub.i =M.sub.i β.sub.i 
    
     
         θ.sub.i =H.sub.i 0+H.sub.i β.sub.i =H.sub.i β.sub.i 
    
     Because `hot ones` are not supplied to the three-to-one ALU for executing category four and since the pseudo-generate G i  is a logic zero at each bit position i, the new carry φ i+1  =0. Therefore, 
     
         Λ.sub.i =μ.sub.i 0+θ.sub.i 1+0=θ.sub.i 
    
     
         Λ.sub.i =H.sub.i β.sub.i 
    
     
         Λ.sub.i =L.sub.i β.sub.i 
    
     But L i  =α i  γ i  ; therefore, 
     
         Λ.sub.i =β.sub.i (α.sub.i γ.sub.i) 
    
     
         Λ.sub.i =β.sub.i +(α.sub.i γ.sub.i) 
    
     Also, for this category, the operands, B and A are fed to the ALU while the ones complement of the operand Γ is supplied to the ALU. Therefore, γ i  =Γ i . Substituting these into the last expression for the result produces: 
     
         Λ.sub.i =B.sub.i +(A.sub.i Γ.sub.i) 
    
     or 
     
         Λ=B+(AΓ) 
    
     where + represents the bitwise logical OR. Thus, the AND-NOR function is achieved as desired. 
     The computing apparatus with the 3-1 ALU which we have described in a preferred embodiment has been combined as shown in FIG. 2 with a conventional 2-1 ALU (ALU1) wherein both the 3-1 computing apparatus 3-1 ALU (ALU2) and the 2-1 ALU (ALU1) share a common general purpose register array (GPR Array) having five read ports, one independent port for each of the ALUs&#39; inputs, and two write ports, one for each of the ALUs&#39; results. Thus, the first of an instruction pair, specifying ALU operations, is executed by the 2-1 ALU with the second instruction executed in the identical machine cycle and in parallel with the first instruction, by the 3-1 ALU even when the instruction possess data dependency interlocks as shown in FIG. 2. 
     Such a combined computing apparatus can provide an architecture which executes instructions that have an &#34;add/logical combinatorial operation&#34; which means combining all four of the following combinations: add-add; add-logical; logical-add; and logical-logical functions, and wherein two or more disassociated ALU operations are specified by a single interlock collapsing ALU which responds to the parallel issuance of a plurality of separate instructions, including RISC type instructions, each of which specifies ALU operations, and the computing apparatus executes the instructions in parallel in a single machine cycle. With such a combined apparatus a computer system apparatus can execute combinations of two independent or dependent arithmetic or logical instruction types and the execution of the two arithmetic or logical instruction types in one machine cycle without increasing cycle time. 
     While we have described our preferred embodiments of our invention, it will be understood that those skilled in the art, both now and in the future, may make make various improvements and enhancements which fall within the scope of the claims which follow. These claims should be construed to maintain the proper protection for the invention first disclosed.