Compact linked-list-based multi-threaded instruction graduation buffer

An instruction graduation unit for a processor, comprising:

• a graduation buffer having a plurality of entries each of which stores therein a results buffer identification value that identifies a register in a result buffer generated by an instruction decode and dispatch unit of the processor as part of a linked-list data structure for a respective program thread, wherein a first entry in the linked-list data structure comprises a buffer ID to store an allocated results buffer identification value, and a next buffer ID to store a newly allocated results buffer identification value, the next buffer ID having a value equal to the buffer ID of a second entry in the linked-list data structure;
• and
• a graduation controller to identify a single instruction for graduation during an instruction graduation cycle coupled to the graduation buffer, wherein the graduation controller includes a plurality of first head-ID multiplexers, wherein each first head-ID multiplexer is associated with a respective program thread and is coupled to the decode and dispatch unit for receiving a results buffer identification value of a respective program thread as a first input and coupled to the graduation buffer for receiving the next buffer ID of the first entry of the linked-list data structure for the respective program thread from the graduation buffer as a second input, each first head-ID multiplexer further coupled to an input of a respective linked-list head identification register, each linked-list head identification register having an output coupled to a second head-ID multiplexer, the second head-ID multiplexer coupled to the graduation buffer and a results buffer;
• and
• a respective linked-list tail identification register for each program thread, each linked-list tail identification register having an input coupled to dispatch and decode unit and an output coupled to a tail-ID multiplexer, the tail-ID multiplexer coupled to the graduation buffer;
• wherein when a new results buffer identification value is generated for an instruction of a particular program thread the linked-list head identification register associated with the particular program thread is updated with the new results buffer identification value or with the next buffer ID of the first entry of the linked-list data structure associated with the particular program thread dependent on the buffer ID and next buffer ID of the first entry of the linked-list data structure associated with the particular program thread and wherein the linked-list tail identification register associated with the particular program thread is updated with the new results buffer identification value.

A computer readable storage medium comprising a processor embodied in software, the processor comprising:

• a results buffer having a plurality of registers, each register to store a result of an executed instruction prior to the result being written to a register file;
• a results buffer allocater that generates results buffer identification values, wherein each results buffer identification value identifies one of the plurality of registers of the results buffer;
• a graduation buffer coupled to the results buffer and the results buffer allocater, the graduation buffer having a plurality of entries to store each results buffer identification value as part of a linked-list data structure for a respective program thread, wherein a first entry in the linked-list data structure comprises a buffer ID to store an allocated results buffer identification value, and a next buffer ID to store a newly allocated results buffer identification value, the next buffer ID having a value equal to the buffer ID of a second entry in the linked-list data structure;
• and
• a graduation controller to identify a single instruction for graduation during an instruction graduation cycle, which includes:
• a plurality of first head-ID multiplexers, wherein each first-head ID multiplexer is associated with a respective program thread and is coupled to the results buffer allocater for receiving a results buffer identification value as a first input and to the graduation buffer for receiving the next buffer ID of the first entry of the linked-list data structure for the respective program thread as a second input, the output of each first head-ID multiplexer coupled to an input of a respective linked-list head identification register, each linked-list head identification register having an output coupled to an input of second head-ID multiplexer, the output of second head-ID multiplexer coupled to the graduation buffer and results buffer, and
• a respective linked-list tail identification register for each program thread, each linked list tail identification register having an input coupled to results buffer allocater and an output coupled to an input of a tail-ID multiplexer, the output of the tail-ID multiplexer coupled to the graduation buffer;
• wherein when the results buffer allocater generates a new results buffer identification value for an instruction of a particular program thread the linked-list head identification register associated with the particular program thread is updated with the new results buffer identification value or with the next buffer ID of the first entry of the linked-list data structure associated with the particular program thread dependent on the buffer ID and next buffer ID of the first entry of the linked-list data structure associated with the particular program thread and wherein the linked-list tail identification register associated with the particular program thread is updated with the new results buffer identification value.

A computer readable storage medium comprising an instruction graduation unit for a processor, embodied in software, the instruction graduation unit comprising:

• a graduation buffer having a plurality of entries each of which stores therein a results buffer identification value that identifies a register in a result buffer generated by an instruction decode and dispatch unit of the processor as part of a linked-list data structure for a respective program thread, wherein a first entry in the linked-list data structure comprises a buffer ID to store an allocated results buffer identification value, and a next buffer ID to store a newly allocated results buffer identification value, the next buffer ID having a value equal to the buffer ID of a second entry in the linked-list data structure;
• and
• a graduation controller to identify a single instruction for graduation during an instruction graduation cycle, coupled to the graduation buffer, wherein the graduation controller includes a plurality of first head-ID multiplexers, wherein each first head-ID multiplexer is associated with a respective program thread and is coupled to the decode and dispatch unit for receiving a results buffer identification value of a respective program thread as a first input and coupled to the graduation buffer for receiving the next buffer ID of the first entry of the linked-list data structure for the respective program thread from the graduation buffer as a second input, each first head-ID multiplexer further coupled to an input of a respective linked-list head identification register, each linked-list head identification register having an output coupled to a second head-ID multiplexer, the second head-ID multiplexer coupled to the graduation buffer and a results buffer;
• and
• a respective linked-list tail identification register for each program thread, each linked-list tail identification register having an input coupled to dispatch and decode unit and an output coupled to a tail-ID multiplexer, the tail-ID multiplexer coupled to the graduation buffer;
• wherein when a new results buffer identification value is generated for an instruction of a particular program thread the linked-list head identification register associated with the particular program thread is updated with the new results buffer identification value or with the next buffer ID of the first entry of the linked-list data structure associated with the particular program thread dependent on the buffer ID and next buffer ID of the first entry of the linked-list data structure associated with the particular program thread and wherein the linked-list tail identification register associated with the particular program thread is updated with the new results buffer identification value.