Parallelized execution of instruction sequences

• US 10,296,350 B2
• Filed: 03/31/2015
• Issued: 05/21/2019
• Est. Priority Date: 03/31/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): Coleman, Eric
• Application Number:
  US14/673,889
• Publication Number:
  US 20160291979A1
• Time in Patent Office: 1,512 Days
• CPC Class Codes: G06F 9/30065 Loop control instructions; iterative instructions, e.g. LOOP, REPEAT
• 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

Abstract

A method which includes, in a processor that processes instructions of program code, processing one or more of the instructions by a first hardware thread. Upon detecting that an instruction defined as a parallelization point has been fetched for the first thread, a second hardware thread is invoked to process at least one of the instructions at least partially in parallel with processing of the instructions by the first hardware thread.

Claims

1. A method, comprising:

in a processor that processes instructions of program code by a pipeline comprising at least first and second hardware threads, monitoring at least a first occurrence of a sequence of instructions being processed by the processor, and identifying in the first occurrence of the monitored sequence an instruction that is defined as a parallelization point;

after monitoring the first occurrence, processing one or more of the instructions, including a second occurrence of the sequence that was monitored, by the first hardware thread;

immediately in response to detecting that a fetch unit in the pipeline has fetched for the first hardware thread a given instruction in the second occurrence of the sequence that was monitored, before any decoding of the fetched given instruction in the pipeline, identifying, based on the monitoring of the first occurrence of that sequence, that the fetched given instruction is defined as a parallelization point; and

in response to identifying that the fetch unit in the pipeline has fetched the given instruction defined as the parallelization point for the first hardware thread, invoking the second hardware thread to process at least one of the instructions in the sequence that was monitored, which have one or more data dependencies with the instructions processed by the first hardware thread, wherein processing of the instructions by the second hardware thread is performed at least partially in parallel with processing of the instructions by the first hardware thread.

2. The method according to claim 1, wherein invoking the second hardware thread is performed before the processor begins to resolve dependencies in the instructions processed by the first hardware thread.

3. The method according to claim 1, wherein the parallelization point comprises a backward branch instruction.

4. The method according to claim 1, wherein the parallelization point comprises a function call.

5. The method according to claim 1, wherein the parallelization point is marked with an indication embedded in the program code.

6. The method according to claim 1, wherein invoking the second hardware thread comprises, upon invoking the second hardware thread, providing to the second hardware thread at least part of a flow-control trace to be traversed in fetching of the instructions for processing by the second hardware thread.

7. The method according to claim 6, further comprising selecting the flow-control trace from a set of possible traces using branch prediction.

8. The method according to claim 7, wherein the set of possible traces is stored in the processor, in a cache of the processor, or in a memory accessed by the processor.

9. The method according to claim 6, wherein the flow-control trace was previously monitored and recorded by the processor during execution of the program code.

10. The method according to claim 6, wherein invoking the second hardware thread comprises stalling the second hardware thread after invocation, until the at least part of the flow-control trace is available.

11. The method according to claim 6, wherein invoking the second hardware thread comprises providing only part of the flow-control trace upon invoking the second hardware thread, and providing a remainder of the flow-control trace during processing of the instructions by the second hardware thread.

12. The method according to claim 6, further comprising processing the instructions by the second hardware thread in accordance with the at least part of the flow-control trace, irrespective of a flow-control prediction provided by a branch-prediction unit of the processor.

13. The method according to claim 6, further comprising processing the instructions by the second hardware thread in accordance with a flow-control prediction provided by a branch-prediction unit of the processor, and flushing one or more future segments of the instructions upon detecting a discrepancy between the flow-control prediction and the at least part of the flow-control trace.

14. The method according to claim 6, further comprising processing the instructions by the second hardware thread in accordance with the flow-control prediction provided by a branch-prediction unit of the processor, and flushing one or more future segments of the instructions upon detecting a violation of a specification of register access by the instructions.

15. The method according to claim 1, further comprising flushing one or more future segments in response to a branch mis-prediction event in processing of the instructions by the second hardware thread.

16. The method according to claim 1, further comprising processing the instructions by the first and second hardware threads in accordance with a same specification of register access that is indicative of data dependencies, and in accordance with a single flow-control trace.

17. The method according to claim 1, further comprising processing the instructions by the first and second hardware threads in accordance with respective different specifications of register access that are indicative of data dependencies, and in accordance with respective different flow-control traces.

18. The method according to claim 1, wherein invoking the second hardware thread comprises invoking multiple hardware threads to process multiple segments in response to detecting the parallelization point.

19. The method according to claim 1, wherein invocation of the second hardware thread is permitted only if a first segment processed by the first hardware thread is non-speculative.

20. The method according to claim 1, wherein invocation of the second hardware thread is permitted regardless of whether a first segment processed by the first hardware thread is speculative or non-speculative.

