Pipelined central processor managing the execution of instructions with proximate successive branches in a cache-based data processing system while performing block mode transfer predictions

• US 6,442,681 B1
• Filed: 12/28/1998
• Issued: 08/27/2002
• Est. Priority Date: 12/28/1998
• Status: Expired due to Term

• Current Assignee: Bull HN Information Systems Incorporated (Atos SE)
• Original Assignee: Bull HN Information Systems Incorporated (Atos SE)
• Inventors: Brossard, Patrice, Ryan, Charles P.
• Primary Examiner(s): Chan, Eddie
• Assistant Examiner(s): Wood, William H.
• Application Number:
  US09/221,392
• Time in Patent Office: 1,338 Days
• Field of Search: 712/238, 712/237, 712/233, 712/234, 711/119, 711/140, 711/125, 711/169
• US Class Current: 712/238
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables

Abstract

A cache used with a pipelined processor includes an instruction cache, instruction buffers for receiving instruction sub-blocks from the instruction cache and providing instructions to the pipelined processor, and a branch cache. The branch cache includes an instruction buffer adjunct for storing an information set for each sub-block resident in the instruction buffers. A branch cache directory stores instruction buffer addresses corresponding to current entries in the instruction buffer adjunct, and a target address RAM stores target addresses developed from prior searches of the branch cache. A delay pipe is used to selectively step an information set read from the buffer instruction adjunct in synchronism with a transfer instruction traversing the pipeline. A comparison, at a predetermined phase along the delay pipe, determines if the information set identifies, as currently resident in the instruction buffers, a target address that matches the target address in the transfer instruction traversing the pipeline. If there is a finding that the information set traversing the delay pipe identifies a target address in the instruction buffers that matches the target address in the transfer instruction traversing the pipeline and there is an indication of TRA-GO from the pipeline, the instruction identified by the target address is sent to the pipeline from the instruction buffers rather than from the instruction cache.

Claims

1. A data processing system with a pipelined processor and a cache which includes an instruction cache, instruction buffers for receiving instruction sub-blocks from the instruction cache and providing instructions to the pipelined processor and a branch cache, said branch cache comprising:

A) an instruction buffer adjunct for storing an information set for each of sub-blocks which are currently resident in the instruction buffers, which information set includes;

1) a search address;

2) a predicted transfer hit/miss;

3) a projected location of a target in a sub-block; and

4) a predicted target address;

B) a branch cache directory for storing instruction buffer addresses corresponding to current entries in the instruction buffer adjunct;

C) a target address RAM for storing target addresses;

D) a delay pipe for selectively stepping an information set read from the buffer instruction adjunct in synchronism with a transfer instruction traversing the pipeline;

E) means for addressing the buffer instruction buffer adjunct for sending a selected information set to the delay pipe when a transfer instruction is sent to the pipeline from the instruction buffers, which transfer instruction includes a target address;

F) comparison means for determining, at a predetermined phase along the delay pipe, if the information set traversing the delay pipe identifies, as currently resident in the instruction buffers, a target address that matches the target address in the transfer instruction traversing the pipeline; and

G) selection means, responsive to a finding that the information set traversing the delay pipe includes a target address that matches the target address in the transfer instruction traversing the pipeline, for sending the instruction identified by the target address to the pipeline from the instruction buffers.

2. The data processing system of claim 1 in which the selection means is responsive to a finding that the information set traversing the delay pipe does not include a target address that matches the target address in the transfer instruction traversing the pipeline by sending the instruction identified by the target address to the pipeline from the instruction cache.

3. The data processing system of claim 2 in which the branch cache further includes update means responsive to the sending of a new sub-block from the instruction cache to the instruction buffer for developing an information set for the new sub-block and for storing the information set for the new sub-block into the instruction buffer adjunct.

4. The data processing system of claim 3 in which the selection means is further responsive to a TRA-GO signal from the pipeline such that, if there is a finding that the information set traversing the delay pipe includes a target address that matches the target address in the transfer instruction traversing the pipeline, the instruction identified by the target address is sent to the pipeline from the instruction buffers only if the TRA-GO signal is received, else the instruction identified by the target address is sent to the pipeline from the instruction cache.

