Multithreading instruction scheduler employing thread group priorities

A method for dispatching instructions to an execution pipeline in a multi threading microprocessor that concurrently executes N threads each being in one of G groups, each of the G groups having a priority, the priority being one of P priorities, the method comprising:

• generating G round-robin vectors, corresponding to the G groups, each having N bits corresponding to the N threads, each being a 1-bit left-rotated and subsequently sign-extended version of an N-bit input vector, the input vector having a single bit true corresponding to a last one of the N threads selected for dispatching in a corresponding one of the G groups;
• for each of the N threads, receiving a corresponding one of the N bits of each of the G round-robin vectors, and selecting as a round-robin bit one of the G received corresponding one of the N bits of each of the G round-robin vectors specified by the corresponding thread's group;
• and
• receiving an instruction from each of the N threads, and selecting for dispatching to the execution pipeline one of the N instructions corresponding to one of the N threads having a dispatch value greater than or equal to any of the N threads left thereof in the N-bit input vectors;
• wherein the dispatch value of each of the N threads comprises a least-significant bit equal to the round-robin bit of the thread, a most-significant bit that is true if the corresponding instruction of the thread is dispatchable, and middle bits comprising the priority of the thread's group.

A multi threading microprocessor for concurrently executing N threads, each of the N threads being in one of G groups, each group having a priority, the priority being one of P priorities, wherein a subset of the N threads may have a dispatchable instruction in a selection cycle, the microprocessor configured to dispatch instructions of the N threads to an execution pipeline in a round-robin fashion within each of the G groups independent of the other G groups, comprising:

• G round-robin circuits, each for generating an N-bit round-robin vector for a corresponding one of the G groups, wherein said N-bits correspond to the N threads, each of said G round-robin circuits comprising:
• a first input, for receiving a first corresponding N-bit value specifying which of the N threads was last selected in said group to dispatch an instruction, wherein only one of said N bits corresponding to said last selected thread is true;
• a second input, for receiving a second corresponding N-bit value, each of said N bits being false if said corresponding thread has a dispatchable instruction and is in said group;
• a barrel incrementer, coupled to receive said first and second inputs, configured to 1-bit left-rotatively increment said second value by said first value to generate a sum;
• and
• combinational logic, coupled to said barrel incrementer, configured to generate said N-bit round-robin vector specifying which of the N threads is selected next to dispatch an instruction, said round-robin vector comprising a Boolean AND of said sum and an inverted version of said second value, wherein only one of said N bits corresponding to said next selected one of the N threads is true;
• N G-input muxes, each coupled to receive a corresponding one of said N bits of each of said G round-robin vectors, each configured to select one of said G inputs specified by the group of the corresponding thread as a round-robin bit for said associated thread;
• and
• hardware selection logic, coupled to said N G-input muxes, configured to select one of the N threads for dispatching an instruction thereof to the execution pipeline, wherein said selection logic selects said one of the N threads having said round robin bit set, having a dispatchable instruction, and being in a group having said priority a highest of the P priorities having one of the plurality of threads with a dispatchable instruction.

A method for generating a round-robin bit for use in selecting one of N threads for dispatching an instruction to an execution pipeline in a multi threading microprocessor, the N threads each being in one of G groups, each group having a priority, the priority being one of P priorities, wherein a subset of the N threads may have a dispatchable instruction in a selection cycle, the method comprising:

• generating G N-bit round-robin vectors each for a corresponding one of the G groups, wherein the N-bits correspond to the N threads, said generating each of the G N-bit round-robin vectors comprising:
• receiving a first corresponding N-bit value specifying which of the N threads was last selected in the group to dispatch an instruction, wherein only one of the N bits corresponding to the last selected thread is true;
• receiving a second corresponding N-bit value, each of the N bits being false if the corresponding thread has a dispatchable instruction and is in the group;
• 1-bit left-rotatively incrementing the second value by the first value to generate a sum;
• and
• generating the N-bit round-robin vector specifying which of the N threads is selected next to dispatch an instruction, the round-robin vector comprising a Boolean AND of the sum and an inverted version of the second value, wherein only one of the N bits corresponding to the next selected one of the N threads is true;
• and
• for each of the N threads, receiving a corresponding one of the N bits of each of the G round-robin vectors, and selecting as the round-robin bit for the corresponding thread one of the G received bits specified by the group of said thread.

A computer program product for use with a computing device, the computer program product comprising:

• a computer usable storage medium, having computer readable program code embodied in said medium, for modeling an apparatus for dispatching instructions to an execution pipeline in a multi threading microprocessor that concurrently executes N threads each being in one of G groups, each of the G groups having a priority, the priority being one of P priorities, said computer readable program code comprising:
• first program code for providing G round-robin vectors, corresponding to the G groups, each having N bits corresponding to the N threads, each being a 1-bit left-rotated and subsequently sign-extended version of an N-bit input vector, said input vector having a single bit true corresponding to a last one of the N threads selected for dispatching in a corresponding one of the G groups;
• second program code for providing N G-input muxes, each coupled to receive a corresponding one of said N bits of each of said G round-robin vectors, each configured to select for output one of said G inputs specified by the corresponding thread's group;
• and
• third program code for providing selection logic, coupled to receive an instruction from each of the N threads and to select for dispatching to the execution pipeline one of said N instructions corresponding to one of the N threads having a dispatch value greater than or equal to any of the N threads left thereof in said N-bit input vectors, wherein said dispatch value of each of the N threads comprises a least-significant bit equal to said corresponding G-input mux output, a most-significant bit that is true if said corresponding instruction is dispatchable, and middle bits comprising the priority of the thread's group.