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

Abstract

A processor and instruction graduation unit for a processor. In one embodiment, a processor or instruction graduation unit according to the present invention includes a linked-list-based multi-threaded graduation buffer and a graduation controller. The graduation buffer stores identification values generated by an instruction decode and dispatch unit of the processor as part of one or more linked-list data structures. Each linked-list data structure formed is associated with a particular program thread running on the processor. The number of linked-list data structures formed is variable and related to the number of program threads running on the processor. The graduation controller includes linked-list head identification registers and linked-list tail identification registers that facilitate reading and writing identifications values to linked-list data structures associated with particular program threads. The linked-list head identification registers determine which executed instruction result or results are next to be written to a register file.

1 . A processor, comprising: 
 a results buffer having a plurality of registers, each register for temporarily storing a result of an executed instruction prior to the result being written to a register file;    a results buffer allocater that generates identification values, wherein each identification value identifies a register of the results buffer in which an executed instruction's result can be temporarily stored; and    a graduation buffer having a plurality of registers, wherein identification values generated by the results buffer allocater are temporarily stored as part of a linked-list data structure.    
     
     
         2 . The processor of  claim 1 , wherein identification values generated by the results buffer allocater are temporarily stored as part of a plurality of linked-list data structures, each linked-list data structure being associated with a particular program thread.  
     
     
         3 . The processor of  claim 1 , further comprising: 
 a graduation controller, coupled to the graduation buffer, that includes a linked-list head identification register and a linked-list tail identification register.    
     
     
         4 . The processor of  claim 3 , wherein the graduation controller includes a plurality of linked-list head identification registers and a plurality of linked-list tail identification registers.  
     
     
         5 . The processor of  claim 1 , further comprising: 
 a graduation controller, coupled to the graduation buffer, that includes 
 a plurality of linked-list head identification units each having a first linked-list head identification register and a second linked-list head identification register, and  
 a plurality of linked-list tail identification units each having a first linked-list tail identification register and a second linked-list tail identification register.  
   
     
     
         6 . The processor of  claim 1 , wherein the graduation controller specifies a plurality of results to be written to the register file in a particular clock cycle of the processor.  
     
     
         7 . An instruction graduation unit for a processor, comprising: 
 a graduation buffer having a plurality of registers, wherein identification values generated by an instruction decode and dispatch unit of a processor are temporarily stored as part of a linked-list data structure; and    a graduation controller, coupled to the graduation buffer, that includes a linked-list head identification register and a linked-list tail identification register.    
     
     
         8 . The instruction graduation unit of  claim 7 , wherein identification values generated by the instruction decode and dispatch unit are temporarily stored as part of a plurality of linked-list data structures, each linked-list data structure being associated with a particular program thread.  
     
     
         9 . The instruction graduation unit of  claim 7 , wherein the graduation controller includes a plurality of linked-list head identification registers and a plurality of linked-list tail identification registers.  
     
     
         10 . The instruction graduation unit of  claim 7 , wherein the graduation controller specifies a plurality of results to be written from a results buffer to a register file in a particular clock cycle of a processor.  
     
     
         11 . A computer readable storage medium comprising a processor embodied in software, the processor comprising: 
 a results buffer having a plurality of registers, each register for temporarily storing a result of an executed instruction prior to the result being written to a register file;    a results buffer allocater that generates identification values, wherein each identification value identifies a register of the results buffer in which an executed instruction's result can be temporarily stored; and    a graduation buffer having a plurality of registers, wherein identification values generated by the results buffer allocater are temporarily stored as part of a linked-list data structure.    
     
     
         12 . The computer readable storage medium of  claim 11 , wherein identification values generated by the results buffer allocater are temporarily stored as part of a plurality of linked-list data structures, each linked-list data structure being associated with a particular program thread.  
     
     
         13 . The computer readable storage medium of  claim 11 , wherein the processor further comprises: 
 a graduation controller, coupled to the graduation buffer, that includes a linked-list head identification register and a linked-list tail identification register.    
     
     
         14 . The computer readable storage medium of  claim 13 , wherein the graduation controller includes a plurality of linked-list head identification registers and a plurality of linked-list tail identification registers.  
     
     
         15 . The computer readable storage medium of  claim 11 , wherein the graduation controller specifies a plurality of results to be written to the register file in a particular clock cycle of the processor.  
     
     
         16 . The computer readable storage medium of  claim 11 , wherein the processor is embodied in hardware description language software.  
     
     
         17 . The computer readable storage medium of  claim 16 , wherein the processor core is embodied in one of Verilog hardware description language software and VHDL hardware description language software.  
     
     
         18 . 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 registers, wherein identification values generated by an instruction decode and dispatch unit of a processor are temporarily stored as part of a linked-list data structure; and    a graduation controller, coupled to the graduation buffer, that includes a linked-list head identification register and a linked-list tail identification register.    
     
     
         19 . The computer readable storage medium of  claim 18 , wherein identification values generated by the instruction decode and dispatch unit are temporarily stored as part of a plurality of linked-list data structures, each linked-list data structure being associated with a particular program thread.  
     
     
         20 . The computer readable storage medium of  claim 19 , wherein the graduation controller includes a plurality of linked-list head identification registers and a plurality of linked-list tail identification registers.  
     
     
         21 . The computer readable storage medium of  claim 18 , wherein the graduation controller specifies a plurality of results to be written from a results buffer to a register file in a particular clock cycle of a processor.  
     
     
         22 . The computer readable storage medium of  claim 18 , wherein the instruction graduation unit is embodied in hardware description language software.  
     
     
         23 . A method for controlling the order in which instruction results are written to a register file of a processor, the method comprising: 
 assigning a first identification value to a first instruction of a program thread, a second identification value to a second instruction of the program thread, and a third identification value to a third instruction of the program thread, wherein the first identification value specifies where in a first buffer of a processor a result of the first instruction is to be written by an execution unit of the processor, the second identification value specifies where in the first buffer a result of the second instruction is to be written by the execution unit, and the third identification value specifies where in the first buffer a result of the third instruction is to be written by the execution unit;    writing the first identification value to a first register of a second buffer of the processor, the second identification value to a second register of the second buffer, and the third identification value to a third register of the second buffer, wherein the first identification value, the second identification value, and the third identification value form part of a linked-list data structure; and    writing results stored in the first buffer to a register file of the processor in an order determined by the values that form the linked-list data structure.    
     
     
         24 . The method of  claim 23 , further comprising: 
 assigning a fourth identification value to a first instruction of a second program thread, a fifth identification value to a second instruction of the second program thread, and a sixth identification value to a third instruction of the second program thread, wherein the fourth identification value specifies where in the first buffer of t processor a result of the first instruction of the second program thread is to be written by the execution unit of the processor, the fifth identification value specifies where in the first buffer a result of the second instruction of the second program thread is to be written by the execution unit, and the sixth identification value specifies where in the first buffer a result of the third instruction of the second program thread is to be written by the execution unit;    writing the fourth identification value to a fourth register of the second buffer of the processor, the fifth identification value to a fifth register of the second buffer, and the sixth identification value to a sixth register of the second buffer, wherein the fourth identification value, the fifth identification value, and the sixth identification value form part of a second linked-list data structure; and    writing results stored in the first buffer, for instructions belonging to the second program thread, to the register file of the processor in an order determined by the values that form the second linked-list data structure.