Parallel processing method having arithmetical conditions code based instructions substituted for conventional branches

Abstract

A computer implemented method performed by a processor having multiple functional units avoids branches in decision support codes by doing arithmetic instructions incorporating condition codes generated by compare instructions. The method comprising the steps of analyzing operations in code to be performed by said processors to identify branch operations, substituting for identified branch operations arithmetic condition codes, decoding and dispatching multiple instructions in one processor cycle, and executing multiple functions in parallel per cycle using each of the functional units of said processor.

Claims

Having thus described my invention, what I claim as new and desire to secure by Letters Patent is as follows:

1. A computer implemented method performed by a processor having multiple functional units, comprising the steps of:

identifying at least one branch operation in a code to be performed by said processor, said branch operation having an IF(FUNCTION(OPERAND)) -THEN-OPERATION form;

substituting for said identified branch operation a plurality of arithmetic instructions, said plurality of arithmetic instructions substantially devoid of said IF(FUNCTION(OPERAND)) -THEN-OPERATION branch operation, said plurality comprising arithmetic instructions for calculating condition codes based on comparative values of said OPERANDS of said identified branch operation, and comprising arithmetic instructions incorporating said condition codes, said condition codes logically operating on other operands in said arithmetic instructions, wherein said plurality of instructions is substantially devoid of instructions calculating a difference in value between executing according to a first and a second branch of said branch operation to eliminate a conditional execution of said code and thereby enable a parallel execution of said substituted arithmetic instructions;

decoding said plurality of arithmetic instructions and dispatching decoded instructions representing said substitute code to said plurality of functional units for parallel processing; and

executing said plurality of dispatched decoded instructions in parallel using each of the functional units of said processor, thereby fully exploiting the multiple functional units of the processor through instruction level parallelism.

2. The computer implemented method recited in claim 1 wherein the step of executing said plurality of dispatched decoded instructions executes a logical operation of said condition codes and operands in said plurality of arithmetic instructions with a select function which, on the basis of said condition code, selects from two operands.

3. The computer implemented method recited in claim 2 wherein the select function comprises the steps of:

receiving first and second operands;

selecting one of said first and second operands depending on the generated condition code.

4. The computer implemented method recited in claim 3 wherein the step of selecting one of said first and second operands is performed by a conditional valued addition of two numbers representing said first and second operands having an output value further conditional on at least one of said condition codes.

5. The computer implemented method as recited in claim 1 wherein the code is a quick sort code.

6. The computer implemented method as recited in claim 1 wherein the code is a merge sort code.

7. The computer implemented method as recited in claim 1 wherein the code is a multi-way merge code.

8. A computer system which exploits arithmetic instructions with condition codes to eliminate dependencies in a code and thereby enable a parallel execution, comprising:

a processor having a plurality of functional units which can independently execute instructions in parallel;

mean for identifying at least one branch operations in a code to be performed by said processor said branch operation having an IF(FUNCTION(OPERAND)) -THEN-OPERATION form;

means for substituting for said identified branch operation a plurality of arithmetic instructions, said plurality substantially devoid of IF(FUNCTION(OPERAND)) -THEN-OPERATION branch operations and comprising arithmetic instructions for calculating condition codes based on comparative values of said OPERANDS and comprising arithmetic instructions incorporating said condition codes, said condition codes logically operating on other operands in said arithmetic instructions, wherein said plurality of instructions is substantially devoid of instructions calculating a difference in value between executing according to a first branch and a second branch of said branch operation to eliminate a conditional execution of said code and thereby enable a parallel execution of said substituted arithmetic instructions;

means for decoding said plurality of arithmetic instructions and dispatching decoded instructions representing said substitute code to said plurality of functional units in one processor cycle, wherein said plurality of functional units execute said dispatched instructions in parallel with one another, thereby fully exploiting the plurality of functional units of the processor through instruction level parallelism.

9. The computer system recited in claim 8 wherein the plurality of functional units includes a comparator means for calculating said conditional codes based on a first and a second operand and wherein at least one of the plurality of arithmetic instructions is implemented by a select means which, on the basis of the comparator result selects from a first and a second operand.

10. The computer system recited in claim 9 wherein the select function is performed by a multiplexer receiving the first and the second operand and at least one of said condition codes, said multiplexer selecting one of said first and second operands depending on said at least one condition code.

11. The computer system recited in claim 10 wherein the selection function is performed by a conditional output adder which adds two numbers representing said first and second operands and outputs a value further conditional on said at least one condition code.