5. The data processing system of claim 4 in which the sub-block containing the target address in the transfer instruction is processed as a new entry into the branch cache and an instruction set therefor is stored in the branch case adjunct.

6. The data processing system of claim 5 in which the sub-block is four instruction words in length.

7. The data processing system of claim 4 in which the sub-block is four instruction words in length.

8. The data processing system of claim 3 in which the sub-block containing the target address in the transfer instruction is processed as a new entry into the branch cache and an instruction set therefor is stored in the branch case adjunct.

9. The data processing system of claim 8 in which the sub-block is four instruction words in length.

10. The data processing system of claim 3 in which the sub-block is four instruction words in length.

11. The data processing system of claim 2 in which the selection means is further responsive to a TRA-GO signal from the pipeline such that, if there is a finding that the information set traversing the delay pipe includes a target address that matches the target address in the transfer instruction traversing the pipeline, the instruction identified by the target address is sent to the pipeline from the instruction buffers only if the TRA-GO signal is received, else the instruction identified by the target address is sent to the pipeline from the instruction cache.

12. The data processing system of claim 11 in which the sub-block containing the target address in the transfer instruction is processed as a new entry into the branch cache and an instruction set therefor is stored in the branch case adjunct.

13. The data processing system of claim 12 in which the sub-block is four instruction words in length.

14. The data processing system of claim 11 in which the sub-block is four instruction words in length.

15. The data processing system of claim 2 in which the sub-block containing the target address in the transfer instruction is processed as a new entry into the branch cache and an instruction set therefor is stored in the branch case adjunct.

16. The data processing system of claim 15 in which the sub-block is four instruction words in length.

17. The data processing system of claim 2 in which the sub-block is four instruction words in length.

18. The data processing system of claim 1 in which the branch cache further includes update means responsive to the sending of a new sub-block from the instruction cache to the instruction buffer for developing an information set for the new sub-block and for storing the information set for the new sub-block into the instruction buffer adjunct.

19. The data processing system of claim 18 in which the selection means is further responsive to a TRA-GO signal from the pipeline such that, if there is a finding that the information set traversing the delay pipe includes a target address that matches the target address in the transfer instruction traversing the pipeline, the instruction identified by the target address is sent to the pipeline from the instruction buffers only if the TRA-GO signal is received, else the instruction identified by the target address is sent to the pipeline from the instruction cache.

20. The data processing system of claim 19 in which the sub-block containing the target address in the transfer instruction is processed as a new entry into the branch cache and an instruction set therefor is stored in the branch case adjunct.

21. The data processing system of claim 20 in which the sub-block is four instruction words in length.

22. The data processing system of claim 19 in which the sub-block is four instruction words in length.

23. The data processing system of claim 18 in which the sub-block containing the target address in the transfer instruction is processed as a new entry into the branch cache and an instruction set therefor is stored in the branch case adjunct.

24. The data processing system of claim 23 in which the sub-block is four instruction words in length.

25. The data processing system of claim 18 in which the sub-block is four instruction words in length.

26. The data processing system of claim 1 in which the selection means is further responsive to a TRA-GO signal from the pipeline such that, if there is a finding that the information set traversing the delay pipe includes a target address that matches the target address in the transfer instruction traversing the pipeline, the instruction identified by the target address is sent to the pipeline from the instruction buffers only if the TRA-GO signal is received, else the instruction identified by the target address is sent to the pipeline from the instruction cache.

27. The data processing system of claim 26 in which the sub-block containing the target address in the transfer instruction is processed as a new entry into the branch cache and an instruction set therefor is stored in the branch case adjunct.

28. The data processing system of claim 27 in which the sub-block is four instruction words in length.

29. The data processing system of claim 26 in which the sub-block is four instruction words in length.

30. The data processing system of claim 1 in which the sub-block containing the target address in the transfer instruction is processed as a new entry into the branch cache and an instruction set therefor is stored in the branch case adjunct.

31. The data processing system of claim 30 in which the sub-block is four instruction words in length.

32. The data processing system of claim 1 in which the sub-block is four instruction words in length.