Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Reexamination Certificate
2000-07-17
2002-08-06
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
C711S005000, C711S202000, C711S206000, C711S208000, C711S209000
Reexamination Certificate
active
06430672
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method for data processing in general, and in particular to a method for performing address mapping for a system memory. Still more particularly, the present invention relates to a method for performing address mapping to access information stored in a system memory within a computer system.
2. Description of the Prior Art
In a typical data processing system, information is typically loaded in a system memory at wherever free space is available. Thus, a virtual address of a block of information usually do not reflect where the physical address (or actual address) in the system memory in which the information is actually stored.
The physical address space is considered as a contiguous space. Each physical address corresponds to a storage location in a memory bank within a system memory. A line is the part of a memory bank that consists of a number of storage locations that can be 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 storage locations contained within one block, are only different from each other by several least significant address bits called a block offset. The most significant address bits of a physical address constitute a block address, and they are identical for the same block. If a block includes one line, and a line consists of one storage location, then the block address equals the physical address.
Accordingly, a virtual address can be translated into a physical address by a translation process graphically illustrated in FIG.
1
. As shown, a virtual address includes a page number
11
and a page offset
12
. Page offset
12
represents a certain point within a page. Page number
11
and page offset
12
are then translated into a block address
13
and a block offset
14
. Block offset
14
represents a certain point within a block. Usually, the least significant bits of page offset
12
are used as block offset
14
, and the remaining bits of page offset
12
are used as the least significant bits for block address
13
. The most significant bits of block address
13
are obtained by translating page number
11
via a page table
15
. Page table
15
is updated each time new information is loaded into a memory. In a data processing system having only one memory bank
16
,
FIG. 1
represents the entire process of addressing a predetermined block i within memory bank
16
.
A system memory typically have more than one memory bank. If blocks of data having 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. This is because after an access has been made to one line of a memory bank, the memory bank usually needs a short period of time to “recover” before another access can be made. Hence, consecutive block address accesses would require more time than is desirable.
One solution to the above-mentioned problem is to interleave data in different memory banks that can be separately accessed. Thus, if storage locations with consecutive block addresses are distributed over separate memory banks, the blocks can be accessed one memory bank immediately after the other without any wait 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 line-number (or bank-internal address), as graphically shown in FIG.
2
. With this method, the distribution of consecutive block. addresses over a system memory
20
is bank-wise, and the overall access time is much improved in many cases.
However, this known method requires that the number of memory banks within system memory
20
to be a power of two, and that the interleaving be uniform (i.e., sequential), which is not optimal in various applications. Generally speaking, sequential accesses to a memory, such as system memory
20
, are not randomly distributed but follow a certain pattern, depending on the type of applications. Thus, even if data is stored in an interleaved manner in several memory banks, such as system memory
20
shown in
FIG. 2
, sequential accesses for consecutive block addresses may occur at the same memory bank.
Ideally, memory accesses should be distributed uniformly over all memory banks in order to achieve best performance. To that end, various interleaving schemes, such as prime degree interleaving, pseudo-random interleaving, irreducible interleaving, etc., have been developed over the years for handling the memory distribution problem, specifically related to scientific applications. However, with these prior art interleaving schemes, address mapping often involves complex calculations that also lead to relatively large memory latencies. Consequently, it would be desirable to provide an improved method for performing address mapping to access information stored in a memory.
SUMMARY OF THE INVENTION
In accordance with a preferred embodiment of the present invention, a memory is organized in multiple of memory banks, and each memory bank is identified by a respective bank number. A block address portion of a physical address is translated to a corresponding bank number and an associated internal bank address. The bank number is formed by concatenating an output from a first lookup table and an output from a second lookup table. The output from the first lookup table is obtained by a first and a second segments of the block address portion, while the output from the second lookup table is obtained by a third and a fourth segments of the block address portion. Data stored in a specific location within the memory banks can be accessed by the bank number and the associated internal bank address.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4654777 (1987-03-01), Nakamura
patent: 4692879 (1987-09-01), Ikuta
patent: 5333289 (1994-07-01), Kaneko et al.
patent: 5937435 (1999-08-01), Dobbek et al.
patent: 5963983 (1999-10-01), Sakakura et al.
patent: 6046996 (2000-04-01), Hoshino et al.
patent: 6185674 (2001-02-01), Chan et al.
patent: 6289014 (2001-09-01), Hoshino et al.
patent: WO 98/43168 (1998-10-01), None
J. Van Lunteren, “Towards Memory Centric Computing: A Flexible Address Mapping Scheme”, IBM Research Division, 6 pp.
Dhong Sang Hoo
Hofstee Harm Peter
Lunteren Jan Van
Takahashi Osamu
LandOfFree
Method for performing address mapping using two lookup tables 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 for performing address mapping using two lookup tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for performing address mapping using two lookup tables will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2893630