Run-time code parallelization with monitoring of repetitive instruction sequences during branch mis-prediction

• US 9,135,015 B1
• Filed: 12/25/2014
• Issued: 09/15/2015
• Est. Priority Date: 12/25/2014
• Status: Active Grant

• Current Assignee: Centipede Semi ltd.
• Original Assignee: Centipede Semi ltd.
• Inventors: Mizrahi, Noam, Mandler, Alberto, Koren, Shay, Friedmann, Jonathan
• Primary Examiner(s): Faherty, Corey S
• Application Number:
  US14/583,119
• Time in Patent Office: 264 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 11/30 Monitoring
• CPC Class Codes: G06F 11/302 where the computing system component is a software system
• CPC Class Codes: G06F 11/3055 Monitoring arrangements for monitoring the status of the computing system or of the computing system component, e.g. monitoring if the computing system is on, off, available, not available error or fault processing without redundancy G06F11/0703; error detection or correction by redundancy in data representation G06F11/08; error detection or correction by redundancy in operation G06F11/14; error detection or correction by redundancy in hardware G06F11/16
• CPC Class Codes: G06F 11/3065 Monitoring arrangements determined by the means or processing involved in reporting the monitored data error or fault reporting or logging G06F11/0766
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 9/3808 for instruction reuse, e.g. trace cache, branch target cache
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00

Abstract

A method includes, in a processor that executes instructions of program code, monitoring the instructions in a segment of a repetitive sequence of the instructions so as to construct a specification of register access by the monitored instructions. In response to detecting a branch mis-prediction in the monitored instructions, the specification is corrected so as to compensate for the branch mis-prediction. Execution of the repetitive sequence is parallelized based on the corrected specification.

Claims

1. A method, comprising:

in a processor that executes instructions of program code, monitoring a repetitive sequence of the instructions that exhibits a constant, recurring register access, and constructing a specification that specifies the recurring register access;

in response to detecting a branch mis-prediction in the monitored instructions, rolling-back the recurring register access specified in the specification so as to compensate for a deviation in the recurring register access caused by the branch mis-prediction; and

parallelizing execution of at least some of the instructions based on the specification having the rolled-back recurring register access.

2. The method according to claim 1, wherein monitoring the instructions further comprises generating a flow-control trace traversed by the monitored instructions, and comprising correcting the flow-control trace so as to compensate for the branch mis-prediction.

3. The method according to claim 1, and comprising continuing monitoring the instructions during parallelized execution.

4. The method according to claim 1, and comprising continuing to monitor the instructions and construct the specification after rolling-back the recurring register access.

5. The method according to claim 1, wherein rolling-back the recurring register access comprises terminating monitoring of a segment of the instructions in which the branch mis-prediction occurred, and discarding at least part of the specification of the recurring register access collected in the segment.

6. The method according to claim 1, wherein rolling-back the recurring register access comprises rolling-back the recurring register access, based on the instructions following the branch mis-prediction, to a previous state corresponding to an instruction at or prior to a branch instruction in which the branch mis-prediction occurred.

7. The method according to claim 6, wherein monitoring the instructions comprises recording in the specification a location in the sequence of a last write operation to a register, and wherein rolling-back the recurring register access comprises correcting the location of the last write operation.

8. The method according to claim 7, wherein recording the location of the last write operation comprises incrementing a count of write operations to the register, and wherein correcting the location comprises decrementing the count to a value corresponding to the branch instruction in which the branch mis-prediction occurred.

9. The method according to claim 1, wherein monitoring the instructions comprises recording in the specification a classification of registers accessed by the monitored instructions, and wherein rolling-back the recurring register access comprises re-classifying one or more of the registers so as to compensate for the branch mis-prediction.

10. The method according to claim 1, wherein monitoring the instructions comprises saving one or more states of the specification at or prior to one or more respective branch instructions along a monitored segment of the instructions, and wherein rolling-back the recurring register access comprises reverting to a saved state corresponding to an instruction at or prior to a branch instruction in which the branch mis-prediction occurred.

11. The method according to claim 10, wherein saving the states comprises saving the states only for a partial subset of the branch instructions along the monitored segment.