21. The method according to claim 1, wherein hardware threads are invoked to execute segments of the instructions in the order of appearance of the segments in the program code.

22. A processor, comprising:

an execution pipeline, which comprises at least first and second hardware threads and which is configured to process instructions of program code; and

parallelization circuitry, which is configured to;

monitor at least a first occurrence of a sequence of instructions being processed by the execution pipeline, and identifying in the first occurrence of the monitored sequence an instruction that is defined as a parallelization point;

after monitoring the first occurrence, invoke the first hardware thread to process one or more of the instructions, including a second occurrence of the sequence that was monitored;

immediately in response to detecting that a fetch unit in the execution pipeline has fetched for the first hardware thread a given instruction in the second occurrence of the sequence that was monitored, before any decoding of the fetched given instruction in the execution pipeline, identify, based on the monitoring of the first occurrence of that sequence, that the fetched given instruction is defined as a parallelization point; and

in response to identifying that the fetch unit in the pipeline has fetched the given instruction defined as the parallelization point for the first hardware thread, invoke the second hardware thread to process at least one of the instructions in the sequence that was monitored, which have one or more data dependencies with the instructions processed by the first hardware thread, wherein processing of the instructions by the second hardware thread is performed at least partially in parallel with processing of the instructions by the first hardware thread.

23. The processor according to claim 22, wherein the parallelization circuitry is configured to invoke the second hardware thread before the execution pipeline begins to resolve dependencies in the instructions processed by the first hardware thread.

24. The processor according to claim 22, wherein the parallelization circuitry is configured to detect the parallelization point by detecting a backward branch instruction.

25. The processor according to claim 22, wherein the parallelization circuitry is configured to detect the parallelization point by detecting a function call.

26. The processor according to claim 22, wherein the parallelization point is determined by an indication embedded in the program code.

27. The processor according to claim 22, wherein the parallelization circuitry is configured, upon invoking the second hardware thread, to provide to the second hardware thread at least part of a flow-control trace to be traversed in fetching of the instructions for processing by the second hardware thread.

28. The processor according to claim 27, wherein the parallelization circuitry is configured to select the flow-control trace from a set of possible traces using branch prediction.

29. The processor according to claim 28, wherein the set of possible traces is stored in the processor, in a cache of the processor, or in a memory accessed by the processor.

30. The processor according to claim 27, wherein the flow-control trace was previously monitored and recorded by the processor during execution of the program code.

31. The processor according to claim 27, wherein the parallelization circuitry is configured to stall the second hardware thread after invocation, until the at least part of the flow-control trace is available.

32. The processor according to claim 27, wherein the parallelization circuitry is configured to provide only part of the flow-control trace upon invoking the second hardware thread, and to provide a remainder of the flow-control trace during processing of the instructions by the second hardware thread.

33. The processor according to claim 27, wherein the parallelization circuitry is configured to process the instructions by the second hardware thread in accordance with the at least part of the flow-control trace, irrespective of a flow-control prediction provided by a branch-prediction unit of the processor.

34. The processor according to claim 27, wherein the parallelization circuitry is configured to process the instructions by the second hardware thread in accordance with a flow-control prediction provided by a branch-prediction unit of the processor, and to flush one or more future segments of the instructions upon detecting a discrepancy between the flow-control prediction and the at least part of the flow-control trace.

35. The processor according to claim 27, wherein the parallelization circuitry is configured to process the instructions by the second hardware thread in accordance with the flow-control prediction provided by a branch-prediction unit of the processor, and to flush one or more future segments of the instructions upon detecting a violation of a specification of register access by the instructions.

36. The processor according to claim 22, wherein the parallelization circuitry is configured to flush one or more future segments in response to a branch mis-prediction event in processing of the instructions by the second hardware thread.

37. The processor according to claim 22, wherein the parallelization circuitry is configured to process the instructions by the first and second hardware threads in accordance with a same specification of register access that is indicative of data dependencies, and in accordance with a single flow-control trace.

38. The processor according to claim 22, wherein the parallelization circuitry is configured to process the instructions by the first and second hardware threads in accordance with respective different specifications of register access that is indicative of data dependencies, and in accordance with respective different flow-control traces.

39. The processor according to claim 22, wherein the parallelization circuitry is configured to invoke multiple hardware threads to process multiple segments in response to detecting that the parallelization point has been reached.

40. The processor according to claim 22, wherein the parallelization circuitry is configured to permit invocation of the second hardware thread only if a first segment processed by the first hardware thread is non-speculative.

41. The processor according to claim 22, wherein the parallelization circuitry is configured to permit invocation of the second hardware thread regardless of whether a first segment processed by the first hardware thread is speculative or non-speculative.

42. The processor according to claim 22, wherein the parallelization circuitry is configured to invoke hardware threads to execute segments of the instructions in the order of appearance of the segments in the program code.