System for Reducing Delay in Instruction Execution by Executing Branch Instructions in Separate Processor While Dispatching Subsequent Instructions to Primary Processor

1. Related Applications

This patent application is related U.S. Pat. application, Ser. No. 07/126,818, entitled "Parallel Processor Instruction Dispatch Apparatus With Interrupt Handler", now abandoned and U.S. Pat. application, Ser. No. 07/135,170, entitled "Dynamic Buffer Control", now U.S. Pat. No. 4,916,658.

2. Technical Field

This invention relates to data processing systems and more specifically to a data processing system executing branch instructions.

3. Background Art

An obstacle to the fast execution of instructions in a data processing system is the execution of a branch instruction. Traditional processors execute instructions in a serial fashion, i.e., one instruction at a time. Therefore, instructions are executed sequentially in a normal mode. However, when a branch instruction is encountered, the instruction sequence may be varied, i.e., the instruction following the branch instruction may not be the new instruction executed. In traditional data processing systems, the execution of instructions is delayed until a branch instruction execution can be completed. This is because the result of the branch instruction execution must be known in order to determine which instruction is to be executed next. In data processing systems executing conditional branch instructions, a pre-existing condition must be determined before it will be known whether or not a branch may be taken as a result of a conditional branch instruction execution. As a result, the execution of a conditional branch instruction is delayed until the specified condition for the branch has been determined. In traditional processors the requirement for the resolution of conditions to perform branches has not been as much a problem as in more modern processing systems. In a pipeline processing system where an instruction is being fetched, dispatched, decoded and executed at different cycle times, the execution of branch instructions will result in delays since the execution phase must be completed for a conditional branch before the data processing system knows which instructions to fetch for execution after the branch.

The use of multiple processors in a data processing system increases the conditional branch execution problem even more since it is advantageous to distribute instructions in parallel to the multiple processors for execution. However, if the multiple processor system is to emulate the execution of instructions in a serial fashion, the execution of instructions after the occurrence of a branch instruction must be delayed until the branch instruction execution is completed.

An example of a prior art instruction dispatching apparatus for a multiple processing system is disclosed in the IBM Technical Disclosure Bulletin, Vol. 29, No. 1, Jun., 1986, entitled "Branch-Processing Instruction Cache", pages 357-359. This disclosure illustrates a mechanism for fetching instructions and includes the capability to process branch instructions while other instructions are being fetched.

It is an object of the present invention to provide a mechanism for executing branch instructions in a more efficient manner.

In accordance with the present invention a data processing system is provided that includes a circuit for storing a sequence of instructions, a circuit for determining if said instruction sequence includes a branch instruction, a circuit responsive to the determination of whether or not there is a branch instruction for storing a sequence of branch target instructions in the storing circuit. A circuit for dispatching instructions in sequence after the branch instruction to a processor. This sequence of instruction is to be executed on condition that the branch is not taken. This dispatch of the sequence of instructions is before a determination of whether the branch will be taken and simultaneous with the determination that the branch is to be taken. Also included is a circuit for directing, if the branch is not to be taken, the processor to execute the instructions in sequence after the branch instruction or, if the branch is to be taken, for dispatching the branch target instruction sequence to the processor for execution.

In the preferred embodiment the invention includes the data processing system having a memory, an instruction fetching and branch processing unit, and a fixed point processing unit. In the instruction fetching and branch processing unit, a mechanism is provided for fetching multiple instructions at a time and for storing these instructions in buffers. In this embodiment one buffer is provided for sequential instructions and a second buffer is provided for target instructions. Sequential instructions include the normal sequence of instructions that are being fetched and also instructions that are present after a branch instruction is encountered. Target instructions are instructions that are to be branched to if a branch is taken as a result of a branch instruction execution. In the preferred embodiment the instruction fetching and branch processing unit executes branch instructions while coordinating the dispatching of instructions to the fixed point processing unit. According to the teachings of this invention, in certain circumstances, branch instructions can be generated in a pipeline fashion without causing any pipeline cycle delays of instruction execution.

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as other features and advantages thereof will be best understood by reference to the detailed description which follows, read in conjunction with the accompanying figures, wherein:

