Electrical computers and digital processing systems: memory – Addressing combined with specific memory configuration or... – Addressing cache memories
Reexamination Certificate
1999-01-12
2002-01-22
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Addressing combined with specific memory configuration or...
Addressing cache memories
C711S220000, C711S221000
Reexamination Certificate
active
06341325
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to memory addressing schemes in computer systems, and specifically, to a system and method for enabling computer processors and CPUs to access data contents of main memory systems in which main memory is addressed by means of hardware translations of real addresses using a directory structure stored in the main memory.
BACKGROUND OF THE INVENTION
An emerging development in computer organization is the use of data compression in a computer system's main memory, such that each cache line may be compressed before storage in main memory. The result is that cache lines, which in conventional computer systems that do not use main memory compression are of a uniform fixed size in the main memory, now, using memory compression, occupy varying amounts of space. Techniques for efficiently storing and accessing variable size cache lines in main memory can be found in U.S. Pat. No. 5,761,536, and in co-pending U.S. patent application Ser. No. 08/603,976, entitled “COMPRESSION STORE ADDRESSING”, both assigned to the assignee of the present invention, and in the reference entitled “Design and Analysis of Internal Organizations for Compressed Random Access Memories,” by P. Franaszek and J. Robinson, IBM Research Report RC 21146, IBM Watson Research Center, Mar. 30, 1998.
Techniques for efficiently storing and accessing variable size cache lines require the use of a directory structure, in which real memory addresses generated by the CPU(S) (or processors) of the computer system are used to index into the directory, which is then used to find the main memory contents containing the compressed data. An example of a compressed main memory system and directory structure is now described with reference to
FIGS. 1-3
.
FIG. 1
shows the overall structure of an example computer system using compressed main memory. A CPU
102
reads and writes data from a cache
104
. Cache misses and stores result in reads and writes to the compressed main memory
108
by means of a compression controller
106
.
FIG. 2
shows in more detail the structure of the cache
104
, components of the compression controller
106
, and compressed main memory
108
of FIG.
1
. The compressed main memory is implemented using a conventional RAM memory M
210
, which is used to store a directory D
220
and a number of fixed size blocks
230
. The cache
240
is implemented conventionally using a cache directory
245
for a set of cache lines
248
. The compression controller
106
includes a decompressor
250
which is used for reading compressed lines and a compressor
260
which is used for writing compressed lines. Each cache line is associated with a given real memory address
270
. Unlike a conventional memory, however, the address
270
does not refer-to an address in the memory M
210
; rather, the address
270
is used to index into the directory D
220
. Each directory entry contains information (shown in more detail in
FIG. 3
) which allows the associated cache line to be retrieved. For example, the directory entry
221
for line
1
associated with address A
1
271
is for a line which has compressed to a degree in which the compressed line can be stored entirely within the directory entry; the directory entry
222
for line
2
associated with address A
2
272
is for a line which is stored in compressed format using a first full block
231
and second partially filled block
232
; finally the directory entries
223
and
224
for line
3
and line
4
associated with addresses A
3
273
and A
4
274
, respectively, are for lines stored in compressed formats using a number of full blocks (blocks
233
and
234
for line
3
and block
235
for line
4
) and in which the remainders of the two compressed lines
3
and
4
have been combined in block
236
.
FIG. 3
shows some examples of directory entry formats. For this example, it is assumed that the blocks
230
of
FIG. 2
are of size 256 bytes and that the cache lines
248
of
FIG. 2
are of size 1024 bytes. This means that lines can be stored in an uncompressed format using four blocks. For this example, directory entries of size 16 bytes are used, in which the first byte consists of a number of flags; the contents of the first byte
305
determine the format of the remainder of the directory entry. A flag bit
301
specifies whether the line is stored in compressed or uncompressed format; if stored in uncompressed format, the remainder of the directory entry is interpreted as for line
1
310
, in which four 30-bit addresses give the addresses in memory of the four blocks containing the line. If stored in compressed format, a flag bit
302
indicates whether the compressed line is stored entirely within the directory entry; if so, the format of the directory entry is as for line
3
330
, in which up to 120 bits of compressed data are stored. Otherwise, for compressed lines longer than 120 bits, the formats shown for line
1
310
or line
2
320
may be used. In the case of the line
1
310
format, additional flag bits
303
specify the number of blocks used to store the compressed line, from one to four 30-bit addresses specify the locations of the blocks, and finally the size of the remainder, or fragment, of the compressed line stored in the last block (in units of 32 bytes), together with a bit indicating whether the fragment is stored at the beginning or end of the block, is given by four fragment information bits
304
. Directory entry format
320
illustrates an alternative format in which part of the compressed line is stored in the directory entry (to reduce decompression latency); in this case, addresses to only the first and last blocks used to store the remaining part of the compressed line are stored in the directory entry, with intervening blocks (if any) found using a linked list technique, that is each blocked used to store the compressed line has, if required, a pointer field containing the address of the next block used to store the given compressed line.
In contrast, in conventional computer systems that do not use compressed main memory, real memory addresses are used directly as main memory addresses. In compressed main memory systems, the mapping using the directory to the data containing the compressed cache line contents occurs automatically using compression controller hardware, and the directory is “invisible” to the processor(s); that is, there is no way (using conventional processor architectures) for processors to access the directory contents. However, it is desirable for a variety of reasons to provide such access. One approach is to modify the processor architecture, so that, for example, addressing modes that bypass the compression controller hardware and allow direct examination of main memory contents are made available. Although this provides a solution to the problem, clearly it has a number of drawbacks, for example, it may not be possible to use “off-the-shelf” processors using existing processor architectures in this approach.
Even assuming that an additional addressing mode, which could be termed an “R=P” (real=physical) mode, is available, which bypasses the hardware translation of real memory addresses to physical memory locations using the directory structure, there is the following problem: after switching to this mode, all cache contents in all cache levels of the computer system become invalid, since the cache contents under normal operation reflect the contents of main memory as addressed using the translation of real memory addresses to physical locations via the directory structure. Therefore, in order to switch to this mode, all modified cache lines in all cache levels must first be forced to be written through to main memory, and then all cache lines in all cache levels must be marked invalid. A similar process must occur for correct operation which switching out of R=P mode. Thus, switches between R=P mode and normal addressing modes represent significant processing time overheads. Furthermore, in a multiprocessor syste
Franaszek Peter A.
Robinson John T.
Nguyen Hiep T.
Scully Scott Murphy & Presser
Tassinari, Esq Robert P.
LandOfFree
Method and apparatus for addressing main memory contents... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for addressing main memory contents..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for addressing main memory contents... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2844677