Granted Patent B2

US 9,417,920 · App. 14/046,438 · Granted Aug 16, 2016

Abstract

Claims (92)

1. A method comprising:

decoding a received instruction from a first thread executing on a processor to produce a decoded instruction, wherein

a first set of instruction queues is allocated to the first thread,

a second set of instruction queues different from the first set of instruction queues is allocated to a second thread executing on the processor,

the first thread and the second thread are configured to execute simultaneously, and

the processor comprises a plurality of instruction queues that comprises the first and second sets of instruction queues;

in response to a first determination that each of the first set of instruction queues is full after decoding the received instruction from the first thread,

determining whether an empty queue of the plurality of instruction queues is available to be allocated to the first thread;

in response to a second determination that no empty queue is available to be allocated to the first thread after decoding the received instruction from the first thread,

performing a fairness determination based on priority of the first thread and the second thread;

in response to the first thread having a higher fairness indicator than the second thread:

stalling the second thread temporarily while executing already-queued decoded instructions in the first and second sets of instruction queues until a candidate queue becomes available, wherein the candidate queue is selected from a group of:

a first allocated queue of the first set of instruction queues that is no longer full, and

a second allocated queue of the second set of instruction queues that becomes empty;

in response to the first thread not having a higher fairness indicator than the second thread:

stalling the first thread temporarily while executing already-queued decoded instructions in the first and second sets of instruction queues until the candidate queue becomes available;

dispatching the decoded instruction to the first allocated queue becoming the candidate queue, in response to the first allocated queue being no longer full;

re-allocating the second allocated queue becoming the candidate queue to the first thread, in response to the second allocated queue becoming empty; and

dispatching the decoded instruction to the second allocated queue, in response to the re-allocating the second allocated queue.

2. The method of claim 1 , wherein the performing the fairness determination is further based at least in part on one or more of: a load-balancing consideration, a cache-fetch time, a count of queues currently allocated to the first thread, maximum queue allocation limits for the first and second threads, and minimum queue allocation limits for the first and second threads.

3. The method of claim 1 , further comprising:

re-assigning one of the first set of instruction queues to the second thread, in response to the first thread being stalled.

4. The method of claim 3 , wherein the first thread is stalled in response to the first thread experiencing a cache miss.

5. The method of claim 1 , further comprising:

receiving a second decoded instruction associated with a new thread executing on the processor, wherein the new thread is configured to execute simultaneously with the first thread and the second thread;

in response to a third determination that no empty queue is available to be allocated to the new thread,

stalling the first thread and the second thread while executing decoded instructions in the first and second sets of instruction queues until one of the first and second sets of instruction queues becomes an empty queue;

allocating the empty queue to the new thread; and

dispatching the second decoded instruction to the empty queue.

6. The method of claim 5 , wherein

the new thread is associated with a minimum allocation queue limit of one or more queues, and

the stalling the first thread and the second thread continues until the minimum allocation queue limit is met.

7. The method of claim 1 , wherein the first set of instruction queues comprises N queues of a first instruction type, wherein the first instruction type is one of: a load/store instruction type, a simple-execution instruction type, and a complex-execution instruction type, and wherein the method further comprises:

determining that the first thread has a minimum requested guarantee of M queues of the first instruction type;

determining that more than N-M queues of the first instruction type are assigned to receive instructions from the second thread;

temporarily stalling the second thread until M queues of the first instruction type are available to receive instructions from the first thread; and

assigning M queues to receive instructions of the first instruction type from the first thread.

8. The method of claim 7 , wherein

instructions of the simple-execution instruction type are each configured to be performed in one unit of processor cycles, and

instructions of the complex-execution instruction type are each configured to be performed in multiple units of processor cycles.

9. The method of claim 1 , further comprising:

prioritizing a first port of a data cache for load/store instructions of the first thread; and

prioritizing a second port of the data cache for load/store instructions of the second thread.

10. The method of claim 1 , wherein

the second determination that no empty queues are available to be allocated to the first thread is based on the first set of instruction queues meeting a maximum queue limit.

11. A system comprising:

a processor comprising:

a plurality of instruction queues, the plurality of instruction queues comprising:

a first set of queues, and

a second set of queues;

one or more execution units configured to execute decoded instructions in the first and second sets of queues; and

one or more dispatch units, wherein the one or more dispatch units are configured to:

provide the first set of queues with decoded instructions from a first thread among a plurality of simultaneous instruction threads,