FIG. 1 is a block diagram of the data processing system;

FIG. 2a is an instruction sequence containing an unconditional branch;

FIG. 2b is a timing diagram illustrating the pipelined instruction flow for the instruction sequence in FIG. 2a;

FIG. 2c is an instruction sequence including a not taken conditional compare adjacent to a compare instruction;

FIG. 2d is a timing diagram illustrating the pipelined data flow of the instruction sequence in FIG. 2c;

FIG. 2e is an instruction sequence including a taken conditional branch instruction adjacent to a compare instruction;

FIG. 2f is a timing diagram illustrating the pipelined instruction flow for the instruction sequence of FIG. 2e;

FIG. 2g is an instruction sequence including a compare instruction with instructions between the compare and the taken conditional branch instruction;

FIG. 2h is a timing diagram illustrating the pipelined instruction flow for the instruction sequence in FIG. 2g;

FIG. 2i is an instruction sequence including a compare instruction with three intermediate instructions adjacent to a conditional branch instruction;

FIG. 2j is a timing diagram illustrating the pipeline instruction flow for the instruction sequence in FIG. 2i;

FIG. 3 is a block diagram illustrating the contents of the instruction fetching and branch processing unit; and

FIG. 4 is a flow diagram illustrating the operation of the interlock, dispatch, branch execution, and buffer control logic unit.

This invention relates to the field of data processing and a provides a capability to execute branch instructions in a small amount of time. The objective of the invention is to execute a branch in zero cycles of a fixed point processor.

FIG. 1 is a block diagram illustrating the processor system of the invention. In FIG. 1, memory 10 :s connected by bus 12 to an instruction fetching and branch processing unit 14, a fixed point processing unit 20 and other processing units represented by block 22. The function of bus 12 is to provide a transfer of instructions and data from memory 10. The instruction fetching and branch processing unit 14 provides instructions over line 16 to the fixed point processing unit 20. Also conditional code information is provided to the instruction fetching and branch processing unit 14 over line 18 by the fixed point processing unit 20. In response to the condition code information or bus 18 provided the fixed point unit 20 to the instruction fetching unit 14, branch execution logic in the instruction fetching unit 14 generates the execute conditional signal via line 41 if the branch is not to be taken or generates the cancel conditional signal via line 43 if the branch is to be taken.

FIGS. 2a to 2j represent example instruction sequences and resulting timing diagrams for the execution of those sequences. In FIG. 2a an instruction sequence is provided that includes an unconditional branch instruction. Specifically the unconditional branch instruction (BRU) branches to instruction T1 (the target instruction). The timing diagram illustrating the operation of the invention with this instruction sequence is illustrated in FIG. 2b. In FIG. 2b four phases of the pipeline operation are illustrated. The first phase is the instruction fetch operation (IF). The second phase is the instruction dispatch operation (Disp). During the second phase the instruction fetching and processing unit 14 detects branch instructions and initiates branch instruction execution. The third phase is the fixed point processor decoding operation (FXD). The fourth is the fixed point processor execution of the instruction (FXE). In cycle 1, four instructions are fetched from the cache 34 (FIG. 3) which include X1, X2, BRU and S. Note that S designates the sequential instructions that occur after the unconditional branch instruction (BRU). In cycle 2 the instruction fetch operation fetches additional sequential instructions (S2 and S3). At the same time during cycle 2, the dispatch operation dispatches instructions X1 and X2 to the fixed point processing unit 20. The BRU instruction is dispatched and executed internally in the branch processing unit 14. The target address is generated in cycle 2. In cycle 3, as a result of the execution of the unconditional branch in the branch processing unit 14, the four target instructions are fetched, T1, T2, T3, T4. Also in cycle 3, instruction X1 is decoded in the fixed point processing unit 20. In cycle 4 an additional four target instructions are fetched (T5, T6, T7 and T8). Also in cycle 4 instructions T1 and T2 are dispatched to the fixed point processing unit 20. Meanwhile in cycle 4 the fixed point processing unit 20 decodes the instruction X2 and executes instruction X1. In cycle 5, the target instructions T3 and T4 are dispatched to the fixed point processing unit 20 while the fixed point processing unit 20 decodes instruction T1 and executes instruction X2. In cycle 6, instructions T5 and T6 are dispatched while the fixed processing unit 20 decodes target instruction T2 and executes instruction T1. Finally in cycle 7, the instruction T3 is being decoded while instruction T2 is being executed in the fixed point processing unit 20. Note that the branch operation takes no execution cycles and causes no execution delay since the fetching of the target instructions was accomplished as a result of the early execution of the branch instruction during the dispatch cycle 2.

