Processes, circuits, devices, and systems for branch prediction and other processor improvements

• US 20060095750A1
• Filed: 08/24/2005
• Published: 05/04/2006
• Est. Priority Date: 08/30/2004
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Tran, Thang, Nye, Jeffrey L.
• Granted Patent: US 7,752,426 B2
• Time in Patent Office: Days
• US Class Current: 712/240
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A processor (1700) for processing instructions has a pipeline (1710, 1736, 1740) including a fetch stage (1710) and an execute stage (1870), a first storing circuit (aGHR 2130) associated with said fetch stage (1710) and operable to store a history of actual branches, and a second storing circuit (wGHR 2140) associated with said fetch stage (1710) and operable to store a pattern of predicted branches, said second storing circuit (wGHR 2140) coupled to said first storing circuit (aGHR 2130), said execute stage (1870) coupled back to said first storing circuit (aGHR 2130). Other processors, wireless communications devices, systems, circuits, devices, branch prediction processes and methods of operation, processes of manufacture, and articles of manufacture, as disclosed and claimed.

Claims

1. A processor for processing instructions comprising

a pipeline including a fetch stage and an execute stage;

a first storing circuit associated with said fetch stage and operable to store a history of actual branches; and

a second storing circuit associated with said fetch stage and operable to store a pattern of predicted branches, said second storing circuit coupled to said first storing circuit, said execute stage coupled back to said first storing circuit.

2. The processor claimed in claim 1 further comprising a third storing circuit situated in said pipeline earlier than said fetch stage associated with said second storing circuit, said third storing circuit readable for branch Taken and Not-Taken information indexed on read by a pattern from said second storing circuit.

3. The processor claimed in claim 2 further comprising a branch target buffer having stored branch target addresses and a multiplexer circuit fed with one of the branch target addresses and responsive to said branch Taken and Not-Taken information from said third storing circuit to select the branch target address when the information represents branch Taken.

4. The processor claimed in claim 3 further comprising a memory for holding an instruction accessible by the branch target address from said multiplexer circuit, whereby the instruction is fetched from the memory for processing.

5. The processor claimed in claim 4 further comprising a branch decoder circuit responsive to the instruction fetched from the memory, said second storing circuit responsive to said branch decoder.

6. The processor claimed in claim 1 further comprising an instruction cache having cache lines stored therein, and a cache line branch decoder circuit responsive to a cache line to update said second storing circuit.

7. The processor claimed in claim 6 wherein said cache line branch decoder circuit is operable to detect branches on the cache line and includes update circuitry coupled to said second storing circuit and operable to modify the pattern with different numbers of bits dependent on the number of detected branches.

8. The processor claimed in claim 7 wherein said update circuitry is responsive to a predicted address to ignore branches on the cache line having an address prior to the predicted address, whereby the different numbers of bits are also dependent on the predicted address.

9. The processor claimed in claim 8 further comprising address prediction circuitry responsive to a pattern from said second storing circuit and operable to supply the predicted address.

10. The processor claimed in claim 8 further comprising address prediction circuitry responsive to a pattern from said second storing circuit to feed the predicted address to said instruction cache to supply a said cache line.

11. The processor claimed in claim 1 wherein said first storing circuit has an input for a branch mis-prediction signal from said execute stage whereby said execute stage is coupled back to said first storing circuit.

12. The processor claimed in claim 1 wherein said first storing circuit has an input for a signal representing an occurrence of an actual taken branch from said execute stage whereby said execute stage is coupled back to said first storing circuit.

13. The processor claimed in claim 1 wherein said execute stage has a program counter value and said first storing circuit has an input coupled to the program counter value from said execute stage.

14. The processor claimed in claim 1 further comprising a third storing circuit situated in said pipeline earlier than said fetch stage associated with said second storing circuit, said third storing circuit readable for branch Taken and Not-Taken information indexed on read by a pattern from said second storing circuit and further indexed on read by bits from an instruction address representing a next instruction to fetch.

15. The processor claimed in claim 14 further comprising a branch target buffer holding branch target addresses and the third storing circuit being further indexed on read by particular index bits dependent on a subset of bits from a branch target address accessed from said branch target buffer in response to the instruction address.

