CHECK POINTING A SHIFT REGISTER WITH A CIRCULAR BUFFER

• US 20180321852A1
• Filed: 07/16/2018
• Published: 11/08/2018
• Est. Priority Date: 07/08/2015
• Status: Active Grant

• Current Assignee: MIPS Tech, LLC
• Original Assignee: MIPS Tech, LLC
• Inventors: Day, Philip, Bailey, Julian
• Granted Patent: US 10,642,527 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 5/01 for shifting, e.g. justifying, scaling, normalising digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00
• CPC Class Codes: G06F 5/017 using recirculating storage elements
• CPC Class Codes: G06F 9/30116 Shadow registers, e.g. coupled registers, not forming part of the register space
• CPC Class Codes: G06F 9/30134 Register stacks; shift registers
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

Hardware structures for check pointing a main shift register one or more times which include a circular buffer used to store the data elements most recently shifted onto the main shift register which has an extra data position for each check point and an extra data position for each restorable point in time; an update history shift register which has a data position for each check point which is used to store information indicating whether the circular buffer was updated in a particular clock cycle; a pointer that identifies a subset of the data positions of the circular buffer as active data positions; and check point generation logic that derives each check point by selecting a subset of the active data positions based on the information stored in the update history shift register.

Claims

1. A hardware structure for check pointing comprising:

a main shift register;

a circular buffer having a plurality of data positions for storing data elements, wherein the plurality of data positions includes a data position for each data position of the main shift register, an additional data position for each of one or more check points of the main shift register, and an additional data position for each of a plurality of points in time;

a pointer configured to identify a plurality of active data positions from the plurality of data positions of the circular buffer;

an update history shift register having a data position for each check point; and

check point generation logic configured to derive each check point for restoration based on selecting a subset of the plurality of active data positions identified by the pointer and on information stored in the update history shift register.

2. The hardware structure of claim 1 wherein the main shift register is restorable to a plurality of points in time.

3. The hardware structure of claim 1 wherein the check points are triggered by check point trigger events.

4. The hardware structure of claim 3 wherein the number of check points is at least two, and the check point generation logic is configured to derive a second check point representing the main shift register prior to the two most recent check point trigger events by:

counting the number of the first two data positions of the update history shift register that comprise information indicating that the circular buffer was updated; and

selecting a subset of the plurality of active data positions that is offset from the first subset of data positions by the count.

5. The hardware structure of claim 1 wherein data positions of the update history shift register store information indicating whether the circular buffer was updated in a same clock cycle as a particular check point trigger event.

6. The hardware structure of claim 1 wherein the main shift register comprises a global history register for tracking conditional branch instruction outcomes.

7. The hardware structure of claim 1 wherein the active data positions include a first subset of the plurality of data positions of the circular buffer that represent the main shift register and an additional data position for each check point.

8. The hardware structure of claim 7 wherein a selected subset of the plurality of active data positions for a particular check point can have an offset from the first subset of data positions by none, one, or more than one data position.

9. The hardware structure of claim 8 wherein the check point generation logic is configured to determine the offset from the first subset of data positions for a particular check point by evaluating the information stored in a number of relevant data positions of the update history shift register.

10. The hardware structure of claim 9 wherein each check point represents the main shift register prior to a number of check point trigger events;

and the number of relevant data positions of the update history shift register for a particular check point is equal to the number of check point trigger events for that check point.

11. The hardware structure of claim 9 wherein the offset is equal to a count of relevant data positions of the update history shift register that comprise information indicating that the circular buffer was updated.

12. The hardware structure of claim 8 wherein the check point generation logic is configured to derive a first check point representing the main shift register prior to a most recent check point trigger event by:

determining, in the check point generation logic, whether a first data position of the update history shift register comprises information indicating that the circular buffer was updated;

in response to determining that the first data position of the update history shift register comprises information, indicating that the circular buffer was not updated, selecting, in the check point generation logic, the first subset of data positions of the circular buffer; and

in response to determining, in the check point generation logic, that the first data position of the update history shift register comprises information indicating that the circular buffer was updated, selecting, in the check point generation logic, a subset of the plurality of active data positions that is offset from the first subset of data positions by one data position.

13. The hardware structure of claim 1 further comprising update logic configured to, in each clock cycle:

determine, in the update logic, whether a check point trigger event has occurred;

in response to determining that a check point trigger event has occurred, determine, in the update logic, whether the circular buffer is updated in the current clock cycle;

in response to determining that the circular buffer is updated in the current clock cycle, shift information onto the update history shift register indicating the circular buffer has been updated; and

in response to determining that the circular buffer is not updated in the current clock cycle, shift information onto the update history shift register indicating the circular buffer has not been updated.

14. The hardware structure of claim 1 further comprising a restoration buffer having a plurality of data positions, each data position of the restoration buffer storing a copy of information of the update history shift register and a copy of the pointer at a particular point in time.

15. The hardware structure of claim 14 further comprising restoration logic, the restoration logic configured to, in response to receiving an indication that a restoration is to be performed, restore the update history shift register and the pointer to a particular point in time using the copies stored in the restoration buffer.

16. The hardware structure of claim 15 wherein the main shift register is a global history register and each data element of the global history register indicates a predicted outcome for a conditional branch instruction;

and the indication that a restoration is to be performed is an indication that a conditional branch instruction was mis-predicted.

17. The hardware structure of claim 1 wherein the main shift register is a global history register and each data element of the global history register indicates a predicted outcome for a conditional branch instruction.

18. The hardware structure of claim 1 wherein the hardware structure comprises a processor.

19. The hardware structure of claim 1 wherein the hardware structure comprises an instruction fetch unit.

20. A method for deriving one or more check points for a main shift register comprising:

storing data elements in a plurality of data positions of a circular buffer, the plurality of data positions including a data position for each data position of the main shift register, an additional data position for each check point, and an additional data position for each of a plurality of points in time;

storing an index to the circular buffer in a pointer;

storing information indicating whether the circular buffer was updated in a same clock cycle as a particular check point trigger event in a data position of an update history shift register; and

deriving each check point by selecting, with hardware logic, a subset of a plurality of active data positions based on the information stored in the update history shift register.

21. The method of claim 20 wherein the index identifies a plurality of active data positions of the plurality of data positions of the circular buffer, wherein the plurality of active data positions include a first subset of the plurality of data positions of the circular buffer that represent the main shift register and an additional data position for each check point.

22. The method of claim 20 wherein a selected subset of the plurality of active data positions for a particular check point can be offset from the first subset of data positions by none, one, or more than one data position.

23. The method of claim 22 wherein the offset from the first subset of data positions for a particular check point is determined by the hardware logic evaluating the information stored in a number of relevant data positions of the update history shift register.

24. The method of claim 23 wherein each check point represents the main shift register prior to a number of check point trigger events;

and the number of relevant data positions of the update history shift register for a particular check point is equal to the number of check point trigger events for that check point.

25. The method of claim 23 wherein the offset is equal to a count of relevant data positions of the update history shift register that comprise information indicating that the circular buffer was updated.

26. The method of claim 20 further comprising storing a copy of the information of the update history shift register and a copy of the pointer at a particular point in time in a data position in a restoration buffer.