Patent Publication Number: US-8533401-B2

Title: Implementing direct access caches in coherent multiprocessors

Description:
BACKGROUND 
     This invention relates generally to processor cache architectures. More particularly, the present invention relates to multiprocessors that provide hardware cache coherency using shared states. 
     In typical computer systems, non-processor agents, such as input/output controllers and direct memory access devices, as two examples, are not able to push data directly to the local cache of a processor. However, some applications could benefit if non-processor agents were permitted to push data directly into a processor cache. 
     For instance, in a network packet processing system, allowing a non-processor agent to push a packet directly into a processor cache, rather than into main memory, enables the processor to read the packet directly from the local cache instead of from memory. This may be an important feature since the performance of network processors is measured by the number of packets they can process per second. In effect, the processor may process more packets because it does not need to access the information from memory, place it in a cache and then read it from the cache. 
     Thus, it would be desirable to enable non-processor agents to access caches in multiprocessor systems. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic depiction of one embodiment of the present invention; 
         FIG. 2  is a flow chart for one embodiment of the present invention; 
         FIG. 3  is a flow chart for another embodiment of he present invention; 
         FIG. 4  is a schematic depiction of another embodiment of the present invention; 
         FIG. 5  is a flow chart for the embodiment shown in  FIG. 4  in accordance with one embodiment of the present invention; 
         FIG. 6  is a flow chart for the embodiment shown in  FIG. 4  in accordance with one embodiment of the present invention; and 
         FIG. 7  is a flow chart for the embodiment shown in  FIG. 4  in accordance with one embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     Referring to  FIG. 1 , a processor-based system may include a plurality of processors, including the processors  12   a ,  12   b , and  12   c  in one embodiment. In some embodiments, only two processors may be included and in other embodiments, more than two processors may be utilized. The processors  12  may be general purpose processors, digital signal processors, or a combination of a digital signal and general purpose processor in one embodiment. 
     Each processor  12  may include a cache  14 . The cache  14  may be integrated in the same integrated circuit with the processor  12  in one embodiment. Coupled to each processor  12  is an interconnection network  16 . The network  16  may in turn be coupled to a memory controller  18  and one or more non-processor agents  20 , such as medium access control (MAC) devices for a wireless network. A coherency protocol  22  and a protocol  40 , discussed later, may be resident in the caches  14  in one embodiment. 
     The embodiment of  FIG. 1  is a wireless network processor-based system where the agents  20  are wireless interfaces including antennas  21 . However, the present invention is not limited to any particular application, but instead may be applicable to any situation where it is advantageous to allow a non-processor agent to directly access a processor cache. 
     Traditionally, hardware-based cache coherency is enforced by a caching agent that obtains the exclusive ownership of a cache line before the cache line in the agent&#39;s cache may be modified. In one embodiment of the present invention, a non-processor agent  20   a , such as a MAC, may “push” data directly to a processor cache, such as a cache  14   b , as shown in  FIG. 1 . Since non-processor agents are not conventionally able to push data directly into a processor cache  14 , the applicable caching agent performs additional steps to guarantee memory consistency. 
     In the discussion that follows, requests to push data directly to a processor cache  14  are targeted to only one processor in the coherency domain. However, in other embodiments, the push requests may involve more than one processor. Moreover, in the example provided below, the modified owned exclusive shared invalid (MOESI) cache coherency protocol is used. However, those skilled in the art will appreciate that the same principles can be applied to any cache coherency protocol that uses a shared state, including modified exclusive shared invalid (MESI) and modified shared invalid (MSI) cache coherency protocols. 
     In the MOESI protocol, the shared state is different than in prior protocols and the owned state is new. In the MOESI protocol the shared state cannot be consistent with memory. However, the shared state still involves more than one processor having the same cache line. A second processor can access a line modified by a first processor. The line is in the shared state for the second processor and the owned state for the first processor. In the modified state there is only one updated copy of the cache line and that copy is not consistent with memory. In the exclusive state data is read and then you go to the exclusive state. In the exclusive state one processor has a copy and no other processor has the cache line and the cache line is consistent with memory. The invalidate state involves a cache line that got invalidated or is not present. 
     Referring to  FIG. 2 , in one embodiment of the present invention, the coherency protocol  22  may be implemented as software that may be stored, for example, within a cache  14 . Alternatively, the protocol  22  may be stored in any memory available on the processor-based system. In addition, the cache coherency protocol  22  may be implemented in hardware, for example in one or more of the caches  14 . 
     Initially, upon receiving a cache line push request from an agent  20 , a check at diamond  24  determines whether the subject processor  12  is the processor targeted by the request, as indicated in diamond  24 , in  FIG. 2 . Thus, in the case of the push request illustrated in  FIG. 1 , the processor  12   b  is the targeted processor, while the processors  12   a  and  12   c  are the non-targeted processors. 
     If the subject processor is the target of the push request, a check at diamond  26  determines whether the request is retried. If the request is not retried, the cache line is simply overwritten and set to the modified state as indicated in blocks  28  and  30 . 
     However, if the subject processor  12  is not a targeted processor, then a check at diamond  32  determines whether the cache line is already present in the cache  14  in the modified, exclusive, shared, or owned state. If so, the cache line is invalidated as indicated in block  34 . 
     In another embodiment, after it is determined that the processor is not the targeted processor, a check can determine if the request was retried as in diamond  26 . If not, the flow ends but, otherwise, the flow continues to diamond  32 . 
     Referring to  FIG. 3 , a hardware or software solution is illustrated for the situation where a processor  12  receives a partial push request. A partial push request is a request to access less than an entire cache line. 
     The protocol  40 , illustrated in  FIG. 3 , begins by determining whether the subject processor  12  is the targeted processor as indicated in diamond  42 . If so, a check at diamond  44  determines if the cache line is already present in the processor&#39;s cache in the modified, owned, exclusive, or shared state. If so, a check at diamond  46  determines whether the request was retried. If not, the cache line is modified by merging it with the partial push data and set to the modified state as indicated in blocks  48  and  50 . 
     If the cache line is not present in the cache  14  of the targeted processor, as determined in diamond  44 , the request is retried at block  52 . Then a read and invalidate (read for ownership) request to that cache is issued to bring the cache line to the relevant cache as indicated at block  54 . The cache line is then stored in the cache in the modified state as indicated in block  56 . 
     In the case of a non-targeted processor, as determined in diamond  42 , a check at diamond  58  determines whether the cache line is in the modified or owned state. If so, the request is retried as indicated in block  60 . Then the cache line is written back to system memory as indicated in block  62 . The cache line is then invalidated in the local cache as indicated in block  64 . 
     Finally, if the cache line is not in the modified or owned states, as determined in diamond  58 , or in other words is in the exclusive or shared state, then the cache line is invalidated in the local cache as indicated in block  66 . 
     In some embodiments of the present invention, non-processor devices coupled to a processor may directly move data directly into a processor&#39;s cache. This avoids the need for two distinct memory operations, including a write generated by the non-processor agent to memory, followed by a read generated by the processor to bring the data into the processor from memory. With embodiments of the present invention, a non-processor agent can use just one write operation to move data into a processor cache. This improves the latency (when accessing full cache lines and, in some cases, partial cache lines) compared to traditional architectures and reduces processor bus traffic in some embodiments. 
     In another embodiment, if the processor is not the targeted processor, a check may determine if the request was retried. If so, the flow ends but, otherwise, the flow continues with diamond  58 . 
     Referring to  FIG. 4 , a system, similar to the one shown in  FIG. 1 , includes processors  12   d  through  12   f , caches  14   d  through  14   f , and push counters  70   d  through  70   f . The processors  12  may be coupled to non-processor agents  20   a  and  20   b  through an interconnection network  72  in one embodiment. The agents  20  may be wireless interfaces, in one embodiment of the present invention, having antennas  21   a  and  21   b . The interconnection network  72  also couples a memory controller  18 . 
     While a network processor-based system is illustrated, those skilled in the art will appreciate that a variety of other arrangements may also be utilized. 
     In the embodiment shown in  FIG. 4 , a push functionality is implemented which enables a non-processor agent, such as the agent  20   b , to push data directly to a cache, such as a cache  14   a , while preserving the coherency of the multiprocessor system. A mechanism dynamically identifies a processor  12  that will accept the push operation. Assuming that there are N processors, including the processors P( 0 ), P( 1 ), and P(N−1) in the coherency domain, each processor  12  implements a roll-over push counter  70  that counts from zero to N−1. Coming out of a reset, all of the counters  70  may be reset to zero. 
     Whenever a push request is generated, the processors  12  increment their push counters  70  by one. The processor  12  whose identifier matches the current push counter  20  value, then claims the push operation and stores the associated data in its cache  14 . 
     All other processors  12  invalidate the cache line in their local caches  14 . Since processor identifiers within the multiprocessor system are unique, one and only one processor  12  accepts any push operation. In one embodiment of the present invention, a selection mechanism may guaranty that only one processor responds to a push operation. 
     Thus, while the non-processor agents  20  may be allowed to push data directly into a processor cache  14 , the processors  12  in that coherency domain perform additional steps that guarantee memory consistency. Again, a set of rules, in accordance with one embodiment, are described below assuming the MOESI cache protocol. However, again, any cache coherency protocol that includes a shared state may be utilized. 
     Referring to  FIG. 5 , the protocol  22   a  for receiving a cache line push request may be implemented in software or hardware as described previously. If the subject processor&#39;s identifier is equal to the push counter  70  value as determined in diamond  74 , a check at diamond  76  determines whether the request was retried. If not, the cache line is simply overwritten and the state is set to modify as indicated in blocks  28  and  30 . 
     If the processor&#39;s identifier is not equal to the push counter value or the request is not retried, a check at diamond  32  determines whether the cache line is already present in the cache of the subject processor. If so, the cache line is invalidated as indicated in block  34 . 
     In another embodiment, if the processor identifier does not equal the push counter value, a check can determine if the request was retried. If so, the flow may end but, otherwise, the flow may continue to diamond  32 . 
     Referring to  FIG. 6 , upon receiving a partial push request, the protocol  40   a  checks at diamond  78  to determine whether the processor&#39;s identifier is equal to the push counter value. If so, a check at diamond  94  determines whether the cache line is already present in the cache and the request is not retried. If so, the cache line is modified and set to the modified state as indicated in blocks  64  and  66 . 
     If the cache line is not present in the cache, the request is retried as indicated in block  88 . A read and invalidate (read for ownership) request is issued to that cache line as indicated in block  90  and the cache line is stored in the cache as indicated in block  92 . 
     If the processor&#39;s identifier is not equal to the push counter value, then a check at diamond  80  determines whether the cache line is in either the modified or own state. If so, the request is retried as indicated in block  82  and the cache line is written back to system memory as indicated in block  84  and the cache line is invalidated in the local cache as indicated in block  86 . 
     If the cache line is in either the exclusive or shared state as determined in diamond  80 , then the cache line is invalidated in the local cache as indicated in block  94 . 
     Referring to  FIG. 7 , the operation of the push counters  70  is further illustrated. The push counters  70  may be software or hardware-based devices. Initially a check at diamond  102  determines whether there has been a system reset. If so, the push counters  70  are set to zero as indicated in block  104 . When a push request is generated, as determined in diamond  106 , the processors  12  increment their push counters  70  by one as indicated in block  108 . A check at diamond  110  determines whether the push counter value equals N−1. If so, the push counter  70  is reset to zero as indicated in block  112 . 
     While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.