16. The processor claimed in claim 15 wherein the particular index bits include a hash of said subset of bits from the branch target address with some bits from the pattern from said second storing circuit.

17. The processor claimed in claim 1 further comprising a writable third storing circuit situated in said pipeline earlier than said fetch stage associated with said first storing circuit, said third storing circuit writable to load branch Taken and Not-Taken information indexed on write by a pattern from said first storing circuit.

18. The processor claimed in claim 1 further comprising logic circuitry coupled to said first storing circuit and said second storing circuit, said logic circuitry operable to keep information in said second storing circuit coherent with information in said first storing circuit in case of a mispredicted branch.

19. The processor claimed in claim 1 further comprising logic circuitry coupled to said first storing circuit and said second storing circuit, said logic circuitry operable in case of a mis-prediction to load at least some bits of actual branch history from said first storing circuit into said second storing circuit.

20. The processor claimed in claim 1 further comprising a third storing circuit readable for branch Taken and Not-Taken information indexed on read by a pattern from said second storing circuit and operable to supply a predicted taken bit, and update logic circuitry operable to supply an updated pattern to said second storing circuit including at least some bits of a pattern from said second storage circuit and the predicted taken bit from said third storing circuit.

21. The processor claimed in claim 20 further comprising a cache having a cache line and the processor further comprising a branch decoder circuit operable to detect branches on the cache line, the update logic circuitry operable to include a number of insertion bits between the at least some bits of the pattern and the at least one bit of predicted branch history, the number of insertion bits being a function of the number of detected branches on the cache line.

22. The processor claimed in claim 21 wherein said update circuitry is responsive to a predicted address input to ignore, for purposes of establishing the number of insertion bits, any branches on the cache line having an address prior to the predicted address.

23. The processor claimed in claim 1 further comprising a second pipeline including an additional execute stage, said additional execute stage coupled to said first storing circuit.

24. The processor claimed in claim 1 wherein said execute stage is operable to resolve branches free of pattern bits from said second storing circuit, whereby any pipelining of pattern bits from said second storing circuit to said execute stage is absent.

25. The processor claimed in claim 1 wherein said pipeline is selected from the group consisting of 1) reduced instruction set computing (RISC), 2) digital signal processing (DSP), 3) complex instruction set computing (CISC), 4) superscalar, 5) skewed pipelines, 6) in-order, 7) out-of-order, 8) very long instruction word (VLIW), 9) single instruction multiple data (SIMD), and 10) multiple instruction multiple data (MIMD).

26. A method of branch prediction in a processor having a pipeline with a fetch stage and an execute stage, the method comprising storing a history of actual branches and separately storing a pattern of predicted branches so that the storing and separately storing are both time-wise parallel to the fetch stage, and coupling back branch data from the execute stage for the storing of the history of actual branches.

27. The method claimed in claim 26 further comprising reading stored Taken and Not-Taken information indexed on read by a pattern from said second storing circuit in a stage earlier than said fetch stage associated with the second storing.

28. The method claimed in claim 27 further comprising retrieving a stored branch target address and fetching a cache line from an instruction cache with the branch target address when the information represents branch Taken.

29. The method claimed in claim 28 further comprising branch decoding the cache line, wherein the separately storing is responsive to said branch decoding.

30. The method claimed in claim 26 further comprising branch decoding to detect branches on a cache line, and modifying the pattern with different numbers of bits dependent on the number of detected branches.

31. The method claimed in claim 30 wherein the branch decoding ignores branches on the cache line having an address prior to a predicted address, whereby the different numbers of bits are also dependent on the predicted address.

32. The method claimed in claim 31 further comprising supplying the predicted address in response to the pattern prior to modifying the pattern.

33. The method claimed in claim 31 further comprising using the predicted address to read an instruction cache to supply the cache line.

34. The method claimed in claim 26 wherein the branch data coupled back from the execute stage includes a branch mis-prediction signal.

35. The method claimed in claim 26 wherein the branch data coupled back from the execute stage includes a signal representing an occurrence of an actual taken branch from said execute stage.

36. The method claimed in claim 26 further comprising coupling a program counter value back to the fetch stage from the execute stage.

37. The method claimed in claim 26 further comprising writing branch Taken and Not-Taken information indexed by the history of actual branches.

