Run-time parallelization of code execution based on an approximate register-access specification

• US 9,715,390 B2
• Filed: 04/19/2015
• Issued: 07/25/2017
• Est. Priority Date: 04/19/2015
• 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): Xiao, Yuqing
• Application Number:
  US14/690,424
• Publication Number:
  US 20160306633A1
• Time in Patent Office: 828 Days
• Field of Search: 712217, 712216, 712219
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 9/3808 for instruction reuse, e.g. trace cache, branch target cache
• CPC Class Codes: G06F 9/382 Pipelined decoding, e.g. using predecoding
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers
• 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/3854 Instruction completion, e.g. retiring, committing or graduating
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00
• CPC Class Codes: G06F 9/3875 Pipelining a single stage, e.g. superpipelining
• CPC Class Codes: G06F 9/455 Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements

Abstract

A method includes, in a processor that processes instructions of program code, processing a first segment of the instructions. One or more destination registers are identified in the first segment using an approximate specification of register access by the instructions. Respective values of the destination registers are made available to a second segment of the instructions only upon verifying that the values are valid for readout by the second segment in accordance with the approximate specification. The second segment is processed at least partially in parallel with processing of the first segment, using the values made available from the first segment.

Claims

1. A method, comprising:

in a processor that processes instructions of program code, processing a first segment of the instructions;

constructing an approximate specification that defines register access by the instructions in the first segment by indicating for one or more destination registers that a respective number of writes in the first segment to each of the one or more destination registers exceeded a predefined threshold, without specifying the respective number;

making respective values of the one or more destination registers available to a second segment of the instructions only upon verifying that the values are known to be valid for readout by the second segment even though the approximate specification is not exact in pointing to the instructions that are last to write to the destination registers; and

processing the second segment at least partially in parallel with processing of the first segment, using the values made available from the first segment.

2. The method according to claim 1, wherein processing the second segment comprises processing at least one instruction in the second segment, which according to the approximate specification does not depend on the values, before the values are made available.

3. The method according to claim 1, wherein verifying that a value of a destination register is valid for readout by the second segment comprises verifying that all conditional branch instructions in the first segment that precede a last write to the destination register are resolved.

4. The method according to claim 1, wherein verifying that a value of a destination register is valid for readout by the second segment comprises verifying that a last write to the destination register has been fully committed in the first segment.

5. The method according to claim 1, wherein verifying that the values are valid for readout by the second segment comprises verifying that a last write instruction, to any of the destination registers in the first segment, has been fully or speculatively committed.

6. The method according to claim 1, wherein processing of the second segment is performed without providing at least one of a flow-control trace and a scoreboard to the second segment.

7. The method according to claim 1, wherein processing of the second segment is performed without providing a flow-control trace to the first segment.

8. The method according to claim 1, wherein processing the second segment comprises continuing processing of the second segment regardless of branch mis-prediction occurring in the first segment.

9. The method according to claim 1, and comprising flushing the second segment in response to identifying a violation of the approximate specification by the first segment.

10. The method according to claim 9, wherein the violation comprises writing to a register that, in accordance with the approximate specification, is not to be written to, or writing to a register more times than a number of writes specified for the register in the approximate specification.

11. The method according to claim 9, wherein the violation comprises flushing of the first segment.

12. The method according to claim 9, wherein flushing the second segment in response to the violation is performed only if a value of a destination register causing the violation in the first segment is actually used in the second segment.

13. The method according to claim 1, and comprising flushing the second segment in response to identifying that the first segment failed to reach a predefined location in the program code.

14. The method according to claim 13, wherein identifying that the first segment failed to reach the predefined location comprises detecting that processing of the first segment reached an instruction that is predefined as a parallelization point for invoking one or more subsequent segments.

15. The method according to claim 13, wherein identifying that the first segment failed to reach the predefined location comprises detecting that processing of the first segment has processed more than a predefined amount of the program code.

16. A processor, comprising:

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

parallelization circuitry, which is configured to invoke a first hardware thread to process a first segment of the instructions, to construct an approximate specification that defines register access by the instructions by indicating for one or more destination registers that a respective number of writes in the first segment to each of the one or more destination registers exceeded a predefined threshold, without specifying the respective number, to make respective values of the one or more destination registers available to a second hardware thread, which processes a second segment of the instructions, only upon verifying that the values are known to be valid for readout by the second segment even though the approximate specification is not exact in pointing to the instructions that are last to write to the destination registers, so as to process the second segment by the second hardware thread at least partially in parallel with processing of the first segment using the respective values.

17. The processor according to claim 16, wherein the parallelization circuitry is configured to invoke the second thread to process at least one instruction in the second segment, which according to the approximate specification does not depend on the values, before the values are made available.

18. The processor according to claim 16, wherein the parallelization circuitry is configured to verify that a value of a destination register is valid for readout by the second segment, by verifying that all conditional branch instructions in the first segment that precede a last write to the destination register are resolved.

19. The processor according to claim 16, wherein the parallelization circuitry is configured to verify that a value of a destination register is valid for readout by the second segment, by verifying that a last write to the destination register has been fully committed in the first segment.

20. The processor according to claim 16, wherein the parallelization circuitry is configured to verify that the values are valid for readout by the second segment, by verifying that a last write instruction, to any of the destination registers in the first segment, has been fully or speculatively committed.

21. The processor according to claim 16, wherein processing of the second segment is performed without providing at least one of a flow-control trace and a scoreboard to the second segment.

22. The processor according to claim 16, wherein processing of the second segment is performed without providing a flow-control trace to the first segment.

23. The processor according to claim 16, wherein processing of the second segment continues regardless of branch mis-prediction occurring in the first segment.

24. The processor according to claim 16, wherein the parallelization circuitry is configured to flush the second segment in response to identifying a violation of the approximate specification by the first segment.

25. The processor according to claim 24, wherein the violation comprises writing to a register that, in accordance with the approximate specification, is not to be written to, or writing to a register more times than a number of writes specified for the register in the approximate specification.

26. The processor according to claim 16, wherein the parallelization circuitry is configured to flush the second segment in response to identifying that the first segment failed to reach a predefined location in the program code.

27. The processor according to claim 26, wherein the parallelization circuitry is configured to identify that the first segment failed to reach the predefined location by detecting that processing of the first segment reached an instruction that is predefined as a parallelization point for invoking one or more subsequent segments.