Patent Publication Number: US-6910107-B1

Title: Method and apparatus for invalidation of data in computer systems

Description:
FIELD OF THE INVENTION 
   The present invention relates to the field of data storage, and more particularly to methods and systems for invalidating data in a hierarchical data storage system. 
   BACKGROUND OF THE INVENTION 
   A computer typically has a main memory that stores data that is accessed by a processor. In the typical configuration, main memory consists of dynamic random access memory (DRAM). To improve the speed at which data is retrieved from the main memory, a cache memory (a higher-speed data storage medium than the main memory) is often placed between the main memory and the processor. Memory caching is effective because many computer programs that run in the processor repeatedly access the same data. By keeping as much of this data as possible in the cache memory, the computer avoids accessing the slower main memory and instead accesses the higher speed cache memory. 
   When the processor needs to access data from memory, it first checks the cache memory to see if the data is there. If the data is in the cache memory, it is retrieved without accessing the main memory. Memory caching may dramatically improve the performance of applications because accessing a byte of data in cache memory can be many times faster than accessing a byte in main memory. This speed difference is possible because cache memory is usually made of high-speed static random access memory (SRAM) instead of the slower and cheaper DRAM. 
   Alternatively, cache memories may be built into the architecture of microprocessors. For example, the 80486 and the Pentium microprocessors from Intel Corporation contain cache memory. 
   Another form of caching, similar to memory caching, is disk caching. Disk caching works under the same principle as memory caching, but instead of using high-speed SRAM, a disk cache may use conventional main memory. The most recently accessed data from the disk (and possibly adjacent sectors) is stored in the disk cache. When the processor needs to access data from the disk, it first checks the disk cache to see if the data is there. If the data is there, it is retrieved without accessing the disk drive. Disk caching can dramatically improve the performance of programs in the processor because accessing a byte of data from RAM can be thousands of times faster than accessing a byte on a hard disk. 
   Memory caching and disk caching are considered “hierarchical” memory systems. For instance, in memory caching, the slower main memory is lower in the hierarchy than the faster cache memory. It is also possible that there are several layers of cache memory, where a second cache memory is placed between a first cache and the processor. In this case, the second cache memory is higher in the hierarchy than the first cache memory. Similarly, with disk caching, the slower disk drive is lower in the hierarchy than the faster main memory. 
   With memory caching, the processor may write to a memory address whose data is stored in the cache memory. In this case, the processor may write the data to the cache memory but may not to the main memory. Thus, for periods of time it is possible that the cache memory is current, i.e., up-to-date, but the main memory is not current. It is the function of a “coherence protocol” to eventually copy the data in the cache memory to the main memory to keep the main memory current. 
   Cache memory is typically much smaller than main memory. Eventually, the cache memory may become full, and the coherence protocol will copy some data in the cache memory to the main memory to make room for new, more-ofen accessed data from the main memory. Copying data from the cache memory to the main memory, however, is time consuming for the computer system. Often, the data the coherence protocol copies to the main memory is trash or “scratch” data that may be discarded. As a result, the coherence protocol wastes computer resources by copying useless data from the cache memory to the main memory. 
   The Intel Pentium chip provides for a way to prevent data in the cache memory from being copied to the main memory. Using an “INVD” instruction, the entire cache memory may be marked “invalid,” so that the data in the cache memory is not copied to the main memory. This command is used for initialization processes, however, and is impractical for use during normal processing. Because this instruction invalidates the entire cache memory, if the instruction were used during normal processing it is likely that useful, necessary data would be invalidated. Thus, the Intel Pentium chip “INVD” instruction does not address the problem of wasting computer resources by copying scratch data from the cache memory to the main memory during normal processing. 
   Disk caching has the same problem as memory caching. For instance, coherence protocols in a disk caching system may unnecessarily copy scratch data from main memory to the disk drive, wasting computer resources. Other hierarchical storage systems such as virtual memory and non-uniform memory access (NUMA) also encounter this problem. 
   NUMA is a type of parallel processing architecture in which each processor has a designated local memory but can also access remote memory owned by remote processors. It is “non-uniform” because the memory access times are faster when a processor accesses its own local memory than when it accesses memory of a remote processor. To increase memory access times in a NUMA system, the local memory may also act as a cache memory between the local processor and the memory of a remote processor. A coherence protocol functions to keep the remote memory current by coping data from the local memory to the remote memory when necessary. Thus, the processor&#39;s own local memory is higher in the hierarchy than the remote processor&#39;s memory. In this situation, the coherence protocol may unnecessarily copy scratch data from the local memory to the remote processor&#39;s memory. 
   Virtual memory is a type of memory management where some data that would otherwise be stored in main memory is stored on a disk drive instead, possibly because there is not enough main memory to store all the data. The access times of disk drives, as discussed above, is typically slower than the access times of main memory. To increase memory access times in a virtual memory system, the frequently accessed data is stored in main memory. A coherence protocol functions to keep the data stored on the disk drive current by copying data from the main memory to the disk drive when necessary. Thus, the main memory has a higher hierarchy than the disk drive. In this situation, similar to disk caching, the coherence protocol may unnecessarily copy scratch data from the main memory to the disk drive. 
   More generally, therefore, it is desirable to provide a way to save computer system resources in a hierarchical data storage system by preventing scratch data from being copied from a higher hierarchy data storage space to a lower hierarchy data storage space. 
   SUMMARY OF THE INVENTION 
   Methods and systems consistent with this invention hierarchically store data in a computer system comprising a first storage space for storing data, a second storage space for storing data, wherein the first storage space is lower in a hierarchy than the second storage space. Such methods and systems designate an area of the second storage space that contains scratch data as invalid, and permit a writing over of the invalid data in the second storage space. Further, during operation of a coherence protocol, only the area not designated as invalid is copied from the second to the first storage space. 
   Methods and systems consistent with this invention hierarchically store data in a computer system having a main memory and a cache memory. Such methods and systems designate an area of the cache memory that contains scratch data as invalid, wherein the invalid data occupies less space than a maximum space of the cache memory, and permit a writing over of the invalid data in the cache memory. 
   Methods and systems consistent with this invention hierarchically store data in a computer system including a virtual memory having a main memory and a disk storage space. Such methods and systems determine an area of the main memory that contains scratch data as invalid, and permit a writing over of the invalid data in the main memory. 
   Methods and systems consistent with this invention hierarchically store data in a non-uniform memory accessing computer system having a remote memory and a local memory. Such methods and systems designate an area of the local memory that contains scratch data as invalid, and permit a writing over of the invalid data in the local memory. 
   The summary and the following detailed description should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an implementation of the invention and, together with the description, serve to explain the advantages and principles of the invention. In the drawings, 
       FIG. 1  is a block diagram of a general hierarchical storage structure consistent with this invention; 
       FIG. 2  is a flow diagram of a process for hierarchically storing data in the general hierarchal storage space of  FIG. 1  in a manner consistent with this invention; 
       FIG. 3  is a block diagram of a data processing system in which methods and systems consistent with this invention may be implemented; 
       FIG. 4  is a flow diagram of a process for memory caching in the data processing system of  FIG. 3  in a manner consistent with this invention; 
       FIG. 5  is a block diagram of a data processing system, consistent with this invention, including a virtual memory; 
       FIG. 6  is a flow diagram of a process for storing data in a computer system including the virtual memory of  FIG. 5  in a manner consistent with this invention; 
       FIG. 7  is a block diagram of a data processing system, consistent with this invention, including a non-uniform memory access (NUMA) system; and 
       FIG. 8  is a flow diagram of a process for storing data in a computer system having the NUMA in  FIG. 7  in a manner consistent with this invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   Overview 
   The following description of embodiments of the present invention refers to the accompanying drawings. Where appropriate, the same reference numbers in different drawings refer to the same or similar elements. 
   Methods and systems consistent with this invention conserve computer resources in a hierarchical memory system by preventing scratch data from unnecessarily being copied from a higher hierarchy to a lower hierarchy storage space. Such methods and systems invalidate portions of data in the higher hierarchy storage space so that the coherence protocol does not copy the invalidated data to the lower hierarchy storage space. 
   For instance, suppose an application running in a processor calculates the value of R 2  where R 2 =x 2 +y 2 . The application first calculates x 2  and stores the result at a first address. The application then calculates y 2  and stores the result at a second address. Finally, the application sums the values at first and second address and stores this, R 2 , at a third address. The data at first, second, and third addresses may be stored in a high hierarchy memory, such as a cache memory. The data at the first and second addresses, however, are no longer needed and are scratch data. Methods and systems consistent with this invention mark the scratch data at the first and second addresses as invalid. Then, the coherence protocol may save computer resources by not copying the scratch data at first and second address to lower levels of the memory hierarchy, such as a main memory. 
   In a disk caching application, first and second addresses are disk addresses, and the application instructs the disk cache to mark the scratch data as invalid. If the disk cache stores the scratch data, then the scratch data is marked invalid. Then, the coherence protocol may save computer resources by not copying the scratch data from main memory to the disk drive. 
   In a virtual memory application, first and second disk addresses are memory addresses, similar to the situation in memory caching. The application instructs the virtual memory to mark the scratch data as invalid. If the main memory of the virtual memory stores the scratch data, the data is marked invalid. Then, the coherence protocol may save computer resources by not copying the scratch data to the disk. 
   In an NUMA-based application, first and second addresses are also memory addresses. The application instructs the NUMA system to mark the scratch data as invalid. If the local memory stores the scratch data, the data is marked invalid. Then, the coherence protocol may save computer resources by not copying the scratch data to the remote memory. 
   Implementation Details 
     FIG. 1  is a block diagram of a general hierarchical storage structure  100 , consistent with this invention. General hierarchical storage structure  100  comprises a first storage space  102 , and a second storage space  104 . First storage space  102  is lower in a hierarchy for data storage than second storage space  104 . A processor  106 , such as a CPU, is in communication with general hierarchical storage structure  100 . 
   Methods and systems consistent with this invention hierarchically store data in a computer system comprising first storage space  102  and second storage space  104 . Such methods and systems designate an area of second storage space  104  that contains scratch data as invalid, and permit a writing over of the invalid data in second storage space  104  with new data. Such methods and systems may then copy only the data not marked as invalid data from the second storage space  104  to first storage space  102 . 
   For example,  FIG. 2  is a flow diagram of a process  200 , consistent with this invention, for storing data in general hierarchal storage space  100 . Process  200  may be implemented by an operating system or an application program running in processor  106 . Alternatively, all or parts of process  200  are implemented by other portions of general hierarchical data storage space  100 . 
   First, methods and systems consistent with this invention retrieve data stored in first storage space  102  for storage in second storage space  104  (step  201 ). Step  201  may be skipped in some instances when some of the data in first storage space  102  is already stored in second storage space  104 . Such methods and systems then instruct the marking of scratch data that may be discarded at an address as invalid (step  202 ). Such methods and systems determine whether the retrieved data contains the scratch data stored at the memory address (step  204 ). The data stored at the memory address may occupy less space than a maximum capacity of the retrieved data. For instance, the space of the data stored at the memory address may be a line or a page of memory. If the retrieved data contains the data stored at the memory address (step  204 ), such methods and systems mark the scratch data at the memory address as invalid (step  206 ). This allows writing over the marked invalid data in the retrieved data with new data without copying the marked invalid data to first storage space  102  (step  208 ). Finally, such methods and systems may copy the new data from second storage space  104  to first storage space  102  (step  210 ). It is possible, however, that the new data may be marked invalid and copying the new data to first storage space  102  is unnecessary. 
   As process  200  demonstrates, methods and systems consistent with this invention may use the space in second storage space  104  that stores the scratch data without copying the scratch data to first storage space  102 . This also saves clock cycles and increases the speed of processing data. Moreover, the marking of data as “invalid” helps to ensure that applications do not use this data which may not be accurate. 
   More specific embodiments of general hierarchical storage space  100  are described below. These embodiments include memory caching, disk caching, virtual memory, and NUMA-based applications. 
     FIG. 3  is a block diagram of a data processing system, consistent with this invention, for memory caching. Computer  300  includes a main memory  302 , such as a DRAM, and a cache memory  304  such as an SRAM. Main memory  302  and cache memory  304  makeup a hierarchical memory structure  318 . Computer  300  also comprises a secondary storage device  312 , a processor  310  such as a central processing unit (CPU), an input device  314 , and an output device  316 . Input device  314  may comprise a keyboard, a mouse, or both. Output device  316  may be a cathode ray tube (CRT) that can display a graphical user interface (GUI). Processor  310  may also comprise a processor memory  320 . Main memory  302  holds an operating system  306  for operating the data processing of computer  300 . 
   Methods and systems consistent with this invention hierarchically store data in computer  300  having main memory  302  and cache memory  304 . Such methods and systems designate an area of cache memory  304  that contains scratch data as invalid, wherein the invalid data occupies less space than a maximum space of cache memory  304 , and permit a writing over of the invalid data in cache memory  304  with new data. Such methods and systems may then copy only the not invalid data from cache memory  304  to main memory  302 . 
   For example,  FIG. 4  is a flow diagram of a process  400 , consistent with this invention, for memory caching in computer  300  in FIG.  3 . Process  400  may be implemented by the operating system  306  or an application, running in processor  310 . All or parts of process  400  may be implemented by cache memory  304  or other portions of computer  300 . 
   First, methods and systems consistent with this invention instruct the marking of scratch data at an address as invalid (step  401 ). Such methods and systems determine whether cache memory  304  contains the scratch data stored at the memory address (step  402 ). This step may take place in at least either processor  310  or cache memory  304 . The scratch data may occupy less space than a maximum space of the cache memory. For instance, the scratch data may be a line of memory, which is  64  bytes of information, whereas the maximum capacity of cache memory  304  is likely multiple megabytes. If cache memory  304  contains the scratch data (step  402 ), then such methods and systems mark the scratch data in cache memory  304  as invalid (step  404 ). This allows writing over the marked invalid data in cache memory  304  with new data without copying the scratch data to main memory  302  (step  406 ). Finally, such methods and systems may copy the new data to main memory  302  from cache memory  304 , if necessary (step  408 ). It is possible, however, that the new data would also be marked invalid and copying the new data from cache memory  304  to main memory  302  is unnecessary. 
     FIG. 5  is a block diagram of a data processing system, consistent with this invention, including a virtual memory  500 . Virtual memory  500  comprises main memory  302  and disk storage space  312 . Processor  310  interacts with virtual memory  500  as though it were any hierarchical memory structure. 
   Methods and systems consistent with this invention hierarchically store data in computer  300  including virtual memory  500  having main memory  302  and disk storage space  312 . Such methods and systems determine an area of main memory  302  that contains scratch data as invalid, and permit a writing over of the invalid data in main memory  302  with new data. Such methods and system may then copy only the not invalid data from main memory  302  to disk storage space  312 . 
   For example,  FIG. 6  is a flow diagram of a process  600 , consistent with this invention, for storing data in virtual memory  500  shown in FIG.  5 . Process  600  may be implemented by operating system  306  or an application running in processor  310 . All or parts of process  600  may also be implemented by other portions of computer  300 . 
   First, methods and systems consistent with this invention instruct the marking of scratch data at a memory address as invalid (step  601 ). Such methods and systems determine whether main memory  302  contains the scratch data stored at the memory address (step  602 ). The scratch data may occupy less space than a maximum capacity of virtual memory  500  portion of main memory  302 . For instance, the scratch data may be a page of memory, which is less than the maximum capacity of main memory  302 . If main memory  302  contains the scratch data (step  602 ), such methods and systems mark the scratch data stored in main memory  302  as invalid (step  604 ). This allows writing over the marked invalid data in main memory  302 , with new data without copying the scratch data to disk storage space  312  (step  606 ). Finally, such methods and systems may copy the new data to disk storage space  312  from main memory  302  if necessary (step  608 ). It is possible, however, that the new data would also be marked invalid and copying the new data from main memory  302  to disk storage space  312  is unnecessary. 
   Main memory  302  in  FIG. 5  may also be replaced by a hierarchical memory structure, such as hierarchical memory structure  318 . In this case, the present invention could be implemented both within hierarchical memory structure  318  and within virtual memory  500 . 
     FIG. 7  is a block diagram of a NUMA system  700 , consistent with this invention. A remote computer comprises a remote memory  706  and a remote processor  708 , such as a CPU. A local computer comprises a local memory  710  and a local processor  712 , such as a CPU. Remote computer  702  and local computer  704  communicate with each other. For instance, remote and local computers  702 ,  704  may communicate with each other through network  714 . Alternatively, first and second computers  702 ,  704  may communicate with each other in any other way. 
   Methods and systems consistent with this invention hierarchically store data in NUMA system  700  having remote memory  706  and local memory  704 . Such methods and systems designate an area of local memory  704  that contains scratch data as invalid, and permit a writing over of the invalid data in local memory  704  with new data. Such methods and systems then may copy only the not invalid data to remote memory  706 . 
   For example,  FIG. 8  is a flow diagram of a process  800 , consistent with this invention, for hierarchically storing data in NUMA  700 . Process  800  may be implemented by an operating system or application running in local processor  310 . All or parts of process  800  may be implemented by other parts of NUMA  700 . 
   First, methods and systems consistent with this invention may retrieve data stored at remote memory  706  for storage in local memory  710  (step  801 ). Step  101  may be skipped in some instances when some of the data in remote memory  506  is already stored in local memory  510 . Such methods and systems instruct the marking of scratch data at an address as invalid (step  802 ). Such methods and systems determine whether the retrieved data stored in local memory  710  contains the scratch data stored at the memory address (step  804 ). The scratch data may occupy less space than a maximum capacity of the retrieved data. For instance, the scratch data may be a page of memory that is less than the maximum capacity of the retrieved data. If the retrieved data in local memory  710  contains the scratch data at the memory address (step  804 ), such methods and systems mark the scratch data as invalid (step  806 ). This allows writing over the marked invalid data with new data without copying the marked invalid data to remote memory  706  (step  808 ). Finally, such methods and systems may copy the new data to remote memory  706  (step  810 ). It is possible, however, that the new data may be marked invalid and copying the new data from local memory  706  to remote memory  710  is unnecessary. 
   As shown in FIG.  3  and process  400  of  FIG. 4 , first storage space  102  may be a main memory, and second storage space  104  may be a cache memory. Alternatively, as shown in FIG.  5  and process  600  of  FIG. 6 , general hierarchical storage space  100  may comprise a virtual memory. For instance, first storage space  102  may be a disk storage space, and second storage space  104  may be a main memory. Similarly, general hierarchical storage space  100  may be a disk cache system. For instance, first storage space  102  may be a disk storage space and second storage space  104  may be a disk cache in a main memory. Further, as shown in FIG.  7  and process  800  of  FIG. 8 , first storage space  102  and second storage space  104  may be a NUMA. 
   One skilled in the art will appreciate that numerous variations to this system exist. For instance, a cache memory may be a reserved section of a main memory instead of an independent device. Further, it is possible that there are several hierarchical layers in a hierarchical storage system. For instance, in memory caching, a second cache memory may be placed between a first cache and the processor. The first cache memory may be placed between the second cache memory and the processor. In fact, methods and systems consistent with this invention may use a hierarchical memory structure with any number of layers. 
   Further, a disk caching system consistent with this invention operates similarly to virtual memory  500 . In a disk caching system consistent with this invention, a disk cache sits in main memory  302  between disk storage space  312  and processor  310 , similar to FIG.  5 . Further, a process similar to process  600  is implemented in a disk caching system consistent with this invention. 
   Although methods and systems consistent with the present invention have been described with reference to a preferred embodiment thereof, those skilled in the art knows various changes in form and detail which may be made without departing from the spirit and scope of the present invention as defined in the appended claims and their full scope of equivalents.