38. The method claimed in claim 26 further comprising keeping information in the separate storing coherent with information in the first storing in case of a mis-predicted branch.

39. The method claimed in claim 26 further comprising replacing at least some bits of the pattern with actual branch history in case of a mis-predicted branch.

40. The method claimed in claim 26 further comprising updating the pattern by concatenating at least some bits of the pattern with at least one bit of predicted branch history obtained from a global history buffer indexed on the pattern.

41. The method claimed in claim 40 further comprising detecting branches on a cache line, and including a number of insertion bits between the at least some bits of the pattern and the at least one bit of predicted branch history, the number of insertion bits being a function of the number of detected branches on the cache line.

42. The method claimed in claim 41 wherein including the number of insertion bits ignores any branches on the cache line having an address prior to a predicted address.

43. The method claimed in claim 26 further comprising resolving branches in the execute stage free of pattern bits.

44. The method claimed in claim 26 further comprising synchronizing the storing and separate storing to the length of the pipeline between said fetch stage and said execute stage.

45. The method claimed in claim 26 further comprising processing instructions in-order.

46. A wireless communications unit comprising

a wireless antenna;

a wireless transmitter and receiver coupled to said wireless antenna;

a microprocessor coupled to at least one of the transmitter and receiver, the microprocessor including a pipeline having a fetch stage and an execute stage, a first storing circuit associated with said fetch stage and operable to store a history of actual branches, and a second storing circuit associated with said fetch stage and operable to store a pattern of predicted branches, said second storing circuit coupled to said first storing circuit, said execute stage coupled back to said first storing circuit; and

a user interface coupled to said microprocessor;

whereby the wireless communication unit has increased instruction efficiency.

47. The wireless communications unit claimed in claim 46 wherein the instruction issue circuit is operable to issue as many as a plurality of candidate instructions concurrently, whereby the instruction efficiency of the wireless communications unit is further increased.

48. The wireless communications unit claimed in claim 46 further comprising a second microprocessor and a camera interface, the second microprocessor including a second pipeline having an additional fetch stage and an additional execute stage, a third storing circuit associated with said fetch stage and operable to store a history of actual branches, and a fourth storing circuit associated with said additional fetch stage and operable to store a pattern of predicted branches, said fourth storing circuit coupled to said third storing circuit, said additional execute stage coupled back to said third storing circuit.

49. The wireless communications unit claimed in claim 46 further comprising a second microprocessor and an additional wireless interface coupled to said second microprocessor, said second microprocessor including a second pipeline having an additional fetch stage and an additional execute stage, a third storing circuit associated with said fetch stage and operable to store a history of actual branches, and a fourth storing circuit associated with said additional fetch stage and operable to store a pattern of predicted branches, said fourth storing circuit coupled to said third storing circuit, said additional execute stage coupled back to said third storing circuit.

50. The wireless communications unit claimed in claim 46 further comprising a memory system including a flash memory and a dynamic random access memory (DRAM), and a cache system coupled to said flash memory and to said DRAM, said cache system including an instruction cache coupled to said second storing circuit, and a data cache coupled to said pipeline.

51. The wireless communications unit claimed in claim 46 wherein said microprocessor further includes security software including a branch instruction.

52. The wireless communications unit claimed in claim 46 wherein said pipeline is selected from the group consisting of 1) reduced instruction set computing (RISC), 2) digital signal processing (DSP), 3) complex instruction set computing (CISC), 4) superscalar, 5) skewed pipelines, 6) in-order, 7) out-of-order, 8) very long instruction word (VLIW), 9) single instruction multiple data (SIMD), and 10) multiple instruction multiple data (MIMD).

53. The wireless communications unit claimed in claim 46 further comprising user interfaces to provide functionality selected from the group consisting of 1) mobile phone handset, 2) personal digital assistant (PDA), 3) wireless local area network (WLAN) gateway, 4) personal computer (PC), 5) WLAN access point, 6) set top box, 7) internet appliance, 8) entertainment device, and 9) base station.

54. A processor for processing instructions comprising

an instruction cache having a cache line;

a pipeline having at least one fetch stage and at least one decode stage;

