Abstract:
The present invention provides a multiprocessor system and method in which plural memory locations are used for storing TLB-shootdown data respectively for plural processors. In contrast to systems in which a single area of memory serves for all processors&#39; TLB-shootdown data, different processors can describe the memory they want to free concurrently. Thus, concurrent TLB-shootdown request are less likely to result in performance-limiting TLB-shootdown contentions that have previously constrained the scaleability of multiprocessor systems.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     The present invention relates to computers and, more particularly, to multiprocessor systems employing TLB shootdown as part of a memory-management scheme. A major objective of the invention is to provide an approach to TLB shootdown that scales well with large numbers of processors in a multi-processor system.  
         [0002]     Many modern computer systems use virtual-memory schemes to match the memory requirements of the computer programs run on these systems to available memory resources. An operating system typically assigns virtual memory address “pages” to each program, and assigns these virtual-memory pages to physical memory pages, preferably in solid-state random access memory (RAM), with excess virtual memory pages being assigned to hard-disk locations on some priority basis when RAM capacity is exceeded. The virtual-memory assignments are stored in a page table, typically in RAM. So that a processor does not have to perform a time-consuming access of main memory every time a virtual memory assignment needs to be read, copies of recently used page-table assignments can be cached in a translation look-aside buffer (TLB).  
         [0003]     Typically, when a program terminates, some of the virtual memory assigned to it can be made available to other programs. The operating system can instruct the processor running the program to de-assign the no-longer-needed virtual memory pages in the page table. Then any corresponding TLB entries for that processor and for any other processor in a multiprocessor system must be purged so that all TLBs are coherent with the page table. To this end, a processor can write its TLB shootdown to a dedicated location in main memory and send an interrupt to the other processors, which then read the TLB-shootdown data, purge their TLBs accordingly, and report when their purges are complete. The de-assigned virtual memory can then be released for reassignment.  
         [0004]     Various lockout mechanisms can be employed to prevent a processor from writing TLB-shootdown data to the TLB-shootdown memory location when it is in use by another processor. The processor that is locked out waits until the first TLB purge is complete before it can begin its own TLB purge. The “waiting” actually can involve a lot of rechecking, which can consume system bandwidth. As the number of processors increases, the frequency of contentions, the waiting periods, and the bandwidth consumption all increase, limiting scalability. What is needed is an approach to TLB-shootdown that scales better with the number of processors in a multiprocessor system.  
       SUMMARY OF THE INVENTION  
       [0005]     The present invention provides a multiprocessor system and method in which plural memory locations are used for storing TLB-shootdown data respectively for plural processors. A major advantage of the invention is that processors do not have to “take turns” writing their TLB-shootdown list. In contrast to systems in which a single area of memory serves for all processors&#39; TLB-shootdown data, different processors can describe the memory they want to free concurrently. This becomes important in multiprocessor systems with large numbers of processors, since the likelihood of concurrent TLB shootdowns increases rapidly with the number of processors. These and other features and advantages of the invention are apparent from the description below with reference to the following drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]     Specific embodiments of the invention are illustrated in the following figures, which are not depictions of the invention itself.  
         [0007]      FIG. 1  depicts a multiprocessor computer system in accordance with the present invention.  
         [0008]      FIG. 2  is a flow chart of a method of the invention practiced in the context of the system of  FIG. 1 .  
         [0009]      FIG. 3  is a flow chart of a portion of the method of  FIG. 2  showing explicit parallelism.  
         [0010]      FIG. 4  depicts another multiprocessor computer system in accordance with the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0011]     A multiprocessor computer system AP 1  comprises three processor nodes N 1 , N 2 , and N 3 , volatile physical memory  11 , a hard disk  13 , and a signal router  15 . System AP 1  includes three nodes, which suffices to explain the invention. However, the marginal advantage of the invention is greater for embodiments with more nodes, e.g., 48 or more. Node N 1  includes a processor P 1 , a TLB T 1 , and a cache C 1 . Likewise, node N 2  includes a processor P 2 , a TLB T 2 , and a cache C 2 . Also, node N 3  includes a processor P 3 , a TLB T 3 , and a cache C 3 . Data communication among processors P 1 -P 3  and between the processors and memory  11  is via signal router  15 ; in addition, interrupts are transmitted via signal router  15 .  
         [0012]     Hard disk  13  provides non-volatile long-term storage for system AP 1 . It can store an operating system OS, programs including programs PR 1 -PR 4 , non-volatile data DN, and overflow virtual-memory pages VMO (when physical memory is too small to fit all requested virtual memory). Upon boot-up of system AP 1 , part of operating system OS becomes resident in operating system space OSS of physical memory  11 . Operating system OS also reserves memory space for a process-memory table  21 , a page table  23 , and TLB-shootdown lists TS 1 , TS 2 , and TS 3 . Lists TS 1 , TS 2 , and TS 3  provide for storing shootdown data for a respective node N 1 , N 2 , and N 3 ; these lists provide flags F 12 , F 13 , F 21 , F 23 , F 31 , and F 32  that indicate whether a requested shootdown has been completed for each combination of requesting node and responding node. The bulk of memory  11  is assignable physical memory  25  for use by programs PR 1 -PR 4 .  
         [0013]     In this example, program PR 1  is launched on node N 1 . Operating system OS requests a virtual memory block to be reserved for program PR 1 , storing this virtual-memory-to-program assignment in process-memory table  21 . Operating system OS inspects physical page table  23  to find a free region of assignable physical memory space  25  and, accordingly, assigns the requested virtual memory pages to a free physical memory space PS 1 ; processor P 1  then marks space PS 1  unavailable and owned by processor P 1 .  
         [0014]     Then program PR 2  is launched on node N 2 . Operating system OS checks virtual page table  21  for free virtual memory pages and assigns some to program PR 2 . An instance of operating system OS running on processor P 2  inspects physical page table  23  for free physical memory pages; since space PS 1  is marked unavailable, processor P 2  selects free space PS 2 , which is then marked owned by processor P 2 . Program PR 3  is launched on node N 3 ; the virtual memory space it requires cannot be assigned to spaces PS 1  or PS 2 , and so it is assigned to space PS 3 , which is then marked unavailable and owned by processor P 3 . The remainder of assignable memory space  25  remains available for future assignment. The assigned spaces can be used for memory-resident program code and temporary data.  
         [0015]     At this point, a method M 1  in accordance with the invention applies to the example; method M 1  is flow-charted in  FIG. 2 . At step S 1 , program PR 1  terminates. Operating system OS determines from process-memory table  21  that some virtual memory pages can be made available now that program PR 1  no longer requires them. (There may be some virtual-memory pages used by program PR 1  that cannot be freed because they are shared with another program.) Operating system OS instructs node N 1  to free virtual memory for reassignment. Accordingly, node N 1  de-assigns that virtual memory space in physical page table  23 , but retains ownership over the corresponding entries. Then operating system OS instructs node N 1  to purge TLB T 1  of any entries relating to the de-assigned virtual memory space at step S 3 . Then node N 1  writes addresses to be purged to shootdown memory space TS 1  at step S 4 .  
         [0016]     At step S 5 , node N 1  broadcasts a request for a TLB shootdown by activating an interrupt and asserting a vector corresponding to memory space TS 1 . Nodes N 2  and N 3  respond to the request by reading the shootdown specification from space TS 1  and implementing the indicated purge at step S 6 . Each receiving processor N 2 , N 3  reports successful completion of the purge by setting dedicated flags F 12  and F 13  (shown in  FIG. 1 ) at step S 7 . Node N 1  can repeatedly examine flags F 12  and F 13 . Once all flags are set, node N 1  can detect by reading flags F 12  and F 13  that the shootdown request has been met at step S 8 . In response, node N 1  releases ownership of the specified virtual addresses so that they are available for reassignment at step S 9 .  
         [0017]     In  FIG. 2 , steps S 5 , S 6 , and S 7  have supplementary actions described in parentheses. These are intended to show how the illustrated embodiment handles concurrent TLB-shootdown request. For example, node N 2  can request a TLB shootdown concurrent with step S 5 . This request can be received by node N 1  while node N 1  is awaiting a response to its TLB-shootdown request. In the absence of the request from node N 2 , node N 1  would check the flag status for memory space TS 1  periodically to determine when the other nodes have completed their purges in response to the request by node N 1 . However, the request by node N 2  interrupts this checking; rather than continue checking memory, node N 1  responds to the request by node N 2  by reading space TS 2  and purging the addresses indicating therein at step S 6 . Then node N 1  reports completion of the purge by setting a flag at memory space TS 2 . When this reporting is complete, node N 1  returns to checking the completion status of space TS 1 . Completion of the node N 1  request is indicated at step S 9  when all flags of space TS 1  are set. Then node N 1  releases virtual memory by writing to physical page table  23 .  
         [0018]     The parallelism provided by system AP 1  is perhaps more apparent in  FIG. 3 , which is a flow chart of a method M 2 , which is a reconceptualization of steps S 4 -S 9  of method M 1 . Method M 2  begins with steps S 41  and S 42  with nodes N 1  and N 2  writing shootdown data into first and second shootdown memory areas. Then, at steps, S 51  and S 52 , nodes N 1  and N 2  respectively request TLB shootdowns. Each node receives the other&#39;s shootdown request at respective steps S 61  and S 62 . Each node reports completion of the other nodes request respectively at steps S 71  and S 72 . Each node detects that its request has been met respectively at step S 81  and S 82 . Each node releases the virtual memory associated with its purge request at respective steps S 91  and S 92 . As is apparent from  FIG. 3 , the present invention allows a TLB request can be performed concurrently.  
         [0019]     In some cases, shootdown requests are issued a page at a time. However, the invention also provides for embodiments that list a large set of pages in the TLB-shootdown space so that fewer requests are required. Even where a series of request are required for freeing virtual memory for reassignment, the invention provides for performance savings over the prior art. In some embodiments, even though requests are performed serially, some pipelining is possible. For example, a node can begin writing a second page in the page table while issuing a TLB-shootdown request for a first page.  
         [0020]     The assignment of processors and associated components is not fixed, but can be configured by a system administrator for system AP 1 . For example, system AP 1  can be configured with two processors P 1  and P 2  assigned to a node N 11 , as shown in  FIG. 4 . Processor P 3  is assigned to node N 22 . Processors P 1  and P 2  are associated with the same TLB-shootdown memory TS 1 . If processor P 1  and P 2  attempt concurrent TLB-shootdown requests, there will be a race condition. One processor will have its request processed and the other will have to wait, as in some conventional systems employing TLB shootdown. However, as long as the number of processors per node is small, the infrequency of such conflicts renders them manageable. An advantage of combining processors within a node is that fewer vectors and memory spaces are required for the multiprocessor system. For example, assigning two processors per node halves the number of distinct vectors required—which may be helpful in a system with a limited number of vectors (e.g., 256) and with lots of devices to assign to the available vectors.  
         [0021]     In the embodiment of  FIG. 3 , if processor P 1  is requesting a TLB-shootdown, processor P 2  must wait until that shootdown is completed before asserting its own. In alternative embodiments, processors are dynamically reassigned to nodes to minimize such contentions. For example, if processor P 1  is managing a TLB shootdown, processor P 2  can be dynamically reassigned to node N 22  either immediately or in case processor P 2  needs to initiate its own TLB shootdown.  
         [0022]     In the illustrated embodiments, there is a fixed assignment of TLB lists to nodes. In some alternative embodiments, TLB-lists are assigned to nodes upon request, e.g., in a round-robin fashion. This can reduce the number of vectors required as there can be fewer lists than nodes. If more nodes request TLB shootdowns than there are lists available, conventional lockout, e.g., semaphore-based, techniques can be applied. As an alternative to indicating which nodes have completed the purge, it is possible to simply count the number of completions; this allows the use of more efficient hardware atomic increment operations to determine when a TLB-shootdown request has been satisfied. These and other variations upon and modification to the illustrated embodiments are provided for by the present inventions, the scope of which is defined by the following claims.