Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1998-12-11
2001-05-01
Ellis, Kevin L. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
Reexamination Certificate
active
06226720
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention generally relates to data processing systems and more particularly to data processing systems with a memory system incorporating a plurality of memory banks. The present invention more particularly relates to a memory system wherein there are multiple sizes of memory banks.
2. Description of the Related Art
Memory systems are well known in the art and such systems are used in many data processing applications. Memory systems provide program and operating data to associated central processing units to enable the central processing units to execute program instructions. In applications where a large amount of memory space is required, such as in mainframe or mini-computer applications, memory systems may include multiple memory banks. The memory banks may be formed with dynamic random access memories because of their extremely high memory density.
In order to access such memories, central processing units utilize various addressing and retrieval schemes to improve memory access time. One such scheme is interleaved memory. Memory interleaving is a process of organizing Random Access Memory (“RAM”) to reduce wait states. Typically, memory is organized in rows of memory chips with equal sizes of memory banks (a memory section convenient for a Central Processing Unit to address) and logical addresses are assigned to memory banks comprising a memory system. The logical addresses correspond to physical addresses of memory locations in different banks. In most large computer systems, system memory is divided into individual banks that may be independently accessed.
Interleaving is generally performed at startup. Firmware, in the data processing system, may utilize a limited set of tables that contains pre-set memory configuration or a configuration algorithm that interleaves memory at startup. Interleaving is usually expressed in terms of the number of units interleaved together. For example, a system described as having 8-way interleaving (interleaving factor of eight) may be divided into 8 units with interleaved addresses. Addresses that may be assigned to locations in a first unit may be 0, 8, 16, 24, etc., locations in a second unit may have 1, 9, 17, 25, etc., locations in a third unit may have 2, 10, 18, 26, etc. and so forth.
Usually each of the memory banks are accessible independently of the other memory banks. Interleaving permits accessing of data in different memory blocks at approximately the same time thus, an interleaved memory system may provide data faster than an equivalent non-interleaved memory.
Time required to provide data from memory is usually referred to as “latency.” One method to speed up a data processing system is to reduce latency. Maximizing the number of levels of memory interleaving can reduce latency, which increases data throughput in the system, and speed up data retrieval.
More interleave levels reduce memory conflicts when the same memory block is being accessed in separate memory operations. Generally, in a non-interleaved system, the conflicting operations are queued and serviced one at a time.
In an ideal system, all banks of memory would be interleaved together. However the design of many systems requires that banks be of the same size before they may be interleaved. Thus, if a system had 16 banks of memory, 8 of one size and eight of another, it would be common that the first eight would be interleaved together (8-way interleaving) and the next eight would be interleaved as 8-way, but separately from the first group of eight.
Interleaving is generally performed on banks in multiples of two; that is 1-way (no-way or high interleaving), 2-way, 4-way, 8-way, 16-way, etc. Thus a system with 16 possible banks, but only 12 populated (four banks are empty), could only have the first 8 banks interleaved as 8-way and the next 4 as 4-way. Some systems split the memory even further, where the memory banks are composed of one or more fixed-size blocks of memory.
Consider a system with 4 memory cards: Card 0 has 4 32 MB blocks on 4 banks, (a 128 MB card); Card 1 has 8 32 MB blocks on 4 banks. (a 256 MB card); Card 2 has 16 32 MB blocks on 4 banks (a 512 MB card) and Card 3 has 32 32 MB blocks on 4 banks, (a 1024 MB card). Visually one could look at the blocks and banks of memory as shown in Table 1.
TABLE 1
- - - -
- - - -
- - - -
x x x x
- - - -
- - - -
- - - -
x x x x
- - - -
- - - -
- - - -
x x x x
- - - -
- - - -
- - - -
x x x x
- - - -
- - - -
x x x x
x x x x
- - - -
- - - -
x x x x
x x x x
- - - -
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
Bank
0 1 2 3
4 5 6 7
8 9 a b
c d e f
Card
0
1
2
3
An x indicates that a 32MB block is occupied, an a indicates the block is empty.
Ideally, one would interleave memory so that all blocks are configured and that the highest possible interleaving is effected. One way to interleave the banks in Table 1 could be as shown in Table 2.
TABLE 2
- - - -
- - - -
- - - -
4b4b4b4b
- - - -
- - - -
- - - -
4b4b4b4b
- - - -
- - - -
- - - -
4b4b4b4b
- - - -
- - - -
- - - -
4b4b4b4b
- - - -
- - - -
8a8a8a8a
8a8a8a8a
- - - -
- - - -
8a8a8a8a
8a8a8a8a
- - - -
4a4a4a4a
8a8a8a8a
8a8a8a8a
16161616
16161616
16161616
16161616
Bank
0 1 2 3
4 5 6 7
8 9 a b
c d e f
Card
0
1
2
3
The number 16 indicates that the blocks shown are 16-way interleaved,
8
a
indicates that all the blocks with
8
a
are interleaved together in an 8-way interleave.
4
a
indicates that all blocks with
4
a
are interleaved together in a 4-way interleave,
4
b
indicates that all the blocks with
4
b
are interleaved, but it is a different interleave from
4
a.
(The blocks of
4
a
and
4
b
are not interleaved together.)
In typical hardware implementations, there are not an unlimited number of interleave groupings that can be taken, however. Actual interleaving must be mapped to a memory address. Typically part of the memory address is used to select logically defined blocks of memory. Each logical block is programmed with an “interleave register” set which selects, based on additional address bits, the physical bank that the block resides on. Additional address bits select the actual memory word to be accessed. A logical block table and interleave registers must be programmed for the actual memory configuration present. This is usually done by firmware during system initialization at power on.
Typically the memory controller used in the larger systems have register sets which allow for two sets of 2-way interleaving, 1 set of 4-way, 1 set of 8-way and one set of 16-way. If any of the sets for 2-way is not used for 2-way, they can be used for 1-way or high interleaving. The example above would necessarily have to be accomplished differently. Table 3 below indicates a possible solution.
TABLE 3
- - - -
- - - -
- - - -
4a4a4a4a
- - - -
- - - -
- - - -
4a4a4a4a
- - - -
- - - -
- - - -
4a4a4a4a
- - - -
- - - -
- - - -
4a4a4a4a
- - - -
- - - -
8a8a8a8a
8a8a8a8a
- - - -
- - - -
8a8a8a8a
8a8a8a8a
- - - -
2a2a2b2b
8a8a8a8a
8a8a8a8a
16161616
16161616
16161616
16161616
Bank
0 1 2 3
4 5 6 7
8 9 a b
c d e f
Card
0
1
2
3
The 2-way register sets are used since there isn't a second set of 4-way.
Now, however, if the second card has only 2 banks, an attempt to interleave within the constraints would run in to problems. For example in Table 4:
TABLE 4
- - - -
- - - -
- - - -
4a4a4a4a
- - - -
- - - -
- - - -
4a4a4a4a
- - - -
- - - -
- - - -
4a4a4a4a
- - - -
- - - -
- - - -
4a4a4a4a
- - - -
- - - -
8a8a8a8a
8a8a8a8a
- - - -
? ? - -
8a8a8a8a
8a8a8a8a
2a2a2b2b
? ? - -
8a8a8a8a
8a8a8a8a
Bank
0 1 2 3
4 5 6 7
8 9 a b
a d e f
Card
0
1
2
3
The ?? indicate blocks that could not be configured.
There are many different ways to configure the interleaving, but with the constraints given, it is not possible to configure every block.
In the memory systems being considered, all interleaving, except 2-way (and high interleaving), require that a given block in a row of an odd numbered bank must be interleaved with the corresponding block of the next odd numbered bank. In other w
Henderson Daniel James
Nicholson James Otto
Rost John Hughes
Ellis Kevin L.
Felsman Bradley Vaden Gunter & Dillon, LLP
International Business Machines - Corporation
VanLeeuwen Leslie A.
LandOfFree
Method for optimally configuring memory in a mixed... 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 optimally configuring memory in a mixed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimally configuring memory in a mixed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2524916