In FIG. 2c an instruction sequence is included that provides for a fixed point compare instruction (C) followed by a branch on condition instruction (BRC). If the branch is not taken, the sequential instructions following the branch will be executed (S1, S2, and S3). However, if the branch is taken the target instructions are executed (T1, T2, and T3). In the following example the conditional branch is not taken. The timing diagram in FIG. 2d illustrates the operation of the processing unit. Initially in cycle 1 four instructions are fetched including the condition instruction (C), the conditional branch instruction (BRC), and the two sequential instructions S1 and S2. In cycle 2 the next four sequential instructions (S3 through S6) are fetched while the compare instruction C and the sequential instruction S1 are passed to the fixed point processing unit 20. The S1' indicates that instruction S1 is passed as an instruction for conditional execution. In other words, the execution of S1 is conditional on the event that the branch is not taken. The conditional branch instruction (BRC) is passed to the branch processing unit 14 where it is executed. However, the completion of the execution of the conditional branch is delayed until the compare instruction is executed in the fixed point processing unit 20. In cycle 3, because of the initial execution of the branch instruction, four of the target instructions are fetched (T1 through T4). Simultaneously instructions S2 and S3 are dispatched to the fixed point processing unit 20. Note that these instructions are dispatched as conditional instructions that will be executed upon the condition that the conditional branch will not be taken. In the fixed processing unit during cycle 3, the fixed point processor decodes the compare instruction. In cycle 4 the next four target instructions are fetched (T5 through T8). Also the next two sequential instructions S4 and S5 are dispatched as conditional instructions to the fixed point processing unit 20. The fixed point processing unit 20 decodes the sequential instruction S1 while it executes the compare instruction. At the completion of the execution of the compare instruction the result of the compare instruction is provided to the branch processing unit 14 indicating to the branch processing unit 14 that the branch will not be taken (i.e., that the sequential instructions should be executed). The execute condition is asserted via line 41. Next in cycle 5 the fixed point processing unit 20 decodes the sequential instruction S2 while it executes the sequential instruction S1. Also in cycle 5 the fetching of target instructions is suspended and the dispatching of target instructions is suspended. In cycle 6 the fetching of sequential instructions is resumed with the fetching of sequential instructions S7 through S10. Also in cycle 6, the fixed point processing unit 20 decodes instruction S3 and executes sequential instruction S2. Finally in cycle 7, the fixed point processing unit is decoding instruction S4 and is executing instruction S3 illustrating that the sequential instruction sequence is being executed. Note that again the execution of the branch takes no execution cycles and causes no delay even though the branch was not taken.

FIG. 2e illustrates a conditional branch instruction where the branch is taken. The sequence illustrated in FIG. 2e includes a fixed point compare instruction C, a conditional branch instruction BRC followed by a set of sequential instructions S1 through S3 then followed by a sequence of target instructions T1 through T4. The execution of this sequence is illustrated in FIG. 2f.

