Abstract:
A multi-threaded processor that is capable of responding to, and processing, multiple low-latency-tolerant events concurrently and while using relatively slow, low-power memories is disclosed. The illustrative embodiment comprises a multi-threaded processor, which itself comprises a context controller and a plurality of hardware contexts. Each hardware context is capable of storing the current state of one thread in a form that enables the processor to quickly switch to or from the execution of that thread. To enable the processor to be capable of responding to low-latency-tolerant events quickly, each thread—and, therefore, each hardware context is prioritized—depending on the latency tolerance of the thread responding to the event.

Description:
REFERENCE TO RELATED APPLICATIONS  
       [0001]     The following patent applications are incorporated by reference:  
         [0002]     i. U.S. Patent Application 60/716,806, entitled “Multi-Threaded Processor Architecture,” filed 13 Sep. 2005, Attorney Docket 163-001us;  
         [0003]     ii. U.S. Patent Application 60/723,699, entitled “Computer Processor Capable of Responding with Comparable Efficiency to Both Software-State-Independent and State-Dependent Events,” filed 5 Oct. 2005, Attorney Docket 163-002us; and  
         [0004]     iii. U.S. Patent Application 60/723,165, entitled “Computer Processor Architecture Comprising Operand Stack and Addressable Registers,” filed 3 Oct. 2005, Attorney Docket 163-003us. 
     
    
     FIELD OF THE INVENTION  
       [0005]     The present invention relates to computer science in general, and, more particularly, to an architecture for a multi-threaded processor.  
       BACKGROUND OF THE INVENTION  
       [0006]     The trend in the design of consumer electronics is to build portable electronic appliances (e.g., personal digital assistants, cell phones, etc.) that are capable of communicating via two or more radio protocols (e.g., WiFi, Bluetooth, etc.) concurrently, and this mandates that the processor within the appliance be capable of responding to multiple low-latency-tolerant events.  
         [0007]     The requirement that a processor be capable of responding to multiple low-latency-tolerant events has, in general, meant that the processor needed to be fast. A fast processor, however, uses a great deal of wattage and, therefore, drains a portable electronic appliance&#39;s batteries quickly, which is, of course, most disadvantageous.  
         [0008]     The need exists, therefore, for the development of a processor that is capable of capable of responding to multiple low-latency-tolerant events concurrently and with moderate power consumption.  
       SUMMARY OF THE INVENTION  
       [0009]     The present invention enables the manufacturing and use of processors that are capable of responding to multiple low-latency-tolerant events concurrently and with moderate power consumption. For example, the illustrative embodiment is a multi-threaded processor that is capable of responding to, and processing, multiple low-latency-tolerant events concurrently and while using relatively slow, low-power memories.  
         [0010]     In particular, the illustrative embodiment comprises a multi-threaded processor, which itself comprises a context controller and a plurality of hardware contexts. Each hardware context is capable of storing the current state of one thread in a form that enables the processor to quickly switch to or from the execution of that thread. To enable the processor to be capable of responding to low-latency-tolerant events quickly, each thread—and, therefore, each hardware context—is prioritized to reflect the latency tolerance of the event to which it responds.  
         [0011]     The context controller switches contexts—and, therefore, access to the processing capability of the processor—among the highest priority threads on a time-sequenced basis (e.g., an instruction-by-instruction basis, etc.). In this way, the controller ensures that the processor exhibits both the low-latency benefit associated with both coarse-grained multi-threaded architectures and the concurrent-processing benefit associated with fine-grained multi-threaded architectures in the prior art.  
         [0012]     In accordance with the illustrative embodiment, the processor&#39;s memory is constructed of independent memory banks, and the instructions and data for each executing thread are stored in a different bank. This enables the illustrative embodiment to comprise relatively slow-speed program memory because the memory&#39;s access time need only be as fast as the amount of time needed by the processor to execute two or more successive instructions in a single thread depending on parameters that are described in detail below.  
         [0013]     The illustrative embodiment comprises: (a) H hardware contexts, each of which is capable of storing the execution state of one thread in a multi-threaded processor; and (b) a context controller for: 
        (i) activating each of A hardware contexts, wherein each of said A active hardware contexts has a priority,     (ii) maintaining the E highest priority of the A active hardware contexts as executing hardware contexts, wherein E equals the lesser of A and C, and wherein C equals the maximum number of concurrently executing hardware contexts in the multi-threaded processor, and     (iii) initiating a context switch in the multi-threaded processor among the E executing hardware contexts on a time-sequenced basis;     wherein C and H are positive integers and 2 &lt;C&lt;H; and       wherein A and E are non-negative integers and E≦A≦H.       
 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0019]      FIG. 1  depicts a block diagram of the logical components of an electronic appliance in accordance with the illustrative embodiment of the present invention.  
         [0020]      FIG. 2  depicts a block diagram of the salient aspects of multi-threaded processor  103  in accordance with the illustrative embodiment of the present invention.  
         [0021]      FIG. 3  depicts a chart of the salient tasks associated with the operation of the illustrative embodiment. 
     
    
     DETAILED DESCRIPTION  
       [0022]      FIG. 1  depicts a block diagram of the logical components of an electronic appliance in accordance with the illustrative embodiment of the present invention. Electronic appliance  100  comprises: radios  101 - 1  through  101 - 3 , local bus controller  102 , multi-threaded processor  103 , input/output  104 , and memory  105 , interrelated as shown.  
         [0023]     Each of radios  101 - 1  through  101 - 3  is a standard radio as is well known to those skilled in the art that enables electronic appliance  100  to communicate with other electronic appliances wirelessly. Each of radios  101 - 1  through  101 - 3  operates in accordance with a different air-interface: radio  101 - 1  is IEEE 802.11 compliant, radio  101 - 2  is IS- 95  compliant, and radio  101 - 3  is Bluetooth compliant. Each of radios  101 - 1  through  101 - 3  receive messages independently of each other and that require low-latency responses. It will be clear to those skilled in the art how to make and use radios  101 - 1  through  101 - 3 .  
         [0024]     Local bus controller  102  acts as the interface between radios  101 - 1  through  101 - 3  and multi-threaded processor  103  in well-known fashion. For example, local bus controller  102  controls the interaction between radios  101 - 1  through  101 - 3  and multi-threaded processor  103 . It will be clear to those skilled in the art how to make and use local bus controller  102 .  
         [0025]     Multi-threaded processor  103  is a general-purpose processor that is capable of interacting with local bus controller  102 , input/output  104 , and memory  105  as described below and with respect to  FIGS. 2 and 3 . In particular, multi-threaded processor  103  is capable of executing a plurality of concurrent threads in the manner described below.  
         [0026]     Input/output  104  is the non-radio interface for electronic appliance  100  and interacts with multi-threaded processor  103  in well-known fashion.  
         [0027]     Memory  105  is the program memory for electronic appliance  100  and comprises C independent memory banks, wherein C is a positive integer greater than 2. The upper bound of C is described below with respect to  FIG. 2 . The access time of memory  105  is equal to or less than the time required by multi-threaded processor  103  to execute C instructions. In accordance with the illustrative embodiment, the instructions and data for each executing thread is stored in a different bank in memory  105  so that there is no memory contention between threads for data in the same bank. It will be clear to those skilled in the art how to make and use memory  105 . It will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which memory  105  is tightly-coupled memory or the cache of a multi-level memory hierarchy.  
         [0028]      FIG. 2  depicts a block diagram of the salient aspects of multi-threaded processor  103  in accordance with the illustrative embodiment of the present invention. Multi-threaded processor  103  comprises context controller  301  and H hardware contexts  301 - 1  through  301 -H, wherein H is a positive integer greater than C. In accordance with the illustrative embodiment, H equals 8, but it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which H has any integral value greater than C.  
         [0029]     For the purposes of this specification, a “hardware context” is described as the hardware required to store the current state of a thread in a form that enables multi-threaded processor  103  to switch to or from the execution of the thread.  
         [0030]     Context controller  301  is capable of monitoring and regulating the population and execution of hardware contexts  301 - 1  through  301 -H, in the manner described below and with respect to  FIG. 3 . Furthermore, context controller  301  maintains a table which provides the following information for each hardware context:  
         [0031]     (i) is the hardware context vacant or populated? 
         [0032]     (ii) what is the priority of hardware context? 
         [0033]     (iii) is the hardware context active or inactive? 
         [0034]     (iv) is the hardware context executing or not? 
         [0035]     The answer to each of these questions can be stored in a vector that is part of the hardware context. It will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the answers to these questions are stored in another way.  
         [0036]      FIG. 3  depicts a chart of the salient tasks associated with the operation of the illustrative embodiment. In accordance with the illustrative embodiment, tasks  301 ,  302 ,  303 , and  304  run concurrently.  
         [0037]     At task  301 , context controller  201  populates a vacant hardware context of hardware contexts  202 - 1  through  202 -H in response to the spawning of a thread. In accordance with the illustrative embodiment, the thread has a priority, and, therefore context controller  201  associates the priority of that thread with the newly populated hardware context.  
         [0038]     It will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which hardware contexts  202 - 1  through  202 -H are themselves prioritized and context controller  201  populates a vacant hardware context of hardware contexts  202 - 1  through  202 -H in response to the spawning of a thread, which vacant hardware context has a priority commensurate with the priority of the thread.  
         [0039]     well known to those skilled in the art, the normal execution of a thread usually, at some point, terminates, and at that point the hardware context for that thread is vacated and becomes available for repopulation. It will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the hardware context for a thread is retained after the normal execution and becomes dormant after the thread has terminated.  
         [0040]     At task  302 , context controller  201  deems the hardware context populated in task  301  as “active,” which hardware context was initially deemed “inactive.” For the purposes of this specification, an “active hardware context” is defined as a context that is ready to execute and an “inactive hardware context” is defined as a context that is not ready to execute.  
         [0041]     At any one instant, A of hardware contexts  202 - 1  through  202 -H are deemed active, wherein A is a non-negative integer and A≦H. Over time, the value of A can fluctuate as new threads are spawned and completed threads are vacated. Furthermore, the value of A can fluctuate due to the occurrence of events upon which inactive threads are waiting and the voluntary inactivation of threads pending occurrence of expected future events. Furthermore, context controller  201  can deem an active hardware context as inactive when the context encounters a suspension state for whatever reason (e.g., a processor execution stall due to a cache miss, the need to wait for an external event, etc.) and can deem an inactive hardware context as active when the wait or block state has been overcome.  
         [0042]     At task  303 , context controller  201  deems the E highest-priority of the A active hardware contexts as “executing,” wherein E is a non-negative integer and equals the lesser of A and C. For the purposes of this specification, an “executing hardware context” is defined as an active hardware context that is given access to the processing capability of multi-threaded processor  103  and a “non-executing hardware context” is defined as an active hardware context that is not given access to the processing capability of multi-threaded processor  103 . Over time, both the value of E can fluctuate as the number of active hardware contexts fluctuates and the members of the set of executing hardware contexts can fluctuate as the relative priority of the active hardware contexts fluctuates. In other words, when E equals C and an inactive hardware context with a higher priority than at least one of the E executing hardware contexts is deemed active, context controller  201  deems the newly activated hardware context as an executing hardware context and deems the lowest priority of the E executing hardware contexts as non-executing. In this way, context controller  201  maintains the E highest-priority of the A active hardware contexts as executing hardware contexts.  
         [0043]     At task  304 , context controller  201  initiates a context switch among the E executing hardware contexts on a time-sequenced basis. For the purposes of this specification, a “time-sequenced basis” is defined as a resource allocation system that allocates the processing capability of multi-threaded processor  103  across the executing hardware contexts based on time. The switching of contexts on a time-sequenced basis is common among many fine-grained multi-threaded processors.  
         [0044]     One example of context switching on a time-sequenced basis is switching on an instruction-by-instruction basis. Another example of context switching on a time-sequenced basis is switching wherein N instructions in each set of N*E successively-executed instructions is from each of the E executing hardware contexts, and wherein N is a positive integer greater and N≧1. When N equals 1, this is equivalent to switching on an instruction-by-instruction basis.  
         [0045]     In accordance with the illustrative embodiment, when there are fewer executing hardware contexts than multi-threaded processor  103  can concurrently handle (i.e., E&lt;C), each of the E executing hardware contexts receives 1/Cth of the processing capability of multi-threaded processor  103  and (C−E)/C of the processing capability of multi-threaded processor  103  is not used by any of the E executing hardware contexts. This is advantageous because each thread achieves a uniform processing time, which is advantageous (1) in applications where externally relevant time intervals (e.g., network inter-frame spaces, etc.) are generated directly by the instruction sequence and (2) in low-power applications.  
         [0046]     One advantage of context switching on an instruction-by-instruction basis and giving each of the E executing hardware contexts receives 1/Cth of the processing capability of multi-threaded processor  103  is that the instruction execution rate can be synchronized with the memory access. For example, in the case of the illustrative embodiment, the memory is partitioned into C memory banks, and the data for each thread is stored in a different bank. In these cases, the access time of the memory need only be equal to or less than the time required by processor  103  to execute C instructions.  
         [0047]     It will be clear to those skilled in the art, however, after reading this disclosure, how to make and use alternative embodiments of the present invention in which each of the E executing hardware contexts receives 1/Eth of the processing capability of multi-threaded processor  103 . This is advantageous because it achieves faster processing of each thread and lower response time to external events.  
         [0048]     understood that the above-described embodiments are merely illustrative of the present invention and that many variations of the above-described embodiments can be devised by those skilled in the art without departing from the scope of the invention. It is therefore intended that such variations be included within the scope of the following claims and their equivalents.