Address mapping for system memory

Details Address mapping for system memory Address mapping for system memory

1998-11-20

2002-04-30

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Addressing combined with specific memory configuration or...

For multiple memory modules

C711S202000, C711S206000, C711S157000

Reexamination Certificate

active

06381668

ABSTRACT:

FIELD OF INVENTION
Present invention relates generally to address mapping for accessing system memory, and more particularly to address mapping for memories consisting of a plurality of memory banks in which interleaving of stored information is effected.
Meaning of Terms
As some technical terms are not used uniformly in this field, a few definitions are given in the following to clarify the meaning of terms as they are used in this patent application.
Virtual address=an address as used in programs (normal meaning)
Physical address an address uniquely identifying the position in memory (as obtained from a virtual address e.g. by a table lookaside operation)
Memory bank=a piece of memory that can be separately accessed (also called memory module; it may be a memory chip)
Location=a storage place which can be separately addressed, can store usually one byte or word
Line=a portion of a memory bank handled as a whole and addressed as a whole, often consists of a power of 2 number of locations (1, 2, 4, etc.)
Block=a portion of memory handled as a whole (in a given context) and addressed as a whole, here it will consist of one line (lookup table (LUT) with bank numbers) or multiple lines (LUT with masks/bit vectors)
Stride=an address sequence a
0
, a
1
, a
2
, a
3
, . . . has a stride S when for each two succeeding addresses holds: a
i+1
=a
i
+S (i.e., the address sequence is a
0
, a
0
+S, a
0
+2S, a
0
+3S, . . . ) In the drawings, abbreviation ST is used for a stride.
Interleave factor=The interleave factor for an address sequence a
0
, a
1
, a
2
, a
3
, . . . is the average number of memory banks that can be accessed in parallel when accessing the addresses of the address sequence in the given order.
Background
In data processing systems, addresses as used in programs are usually virtual addresses which do not reflect where in systems memory the respective information is actually stored. Because of limited storage capacity, only those data or programs are loaded which are actually used, and this may be anywhere in memory where free space has become or is made available. Thus, by a translation process as shown in
FIG. 1A
, the virtual address has to be translated into a physical address. The virtual address comprises a page offset and a page number which are translated into a block address and a block offset.
The page offset represents a certain point within a page and the block offset represents a certain point within a block. Usually the least significant part of the page offset is used as block offset and the rest of the page offset is used as the least significant part of the block address. The most significant part of the block address is obtained by translation of the page number via a page table. In systems using as memory one single memory bank, this is already the whole process for addressing a predetermined block i within the memory bank. The page table is updated each time new information is loaded into the memory. The physical address space usually is different from the virtual address space, and the effect of translation is as shown in FIG.
1
B.
The physical address space is considered as continous space. Each physical address corresponds to a storage location in one of the memory banks in system memory. A line is a part of a memory bank that consists of a number of storage locations that are addressed as a whole by a line-number or bank-internal address. A block consists of one line or multiple lines. The physical addresses, that are assigned to (mapped on) storage locations contained within one block, are only different from each other in the “x” least significant address bits, called the block offset, where L=2
x
equals the number of storage locations in the block. The identical most significant address bits of the physical addresses constitute the block address.
If a block consists of one line and a line consists of one storage location, then the block address equals the physical address.
If blocks of data (or program segments) with consecutive block addresses are mapped on lines within the same memory bank, then a problem occurs if they have to be accessed in the same sequence, because usually, when access has been made to one line, the memory bank needs a short period of time before the next access can be made. Accesses to consecutive block addresses therefore would need more time than is desirable.
One solution to this problem is the interleaving of data (information) in separate memory banks which can be separately accessed. Thus, if storage locations with consecutive block addresses are distributed over separate memory banks, the blocks can be accessed one immediately after the other without any waiting time. The simplest way to do this is to use one portion of the block address as the memory bank number and the rest of the block address as bank-internal address (or line-number), as shown in FIG.
2
. As a result, the distribution of consecutive block addresses over the memory is bank-wise which much improves the overall access time in many cases.
However, this known method requires that the number of memory banks is a power of two, and that the interleaving is uniform (sequential) which is not optimal in various applications. In general, it can be said that often, sequential accesses to memory are not randomly distributed but follow a certain pattern depending on the respective application. This is in particular true for scientific applications. Thus, even if information is stored in an interleaved manner in several memory banks, as shown in
FIG. 2
, sequential accesses for consecutive block addresses may occur to the same memory bank. If possible, memory accesses should be distributed uniformly over all memory banks to achieve best performance.
Some particular interleaving schemes have been developed for scientific applications, such as prime degree interleaving, pseudo-random interleaving and irreducible interleaving. However, with these schemes, address mapping involves complex calculations resulting in larger memory latencies.
Other methods of interleaving which allow some variation have become known and are discussed in the following.
a) U.S. Pat. No. 5,293,607 “Flexible N-way memory interleaving” (Dixon and Asta) discloses a method of memory interleaving where the memory bank number (called “block number” in the text) is determined by an arithmetic combination of selected portions of the given address. This method allows to use an arbitrary number of memory banks, i.e. which need not be a power of two, and it allows the use of different-size memory blocks to some extent. However, the interleaving which can be achieved is not freely selectable because the existing number of memory banks and their size determine the selection of the portions of the given address and thus the resulting bank numbers. Furthermore, if banks of different sizes are used they have to be grouped, and within any group only one predetermined interleave factor is possible. In addition, in this system only power-of-two interleave factors are possible.
b) U.S. Pat. 5,341,486 “Automatically variable memory interleaving system” (Castle) describes an addressing scheme for memory interleaving which allows to use any number of memory banks, and further allows different interleaving factors. However, the memory banks have to be grouped so that each group consists of a number of memory banks which is a power of two, and for each such group only one interleaving factor is possible. Furthermore, the obtained interleaving factors are all powers of two.
c) U.S. Pat. 4,754,394 “Multiprocessing system having dynamically allocated local/global storage and including interleaving transformation circuit for transforming real addresses to corresponding absolute address of the storage” (Brantley et al.) discloses an address mapping method for a multiple-processor system having several separate memory banks (each associated with one processor). In this method, the physical address (called “real address” in the t

Affiliated with

Also associated with

Rating

Address mapping for system memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Address mapping for system memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address mapping for system memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2840870