12. The computer system recited in claim 11 wherein the conditional adder comprises:

a first AND gate receiving the first operand and enabled by a first condition code;

a second AND gate receiving the second operand and enabled by a second condition code; and

a full adder connected to outputs of said first and second AND gate and generating a sum output.

13. The computer system recited in claim 11 wherein the conditional output adder comprises:

a full adder receiving said first and second operands and generating a sum output; and

a multiplexer receiving as a first input said first operand and as a second input the sum output of said full adder and responsive to said condition code for selecting one of said first and second inputs.

14. The computer system recited in claim 8 wherein the code is quick sort code, said computer system further comprising:

an input array which receives an address and, in response, outputs a plurality of values equal in number to the number of functional units of said processor;

a plurality of output arrays for receiving results of a quick sort, wherein said plurality of functional units of said processor implement a corresponding plurality of comparators receiving a scale reference value and a corresponding one of the values output by the input array and generate a plurality of condition codes,

wherein said plurality of functional units perform arithmetic operations having outputs dependent on the condition codes, and

wherein results based on said functional units' outputs are output to to said plurality of output arrays.

15. The computer system recited in claim 8 wherein sorting code is a merge sort code, said computer system further comprising:

a plurality of input arrays which receive an address and, in response, output a plurality of values equal in number to the number of functional units of said processor;

an output array output arrays for receiving results of a quick sort,

wherein said plurality of functional units of said processor implement a corresponding plurality of comparators receiving a scale reference value and a corresponding one of the values output by the input array and generate a plurality of condition codes,

wherein said plurality of functional units perform arithmetic operations having outputs dependent on the condition codes, and

wherein results based on said functional units' outputs are output to said output array.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention generally relates to general purpose data processing methods and apparatus and, more particularly, to a technique for avoiding branches in decision support system (DSS) codes by doing arithmetic with condition codes thereby making possible parallel and pipeline processing afforded by multi functional unit processors, such as reduced instruction set computers (RISC) and very long instruction word (VLIW) processors.

2. Background Description

In commercial decision support systems (DSS), a large fraction of computational time is spent in sorting, hashing, searching, and scanning operations. These computational steps are generally implemented using compare and branch instructions. In these computations, the outcome of the comparison is used to branch to different segments of the code. In older computers, this was not a major performance concern, because each instruction was executed sequentially. Modern high performance computers are heavily pipelined. They can decode and dispatch multiple instructions in one cycle. They also contain multiple functional units working in parallel. In such a situation, the highest level of performance can be obtained only if the instructions to be executed are known several cycles in advance. On machines executing multiple instructions per cycle, this often translates into dozens of instructions. On these machines, compare and branch instruction sequences result in a control flow interruption and thus create a performance bottleneck. To achieve the highest level of performance, the code should not have any conditional branch instructions; in other words, it must be a "straight line" code. Additionally, it is important that multiple independent instruction streams be executed in parallel to fully utilize multiple functional units. Most engineering/scientific codes satisfy these requirements by unrolling the loop, so as to create multiple independent instruction streams. Unfortunately, such unrolling is usually not possible in commercial codes such as sorting/searching, because of the conditional branches. These codes have not been able to effectively utilize the multiple functional units present on modern high performance reduced instruction set computers (RISC), such as the PowerPC.RTM. microprocessor. This problem will get worse in the next generation of processors which are likely to be very long instruction word (VLIW) processors with a very large number of functional units.

SUMMARY OF THE INVENTION

It is therefore an object of the present invention to provide a method and a system to avoid most of the conditional branches in the above operations.

According to the invention, a computer implemented method performed by a processor having multiple functional units avoids branches in decision support codes by doing arithmetic instructions incorporating condition codes generated by compare instructions. The method comprising the steps of analyzing operations in code to be performed by said processors to identify branch operations, substituting for identified branch operations arithmetic condition codes, decoding and dispatching multiple instructions in one processor cycle, and executing multiple functions in parallel per cycle using each of the functional units of said processor.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which:

FIG. 1 is a block diagram of an illustrative processor on which the invention may be implemented;

FIG. 2 is a block diagram of the select function according to the invention;

FIGS. 3A and 3B are block diagrams of implementations of conditional arithmetic instructions according to the invention;

FIG. 4 is a block diagram of the quick sort function according to the invention;

FIG. 5 is a block diagram of the merge sort function according to the invention;

FIG. 6 is a schematic diagram illustrating an eight-way merge;

FIG. 7 is a schematic diagram illustrating the eight-way merge of FIG. 6 and showing the pointers associated with each data stream and all intermediate streams are of length one; and