provide the second set of queues with decoded instructions from a second thread among the plurality of simultaneous instruction threads,

decode a received instruction from the first thread to produce a decoded instruction,

in response to a first determination that each of the first set of queues is full after the received instruction is decoded, determine whether an empty queue of the plurality of instruction queues is available to be allocated to the first thread,

in response to a second determination that no empty queue is available to be allocated to the first thread after the received instruction is decoded, perform a fairness determination based on priority of the first thread and the second thread,

in response to the first thread having a higher fairness indicator than the second thread, stall the second thread temporarily while the one or more execution units execute already-queued decoded instructions in the first and second sets of queues until a candidate queue becomes available, wherein the candidate queue is selected from a group of:

a first allocated queue of the first set of queues that is no longer full, and

a second allocated queue of the second set of queues that becomes empty,

in response to the first thread not having a higher fairness indicator than the second thread, stall the first thread temporarily while the one or more execution units execute already-queued decoded instructions in the first and second sets of queues until the candidate queue becomes available,

dispatch the decoded instruction to the first allocated queue becoming the candidate queue, in response to the first allocated queue being no longer full,

re-allocate the second allocated queue becoming the candidate queue to the first thread, in response to the second allocated queue becoming empty, and

dispatch the decoded instruction to the second allocated queue, in response to the re-allocation of the second allocated queue.

12. The system of claim 11 , wherein:

the plurality of instruction queues comprises a plurality of load/store queues, a plurality of simple-execution queues, and a plurality of complex-execution queues;

the load/store queues comprises two thread-reserved load/store queues and at least one dynamically assignable load/store queue;

the simple-execution queues comprises two thread-reserved simple-execution instruction queues;

the complex-execution queues comprises two thread-reserved complex-execution queues and at least one dynamically assignable complex-execution queue;

the dispatch units are configured to provide load instructions and store instructions to the load/store queues;

the dispatch units are configured to provide simple-execution instructions and load/store instructions to the simple-execution queues;

the dispatch units are configured to provide complex-execution instructions, simple-execution instructions, and load/store instructions to the complex-execution queues.

13. The system of claim 11 , wherein at least one of the one or more dispatch units is configured to perform the fairness determination further based at least in part on one or more of: a load-balancing consideration, a cache-fetch time, a count of queues currently allocated to one or more of the threads, and maximum and minimum queue allocation limits for one or more of the first and second threads.

14. The system of claim 11 , wherein at least one of the one or more dispatch units is configured to re-assign at least one of the first set of queues to the second thread, in response to the first thread being paused.

15. The system of claim 14 , wherein the first thread is paused in response to a cache miss for the first thread.

16. The system of claim 11 , further comprising:

a data cache, wherein the data cache comprises

a first port prioritized for the first thread, and

a second port prioritized for the second thread.

17. A method comprising:

providing decoded instructions from a first thread, among a plurality of instruction threads executing simultaneously, to a first set of queues among a plurality of instruction queues in a processor, wherein instructions in the first set of queues are executed by the processor;

providing decoded instructions from a second thread, among the plurality of instruction threads, to a second set of queues among the plurality of instruction queues, wherein instructions in the second set of queues are executed by the processor;

decoding a received instruction from the first thread to produce a decoded instruction;

in response to a first determination that each of the first set of queues is full after decoding the received instruction from the first thread, determining whether an empty queue of the plurality of instruction queues is available to be allocated to the first thread;

in response to a second determination that no empty queue is available to be allocated to the first thread after decoding the received instruction from the first thread, performing a fairness determination based on priority of the first thread and the second thread;

in response to the first thread having a higher fairness indicator than the second thread, stalling the second thread temporarily while already-queued decoded instructions in the first and second sets of queues are executed until a candidate queue becomes available, wherein the candidate queue is selected from a group of:

a first allocated queue of the first set of queues that is no longer full, and

a second allocated queue of the second set of queues that becomes empty;

in response to the first thread not having a higher fairness indicator than the second thread, stalling the first thread temporarily while already-queued decoded instructions in the first and second sets of queues are executed until the candidate queue becomes available;

dispatching the decoded instruction to the first allocated queue becoming the candidate queue, in response to the first allocated queue being no longer full;

re-allocating the second allocated queue becoming the candidate queue to the first thread, in response to the second allocated queue becoming empty; and

dispatching the decoded instruction to the second allocated queue, in response to the re-allocating the second allocated queue.

Assignments (22)