Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2000-04-29
2002-11-12
Hudspeth, David (Department: 2651)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S127000, C711S202000, C711S209000
Reexamination Certificate
active
06480943
ABSTRACT:
TECHNICAL FIELD
The invention is directed to a computer system with multiple memory subsystems and more particularly to interleaving access of the subsystems.
BACKGROUND
Historically, main memory was physically situated on a central bus. Within this type of system, memory requests consisting of full physical addresses, were forwarded to the memory subsystem and the data was returned. In a distributed memory system, main memory is physically distributed across many different cells. A cell may consist of a number of processors, an input/output (I/O) device, a cell controller, and memory.
In a distributed system, memory can be noninterleaved or interleaved. Prior art systems of and methods for interleaving memory are described and set forth in, for example, U.S. Pat. No. 5,530,837 issued Jun. 25, 1996 to Williams et al. and U.S. Pat. No. 5,293,607 issued Mar. 8, 1994 to Brockman et al., both patents are assigned to the owner of the present invention, and both of which are incorporated herein by reference in their entireties. In a noninterleaved access method wherein memory is divided into or across multiple physical cells, a unified, contiguous block of memory space is addressed by first sequentially accessing all memory of a first cell followed by sequential access of all memory available in a second cell, etc. If each cell has been configured with its maximum amount of possible memory, the memory will appear, and be addressed as one contiguous memory block to the system. However, if not every cell is configured to its maximum memory capability, this noninterleaved scheme may result in holes within the memory space corresponding to missing memory blocks within the cells. Noninterleaved memory also requires multiple, sequential access to a particular cell since both instructions and data tend to be used sequentially. While a benefit when stored locally, a processor continuously or frequently accessing a remote memory in another cell consumes significant overhead including processing and communications resources at both the local and remote cells and the connecting network(s). When substantially continuous, these resources may become unavailable to other processes and degrade system performance.
Alternatively, the memory within a distributed memory system can be accessed through an interleaving protocol. Interleaving memory across several cells allows for more uniform access to memory. For example, if a system includes two cells of memory which are connected together through a bus system, each cell may include four separate processors. Each cell may also include memory. By interleaving the memory in cell
1
with the memory in cell
2
, all eight processors in the system have a more uniformed access to each memory location. Interleaving memory across the two cells also ensures consistency in latency delays for each processor in accessing memory locations. Interleaving memory across the two memory locations also reduces the possibility of bottlenecks when processors attempt to access or retrieve information from memory.
When interleaving is used in a distributed memory system, processors or devices which require access to memory must be able to determine the physical location of the portion of accessible memory.
While systems and methods for interleaving across distributed memory systems are known, their use has included a number of restrictions. For example, some prior distributed systems using interleaving required that the number of cells containing interleaved memory be equal to a power of two. The overall system memory could be contained in two, four, eight, sixteen, etc., different cells. However, problems arose if the overall system memory were contained in a number of cells which were not equal to a power of two. For example, the overall system memory could not be interleaved effectively across seven different cells without difficulty and special processing. Additionally, the amount of memory interleaved in each of the cells also had to be equal to a power of two. So a specific cell location could contain 2, 4, 8 or 16 gigabytes (GB) but not, easily, for example 5 or 13 GB. Also, interleaving across distributed memory cells was easily achievable only when the amount of memory within each cell was equal.
For example, suppose the memory contained within a system is distributed across four cells labeled
0
,
1
,
2
, and
3
, respectively. Further suppose each of cell
0
and cell
1
contain 8 GB of memory while cells
2
and
3
each contain 4 GB of memory. The overall system therefore contains 24 GB of memory. The distributed memory could be interleaved as follows. Since each of the four cells contains at least 4 GB of memory, the first interleave entry, entry
0
, would contain 4 GB of memory from each of cell
0
,
1
,
2
, and
3
for a total of 16 GB of memory (four from each of the four cells). All of the memory available in cell
2
and cell
3
have now been used in interleave entry
0
. Cell
0
and cell
1
each contain four GB of unused memory. Interleave entry
1
would contain the 4 GB of memory from cell
0
and the 4 GB of memory from cell
1
. Interleave entry
1
therefore contains 8 GB of memory, four from cell
0
and four from cell
1
. The 24 GB of memory in the four cells have now been broken out into two interleave groups. The 24 GB of memory from the four cells can now be viewed as one contiguous block as follows. GB 0 through 15 are located in the lower half of cells
0
,
1
,
2
, and
3
, GB 16 through 23 are located in the upper portion of cells
0
and
1
. This interleaving occurs at the cache line level. To a processor, the 24 GB of information appears to be one contiguous block. While the 24 GB of information appears to be one contiguous block, physically the 24 GB of information is distributed among four different cells.
In order to successfully access information contained within the memory, a processor would need to determine which cell contains a specific memory address. Prior interleaved distributed memory systems accomplished this through a one-to-one mapping between the logical memory and the physical address. For example, a look up table could be formed which consisted of 24 rows and four columns. The first column would contain the logical GB block, i.e., the most significant address bits representing 2
30
and greater address values which would range from 0 to 23. The second through the fourth columns would contain the physical address of the logical GB blocks within the respective cell. The first 16 rows of this table would identify interleave group
0
i.e., the first 16 GB of memory. Interleave group
1
would start on the 17th row of the table. When a specific processor had to access information stored in memory, the processor could identify the physical location of the memory address from this one-to-one map. These prior art systems have several disadvantages. For example, these methods are inflexible in their mappings so that each segment of physical memory requires a row entry mapping a contiguous portion of logical memory space to that physical location. The system is further inflexible in requiring predetermined, fixed physical block sizes of memory. These limitations result in both overhead requirements and performance issues if the physical memory is non-uniformly distributed over a large number of remote cells, each having its own configuration and distribution of memory resources.
Accordingly, a need exists for a more flexible approach to interleaving memory across the distributed memory system. A need further exists for a memory system and method of configuring and operating memory resources that readily accommodate cell numbers that are not integer powers of 2. Additionally, a need exists for a technique that allows the amount of memory within each cell to be equal to non-powers of 2. A further need exists for a system and method that eliminates the gaps in memory which result from each cell not having its memory configuration maximized so that all cells have equal memory spaces. Further, a need exists which allows a
Dickey Kent A.
Douglas Robert C.
Hewlett--Packard Company
Hudspeth David
Tzeng Fred F.
LandOfFree
Memory address interleaving and offset bits for cell... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory address interleaving and offset bits for cell..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory address interleaving and offset bits for cell... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2992511