FIG. 8 is a schematic diagram illustrating the eight-way merge of FIGS. 6 and 7 modified so that all intermediate streams are of length two to exploit the parallelism of the processor.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS OF THE INVENTION

Referring now to the drawings, and more particularly to FIG. 1, there is shown a representative hardware environment on which the subject invention may be implemented. This hardware environment may be a workstation such as IBM's RS/6000 Workstations as described, for example, by Jim Hoskins, IBM RISC System/6000, 5th Ed. John Wiley & Sons, Inc. (1995). The hardware includes a central processing unit (CPU) 10, which may be a RISC microprocessor such as IBM's PowerPC.TM. microprocessor as described in The PowerPC.TM. Architecture: A Specification for a New Family of RISC Processors, edited by Cathy May, Ed Silha, Rick Simpson and Hank Warren, Morgan Kaufmann Publishers (1994). In one example, the PowerPC.RTM. 601 architecture is used in the RISC System/6000 Model 250 workstation. The instruction and data caches are combined as a single cache 101. The branch processor 102 executes only branch instructions from cache 101. The CPU 10 additionally has a branch processor 102, and multiple functional arithmetic units. The multiple functional units include fixed-point processors or integer units (FXU) 103 and 103a and floating-point processors or units (FPU) 104 and 104a which execute instructions on data supplied by cache 101. The cache 101 communicates with the bus interface 105.

The CPU 10 is attached to a system bus 12 to which are attached a random access memory (RAM) 14, a read only memory (ROM) 16, an input/output (I/O) adapter 18, and a user interface adapter 22. The RAM 14 functions as main memory to the CPU 10 and provides temporary storage for application program code and data, while ROM 16 typically includes the basic input/output system (BIOS) code and may be implemented with flash, or electronically programmable, memory. The I/O adapter 18, such as a SCSI (for small computer system interface) adapter, is connected to one or more Direct Access Storage Devices (DASDs), here represented as a disk drive 20. The disk drive 20 typically stores the computer's operating system (OS), such as IBM's AIX.TM. operating system, and various application programs, each of which are selectively loaded into RAM 14 via the system bus 12. The user interface adapter 22 has attached to it a keyboard 24, a mouse 26, and/or other user interface devices such as a touch screen device (not shown). Such touch screen device would optionally be installed on the display 38, here represented as a cathode ray tube (CRT) display but which may be a liquid crystal display (LCD) or other suitable display device. The display 38 is connected to the system bus 12 via a display adapter 34.

