Electrical computers and digital processing systems: memory – Addressing combined with specific memory configuration or... – For multiple memory modules
Reexamination Certificate
2002-02-22
2004-10-19
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Addressing combined with specific memory configuration or...
For multiple memory modules
C711S157000, C711S206000, C711S207000, C711S208000
Reexamination Certificate
active
06807603
ABSTRACT:
THE FIELD OF THE INVENTION
This invention relates generally to cell maps for computer systems. This invention relates more particularly to a system and method for input/output module virtualization and memory interleaving using cell maps.
BACKGROUND OF THE INVENTION
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 non-interleaved 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, entitled METHODS AND APPARATUS FOR INTERLEAVING MEMORY TRANSACTIONS INTO AN ARBITRARY NUMBER OF BANKS, issued Jun. 25, 1996 to Williams et al. and U.S. Pat. No. 5,293,607, entitled FLEXIBLE N-WAY MEMORY INTERLEAVING, issued Mar. 8, 1994 to Brockmann et al. U.S. Pat. Nos. 5,530,837 and 5,293,607 are assigned to the owner of the present invention, and both patents are incorporated herein by reference in their entireties. In a non-interleaved 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 non-interleaved scheme may result in holes within the memory space corresponding to missing memory blocks within the cells. Non-interleaved memory also requires multiple, sequential accesses 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 that are connected together through a bus system, with each cell including memory and four separate processors, by interleaving the memory in cell
1
with the memory in cell
2
, all eight processors in the system have a more uniform 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.
As an example of interleaving, assume that the memory contained within a system is distributed across four cells labeled
0
,
1
,
2
, and
3
. Further assume that each of cell
0
and cell
1
contain eight gigabytes (GB) of memory, while cells
2
and
3
each contain four GB of memory. The overall system therefore contains twenty-four GB of memory. The distributed memory could be interleaved as follows. Since each of the four cells contains at least four GB of memory, the first interleave entry, entry
0
, would contain four GB of memory from each of cell
0
,
1
,
2
, and
3
for a total of sixteen GB of memory. 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 four GB of memory from cell
0
and the four GB of memory from cell
1
. Interleave entry
1
therefore contains eight GB of memory, four from cell
0
and four from cell
1
. The twenty-four GB of memory in the four cells have now been broken out into two interleave entries. The twenty-four 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 twenty-four GB of information appears to be one contiguous block. While the twenty-four GB of information appears to be one contiguous block, physically the twenty-four GB of information is distributed among four different cells.
Large computer systems have used cell maps to distribute processor accesses around to avoid hot spots. Cell maps have been used to find destination modules for the cell
ode based systems. Cell maps have been used to interleave memory across cells to provide a more uniform access pattern to the memory. Cell map entries have been used to provide one, two, four, eight, sixteen, thirty-two, and sixty-four way interleaving. The size of cell map entries determines how many ways the memory is interleaved.
Some previous systems, as described above, have used cell maps to implement virtualization and interleaving for memory. The interleaving for memory is generally fine-grained, with two addresses to adjacent cache lines going to different modules. Such fine-grained access is not typically needed for input/output (I/O) virtualization.
In previous systems, separate resources were used for mapping memory and I/O. Depending on the system topologies and architecture, and the current needs of the system, the system would “flip-flop” to provide a desired memory or I/O operation. Also, the programming model for interleaved memory and for mapping out I/O modules has been quite different.
It would be desirable to use a single cell map structure to provide both memory interleaving and virtualization for I/O modules.
SUMMARY OF THE INVENTION
One form of the present invention provides a method of accessing a plurality of memories in an interleaved manner and a plurality of input/output modules using a contiguous logical address space. At least one map table is provided. The at least one map table includes a plurality of entries. Each entry includes an entry type identifier and a plurality of entry items. Each entry item includes a module identifier. Each entry is one of a memory type entry and an input/output type entry. A first logical address is received. The first logical address includes a plurality of address bits. An entry in the at least one map table is identified based on a first set of the address bits. A type of the identified entry is determined based on the entry type identifier of the identified entry. An entry item in the identified entry is identified based on a second set of the address bits if the entry type identifier indicates an input/output type entry. An entry item in the identified entry is identified based on a third set of the address bits if the entry type identifier indicates a memory type entry. A module identified by the module identifier of the identified entry item is accessed.
REFERENCES:
patent: 5293607 (1994-03-01), Brockmann et al.
patent: 5530837 (1996-06-01), Williams et al.
patent: 6381668 (2002-04-01), Lunteren
patent: 6393504 (2002-05-01), Leung et al.
patent: 6480943 (2002-11-01), Douglas et al.
patent: 6526459 (2003-02-01), Campbell et al.
patent: 6553478 (2003-04-01), Grossier
Das Sharma Debendra
Gupta Ashish
LandOfFree
System and method for input/output module virtualization and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for input/output module virtualization and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for input/output module virtualization and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3322534