In FIG. 2f in cycle 1 the four instructions are fetched (C, BRC, S1, and S2). In cycle 2, the next four instructions are fetched (S3 through S6) and the compare instruction and the first sequential instruction (S1) are dispatched to the fixed point processing unit 20 while the conditional branch instruction BRC is initially executed in the branch processing unit 14. In cycle 3 four of the target instructions are fetched (T1 through T4). The sequential instructions S2 and S3 are conditionally dispatched to the fixed point processing unit 20. Meanwhile, the compare instruction is decoded in the fixed point processing unit 20. In cycle 4 the next four target instructions are fetched (T5 through T8), while the sequential instructions S4 and S5 are conditionally dispatched to the fixed point processing unit 20. The sequential instruction S1 is being decoded in the fixed processing unit at the same time the compare instruction is being executed. As a result of the completion of the execution of the compare instruction in cycle 4, the branch processing unit 14 is informed that the branch should be taken. Therefore, in cycle 5 the sequential instruction S1 whose execution is conditioned on the branch not being taken will not be executed as a result the assertion of the cancel conditional line 43. Also even though the sequential instruction S2 is being decoded it will be purged. In cycle 6 the first two target instructions T1 and T2 are dispatched to the fixed point processing unit 20. In cycle 7 instruction T1 is being decoded and executed in cycle T8. Note that the execution of this conditional branch results in a three cycle delay. This is a worse case condition since the maximum delay in this configuration is 3-i cycles where i is the number of fixed point operations that are located between the compare and branch on compare instructions.

In FIG. 2g another instruction sequence is illustrated that first includes a compare instruction followed by two fixed point instructions X1 and X2. Following X2 is a branch on condition of the compare instruction. Following the branch is the set of sequential instructions S1 and S3 followed later by the target instructions T1 through T4. The timing execution of these instruction sequences are illustrated in FIG. 2h. Referring to FIG. 2h, in cycle 1, the first four instructions are fetched (C, X1, X2 and BRC) In cycle 2 the next four instructions in the sequence are fetched (S1 through S4) while the compare instruction and the first fixed point instruction X1 are dispatched to the fixed point unit 20. Also during cycle 2, the instruction sequence that has been fetched has been scanned for branch instructions. Upon encountering a branch instruction, the scanning logic determines if the target instructions of the branch can be computed. In the example given the target instruction addresses are computed and then in cycle 3 the first four target instructions T1 through T4 are fetched. Also during cycle 3 instruction X2 is unconditionally dispatched and sequential instruction S1 is conditionally are dispatched to the fixed point processing unit 20. The conditional branch instruction BRC is dispatched to the processing unit 14. The fixed point processing unit 20 decodes the compare instruction C. In cycle 4, the next four target instructions are fetched (T5 through T8) while sequential instructions S2 and S3 are dispatched to fixed point processing unit. The fixed point processing unit 20 decodes instruction X1 and executes the compare C. As a result of the compare instruction the branch is taken. In cycle 5 instruction X2 is decoded by the fixed point processing unit 20 while the instruction X1 is executed. However, no additional instructions are fetched during these cycles and no instructions are dispatched. In cycle 6, the fetching of target instructions would continue however for the simplicity of this example only eight target instructions have been fetched. In cycle 6, the target instructions T1 and T2 are dispatched to the fixed point processing unit 20 during the execution of instruction X2. In cycle 7 instructions T3 and T4 are dispatched while instruction T1 is being decoded. Finally in cycle 8, instruction T1 is executed by the fixed point processing unit 20. Note that the branch in this case only causes a one cycle delay since there were two intermediate instructions between the compare and branch on condition instructions.

In FIG. 2i another example instruction sequence is illustrated that includes three intermediate instructions between the fixed point compare instruction and the conditional branch instruction. The timing diagram for the execution of this instruction sequence is illustrated in FIG. 2j. In FIG. 2j during cycle the first four instructions of this instruction sequence in FIG. 2i is illustrated. In cycle 2 the second four instructions are fetched while the first two instructions are dispatched. Note that since the first four instructions that were fetched did not contain the branch instruction, the scanning logic would not detect that there is a branch, until cycle 3. Therefore in cycle 3 if additional sequential instructions were available they would be fetched. Also in cycle 3 instructions X2 and X3 are dispatched to the fixed point processing unit 20 while the conditional branch is dispatched to the branch processing unit 14 while the fixed point processing unit decodes the compare instruction. In cycle 4, the target instructions T1 through T4 are now prefetched as a result of the scanning of the conditional branch instruction in cycle 3. Sequential instructions S1 and S2 are conditionally dispatched to the fixed point processing unit 20 while instruction X1 is decoded and the compare instruction is executed. At the completion of the execution of the compare instruction in the fixed point processing unit 20, the branch processing unit is signalled that the branch will be taken. In cycle 5 the next four target instructions are fetched (T5 through T8) while in the fixed point processing unit 20 instruction X2 is decoded and instruction X1 is executed. In cycle 6 the first of the two target instructions T1 and T2 are dispatched to the fixed point processing unit 20 while instruction X3 is decoded and instruction X2 is executed. In cycle 7 the next two target instructions T3 and T4 are dispatched while instruction T1 is decoded and instruction X3 is executed. In cycle 8 finally instruction T2 is being decoded while the first of the target instructions T1 is being executed. Note that the execution of this conditional branch results in a zero cycle delay since the number of intermediate instructions between the compare instruction and the branch is equal to three.