an additional decode circuit having respective circuit portions situated for fetch purposes time-wise in parallel with said at least one fetch stage and said at least one decode stage, said additional decode circuit responsive to said cache line to generate at least one set of bits representing presence of plural branches in said cache line when plural branches occur and at least one different bit representing presence of a single branch in said cache line; and

a pattern storing circuit responsive to the additional decode circuit to hold and update a pattern of predicted branches.

55. The processor claimed in claim 54 wherein said pipeline further has an execute stage, the processor further comprising an actual history storing circuit situated for fetch purposes time-wise in parallel with at least one decode stage, said actual history storing circuit fed by said execute stage and operable to store a history of actual branches.

56. The processor claimed in claim 55 wherein said actual history storing circuit is coupled to said pattern storing circuit.

57. The processor claimed in claim 55 wherein said actual history circuit has flops fed by said execute stage, and actual history storing logic fed by said flops.

58. The processor claimed in claim 54 wherein said additional decode circuit is operable to identify each of the instructions in the cache line that are branch instructions if any.

59. The processor claimed in claim 54 wherein said additional decode circuit is operable to identify each respective position in said cache line at which each branch instruction is located in said cache line.

60. The processor claimed in claim 54 further comprising a branch history storing circuit responsive to the pattern to supply a branch Taken/Not-Taken prediction for a branch instruction in the cache line.

61. The processor claimed in claim 60 further comprising a branch target storing circuit for branch target addresses, said instruction cache responsive to said branch history storing circuit and said branch target storing circuit to retrieve the cache line.

62. The processor claimed in claim 54 wherein said pattern storing circuit is operable to update the pattern by concatenating plural bits already in the pattern with differing numbers of bits depending the presence of branches on the cache line.

63. The processor claimed in claim 54 further comprising a branch history storing circuit responsive to the pattern to supply a branch Taken/Not-Taken prediction for a branch instruction in the cache line, and wherein said pattern storing circuit is operable to update the pattern by concatenating plural bits already in the pattern with differing numbers of bits depending on the presence of branches on the cache line, together with at least one bit representing the branch Taken/Not-Taken prediction from the branch history storing circuit.

64. The processor claimed in claim 54 wherein said pattern storing circuit includes a register coupled to said additional decode circuit.

65. The processor claimed in claim 54 wherein said pipeline has an execute stage and said execute stage produces a signal representative of a mis-predicted branch, and said pattern storing circuit is responsive to the signal representative of a mis-predicted branch to update the pattern.

66. The processor claimed in claim 54 wherein said additional decode circuit is operable to detect branch instructions in said cache line wherein the branch instructions are from two different instruction sets.

67. The processor claimed in claim 54 wherein said additional decode circuit is operable to detect branch instructions in said cache line wherein a branch instruction wraps around from said cache line to a succeeding cache line.

68. The processor claimed in claim 54 wherein said additional decode circuit is operable to detect a branch instruction that wraps around from another cache line to said cache line.

69. The processor claimed in claim 54 wherein said additional decode circuit is operable to count branch instructions in said cache line wherein the branch instructions are of different lengths.

70. The processor claimed in claim 54 wherein said additional decode circuit is operable to count branch instructions in said cache line wherein the branch instructions are of different lengths, not counting a branch instruction that wraps around to a succeeding cache line.

71. The processor claimed in claim 54 wherein said additional decode circuit is operable to count branch instructions in said cache line wherein the branch instructions are of different lengths, not counting any branch instruction on the cache line that has an address less than a predicted address.

72. The processor claimed in claim 54 further comprising an instruction fetch queue fed by said instruction cache and wherein said at least part of said additional decode circuit is time-wise in parallel with said instruction fetch queue.

73. The processor claimed in claim 54 further comprising a branch target storing circuit for branch target addresses, said branch target storing circuit having a first way and a second way and being at least two-way set associative, said instruction cache responsive to said branch target storing circuit to retrieve the cache line.

74. A method of branch prediction in a processor having a pipeline with a fetch stage and a decode stage and an instruction cache having a cache line, the method comprising decoding branch instructions in the cache line time-wise in parallel with the fetch stage and the decode stage.

75. The method claimed in claim 74 further comprising generating at least one set of bits representing presence of plural branches in the cache line and at least one different bit representing presence of a single branch in said cache line.

