Data dependency collapsing hardware apparatus

Abstract

A multi-function ALU (arithmetic/logic unit) for use in digital data processing facilitates the execution of instructions in parallel, thereby enhancing processor performance. The proposed apparatus reduces the instruction execution latency that results from data dependency hazards in a pipelined machine. This latency reduction is accomplished by collapsing the interlocks due to these hazards. The proposed apparatus achieves performance improvement while maintaining compatibility with previous implementations designed using an identical architecture.

What is claimed is: 
     
       1. In a computer architected for serial execution of a sequence of single scalar instructions in a succession of execution cycles, an apparatus for supporting parallel execution of a plurality of scalar instructions in a single instruction cycle, the apptratus comprising: an instruction means for receiving a plurality of scalar instructions, a first of the scalar instructions producing a .Iadd.calculation .Iaddend.result used as an operand by a second of the scalar instructions;   an operand means for substantially simultaneously providing a plurality of operands, at least two of said operands being used by the first and second scalar instructions;   a control means connected to the instruction means for generating control signals to indicate operations which execute the plurality of scalar instructions; and   an execution means connected to the operand means and to the control means and responsive to the control signals and to a plurality of operands including the two operands for producing, in a single execution cycle, a single result corresponding to the performance of said operations on said plurality of operands.   
     
     
       2. The apparatus of claim 1, wherein the execution means includes an adder which produces a single adder result in response to three operands. 
     
     
       3. The apparatus of claim 2, wherein the adder includes a carry save adder which produces two outputs in response to the three operands and a carry look ahead adder, connected to the carry save adder, which produces one output in response to the two outputs of the carry save adder. 
     
     
       4. The apparatus of claim 2, wherein the execution means further includes logical means connected to the operand means and to the adder for performing a logic function on the operands to produce a logic result, the adder producing said single adder result in response to the logic result and one of the operands. 
     
     
       5. The apparatus of claim 2, wherein the execution means further includes logic means connected to the operand means and to the adder for performing a logic function on a first and second operand to produce a logic result, the execution means producing the single result in response to the logic result and the single adder result. 
     
     
       6. The apparatus of claim 1 wherein the first scalar instruction is a logical instruction and the second scalar instruction is an arithmetic instruction and the execution means includes logical means for combining first and second operands to produce a logical result required by said logical instruction and arithmetic means for combining the logical result with a third operand to produce said single result, said single result being required by the arithmetic instruction. 
     
     
       7. The apparatus of claim 1 wherein the first scalar instruction is an arithmetic instruction and the second scalar instructlon is a logical instruction and the execution means includes arithmetic means for combining first and second operands to produce an arithmetic result required by said arithmetic instruction and logical means for combining the arithmetic result with a third operand to produce said single result, said single result being required by the logical instruction. 
     
     
       8. The apparatus of claim 1, wherein the first scalar instruction is an arithmetic instruction and the second scalar instruction is an arithmetic instruction and the execution means includes arithmetic means for combining the three operands to produce a single arithmetic result, said single arithmetic result being provided as said single result. 
     
     
       9. The apparatus of claim 1 wherein the first scalar instruction is a logical restruction and the second scalar instruction is a logical instruction and the execution means includes logical means for combining first and second operands to produce a first logical result, said first logical result required by said first logical instruction, and second logical means for combining the first logical result with a third operarand to produce a second logical result, said second logical result being required by the second scalar instruction and said second logical result being provided as said single result. 
     
     
       10. A multifunction ALU (arithmetic logic unit) for combining three operands to produce a single result in response to a pair of instructions, including: a first set of logical elements for logically combining two operands to produce a first logical result;   an adder for arithmetically combining three operands to produce a single arithmetic result;   a circuit for inputting to the adder either all of said operands, two of said operands and a zero, one of said operands, a zero, and said first logical result, or two zeros and said first logical result;   a second set of logical elements for logically combining one of said operands with said single arithmetic result to produce a second logical result; and   a circuit for providing as an output either said arithmetic result or said second logical result.   
     
     
       11. The multifunction ALU of claim 10, wherein said adder includes: a carry-save adder for producing two outputs in response to three operands: and   a carry look ahead adder connected to said carry save adder for producing one output in response to said two outputs.   
     
     
       12. In a computer architected for serial execution of a sequence of scalar mstrucnons in a succession of execution periods, an interlock-collapsing apparatus for supporting simultaneous parallel execution of a plurality of scalar instructions, the apparatus comprising: an instruction register means for receiving a plurality of scalar instructions for simultaneous execution, a first instruction of the plurality of scalar instructions producing a result used as an operand by a second instruction of the plurality of scalar instructions;   an operand means for substantially simultaneously providing a plurality of operands used in execution the plurality of sclar instructions;   a control means connected to the instruction register means for generating control signals to indicate operands which execute the plurality of scalar instructions; and   an interlock-collapsing execution means connected to the operand means and to the control means .[.an.]. .Iadd.and .Iaddend.responsive to the control signals and to the plurality of operands for producing a single result corresponding to the simultaneous execution of .Iadd.said .Iaddend.first and second instructions in a single execution period.   
     
     
       13. The apparatus of claim 12, wherein the interlock-collapsing execution means includes and adder which produces a single adder result in response to three operands. 
     
     
       14. The apparatus of claim 13, wherein the adder includes a carry save adder which produces two outputs in response to the three operands and a carry lookahead adder connected to the carry save adder which produces one output in response to the two outputs of the carry save adder. 
     
     
       15. The apparatus of claim 13, wherein the interlock-collapsing execution means further includes logic means connected to the operand means and to the adder for performing a logic function on the operands to produce a logic result, the adder producing the single adder result in response to the logic result and one of the operands. 
     
     
       16. The apparatus of claim 13, wherein the interlock-collapsing execution means further includes logic means connected to the operand means and to the adder for performing a logic function on a first operand and a second operand to produce a logic result, the interlock-collapsing execution means producing the single result in response to the logic result and the single adder result. 
     
     
       17. The apparatus of claim 12, wherein the first instruction is a logical instruction and the second instruction is an arithmetic instruction and the interlock-collapsing execution means includes logical means for combining first and second operands to produce a logic result required by the logical instruction and arithmetic means for combining the logic result with a third operand to produce the single result, the single result representing exectution of the arithmetic instruction. 
     
     
       18. The apparatus of claim 12, wherein the first instruction is an arithmetic instruction and the second instruction is a logic instruction and the interlock-collapsing execution means includes arithmetic means for combining first and second operands to produce an arithmetic result required by said arithmetic instruction and logic means for combining the arithmetic result with a third operand to produce the single result, the single result representing execution of the logical instruction. 
     
     
       19. The apparatus of claim 12, wherein the first instruction is an arithmetic instruction and the second instruction is an arithmetic instruction and the interlock-collapsing execution means includes arithmetic means for combining three operands to produce a single arithmetic result, the three operands including two operands used in the execution of the first and second instructions. 
     
     
       20. The apparatus of claim 12, wherein the first instruction is a first logic instruction and the second instruction is a second logic instruction and the interlock-collapsing execution means includes logic means for combining first and second operands to produce a first logic result, the first logic result being required by the first logic instruction, and second logic means for combining the first logic result with a third operand to produce a second logic result, the second logic result representing execution of the second logic instruction and the second logic result being provided as the single result. 
     
     
       21. In a computer architected for serial execution of a sequence of scalar instructions in a succession of execution cycles, an execution apparatus for, in a single execution cycle, producing a result representing simultaneous execution of a first scalar instruction and a second scalar instruction in which the second scalar instruction requires a result produced by execution of the first scalar instruction, the execution apparatus comprising: an instruction register means for receiving the first and second scalar instructions;   an operand means for substantially simultaneously providing a plurality of operands, at least two of the plurality of operands being used in executing the first and second scalar instructions:   a control means connected to the instruction register means for generating control signals which indicate execution of the first scalar instruction and the second scalar instruction;   a first execution means connected to the operand means and to the control means and responsive to the control signals and to the two operands for producing, in an execution cycle, a result corresponding to the execution of the first instruction; and   a second execution means connected to the operand means and to the control means and responsive to the control signals and to a plurality of operands including the two operands for producing, in said execution cycle, a single result corresponding to the execution of the first and second instructions.   
     
     
       22. The apparatus of claim 21, wherein the first execution means includes an adder which produces a single adder result in response to two operands. 
     
     
       23. The apparatus of claim 21, wherein the second execution means includes an adder which produces a single adder result in response to three operands. 
     
     
       24. The apparatus of claim 23, wherein the adder includes a carry save adder which produces two outputs in response to the three operands and a carry lookahead adder connected to the carry save adder, which produces one output in response to the two outputs of the carry save adder. .Iadd. 
     
     
       25.  In a computer system, an apparatus for supporting parallel execution of a plurality of instructions in a single execution cycle, the apparatus comprising: an instruction means for receiving a plurality of instructions, a first of the instructions producing a calculation result used as an operand by a second of the instructions;   an operand means for substantially simultaneously providing a plurality of operands;   a control means connected to the instruction means for generating control signals to indicate operations which execute the plurality of instructions; and   an execution means connected to the operand means and to the control means and responsive to the control signals and to the plurality of operands for producing a single result corresponding to the performance of said operations, including execution of the first and second of the instructions, on said plurality of operands in a single execution cycle. .Iaddend..Iadd.26. The apparatus of claim 25, wherein the execution means includes an adder which produces a single adder result in response to three operands in the single execution cycle. .Iaddend..Iadd.27. The apparatus of claim 26, wherein the adder includes a carry save adder which produces two outputs in response to the three operands and a carry look ahead adder, connected to the carry save adder, which produces one output in response to the two outputs of the carry save adder. .Iaddend..Iadd.28. The apparatus of claim 26, wherein the execution means fuher includes logical means connected to the operand means and to the adder for performing a logic function on the operands to produce a logic result, the adder producing said single adder result in response to the logic result and one of the operands. .Iaddend..Iadd.29. The apparatus of claim 26, wherein the execution means further includes logic means connected to the operand means and to the adder for performing a logic function on a first and second operand to produce a logic result, the execution means producing the single result in response to the logic result and the single adder result. .Iaddend..Iadd.30. The apparatus of claim 25, wherein the first instruction is a logical instruction and the second instruction is an arithmetic instruction and the execution means includes logical means for combining first and second operands to produce a logical result required by said logical instruction and arithmetic means for combining the logical result with a third operand to produce said single result, said single result being required by the arithmetic instruction. .Iaddend..Iadd.31. The apparatus of claim 25 wherein the first instruction is an arithmetic instruction and the second instruction is a logical instruction and the execution means includes arithmetic means for combining first and second operands to produce an arithmetic result required by said arithmetic instruction and logical means for combining the arithmetic result with a third operand to produce said single result, said single result being required by the logical instruction. .Iaddend..Iadd.32. The apparatus of claim 25, wherein the first instruction is an arithmetic instruction and the second instruction is an arithmetic instruction and the execution means includes arithmetic means for combining the three operands to produce a single arithmetic result, said single arithmetic result being provided as said single result. .Iaddend..Iadd.33. The apparatus of claim 25, wherein the first instruction is a logical instruction and the second instruction is a logical instruction and the execution means includes logical means for combining first and second operands to produce a first logical result, said first logical result required by said first logical instruction, and second logical means for combining the first logical result with a third operand to produce a second logical result, said second logical result being required by the second instruction and said second ogical result being provided as said single result. .Iaddend..Iadd.34. In a computer system, an interlocking-collapsing apparatus for supporting simultaneous parallel execution of a plurality of instructions, the apparatus comprising:   an instruction register means for receiving a plurality of instructions for simultaneous execution, a first instruction of the plurality of instructions producing a result used as an operand by a second instruction of the plurality of instructions;   an operand means for substantially simultaneously providing a plurality of operands used in executing the plurality of instructions;   a control means coupled to the instruction register means for generating control signals to indicate operations which execute the plurality of instructions; and   an interlock-collapsing execution means coupled to the operand means and to the control means and responsive to the control signals and to the plurality of operands for producing a result corresponding to the simultaneous execution of first and second instructions in a single execution period. .Iaddend..Iadd.35. The apparatus of claim 34, wherein the interlock-collapsing execution means includes a carry save adder which produces two outputs in response to receiving three operands and a carry look ahead adder connected to the carry save adder which produces a single adder result in the execution period. .Iaddend..Iadd.36. The apparatus of claim 35 further including logic means connected to the operand means and to the interlock-collapsing execution means for performing a logic function on the operands to produce a logic result, the interlock-collapsing execution means including an adder which produces the single adder result in response to the logic result and one of the operands. .Iaddend..Iadd.37. The apparatus of claim 35 further including logic means connected to the operand means and to the interlock-collapsing execution means for performing a logic function on a first operand and a second operand to produce a logic result, the interlock-collapsing execution means producing the result in response to the logic result and the single adder result. .Iaddend..Iadd.38. The apparatus of claim 34, wherein the interlock-collapsing execution means includes a carry save adder which produces two outputs in response to receiving three operands and a carry look ahead adder connected to the carry save adder which produces one output in response to the two outputs of the carry save adder. .Iaddend..Iadd.39. The apparatus of claim 34, wherein the first instruction is a logical instruction and the second instruction is an arithmetic instruction and the interlock-collapsing execution means includes logic means for combining first and second operands to produce a logic result required by the logical instruction and arithmetic means for combining the logic result with a third operand to produce a single result, the single result representing execution of the arithmetic instruction. .Iaddend..Iadd.40. The apparatus of claim 34, wherein the first instruction is arithmetic instruction and the second instruction is a logic instruction and the interlock-collapsing execution means includes arithmetic means for combining first and second operands to produce an arithmetic result required by said arithmetic instruction and logic means for combining the arithmetic result with a third operand to produce a single result, the single result representing execution of the logical instruction. .Iaddend..Iadd.41. The apparatus of claim 34, wherein the first instruction is an arithmetic instruction and the second instruction is an arithmetic instruction and the interlock-collapsing execution means includes arithmetic means for combining three operands to produce a single arithmetic result, the three operands including two operands used in the execution of the first and second instructions. .Iaddend..Iadd.42. The apparatus of claim 34, wherein the first instruction is a first logic instruction and the second instruction is a second logic instruction and the interlock-collapsing execution means includes logic means for combining first and second operands to produce a first logic result, the first logic result being required by the first logic instruction, and second logic means for combining the first logic result with a third operand to produce a second logic result, the second logic result representing execution of the second logic instruction and the second logic result being provided as the single result. .Iaddend..Iadd.43. In a computer system, an execution apparatus for, in a single execution cycle, producing a result representing simultaneous execution of a first instruction and a second instruction in which the second instruction requires a result produced by execution of the first instruction, the execution apparatus comprising:   an instruction register means for receiving the first and second instruction;   an operand means for substantially simultaneously providing a plurality of operands, at least two of the plurality of operands being used in execution of the first and second instructions;   a control means connected to the instruction register means for generating control signals which indicate execution of the first instruction and the second instruction;   a first execution means connected to the operand means and to the control means and responsive to the control signals and to the two operands for producing, in an execution cycle, a result corresponding to the execution of the first instruction; and   a second execution means connected to the operand means and to the control means and responsive to the control signals and to a plurality of operands including the two operands for producing, in said execution cycle, a single result corresponding to the execution of the first and second instructions. .Iaddend..Iadd.44. The apparatus of claim 43, wherein the first execution means includes an adder which produces a single adder result in response to two operands. .Iaddend..Iadd.45. The apparatus of claim 43, wherein the second execution means includes an adder which produces a single adder result in response to three operands. .Iaddend..Iadd.46. The apparatus of claim 45, wherein the adder includes a carry save adder which produces two outputs in response to the three operands and a carry look ahead adder connected to the carry save adder, which produces one output in response to the two outputs of the carry save adder. .Iaddend.