FIG. 3 is a block diagram illustrating the instruction cache and branch processing unit 14. In FIG. 3 an instruction cache directory and array 34 is connected to bus 12 to receive instructions from memory. The instructions from the instruction cache 34 are provided to either a target instruction buffer 36 or sequential instruction buffer 38. Target instruction buffer 36 has a capacity of four in the preferred embodiment while the sequential instruction buffer 38 has a capacity of eight instructions. The target instructions in the target instruction buffer 36 pass to the sequential buffer 38 if the target instructions have been selected for dispatching. The interlock, dispatch, branch execution, and buffer control unit 40 is connected to the sequential instruction buffer 38 and scans the contents of the sequential instruction buffer 38 to detect branch instructions. Also, on line 50, the multiplex network 52 is controlled by the control logic 40 to dispatch two instructions over bus 16 to the fixed point processing unit 20.

Upon determining that a branch instructions exists in the sequential instruction buffer 38, the control logic 40 through the multiplexer network 52 provides the branch instruction to the unresolved branch register 54, if the branch is not resolved, and to the branch address generation unit 62. The branch address generation unit determines if the address of the target instruction of the branch can be computed. In certain instances the count register 58 or link register 60 are used in a computation of the address of the target instruction. The address of the target instruction is then provided over bus 61 to the instruction fetch address register 30. When the instruction fetch address register 30 has been loaded with an address of a target instruction the previous address of the sequential instructions being fetched is transferred to the instruction fetch address register shadow 32 to store the address of the sequential instructions if in fact the branch to the target instruction is not taken. The condition register 56 is connected by bus 18 to the fixed point processing unit 20 and determines the result of a condition compare instruction execution that determines whether a conditional branch is taken.

The control logic 40 monitors the condition register 56 and upon determining that a conditional branch is to be taken, the control logic 50 provides target instructions from the target instruction buffer 36 to the sequential instruction buffer 38 to be dispatched. The control of the target instruction buffer and the sequential instruction buffer is provided by lines 37 and 39 respectively. If the branch is not taken, the address of the sequential instruction are restored from register 32 to register 30 and sequential instructions in the sequential instruction buffer 38 continue to be dispatched. The control of the target instruction buffer 36 and the sequential instruction buffer 38 is provided by lines 37 and 39 respectively from the control logic 40. Additionally connected to control logic 40 is line 43 which provides the cancel conditional signal to the fixed point processing unit 20 indicating that the conditional instructions (the sequential instruction occurring after the branch instruction) are not to be executed. Line 41 provides the execute conditional signal to the fixed point processing unit 20 which indicates to the fixed point processing unit that these conditional instructions are to be executed.

FIG. 4 is a flow chart representing the operation of the interlock, dispatch, branch execution and buffer control logic 40. In FIG. 4 at the start of a cycle 100 step 106 determines if an, unresolved branch is pending. This is accomplished by determining if a unresolved branch pending bit has been set. If no unresolved branch is pending the flow proceeds to step 110 at which time the sequential instruction buffer 38 is scanned to determine if there are any branch instructions present. If not, the control flow proceeds to step 104 to fetch a new set of sequential instructions into the sequential instruction buffer 38 and to dispatch sequential instructions from sequential instruction buffer 38. Upon completing step 104 the control flow returns to step 100 to await the beginning of the next cycle. Returning to step 110, if a branch has been detected in the sequential instruction buffer 38 step 116 is executed in which a determination is made as to whether a target address can be generated. If not, the control flow proceeds to step 104. If so, the flow proceeds to step 126 to determine if all previous instructions have been dispatched. If all previous instructions before the branch have not been dispatched, the flow continues to step 132 to determine if prefetching of branch target instructions has begun. If not, in step 146 the target address is placed into the instruction fetch address register 30 and prefetching is begun. At this time the existing contents of the instruction fetch address register 30 is placed into the instruction fetch address register shadow 32. Upon completing step 146 or if prefetching has already begun the control flow proceeds to step 150 to dispatch instruction from the sequential instruction buffer 38. Control flow then proceeds to step 102 where branch target instructions are fetched into the target instruction buffer 36. Afterwards the flow returns to step 100 to await the beginning of the next cycle.

