Method for executing multithreaded instructions grouped into blocks
A method for executing multithreaded instructions grouped into blocks. The method includes receiving an incoming instruction sequence using a global front end; grouping the instructions to form instruction blocks, wherein the instructions of the instruction blocks are interleaved with multiple threads; scheduling the instructions of the instruction block to execute in accordance with the multiple threads; and tracking execution of the multiple threads to enforce fairness in an execution pipeline.
1. A method of executing multithreaded instructions grouped into blocks, the method comprising:
receiving an incoming instruction sequence at a front end of an execution pipeline;
grouping instructions from the instruction sequence to form instruction blocks, where a first group of instruction blocks are a part of a first thread of execution and a second group of instruction blocks are a part of a second thread of execution;
storing the first group of instruction blocks and the second group of instruction blocks in a scheduler array, where a first commit pointer points to a location in the scheduler array for a next block of the first group to be executed and a second commit pointer points to a next block of the second group to be execute;
scheduling the instructions of the instruction blocks to execute in accordance with a position in the scheduler array; and
tracking execution of the first thread and second thread to enforce a fairness policy using allocation counters to track a number of instruction blocks in the scheduler array for each thread.
2. The method of claim 1 , wherein each allocation counter tracks a number of entries in a correlated thread pointer map.
3. The method of claim 1 , wherein the fairness policy prevents any thread from exceeding an allocation threshold.
4. The method of claim 1 , further comprising:
tracking an array entry to place a next block in the scheduler array for each thread using a separate allocate pointer.
5. The method of claim 1 , wherein dynamic counter-based allocation is used to allocate instruction blocks belonging to different threads within a scheduler array to implement the fairness policy.
6. The method of claim 1 , wherein a dynamic counter-based
allocation is used to allocate blocks of threads within the scheduler array to implement a dynamic ratio of thread allocation.
7. The method of claim 6 , wherein the dynamic counter-based allocation adjusts the dynamic ratio in favor of a thread in response to the thread making forward progress in execution of associated instruction blocks.
8. A non-transitory computer-readable media having computer readable code which when executed by a computer system causes the computer system to implement a method of executing multi-threaded instructions grouped into blocks, the method comprising:
receiving an incoming instruction sequence at a front end of an execution pipeline;
grouping instructions from the instruction sequence to form instruction blocks, where a first group of instruction blocks are a part of a first thread of execution and a second group of instruction blocks are a part of a second thread of execution;
storing the first group of instruction blocks and the second group of instruction blocks in a scheduler array, where a first commit pointer points to a location in the scheduler array for a next block of the first group to be executed and a second commit pointer points to a next block of the second group to be execute;
scheduling the instructions of the instruction blocks to execute in accordance with a position in the scheduler array; and
tracking execution of the first thread and second thread to enforce a fairness policy using allocation counters to track a number of instruction blocks in the scheduler array for each thread.
9. The non-transitory computer-readable medium of claim 8 , wherein each allocation counter tracks a number of entries in a correlated thread pointer map.
10. The non-transitory computer-readable medium of claim 8 , wherein the fairness policy prevents any thread from exceeding an allocation threshold.
11. The non-transitory computer-readable medium of claim 8 , further comprising:
tracking an array entry to place a next block in the scheduler array for each thread using a separate allocate pointer.
12. The non-transitory computer-readable medium of claim 8 , further comprising using the allocation counters to allocate instruction blocks belonging to different threads within a scheduler array to implement the fairness policy.
13. The non-transitory computer-readable medium of claim 8 , wherein a dynamic counter-based allocation is used to allocate blocks of threads within the scheduler array to implement a dynamic ratio of thread allocation.
14. The non-transitory computer-readable medium of claim 13 , wherein the dynamic counter-based allocation adjusts the dynamic ratio in favor of a thread in response to the thread making forward progress in execution of associated instruction blocks.
15. A processor comprising:
an execution pipeline having,
a front end to fetch instructions from memory and to group instructions into blocks, where a first group of instruction blocks are a part of a first thread of execution and a second group of instruction blocks are a part of a second thread of execution,
a scheduler including a scheduler array, the scheduler array to store the first group of instruction blocks and the second group of instruction blocks, where a first commit pointer points to a location in the scheduler array for a next block of the first group to be executed and a second commit pointer points to a next block of the second group to be execute, the scheduler to schedule the instructions of the instruction blocks to execute in accordance with a position in the scheduler array, and to track execution of the first thread and second thread to enforce a fairness policy using allocation counters to track a number of instruction blocks in the scheduler array for each thread, and
a set of execution units to execute the instructions.
16. The processor of claim 15 , wherein each allocation counter tracks a number of entries in a correlated thread pointer map.
17. The processor of claim 15 , wherein the fairness policy prevents any thread from exceeding an allocation threshold.
18. The processor of claim 15 , wherein the allocation counters are configured to allocate instruction blocks belonging to different threads within a scheduler array to implement the fairness policy.
19. The processor of claim 15 , wherein a dynamic counter-based allocation is used to allocate blocks of threads within the scheduler array to implement a dynamic ratio of thread allocation.
20. The processor of claim 19 , wherein the dynamic counter-based allocation adjusts the dynamic ratio in favor of a thread in response to the thread making forward progress in execution of associated instruction blocks.