Abstract:
One embodiment of the present invention provides a memory controller that contains a distributed cache that stores cache lines for pending memory operations. This memory controller includes an input that receives memory operations that are directed to an address in memory. It also includes a central scheduling unit and multiple agents that operate under control of the central scheduling unit. Upon receiving a current address, a given agent compares the current address with a cache line stored within the given agent. All of the agents compare the current address with their respective cache line in parallel. If the addresses match, the agent reports the result to the rest of the agents in the memory controller, and accesses data within the matching cache line stored within the agent to accomplish the memory operation.

Description:
BACKGROUND  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to computer memory systems. More specifically, the present invention relates to an apparatus and a method for implementing a distributed, caching mechanism for pending memory operations within a memory controller.  
           [0003]    2. Related Art  
           [0004]    To improve performance, many modern computer systems, especially high-end servers, use multiple processors to provide higher throughput. Each of these processors can act independently to provide computational services; however, the processors typically use a common memory to store instructions and data.  
           [0005]    In order to avoid the long latencies associated with accessing main memory, each processor stores recently used instructions and data in a local high-speed cache memory. A processor continues to access a cache line until the cache line is no longer required or is required by another processor. When the processor finally relinquishes a cache line, any changes to the cache line are typically written back to main memory.  
           [0006]    Since each processor in a multiprocessor system includes its own local cache, these processors can be in competition for data stored at a given address thereby causing an access to main memory each time a different processor requires the data. Accessing main memory in this way can seriously degrade system performance.  
           [0007]    What is needed is an apparatus and a method that mitigates the delay involved in frequently storing and retrieving cache lines from the main memory of a multiprocessor system without the problems listed above.  
         SUMMARY  
         [0008]    One embodiment of the present invention provides a memory controller that contains a distributed cache that stores cache lines for pending memory operations. This memory controller includes an input that receives memory operations that are directed to an address in memory. It also includes a central scheduling unit and multiple agents that operate under control of the central scheduling unit. Upon receiving a current address, a given agent compares the current address with the address of a cache line stored within the given agent. All of the agents compare the current address with their respective cache line in parallel. If the addresses match, the agent reports the result to the rest of the agents in the memory controller, and accesses data within the matching cache line stored within the agent to accomplish the memory operation.  
           [0009]    In one embodiment of the present invention, the agent includes a queue within each agent that stores pending memory operations that are waiting for a current memory operation involving the current cache line in that agent to complete.  
           [0010]    In one embodiment of the present invention, the agent writes data stored within that agent to memory after a last entry in the queue has been processed. After writing the data to memory, the agent is free to be associated with a new cache line.  
           [0011]    In one embodiment of the present invention, the memory controller provides status information to the central scheduling unit indicating whether that agent is currently associated with a cache line or is free to be associated with the new cache line.  
           [0012]    In one embodiment of the present invention, an agent can be associated with the current cache line address when the given agent is free to be associated with the new cache line.  
           [0013]    In one embodiment of the present invention, an agent aborts comparing the address with the current cache line address if another agent reports a match.  
           [0014]    In one embodiment of the present invention, the given agent is allocated to the address when the central scheduling unit signals that the given agent is next to be allocated. 
       
    
    
     BRIEF DESCRIPTION OF THE FIGURES  
       [0015]    [0015]FIG. 1 illustrates a computer system including memory controllers in accordance with an embodiment of the present invention.  
         [0016]    [0016]FIG. 2 illustrates memory controller  106  in accordance with an embodiment of the present invention.  
         [0017]    [0017]FIG. 3 illustrates memory controller  302  in accordance with an embodiment of the present invention.  
         [0018]    [0018]FIG. 4 illustrates agent  402  in accordance with an embodiment of the present invention.  
         [0019]    [0019]FIG. 5 illustrates scheduling unit  304  in accordance with an embodiment of the present invention.  
         [0020]    [0020]FIG. 6 is a flowchart illustrating the process of queuing memory operations within an agent in accordance with an embodiment of the present invention.  
         [0021]    [0021]FIG. 7 is a flowchart illustrating the process of servicing a queue in accordance with an embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0022]    The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.  
         [0023]    Computer System  
         [0024]    [0024]FIG. 1 illustrates a computer system including memory controllers in accordance with an embodiment of the present invention. The computer system includes central processing unit (CPU)  102 , CPU  104 , memory controllers  106  and  108 , and memories  110  and  112 . CPUs  102  and  104  can include any type of processing unit that can execute computer instructions. The system illustrated in FIG. 1 is a symmetric multiprocessor (SMP) system and can include more CPUs than shown. CPUs  102  and  104  are coupled to logical SMP bus  114 . Logical SMP bus  114  can be a bus, a network, or other interconnection that responds as an SMP bus.  
         [0025]    Memory controllers  106  and  108  couple memories  110  and  112 , respectively, to logical SMP bus  114 . Memories  110  and  112  can include any type of memory designed to hold computer instructions and data. Typically, memories  110  and  112  are implemented using dynamic random access memory (DRAM). Each memory controller provides access to and caching for its respective memory from the CPUs on logical SMP bus  114 . For example, memory controller  106  provides access to memory  110  and caching for data within memory  110  for CPUs  102  and  104 . Note that the system can include more memory controllers with an associated memory than shown.  
         [0026]    Memory Controller  106   
         [0027]    [0027]FIG. 2 illustrates memory controller  106  in accordance with an embodiment of the present invention. Memory controller  106  is typical of the memory controllers in the system. Memory controller  106  includes scheduling unit  202  and agents  204  and  206 . Note that a memory controller includes one scheduling unit and multiple agents. While two agents are illustrated in FIG. 2, a memory controller can generally include any number of agents.  
         [0028]    Agents  204  and  206  each are associated with or include storage for one cache line address and one cache line of data. These agents are allocated to a cache line by scheduling unit  202  as is described below.  
         [0029]    Agents  204  and  206 , and scheduling unit  202  receive addresses on address bus  220 . If an agent is currently holding a cache line associated with the address on address bus  220 , that agent signals the other agents and scheduling unit  202  that it owns the cache line. For example, if agent  204  is holding the cache line for the address on address bus  220 , agent  204  signals agent  206  and scheduling unit  202  on owned out  222 . Agent  206  uses owned out  224  to signal agent  204  and scheduling unit  202 .  
         [0030]    If an agent is free to accept a new cache line, the agent signals scheduling unit  202 . For example, if agent  204  is free, agent  204  signals scheduling unit  202  on free  210 . If agent  206  is free, agent  206  signals on free  216 .  
         [0031]    When an address appears on address bus  220  and no agent claims ownership of the cache line, scheduling unit  202  signals a free agent to allocate itself to the cache line. For example, if the address on address bus  220  is not owned and agent  204  is free, scheduling unit  202  can signal agent  204  on allocate  212  to allocate itself to the cache line. Scheduling unit  202  can signal agent  206  on allocate  218  if agent  206  is free.  
         [0032]    Each agent queues operations directed to its cache line so that subsequent operations can be directed to other agents. However, if an agent&#39;s queue is full, memory controller  106  cannot accept new addresses until the agent processes an operation and has room in its queue. Each agent can signal scheduling unit  202  that its queue is full. For example, agent  204  can signal that its queue is full on queue full  208  while agent  206  can signal that its queue is full on queue full  214 .  
         [0033]    When an agent signals that its queue is full, scheduling unit  202  starts filling up a first-in-first-out (FIFO) buffer associated with address bus  220 . This FIFO buffer functions as a common queue for the agents. If the FIFO buffer reaches a high-water mark, scheduling unit  202  stops sending new addresses to the FIFO buffer.  
         [0034]    Alternatively, if no FIFO buffer exists, when an agent signals that its queue is full, scheduling unit  202  can simply stop new addresses from appearing on address bus  220 .  
         [0035]    Memory Controller  302   
         [0036]    [0036]FIG. 3 illustrates memory controller  302  in accordance with an embodiment of the present invention. Memory controller  302  includes scheduling unit  304  and agents  306 ,  308 ,  310 , and  312 . FIG. 3 shows how the owned out signals are coupled between the agents; however, the signals coupled to scheduling unit  304  are not shown. Agents  306 ,  308 ,  310 , and  312  are coupled to scheduling unit  304  as described above in conjunction with FIG. 2. Since each agent can hold one cache line, a memory controller with more agents is more efficient.  
         [0037]    Agent  402   
         [0038]    [0038]FIG. 4 illustrates agent  402  in accordance with an embodiment of the present invention. Agent  402  is typical of the agents within the memory controller. Agent  402  includes cache line address  404 , cache line data  406 , address comparator  408 , queue  410 , memory interface  412 , bus interface  414 , and status generator  416 .  
         [0039]    Cache line address  404  is the address of the current cache line stored in agent  402  and is updated each time agent  402  is allocated to a new cache line. Cache line data  406  is the current value associated with cache line address  404 . Agent  402  updates cache line data  406  for each memory operation related to the address stored in cache line address  404 .  
         [0040]    Address comparator  408  compares the incoming address on address in  418  to cache line address  404 . If these addresses match, status generator  416  signals the other agents and the scheduling unit on owned out  422 , and places the incoming memory operation in queue  410 . Queue  410  ensures that the memory operations are properly ordered. If queue  410  becomes full, agent  402  signals the scheduling unit on queue full  428 . The scheduling unit then stops new addresses until agent  402  becomes available.  
         [0041]    Agent  402  executes the memory operations saved in queue  410  on a first-in, first-out basis. On a first read from memory, memory interface  412  reads the data from memory on memory data  430  and saves the data in cache line data  406 . This data is made available to the requesting processor on SMP bus data  432 . On subsequent operations saved in queue  410 , agent  402  operates on cache line data  406 , either updating cache line data  406  during a write operation or providing cache line data  406  to SMP bus data  432  during a read operation. After the last operation saved in queue  410  has been processed, cache line data  406  is written to memory on memory data  430 .  
         [0042]    Memory interface  412  provides control signals to access memory on memory data  430  and to route data between memory and cache line data  406 . Bus interface  414  provides control signals to access the SMP bus on SMP bus data  432  and to route data between the SMP bus and cache line data  406 .  
         [0043]    In addition to signaling that agent  402  owns the cache line as described above, status generator  416  signals the scheduling unit that agent  402  is free to accept a new cache line on free  424  after the last operation in queue  410  has been processed and cache line data  406  has been written to memory. Note that agent  402  can still respond to an address on address in  418  that matches cache line address  404  while free  424  is set.  
         [0044]    The scheduling unit selects the next agent to allocate as described below and signals that agent. For example, if agent  402  has signaled that it is free on free  424 , the scheduling unit may signal agent  402  that it is next to allocate on allocate  426 . When an address arrives on address in  418  while allocate  426  is set, status agent  402  accepts the address as a new cache line address if none of the other agents set their owned out line. Owned in  420  is coupled to each of the other agents&#39; owned out lines.  
         [0045]    Scheduling Unit  
         [0046]    [0046]FIG. 5 illustrates scheduling unit  304  in accordance with an embodiment of the present invention. Scheduling unit  304  includes agent allocator  504 . In operation, scheduling unit  304  receives address in  508 , free  510 , owned out  512 , and queue full  514 . Free  510 , owned out  512 , and queue full  514  each include a signal line from each agent in the system.  
         [0047]    Agent allocator  504  selects one of the agents that is free from free  510  and sends allocate  516  to that agent. Only one allocate signal can be sent on allocate  516  at any given time. Agent allocator  504  can use any suitable algorithm to select the next agent to allocate. For example, agent allocator  504  could use a least recently used algorithm to select the next agent to allocate.  
         [0048]    If any agent signals that its queue is full on queue full  514 , scheduling unit  304  starts filling up a first-in-first-out (FIFO) buffer that functions as a common queue for the agents. If the FIFO buffer reaches a high-water mark, scheduling unit  304  stops sending new addresses to the FIFO buffer.  
         [0049]    Queuing Memory Operations  
         [0050]    [0050]FIG. 6 is a flowchart illustrating the process of queuing memory operations within an agent in accordance with an embodiment of the present invention. The system starts when the memory controller, receives an address from the SMP (operation  602 ). Next, each agent within the memory controller compares the address with its current cache line address (operation  604 ).  
         [0051]    If no agent sets its owned out line, each agent that is free and has set its free line examines its allocate line (operation  606 ). Note that only one agent can have its allocate line set at a given time. If an agent&#39;s allocate line is set, that agent allocates to the incoming address, and stores the address in it cache line address (operation  608 ).  
         [0052]    After allocating to the address at operation  608  or if the agent has a match at operation  604 , the agent places the memory operation in its queue (operation  614 ).  
         [0053]    If the agent receives a match from another agent at operation  604 , the agent ignores the operation (operation  616 ). After ignoring the operation at operation  616 , putting the operation in the queue at operation  614 , or if the agent&#39;s allocate is not set at operation  606 , control returns to operation  602  to receive a new memory address.  
         [0054]    Processing Operations in the Queue  
         [0055]    [0055]FIG. 7 is a flowchart illustrating the process of servicing a queue in accordance with an embodiment of the present invention. The system starts when an agent gets an operation that is stored in its queue (operation  702 ). Next, the agent processes the operation (operation  704 ). The agent then determines if the queue is empty (operation  706 ). If not, control returns to operation  702  to get the next operation from the queue.  
         [0056]    If the queue is empty because all pending memory operations have completed at operation  706 , the agent flushes the cache line data to memory (operation  708 ). Finally, after the data has been flushed to memory, the agent sets free to signal the scheduling unit that the agent is free (operation  710 ).  
         [0057]    The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.