76. The method claimed in claim 74 further comprising storing and updating a pattern of predicted branches based on the decoding of branch instructions.

77. The method claimed in claim 76 wherein the updating the pattern includes concatenating plural bits already in the pattern with differing numbers of bits depending the presence of branches on the cache line.

78. The method claimed in claim 76 further comprising responding to the pattern to supply a branch Taken/Not-Taken prediction for a branch instruction in the cache line, and the updating the pattern includes concatenating plural bits already in the pattern with differing numbers of bits depending the presence of branches on the cache line together with at least one bit representing the branch Taken/Not-Taken prediction from the branch history storing circuit.

79. The method claimed in claim 76 further comprising generating a series of actual branch history bits for fetch purposes time-wise in parallel with the decode stage.

80. The method claimed in claim 79 further comprising modifying the pattern of predicted branches with at least some of the actual branch history bits upon a mis-prediction.

81. The method claimed in claim 74 wherein the decoding branch instructions includes identifying each of the instructions in the cache line that are branch instructions if any.

82. The method claimed in claim 74 wherein the decoding branch instructions includes identifying each respective position in said cache line at which each branch instruction is located in said cache line.

83. The method claimed in claim 74 further comprising responding to the pattern to supply a branch Taken/Not-Taken prediction for a branch instruction in the cache line.

84. The method claimed in claim 83 further comprising retrieving the cache line in response to the branch Taken/Not-Taken prediction.

85. The method claimed in claim 74 wherein the decoding branch instructions includes detecting branch instructions in the cache line wherein the branch instructions are from two different instruction sets.

86. The method claimed in claim 74 wherein the decoding branch instructions includes detecting branch instructions in the cache line wherein a branch instruction wraps around from the cache line to a succeeding cache line.

87. The method claimed in claim 74 wherein the decoding branch instructions includes detecting a branch instruction that wraps around from another cache line to the cache line.

88. The method claimed in claim 74 wherein the decoding branch instructions includes counting branch instructions in the cache line wherein the branch instructions are of different lengths.

89. The method claimed in claim 74 wherein the decoding branch instructions includes counting branch instructions in the cache line wherein the branch instructions are of different lengths, not counting a branch instruction that wraps around to a succeeding cache line.

90. The method claimed in claim 74 wherein the decoding branch instructions includes counting branch instructions in the cache line wherein the branch instructions are of different lengths, not counting any branch instruction on the cache line that has an address less than a predicted address.

91. The method claimed in claim 74 further comprising queuing fetch instructions and parallelizing at least part of the cache line decoding time-wise with the queueing.

92. A wireless communications unit comprising

a wireless antenna;

a wireless transmitter and receiver coupled to said wireless antenna;

a microprocessor coupled to at least one of the transmitter and receiver, the microprocessor including an instruction cache having a cache line, a pipeline having at least one fetch stage and at least one decode stage, an additional decode circuit having respective circuit portions situated for fetch purposes time-wise in parallel with said at least one fetch stage and said at least one decode stage, said additional decode circuit responsive to said cache line to generate at least one set of bits representing presence of plural branches in said cache line and at least one different bit representing presence of a single branch in said cache line, and a pattern storing circuit responsive to the additional decode circuit to hold and update a pattern of predicted branches; and

a user interface coupled to said microprocessor;

whereby the wireless communication unit has increased instruction efficiency.

93. The wireless communications unit claimed in claim 92 wherein the instruction issue circuit is operable to issue as many as a plurality of candidate instructions concurrently, whereby the instruction efficiency of the wireless communications unit is further increased.

94. The wireless communications unit claimed in claim 92 further comprising a second microprocessor and a camera interface, said second microprocessor including a second instruction cache having a second cache line, another pipeline having at least one fetch stage and at least one decode stage, another additional decode circuit having respective circuit portions situated for fetch purposes time-wise in parallel with said at least one fetch stage and said at least one decode stage of said second microprocessor, said another additional decode circuit responsive to said second cache line to generate at least one set of bits representing presence of plural branches in said cache line and at least one different bit representing presence of a single branch in said cache line, and a second pattern storing circuit responsive to said another additional decode circuit to hold and update a second pattern of predicted branches for said second microprocessor.