Returning to step 126 if all previous instructions before the branch have been dispatched, the flow proceeds to step 130 to determine if it is known at this point if the branch will be taken. If the branch is known to be taken the control flow proceeds to step 136 to determine if prefetching has begun. If not the control flow proceeds to step 144 to place the target address into the instruction fetch address register 30 and the current sequential buffer is invalidated. As before the original contents of register 30 is placed into register 32. The flow then proceeds to step 104. Returning to step 136 if prefetching has already begun the flow proceeds to step 142 to load the instructions from the target instruction buffer 36 into the sequential instruction buffer 38 and to stop prefetching. Again the flow proceeds to step 104. Returning to step 130 if it is not known whether or not the branch will be taken the flow proceeds to step 134 to determine if it is known whether or not the branch will not be taken. If the branch is not taken the flow continues to step 140 to determine if prefetching has begun. If not, the flow continues to step 104. However, if prefetching has begun, the flow proceeds to step 148 to stop the prefetching and restore the instruction fetch address register 30 with the contents of the instruction fetch address shadow 32. Upon completing step 148 the control flow proceeds to step 104. Returning to step 134, if it is not known if the branch will not be taken, the control flow proceeds to step 138 to load the unresolved branch register 54 and to set an internal bit indicating that there is an unresolved branch pending. Also, in sequential instructions are dispatched from the sequential buffer 38. These sequential instructions are for conditional execution, i.e., that they will be executed only if the branch is not taken. The control flow then proceeds to step 102.

Returning to step 106, if there is an unresolved branch pending the flow proceeds to step 108 to determine if the branch is resolved. In determining if the branch has been resolved, the control logic examines the contents of the condition register 56 to determine if the condition code has been set that is required for the resolution of the branch in the unresolved branch register 54. If the branch has not been resolved the flow proceeds to step 114 to determine if prefetching has begun. If not, the flow continues to step 122 to determine if the target address can be generated. If the target address cannot be generated the program flow proceeds to step 104. If the target address can be generated the program proceeds to step 124 to store the contents of the instruction fetch address register 30 into the instruction fetch address register shadow 32 and to place the generated target address into the instruction fetch address register 30 and to begin prefetching of branch target instructions. Proceeding to step 128 the dispatching of sequential instructions is begun. These sequential instructions are being dispatched for conditional execution, i.e., for execution upon the condition that the branch will not be taken. After step 128 the flow proceeds to step 102.

Returning to step 108, if the branch has been resolved the flow continues to step 112 to determine if the branch has been taken. If the branch has not been taken an execution conditional signal on line 41 (FIG. 1) will be provided to the fixed point processing unit 20. The instruction fetch address register 30 will be restored with the contents of the instruction fetch address register shadow 32 and prefetching will be halted. The control flow then proceeds to step 104. If the branch is taken a cancel conditional sequential instruction execution signal is provided on line 43 to the fixed point processing unit 20 and the branch target instructions in the target instruction buffer 36 are loaded into the sequential instruction buffer 38. Also prefetching is halted. Control flow then proceeds to step 104.

Although the invention has been described with reference to this specific embodiment, the description is not meant to be construed in a limiting sense. Various modifications of the disclosed embodiment as well as other embodiments of the invention, will become apparent to those persons skilled in the art upon reference to the description of this invention. It is, therefore, contemplated that the appended claims will cover any such modifications or embodiments that may fall within the true scope of the invention.