The conditional operations are usually represented by "IF THEN ELSE" clause. Depending on the outcome of the condition, the code executes different operations. However, if the two different operations are reformulated to incorporate the outcome of the condition in such a way that they appear to be the same operation, then the conditional clause can be eliminated and unconditional operations (incorporating the outcome of the condition can be executed. As an example, consider the implementation of the max function. Let c=max(a,b). In Fortran, this is implemented as shown below.

If (a.ge.b) then

c=a

else

c=b

endif

If we were to define a select function, which on the basis of a condition code selects from two operands, then the code above can be implemented without any branches.

Select

The select function is defined as c=select(cc,a,b), where cc is a binary condition code. If cc=1, then c=a, else c=b. The implementation of the select function in hardware is straight forward as described in more detail below. Depending on the cc bit, the value of c is set to one or the other operand. In a RISC implementation, a, b and c denote registers and cc is a condition code bit. Alternatively, stored logical variables can also be used in lieu of the condition code bit. Most RISC machines provide for several condition code bits. Depending on the number of condition code bits available, an appropriate number of bits (in the instruction format) must be provided to specify the cc operand. Fortran (and other high level languages) provide logical variables which can be internally (in hardware) translated into condition code bits. Thus, the above function can be implemented as shown below.

cc=(a.ge.b)

. . .

. . .

c=select(cc,a,b)

Note that to avoid delay due to pipeline latency, it is preferable to set the condition code several cycles in advance. The select instruction is straightforward in hardware. It consists of a multiplexer (MUX) which chooses one of the two operands depending on the condition code bit (cc). The important thing about this implementation is that there are no branches. The hardware does not know which way the branch will take place. Branches also create a problem in unrolling the code. In the presence of branches, it is very difficult to unroll the code. However, if there are no branches, then the code can be unrolled by a large degree to avoid the pipeline delays and to fully utilize the multiple functional units. This is the main aim of the invention.

On some RISC machines, a "difference or zero" (DOZ) instruction is provided which can be used to implement the select operation. It is defined as doz(b,a)=(b-a) if a<b, else it is zero. With this definition, c=max(a,b) and d=min(a,b) can be calculated as follows:

t=doz(b,a)

c=a+t

d=b-t

The select instruction helps in eliminating the branches. However, this is not general enough to work in all situations. Now, the concept of evaluating expressions with condition code will be described. With this more powerful concept, a large number of computing kernels encountered in sorting and searching can be implemented. The select function is illustrated in FIG. 2 by a multiplexer having as inputs a and b which are arbitrary integers or floating point values. A one bit condition code, cc, selects one of the inputs, a or b, and provides an output c. For example, the output c=a if cc=1, but the output c=b if cc=0.

Conditional Arithmetic Instructions

As an example, consider conditional addition of two numbers a and b carried out under condition codes ca and cb.

c=csum(ca,a,cb,b)

c=ca.multidot.a+cb.multidot.b

In the above expression, if ca=1, then ca.multidot.a=a; otherwise, it is zero. A similar definition applies to cb.multidot.b. It is fairly easy to implement this instruction. It is very similar to an ordinary sum instruction except that the operands are gated by condition code bits. This additional gate delay should not have a significant impact on the processor cycle time. Similarly, other arithmetic instructions can be defined where operands are gated by condition codes. Sometimes, it is desirable to gate an operand on the inverse (negation or NOT) of a condition code. Thus, it is useful to associate one more bits with each condition code field in the conditional arithmetic instruction above. This bit or bits will decide if the condition code or its inverse is to be used for gating the operand. The select function defined above can be implemented using condition arithmetic as shown below.

c=select (cc,a,b)=csum(cc,a,cc,b)cc.multidot.a+cc.multidot.b

In the expression above, if cc=1, then c=a, else c=b. Thus, conditional arithmetic instructions are more general. However, their implementation requires more operand bits. It requires two condition code bit fields, and each condition code operand requires another bit to select the condition code or its inverse.

Conditional arithmetic instructions also can be defined where only one of the operands is gated by a condition code. For example, c=a+c.multidot.b. In this addition, the operand b is gated by the condition code cc.

FIGS. 3A and 3B illustrate implementations of arithmetic with condition codes. In FIG. 3A, ca and cb are one-bit condition codes, and a and b are either integers or floating point values. The output of AND gate 41 is ca.multidot.a, and the output of AND gate 42 is cb.multidot.b. These outputs are input to full adder 43 which generates the output c=ca.multidot.a+cb.multidot.b. The implementation in FIG. 3B uses a single one-bit condition code, cc. In this implementation, both a and b are input to full adder 44 which outputs a+b to one input of multiplexer 45. The other input to multiplexer 45 is a, and the condition code, cc, is used to select the output as c=a+cc.multidot.b.

Quick Sort

Quick sort is a very important sort kernel. In one step of quick sort, an array of size N is divided into two arrays such that all elements in one array are larger than all elements in the other array. This is done in place. By recursively iterating on the algorithm, in about log(N) steps, the entire array can be sorted. This is described on page 114 of The Art of Computer Programming, Vol. 3, Sorting and Searching, by D. E. Knuth, Addison-Wesley (1973). Consider one step of this algorithm where an array of size N is divided into two arrays. The following paragraph is reproduced from Knuth, supra:

"Consider therefore the following comparison/exchange scheme: Keep two pointers i and j, with i=1 and j=N initially. Compare K(i):K(j), and if no exchange is necessary decrease j by one and repeat the process. After an exchange first occurs, increase i by one, and continue comparing and increasing i until another exchange occurs. Then decrease j again, and so on, `burning the candle at both ends`, until i=j."

With some refinements, this can be coded in Fortran as shown below.

    ______________________________________
              i=1
              j=N
              kk=K(1)
              if(i.eq.j) goto 30
              kkk=K(j)
              if (kkk.ge.kk) then
                j=j-1
                goto 10
              endif
              K(i)=kkk
              i=i+1
              if (i.eq.j) goto 30
              kkk=K(i)
              if (kk.ge.kkk) then
                i=i+1
                goto 20
              endif
              K(j)=kkk
              j=j-1
              goto 10
              K(i)=kk
              return
    ______________________________________

    ______________________________________
              i=1
              j=N
              kk=K(1)
              ij=j
              do m=1,N-1
                kkk=K(ij)
                cc=(kkk.ge.kk)
                ij=cc.j+cc.i
                K(ij)=kkk
                j=j-cc.1
                i=i+cc.1
                ij=cc.j+cc.i
              enddo
              K(i)=kk
              return
    ______________________________________

    ______________________________________
              i=1
              kk=K(1)
              cc=1
              do jmi=N-1,1,-1
                ij=i+cc.jmi
                kkk=K(ij)
                cc=(kkk.ge.kk)
                ij=i+cc.jmi
                K(ij)=kkk
                i=i+cc.1
              enddo
              K(i)=kk
              return
    ______________________________________

    ______________________________________
              i=1
              kk=K1(1)
              do jmi=N-1,1,-1
                kkk=K1(N-jmi+1)
                cc=(kkk.ge.kk)
                ij=i+cc.jmi
                K2(ij)=kkk
                i=i+cc.1
              enddo
              K2(i)=kk
              return
    ______________________________________

    ______________________________________
              i1=1
              i2=1
              i3=I
              i4=1
              kk=K(1)
              ii=1
              do jmi=N-1,0,-1
                kkk1=K(ii)
                kkk2=K(ii+1)
                kkk3=K(ii+2)
                kkk4=K(ii+3)
                ii=ii+4
                cc1=(kkk1.ge.kk)
                cc2=(kkk2.ge.kk)
                cc3=(kkk3.ge.kk)
                cc4=(kkk4.ge.kk)
                ij1=i1+cc1.jmi
                ij2=i2+cc2.jmi
                ij3=i3+cc3.jmi
                ij4=i4+cc4.jmi
                K1(ij1)=kkk1
                K2(ij2)=kkk2
                K3(ij3)=kkk3
                K4(ij4)=kkk4
                i1=i1+cc1.1
                i2=i2+cc2.1
                i3=i3+cc3.1
                i4=i4+cc4.1
              enddo
              return
    ______________________________________

    ______________________________________
              i=1
              j=1
              do m=1,N
                kk=K1(i)
                kkk=K2(j)
                cc=(kkk.ge.kk)
                K(m)=cc.kk+cc.kkk
                i=i+cc.1
                j=j+cc.1
              enddo
              return
    ______________________________________

    ______________________________________
              i1=1
              i2=1
              j1=1
              j2=1
              do m=1,N/2
                kk1=K11(i1)
                kk2=K12(i2)
                kkk1=K21(j1)
                kkk2=K22(j2)
                cc1=(kkk1.ge.kk1)
                cc2=(kkk2.ge.kk2)
                K(m)=cc1.kk1+cc1.kkk1
                K(m+N/2)=cc2.kk2+cc2.kkk2
                i1=i1+cc1.1
                i2=i2+cc2.1
                j1=j1+cc1.1
                j2=j2+cc2.1
              enddo
              return
    ______________________________________

    ______________________________________
              do jj=1,n
                key(jj)=s0
                cc=(s1(0).gt.s1(1))
                i1=cc.1
                s0=s1(i1)
                cc=(s2(2xi1).gt.s2(2xi1+1))
                i2=2xi1+cc.1
                s1(i1)=s2(i2)
                cc=(s3(sxi2).gt.s3(2xi2+1))
                i3=2xi1+cc.1
                s2(i2)=s3(i3)
                s3(i3)=bucket(pt(i3))
                pt(i3)=pt(i3)+1
              enddo
    ______________________________________

    ______________________________________
              do jj=1,n
                i1n=cc0.1
                i2n=2xi1+cc1(i1).1
                i3n=2xi2+cc2(i2).1
                key(jj)=s1b(i1n)
                s1a(i1)=s2b(i2n)
                s2a(i2)=s3b(i3n)
                s1b(i1n)=s1a(i1n)
                s2b(i2n)=s2a(i2n)
                s3b(i3n)=bucket(pt(i3n))
                cc0=(s1b(0).gt.s1b(1))
                cc1(i1)=(s2b(2xi1).gt.s2b(2xi1+1))
                cc2(i2)=(s3b(2xi2).gt.s3b(2xi2+1))
                i1=i1n
                i2=i2n
                pt(i3n)=pt(i3n)+1
              enddo
    ______________________________________

• Inventors
  Agarwal, Ramesh Chandra;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Jun-23-1998
• Current US Classes:
  712/215
  712/221
  712/23
  712/234
  717/141
  717/149
• Application #
  678008
• International Classes
  G06F 009/45
• Field of Search
  395/706 395/708 395/568 395/581 395/562 395/391 395/800.23
• Examiner
  Kim; Kenneth S.
• Agent
  Whitham, Curtis & Whitham, Kaufman; Stephen C.
• US Patent References:
  5471593
  5596732