Global history vector recovery circuits and methods and systems using the same

• US 6,745,323 B1
• Filed: 08/03/2000
• Issued: 06/01/2004
• Est. Priority Date: 08/03/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sinharoy, Balaram
• Primary Examiner(s): TSAI, HENRY
• Application Number:
  US09/631,725
• Time in Patent Office: 1,398 Days
• Field of Search: 712/240, 712/239, 712/238, 712/237, 712/235, 712/234, 712/233, 712/232, 712/220, 712/205, 712/207, 712/23, 712/236
• US Class Current: 712/240
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

A system and method for recovering a global history vector is implemented. In deeply pipelined central processing unit (CPU) architecture instruction fetches may precede execution by several processor cycles. A global history vector (GHV) may be used in predicting the branches in a current fetch cycle. Fetch redirection events, such as a cache miss, or a branch misprediction may lead to loss of synchronization of instruction fetches and the GHV. To recover the GHV following a redirection event, registers are provided to hold a GHV being used to predict branches in a current fetch cycle and two subsequent GHVs. On the occurrence of a redirection event, a fetch redirection is generated. GHV update logic detects the fetch redirection and resets the current GHV to a selected one of the stored values.

Claims

1. A method of recovering a global history vector comprising the steps of:

storing a first global history vector generated in a first cycle in a first storage element;

storing a second global history vector generated in a first succeeding cycle in a second storage element;

storing a third global history vector generated in a second succeeding cycle in a third storage element;

detecting a fetch redirection event, wherein said fetch redirection event corresponds to one of a predetermined set of fetch redirection event types; and

resetting a current global history vector to a value derived from a selected global history vector selected from one of said first, second and third storage elements in response to detecting said redirection event.

2. The method of claim 1 wherein said step of resetting said current global history vector comprises the step of setting a data value in a fourth storage element to said value derived from said selected global history vector, said data value in fourth storage element forming said current global history vector.

3. The method of claim 1 wherein said step of detecting said event includes the steps of:

generating an event signal corresponding to a type of said fetch redirection event; and

detecting said event signal.

4. The method of claim 1 wherein said first, second and third storage elements are included in an entry in a queue, said entry corresponding to an instruction fetched in a second cycle.

5. The method of claim 4 wherein said second cycle lags said first cycle by a predetermined number of periods of a processor cycle.

6. The method of claim 1 further comprising the step of shifting a preselected value into said selected global history vector, and wherein said value derived from said selected global history vector is a result of said shifting step.

7. The method of claim 1 wherein said value derived from said selected global history vector is said selected global history vector.

8. The method of claim 6 wherein said shifting step comprises:

determining a bit to be shifted into said selected global history vector in response to a first type of said redirection event and a branch prediction; and

asserting a shift enable signal, said result being generated in response to said shift enable signal.

9. The method of claim 2 wherein said fourth storage element is selected from the group consisting of a previous advance path register and a previous hold path register in response to a corresponding value of a counter.

10. The method of claim 2 wherein said step of resetting said current global history vector further comprises the step of setting said data value in said fourth storage element in a register operable for providing a global history vector for generating branch predictions for one or more branches in a current fetch group.

11. The method of claim 2 wherein said step of setting said data value in said fourth storage element is performed in response to an occurrence of said fetch redirection event.

12. The method of claim 4 wherein said step of resetting said current global history vector comprises the steps of

setting a first data value derived from a first selected one of said first, second and third global history vectors in a fifth storage element;

and

setting a second data value derived from a second selected one of said first, second and third global history vectors in a sixth storage element, wherein said steps of setting said first and second data values are in response to detecting a fetch redirection of a first type.

13. The method of claim 12 wherein said first type is a branch misprediction type redirection.

14. The method of claim 12 wherein said step of resetting said current global history vector further comprises the step of setting, as said current global history value, a value selected from one of said fifth storage element and said sixth storage element, wherein said value selected is selected in response to a value in a counter.

15. The method of claim 14 wherein said counter is incremented each instruction fetch cycle of a processor, and wherein said counter saturates at a predetermined count value.

16. A processing system comprising:

a central processing unit (CPU), the CPU including;

a first storage element operable for storing a first global history vector generated in a first cycle of said CPU;

a second storage element operable for storing a second global history vector generated in a first succeeding cycle of said CPU;

a third storage element operable for storing a third global history vector generated in a second succeeding cycle of said CPU;

first logic operable for detecting a fetch redirection event, wherein said fetch redirection event corresponds to one of a predetermined set of fetch redirection event types; and

second logic operable for resetting a current global history vector to a value derived from a selected global history vector selected from one of said first, second and third storage elements in response to detecting said redirection event.

17. The system claim 16 wherein said second logic comprises:

a fourth storage element; and

third logic for setting a data value in said fourth storage element to said value derived from said selected global history vector, said data value in fourth storage element forming said current global history vector.

18. The system of claim 16 wherein said first logic includes:

logic operable for generating an event signal corresponding to a type of said fetch redirection event; and

logic operable for receiving said event signal.

19. The system of claim 16 wherein said CPU further comprises a queue having a plurality of entries, and wherein said first, second and third storage elements are included in an entry of said plurality, said entry associated with an instruction fetched in a second cycle.

20. The system of claim 19 wherein said second cycle lags said first cycle by a predetermined number of periods of a processor cycle.

21. The system of claim 16 wherein said CPU further comprises a shift register operable for shifting a preselected value into said selected global history vector, and wherein said value derived from said selected global history vector is an output value from said shift register.

22. The system of claim 16 wherein said value derived from said selected global history vector is said selected global history vector.

23. The system of claim 21 wherein said CPU further comprises:

fourth logic operable for determining a bit to be shifted into said selected global history vector in response to a first type of said redirection event and a branch prediction; and

fifth logic for generating a shift enable signal, said output value being generated in response to said shift enable signal.

24. The system of claim 17 wherein said CPU further includes:

a previous advance path register;

a previous hold path register, and wherein said fourth storage element is selected from a group consisting of said previous advance path register and said previous hold path register in response to a corresponding value of a counter.

25. The system of claim 17 wherein said CPU further comprises:

a register operable for providing a global history vector for generating branch predictions for one or more branches in a current fetch group, and wherein said second logic further comprises;

logic for setting said data value in said fourth storage element in said register.

26. The system of claim 17 wherein said second logic sets said data value in said fourth storage element in response to an occurrence of said fetch redirection event.

27. The system of claim 19 wherein said second logic comprises:

sixth logic operable for setting a first data value derived from a first selected one of said first, second and third global history vectors in a fifth storage element; and

seventh logic operable for setting a second data value derived from a second selected one of said first, second and third global history vectors in a sixth storage element, and wherein said sixth and seventh logic set said first and second data values response to detecting a fetch redirection of a first type.

28. The system of claim 27 wherein said first type is a branch misprediction type redirection.

29. The system of claim 27 wherein said CPU further comprises a counter, and wherein said second logic further comprises:

eighth logic operable for outputting one of said first data value from said fifth storage element and said second data values from said sixth storage element in response to a corresponding predetermined value in said counter; and

ninth logic operable for setting said current global history value to a data value output by said eighth logic.

30. The system of claim 29 wherein said counter is incremented each instruction fetch cycle of said CPU, and wherein said counter saturates at a predetermined count value.