12. The method according to claim 11, and comprising selecting the partial subset of the branch instructions in accordance with a directive in the program code or from a compiler of the program code.

13. The method according to claim 11, and comprising selecting the partial subset of the branch instructions based on a criterion evaluated at runtime.

14. The method according to claim 1, wherein monitoring the instructions comprises generating a flow-control trace of the monitored instructions based on branch instructions being fetched from memory in an execution pipeline of the processor.

15. The method according to claim 1, wherein monitoring the instructions comprises generating a flow-control trace of the monitored instructions based on branch instructions being decoded in an execution pipeline of the processor.

16. The method according to claim 1, wherein monitoring the instructions comprises generating a flow-control trace of the monitored instructions based jointly on branch instructions being fetched from memory, and on the branch instructions being decoded, in an execution pipeline of the processor.

17. The method according to claim 1, wherein monitoring the instructions comprises recording in the specification a location in the sequence of a last write operation to a register, based on the instructions being decoded in an execution pipeline of the processor.

18. The method according to claim 1, wherein monitoring the instructions comprises recording in the specification a location in the sequence of a last write operation to a register, based on the instructions being executed in an execution pipeline of the processor.

19. The method according to claim 1, wherein monitoring the instructions comprises recording in the specification a location in the sequence of a last write operation to a register, based on the instructions that are committed and are not flushed due to the branch mis-prediction.

20. The method according to claim 1, wherein monitoring the instructions comprises collecting the register access only after evaluating respective branch conditions of conditional branch instructions of the sequence.

21. The method according to claim 1, wherein monitoring the instructions comprises generating a flow-control trace for the monitored instructions, including for a branch instruction that is not known to a branch prediction unit of the processor.

22. A processor, comprising:

an execution pipeline, which is configured to execute instructions of program code; and

a monitoring unit, which is configured to monitor a repetitive sequence of the instructions that exhibits a constant, recurring register access, to construct a specification that specifies the recurring register access, to roll-back the recurring register access specified in the specification in response to detecting a branch mis-prediction in the monitored instructions so as to compensate for a deviation in the recurring register access caused by the branch mis-prediction, and to parallelize execution of at least some of the instructions based on the specification having the rolled-back recurring register access.

23. The processor according to claim 22, wherein the monitoring unit is further configured to generate a flow-control trace traversed by the monitored instructions, and to correct the flow-control trace so as to compensate for the branch mis-prediction.

24. The processor according to claim 22, wherein the monitoring unit is configured to roll-back the recurring register access by terminating monitoring of the instructions of a segment of the instructions in which the branch mis-prediction occurred, and discarding the specification of the register access collected in the segment.

25. The processor according to claim 22, wherein the monitoring unit is configured to roll-back the recurring register access, based on the instructions following the branch mis-prediction, to a previous state corresponding to an instruction at or prior to a branch instruction in which the branch mis-prediction occurred.

26. The processor according to claim 22, wherein the monitoring unit is configured to record in the specification a classification of registers accessed by the monitored instructions, and to roll-back the recurring register access by re-classifying one or more of the registers so as to compensate for the branch mis-prediction.

27. The processor according to claim 22, wherein the monitoring unit is configured to save one or more states of the specification at or prior to one or more respective branch instructions along a monitored segment of the instructions, and to roll-back the recurring register access by reverting to a saved state corresponding to an instruction at or prior to a branch instruction in which the branch mis-prediction occurred.

28. The processor according to claim 22,

wherein the monitoring unit is configured to generate a flow-control trace of the monitored instructions based on one of:

branch instructions being fetched from memory in the execution pipeline;

the branch instructions being decoded in the execution pipeline; and

both the branch instructions being fetched from memory and the branch instructions being decoded.

29. The processor according to claim 22, wherein the monitoring unit is configured to record in the specification a location in the sequence of a last write operation to a register, based on at least one of:

the instructions being decoded in the execution pipeline;

the instructions being executed in the execution pipeline; and

the instructions that are committed and are not flushed due to the branch mis-prediction.

30. The processor according to claim 22, wherein the monitoring unit is configured to collect the register access only after evaluating respective branch conditions of conditional branch instructions of the sequence.