Apparatus for branch prediction for computer instructions

Claim 1

In a computing system which executes a multipath sequence of instructions including a branching instruction by producing and manipulating signed, N-bit operands, and includes an arithmetic/logic unit for executing said branching instruction by subtraction of a compare operand, B, having a sign bit B(0), from the sum of a current value operand, Q, having a sign bit Q(0) and an operand, R, having a sign bit R(0), wherein the improvement to said computing system is for predicting the outcome of the execution of said branching instruction concurrently with said execution, the improvement comprising: first logic circuit means receiving said operands Q and R for determining a sign bit, A(0), of the SUM of said operand Q and said operand, R; means for providing said operand B in complement format; a carry-save-adder receiving said operands Q and R and the one's complement of said operand B, said carry-save-adder for providing two N-bit output signals, Px and Py, said carry-save-adder including logic gates for producing Px and Py by executing the formula Px(i)=Q(i) V R(i) V B(i)' and the formula, Py(i)=(Q(i).R(i))|(Q(i).B(i)')|(R(i).B(i)') where Q(i) is the ith bit of operand Q, R(i) is the ith bit of operand R, B(i)' is the ith bit of the one's complement of operand B, Px(i) is the ith bit of said output signal Px, Py(i) is the ith bit of said output signal Py and i is an integer, and 0≦i≦N-1; second logic circuit means connected to said carry-save-adder and responsive to Px and Py for determining the sign bit SUM 0 , resulting from the subtraction of said operand B from the SUM of said operands Q and R; third logic circuit means connected to said carry-save-adder for determining when the SUM of operands Q and R is equal to operand B, said third logic circuit means including logic gates for executing the equation ##EQU12## where E is a logical one when said SUM is equal to operand B, N is an integer equal to the numb of bits in Px and Py, and 0 is the most significant bit of Px and Py; and branch block circuit means connected to said first, second, and third logic circuit means for determining if said third binary word subtracted from the SUM of said first and second binary words is less than or equal to zero, said means including logic gates for executing the formula: ##EQU13## where (A≦B) is a logical one when said third binary word being subtracted from the SUM of said first and second binary words is less than or equal to zero. A(0)' is the inverse of A(0), and B(0)' is the inverse of B(0).

Claim 7

An apparatus for predicting the outcome of an executing branching instruction process in which N-bit operands Q, R, and B, having sign bits Q(0), R(0), and B(0), respectively, are combined according to the relationship: A-B, where A=(Q+R); and, wherein a first program branch condition signal, BCI, occurs when (A-B)>0, and a second program branch condition signal, BC2, occurs when (A-B)≦0, said apparatus comprising: carry-save circuit means for generating signals Px(i) and Py(i) by logically combining respective bits of operands Q, R, and B, according to: Px(i)=Q(i) V R(i) V B(i),'and Py(i)=(Q(i).R(i))|(Q(i).B(i)')|(R(i).B(i)'); second circuit means connected to said carry-save circuit means for logically combining said signals Px(i) and Py(i) to produce a signal, SUM 0 , indicating the sign of A-B; third circuit means responsive to operands Q and R for logically combining respective bits of operands Q and R to produce a signal, AO, indicating the sign of A; fourth circuit means connected to said carry-save circuit means for logically combining said signals Px(i) and Py(i) to produce a signal, E, indicating A=B; means in said third circuit means for providing the complement of A0, said complement signified by A0'; a first gate means connected to said second, third, and fourth circuit means for generating a first condition signal, BC1, indicating said first program branch condition, said first gate means generating BC1 according to: ##EQU15## a second gate means connected to said second, third, and fourth circuit means for generating a second condition signal, BC2, indicating said second program branch condition, said second gate means generating BC2 according to: BC2=[*AO'.BO'.SUM.sub.0)|(AO.BO.SUM.sub.0)|(AO.BO').vertline.E].

Claim 8

An apparatus for predicting the outcome of an executing branching instruction process in which N-bit operands Q, R, and B, having sign bits Q(0), R(0), and B(0), respectively, are combined according to the relationship: A-B, where A=(Q+R); and, wherein a first program branch condition signal, BCI, occurs when (A-B)>0, and a second program branch condition signal, BC2, occurs when (A-B)≦0, said apparatus comprising: carry-save circuit means for generating signals Px(i) and Py(i) by logically combining respective bits of operands Q, R, and B, according to: Px(i)=Q(i) V R(i) V B(i),'and Py(i)=(Q(i).R(i))|(Q(i).B(i)')|(R(i).B(i)'); second circuit means connected to said carry-save circuit means for logically combining said signals Px(i) and Py(i) to produce a signal, SUM 0 , indicating the sign of A-B; third circuit means responsive to operands Q and R for logically combining respective bits of operands Q and R to produce a signal, AO, indicating the sign of A; fourth circuit means connected to said carry-save circuit means for logically combining said signals Px(i) and Py(i) to produce a signal, E, indicating A=B; means in said third circuit means for providing the complement of A0, said complement signified by A0'; a first gate means connected to said second, third, and fourth circuit means for generating a first condition signal, BC1, indicating said first program branch condition, said first gate means generating BC1 according to: ##EQU15## a second gate means connected to said second, third, and fourth circuit means for generating a second condition signal, BC2, indicating said second program branch condition, said second gate means generating BC2 according to: BC2=[*AO'.BO'.SUM.sub.0)|(AO.BO.SUM.sub.0)|(AO.BO').vertline.E].