Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2000-01-06
2003-04-15
Kim, Hong (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S206000, C711S208000, C711S170000, C711S173000, C710S068000
Reexamination Certificate
active
06549995
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to the field of memory management and memory system architectures in computer systems, and more specifically, to the organization of the address space around specific compressed memory data structures and a method and apparatus for managing the access to the memory.
2. Discussion of the Prior Art
Computer systems generally consist of one or more processors that execute program instructions stored within a memory 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.
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 of 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.
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. 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
.
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.
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 scheme results in a variable size output block, ranging 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.
Referring to
FIG. 2
, there is shown a conventional partitioning scheme
200
for the main memory
103
(FIG.
1
). 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.
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
1
)
Each entry is directly mapped to a fixed address range in the processor'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
2
)
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.
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 t
Schulz Charles O.
Smith, III T. Basil
Tremaine Robert B.
Wazlowski Michael
Kim Hong
Morris, Esq. Daniel P.
Scully Scott Murphy & Presser
LandOfFree
Compressor system memory organization and method for low... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compressor system memory organization and method for low..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressor system memory organization and method for low... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3030651