95. The wireless communications unit claimed in claim 92 further comprising a second microprocessor and an additional wireless interface coupled to said second microprocessor, said second microprocessor including a second instruction cache having a second cache line, another pipeline having at least one fetch stage and at least one decode stage, another additional decode circuit having respective circuit portions situated for fetch purposes time-wise in parallel with said at least one fetch stage and said at least one decode stage of said second microprocessor, said another additional decode circuit responsive to said second cache line to generate at least one set of bits representing presence of plural branches in said cache line and at least one different bit representing presence of a single branch in said cache line, and a second pattern storing circuit responsive to said another additional decode circuit to hold and update a second pattern of predicted branches for said second microprocessor.

96. The wireless communications unit claimed in claim 92 wherein said microprocessor further includes security software including said plural branches.

97. The wireless communications unit claimed in claim 92 wherein said pipeline is selected from the group consisting of 1) reduced instruction set computing (RISC), 2) digital signal processing (DSP), 3) complex instruction set computing (CISC), 4) superscalar, 5) skewed pipelines, 6) in-order, 7) out-of-order, 8) very long instruction word (VLIW), 9) single instruction multiple data (SIMD), and 10) multiple instruction multiple data (MIMD).

98. A method of updating a first pattern for accessing a global history buffer in a branch predictor in a processor, the method comprising

detecting a number of branches on a cache line;

accessing the global history buffer with the first pattern to obtain a branch prediction datum; and

supplying an updated pattern including at least some bits of the first pattern, and a number of bits that depend on the number of branches detected on the cache line, and the updated pattern further including the branch prediction datum.

99. The method of claim 98 wherein the detecting ignores for purposes of establishing the number of branches, any branches on the cache line having an address prior to a predicted address.

100. The method of claim 98 wherein said number of bits is one less than the number of branches detected on the cache line disregarding any branches on the cache line having an address prior to a predicted address.

101. The method of claim 98 wherein the updated pattern has a number of bits equal to the first pattern.

102. Circuitry for a processor having an instruction cache with a cache line, the circuit comprising

a register for a first pattern;

a detector of a number of branches on the cache line;

a global history buffer responsive to the first pattern to obtain a branch prediction datum; and

an update circuit operable to supply an updated pattern to said register including at least some bits of the first pattern, and a number of bits that depend on the number of branches detected on the cache line, and the updated pattern further including the branch prediction datum.

103. The processor of claim 102 wherein the detector ignores for purposes of establishing the number of branches, any branches on the cache line having an address prior to a predicted address.

104. The processor of claim 102 wherein said number of bits is one less than the number of branches detected on the cache line disregarding any branches on the cache line having an address prior to a predicted address.

105. The processor of claim 102 wherein the updated pattern has a number of bits equal to the first pattern.

106. A process of manufacturing a processor comprising

preparing a particular design of a processor having an instruction cache having a cache line, a pipeline having at least one fetch stage and at least one decode stage, an additional decode circuit having respective circuit portions situated for fetch purposes time-wise in parallel with said at least one fetch stage and said at least one decode stage, said additional decode circuit to respond to said cache line to generate at least one set of bits representing presence of plural branches in said cache line when plural branches occur and at least one different bit representing presence of a single branch in said cache line, and a pattern storing circuit to respond to the additional decode circuit to hold and update a pattern of predicted branches;

verifying the design of said processor in simulation; and

manufacturing to produce a resulting processor according to the verified design.

107. The process of manufacturing of claim 106 further comprising using scan chain methodology on the resulting processor to verify the contents and timing of the additional decode circuit and said pattern storing circuit.

108. A process of manufacturing a processor comprising

preparing a particular design of a processor having a pipeline including a fetch stage and an execute stage, a first storing circuit associated with said fetch stage to store a history of actual branches, and a second storing circuit associated with said fetch stage to store a pattern of predicted branches, said second storing circuit coupled to said first storing circuit, said execute stage coupled back to said first storing circuit;

verifying the design of said processor in simulation; and

manufacturing to produce a resulting processor according to the verified design.

109. The process of manufacturing of claim 108 further comprising using scan chain methodology on the resulting processor to verify the contents and timing of the first storing circuit, the second storing circuit and said execute stage.