Abstract:
In a processing system having a main memory wherein information is stored in a compressed format for the purpose of gaining additional storage through compression efficiencies, a method and apparatus for enabling termination of a pending compression operation for the purpose of writing the data directly to the main memory, bypassing the compressor hardware during stall conditions. Memory space (compressibility) is sacrificed for higher system performance during these temporary write back stall events. A background memory scrub later detects and recovers the “lost” compressibility by recycling the uncompressed data back through the compressor during idle periods.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates in general to the field of compressed memory architecture in computer systems, and more specifically, to an improved method and apparatus for operating a main memory compressor.  
           [0003]    2. Discussion of the Prior Art  
           [0004]    Computer systems generally consist of one or more processors that execute program instructions stored within a medium. This mass storage medium is most often constructed of the lowest cost per bit, yet slowest storage technology, typically magnetic or optical media. To increase the system performance, a higher speed, yet smaller and more costly memory, known as the main memory, is first loaded with information from the mass storage for more efficient direct access by the processors. Even greater performance is achieved when a higher speed, yet smaller and more costly memory, known as a cache memory, is placed between the processor and main memory to provide temporary storage of recent/and or frequently referenced information. As the difference between processor speed and access time of the final storage increases, more levels of cache memory are provided, each level backing the previous level to form a storage hierarchy. Each level of the cache is managed to maintain the information most useful to the processor. Often more than one cache memory will be employed at the same hierarchy level, for example, when an independent cache is employed for each processor. Cache memory systems have evolved into quite varied and sophisticated structures, but always address the tradeoff between speed and both cost and complexity, while functioning to make the most useful information available to the processor as efficiently as possible.  
           [0005]    Recently, cost reduced computer system architectures have been developed that more than double the effective size of the main memory by employing high speed compression/decompression hardware based on common compression algorithms, in the path of information flow to and from the main memory. Processor access to main memory within these systems is performed indirectly through the compressor and decompressor apparatuses, both of which add significantly to the processor access latency costs.  
           [0006]    Referring now to FIG. 1, a block diagram of a prior art computer system  100  is shown. The computer system includes one or more processors  101  connected to a common shared memory controller  102  that provides access to a system main memory  103 . The shared memory controller contains a compressor  104  for compressing fixed size information blocks into as small a unit as possible for ultimate storage into the main memory, a decompressor  105  for reversing the compression operation after the stored information is later retrieved from the main memory, and write queue  113  for queuing main memory store request information block(s) destined for the compressor. The processor data bus  108  is used for transporting uncompressed information between other processors and/or the shared memory controller. Information may be transferred to the processor data bus  108  from the main memory  103 , either through or around the decompressor  105  via a multiplexor  111 . Similarly, information may be transferred to the main memory  103  from the processor data bus  108  to the write buffer and then either through or around the compressor  104  via a multiplexor  112 .  
           [0007]    The main memory  103  is typically constructed of dynamic random access memory (DRAM) with access controlled by a memory controller  106 . Scrub control hardware within the memory controller can periodically and sequentially read and write DRAM content through error detection and correction logic for the purpose of detecting and correcting bit errors that tend to accumulate in the DRAM. Addresses appearing on the processor address bus  107  are known as Real Addresses, and are understood and known to the programming environment. Addresses appearing on the main memory address bus  109  are known as Physical Addresses, and are used and relevant only between the memory controller and main memory DRAM. Memory Management Unit (MMU) hardware within the memory controller  106  is used to translate the real processor addresses to the virtual physical address space. This translation provides a means to allocate the physical memory in small increments for the purpose of efficiently storing and retrieving compressed and hence, variable size information.  
           [0008]    The compressor  104  operates on a fixed size block of information, say 1024 bytes, by locating and replacing repeated byte strings within the block with a pointer to the first instance of a given string, and encoding the result according to a protocol. This process occurs through a bytewise compare over a fixed length and is paced by a compressor sequence counter, resulting in a constant completion time. The post process output data block ranges from just a few bytes to the original block size, when the compressor could not sufficiently reduce the starting block size to warrant compressing at all. The decompressor  105  functions by reversing the compressor operation by decoding resultant compressor output block to reconstruct the original information block by inserting byte strings back into the block at the position indicated by the noted pointers. Even in the very best circumstances, the compressor is generally capable of only ¼-½ the data rate bandwidth of the surrounding system. The compression and decompression processes are naturally linear and serial too, implying quite lengthy memory access latencies through the hardware.  
           [0009]    Referring to FIG. 2, there is illustrated a prior art main memory partitioning scheme  200 . The main memory  205  is a logical entity because it includes the processor(s) information as well as all the required data structures necessary to access the information. The logical main memory  205  is physically partitioned from the physical memory address space  206 . In many cases the main memory partition  205  is smaller than the available physical memory to provide a separate region to serve as a cache with either an integral directory, or one that is implemented externally  212 . It should be noted that when implemented, the cache storage may be implemented as a region  201  of the physical memory  206 , a managed quantity of uncompressed sectors, or as a separate storage array. In any case, when implemented the cache controller will request accesses to the main memory in a similar manner as a processor would if the cache were not present. Although it is typical for a large cache to be implemented between the processor(s) and main memory for the highest performance, it is not required, and is beyond the scope of the invention.  
           [0010]    The logical main memory  205  is partitioned into the sector translation table  202 , with the remaining memory being allocated to sector storage  203  which may contain compressed, uncompressed, free sector pointers, or any other information as long as it is organized into sectors  204 . The sector translation table region size varies in proportion to the real address space size which is defined by a programmable register within the system. Particularly, equation 1) governs the relation of the sector translation table region size as follows:  
         sector_translation      _table      _size     =           real_memory      _size       compression_block      _size       ·   translation_table        _entry      _size                           
 
           [0011]    1)  
           [0012]    Each entry is directly mapped to a fixed address range in the processor&#39;s real address space, the request address being governed in accordance with equation 2) as follows:  
         STT_entry      _address     =       (         (     real_address     compression_block      _size       )     ·   translation_table        _entry      _size     )     +     cache_region      _size                             
 
           [0013]    2)  
           [0014]    For example, a mapping may employ a 16 byte translation table entry to relocate a 1024 byte real addressed compression block, allocated as a quantity 256 byte sectors, each located at the physical memory address indicated by a 25-bit pointer stored within the table entry. The entry also contains attribute bits  208  that indicate the number of sector pointers that are valid, size, and possibly other information.  
           [0015]    Every real address reference to the main memory causes memory controller to reference the translation table entry  207  corresponding to the real address block containing the request address. For read requests, the MMU decodes the attribute bits  208 , extracts the valid pointer(s)  209  and requests the memory controller to read the information located at the indicated sectors  204  from the main memory sectored region  203 . Similarly, write requests result in the MMU and memory controller performing the same actions, except information is written to the main memory. However, if a write request requires more sectors than are already valid in the translation table entry, then additional sectors need to be assigned to the table entry before the write may commence. Sectors are generally allocated from a list of unused sectors that is dynamically maintained as a stack or linked list of pointers stored in unused sectors. There are many possible variations on this translation scheme, but all involve a region of main memory mapped as a sector translation table and a region of memory mapped as sectors. Storage of these data structures in the DRAM based main memory provides the highest performance at the lowest cost, as well as ease of reverting the memory system into a typical direct mapped memory without compression and translation.  
           [0016]    Large high speed cache memories are implemented between the processor and the compressor and decompressor hardware to reduce the frequency of processor references to the compressed memory, mitigating the effects the high compression/decompression latency. These caches are partitioned into cache lines, equal in size to the fixed information block size required by the compressor and decompressor. Since a cache is smaller than the next level of memory in the hierarchy, it must be continuously updated to contain only information deemed useful to the processors. Often the process of replacing information within the cache results in a cache line having to be written back to the main memory through the compressor. At times, these write back events can occur in rapid succession, thereby backing up behind one another until the processors stall for access to the cache. This situation is exacerbated when a compressor operates at bandwidths lower than that of the surrounding system data flow components.  
           [0017]    Therefore, the need has arisen for an improved method of data management in a compressed memory system, without significant cost or complexity, to minimize processor stall conditions due to cache write back queuing at the compressor.  
         SUMMARY OF THE INVENTION  
         [0018]    It is an object of the invention to provide a data management mechanism in a compressed memory system that functions to minimize processor stall conditions due to cache write back queuing at the compressor.  
           [0019]    It is a further object of the invention to provide a method and apparatus that implements an escape mechanism for aborting a pending write back compression in order to bypass the compressor hardware when a stall situation occurs. This mechanism temporarily sacrifices memory space (compressibility) when system performance would be adversely affected during write back queue full events.  
           [0020]    According to the invention, an abort logic signal is asserted by a cache controller mechanism to the compressor hardware when the cache write back queue, which feeds the compressor, is full and a new write back condition exists within the cache. If the compressor is nearly complete with a pending write back compression, then the signal is ignored, and the current compression is allowed to complete. Otherwise, the write-back compression is aborted, and the pending write back data is immediately written back to the main memory, bypassing the compressor. Other write back operation(s) queued behind the one pending at the compressor remain unaffected by the abort signal. Further, a compressible state bit is set in the compression translation entry associated with the write back to indicate that the information may be compressible, even though it is stored in an uncompressed format. A special process running in conjunction with the main memory scrub background task is provided for detecting the potentially compressible information blocks. Once such a block is detected and the write back queue is below a predetermined threshold, then the uncompressed block is read back from the main memory and placed into the write back queue to be reprocessed through the compressor and restored into the main memory with the associated compressible state bit reset. This prevents the memory from accumulating uncompressed information blocks that would otherwise be compressible, resulting in a reduction in available memory. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0021]    Further features, aspects and advantages of the apparatus and methods of the present invention will become better understood with regard to the following description, appended claims, and accompanying drawings where:  
         [0022]    [0022]FIG. 1 illustrates a block diagram of a prior art computer having a cache and a main memory system with hardware compressor and decompressor;  
         [0023]    [0023]FIG. 2 illustrates a prior art scheme for partitioning a memory address space;  
         [0024]    [0024]FIG. 3 illustrates the apparatus according to the principals of the present invention.  
         [0025]    FIGS.  4 ( a )- 4 ( b ) illustrate respective state diagrams for the methods of memory scrub and the recovery of compressible, yet uncompressed blocks implemented in accordance with the apparatus of the present invention.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0026]    Referring to FIG. 3 there is illustrated an improved apparatus  300  that permits a main memory write access demand based compressor bypass, and background recompress of affected stored information. The compressor control logic  302  is modified to receive and process a new input logic signal  303  and new functional behavior when the signal is asserted. Particularly, when the input logic signal  303  is asserted by the memory/cache control logic  307 , the compressor  303  will abort processing of a pending compression operation, provided the progress of the compression operation to that point, as measured by a compressor sequence counter value, has not exceeded a predetermined threshold. Otherwise, the compressor will proceed normally to completion without interruption. This threshold may be fixed in the design of the compressor  303  or it may be programmable via a register (not shown), of which the contents are used within the compressor to determine the threshold. In either case, the compressor control logic  302  will abort a pending compression operation by simply reverting to the existing operative state which is normally entered only when the compressor determines that a compression will not yield any spatial benefit, and therefore the information block is stored to the main memory in an uncompressed format.  
         [0027]    More particularly, the input logic signal may be asserted as an abort signal when the write queue  301  is in a state such that it cannot accept any more information, and the memory/cache control logic  307 , which is responsible for adding write request information, needs to add the information associated with an additional write request.  
         [0028]    Generally, this occurs when the cache controller needs to replace a line within the cache, and the displaced cache line content needs to be written back to the main memory. The protocol for the abort signal  303  may be implemented in two ways: 1) the abort signal may be level sensitive, where it is asserted only during the few cycles when a new write back is attempted, after which the signal is de-asserted until the situation presents itself again; or, 2) the abort signal  303  may be latched, where once asserted, it remains asserted until some quantity of write back information block(s) are drained from the cache write back queue, bypassing the compressor.  
         [0029]    Generally, the compressible, yet uncompressed information blocks will be read back from main memory for replacement in the cache, and thus have another opportunity to be compressed when the information block is again written back to main memory during a subsequent cache line replacement. However, under certain conditions it is possible for information blocks to not have subsequent opportunities to be recompressed. Thus, the system of the invention implements means for detecting such cases to facilitate an overt compression opportunity. When an information block is written to main memory that has bypassed the compressor in response to an abort signal assertion, then a compressible state bit  310  is asserted within the associated entry  308  within the sector translation table  309  (FIG. 3). This compressible state bit  310  is used to indicate that the information block may be compressible, but is not stored in the compressed format. This provides a means to later detect, through a background task described with respect to FIG. 4( b ), which information blocks may be compressible for the purpose of gaining potential memory space that is otherwise not available.  
         [0030]    Overtly causing the compressible, yet uncompressed information blocks to be compressed may be executed in several ways. In one embodiment, software is executed by the processor(s) that periodically, but infrequently read a part of an information block that occurs next in the linear sequence of all information blocks. A similar software program may periodically, yet infrequently read the entire sector translation table  309 , for the purpose of detecting which entries  308  have the compressible state bit  310  asserted, and then read a part of only the information blocks associated with the detected entries. In a preferred embodiment however, a hardware mechanism is employed to perform the task. A special comparator is incorporated into the memory scrub apparatus  315  within the memory controller  307  to detect when the compressible state bit  310  is asserted during normal background scrub operations. When an entry  308  is detected in this condition, and the write queue fill condition is below a predetermined threshold, the memory controller reads the associated uncompressed information block from memory and places its own write in the write queue  301  through the read path multiplexor  305  and processor data bus, where it is processed in the normal manner as all write requests. If the write queue is not available, then the scrub controller ignores the detection and continues it normal activity.  
         [0031]    Referring now to FIG. 4( a ), there is shown a state diagram  400  for typical memory scrub process according to the prior art. Memory scrub is a process of systematically reading every location of a DRAM over a period of time for the purpose of detecting accumulated storage errors. If a correctable error is detected by the Error Correction Code (ECC) circuits in the memory controller, the corrected data is written back to the DRAM through the ECC circuits to reestablish the data in memory without errors. Since DRAM soft errors accumulate slowly, the scrub process needs to complete a sweep of the DRAM over several tens of hours. Therefore, the scrub process operates in the idle state at step  401  until some infrequent periodic event, for example, some quantity of DRAM refreshes are detected at steps  402  and  403 . At such detection, the scrub process initiates a scrub read to the next block of memory. Once out of the wait loop defined at steps  401 ,  402   403 , a scrub event commences by first reinitializing the wait counter “wait_cnt”  404 , to pace out the period to the next scrub. Then a block of data, say 256 bytes, is read from memory, at the scrub address contained within a counter, and checked through the ECC circuits  405 . If the scrub address counter is equal to last memory address  406 , then the counter is reinitialized with the first memory address at step  407 . Otherwise, the counter is incremented to indicate the next scrub address at step  408 . Any correctable errors detected in the scrub data block from step  405 , would have been corrected by the ECC circuits before the data was stored into a temporary buffer. If there were any errors as indicated at step  409 , then the corrected scrub data block would be written back to the main memory at step  410 . Otherwise, the scrub process reverts back to the idle state  401 .  
         [0032]    Referring now to FIG. 4( b ), there is illustrated a state diagram  450  for detecting and recovering potentially compressible, yet uncompressed information blocks. This Compression Recovery Process (CMP) operates in conjunction with and is dependent on the memory scrub process  400  previously described and shown in FIG. 4( a ), and the apparatus described with respect to FIG. 3. The CMP 450 effectively snoops Sector Translation Table  309  entries  308 , for the presence of the “compressible” state bit  310  as they are read from main memory during normal a scrub process. The compression recovery process operates in the idle state  411  until a scrub read event commences at step  405  (as shown in FIG. 4( a )). If a scrub data address is equal to a sector translation table entry  412 , and the “compressible” state bit  310  is asserted  413 , and the memory write queue  301  is low  414 , and there is no cache read request pending at the main memory  415 , then a write request is asserted to the write back controller and a read request is asserted to the memory controller to read the uncompressed information and deposit it in the write queue  301  via the multiplexor  305 . Otherwise, control is returned to the processor idle state at step  411 .  
         [0033]    While the invention has been particularly shown and described with respect to illustrative and preformed embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and details may be made therein without departing from the spirit and scope of the invention which should be limited only by the scope of the appended claims.