Memory Organization

Memory hierarchy

A computer uses several kinds of memory, arranged in levels. The levels near the CPU are small, fast and costly. The levels far from the CPU are large, slow and cheap.

The levels are CPU registers, cache, main memory, magnetic disk, and tape or optical disk. Going down the hierarchy, the size and access time grow and the cost per bit falls. The hierarchy works because of locality of reference: programs reuse recent data and use data near it. So most accesses are served by the fast upper levels, and the system looks like a memory that is as fast as the cache and as large as the disk. Data moves between the cache and main memory in blocks, and between main memory and disk in pages.

Numerical

The chip has a capacity of $64\text{K} \times 8$. That is 65536 words of 8 bits each.

(i) The number of address lines is

$$\log_2 65536 = 16$$

So 16 address lines are needed.

(ii) The required memory is $256\text{K} \times 16$. The number of chips is

$$\frac{256\text{K} \times 16}{64\text{K} \times 8} = 4 \times 2 = 8$$

So 8 chips are needed.

The word width is 16 bits and a chip gives only 8 bits, so 2 chips are put side by side to make a 16-bit word. The memory has 256K words and a chip has 64K words, so 4 such rows of chips are needed to get 256K words. The chips form 4 rows and 2 columns.

The system has $256\text{K} = 2^{18}$ words, so it has 18 address lines. The lower 16 lines go to all chips in parallel. The upper 2 lines go to a $2 \times 4$ decoder. Each output of the decoder enables one row of 2 chips. Only that row works at a time. The two chips of the row give the upper and lower bytes of the 16-bit word.

 A17 A16 --> [2x4 decoder] -> CS of row 0..3
 A15..A0 --> all 8 chips
 Row k : [64Kx8 chip] [64Kx8 chip] -> D15..D8, D7..D0

A computer needs a memory that is fast, large and cheap, but no single technology has all three. The memory hierarchy solves this by joining several kinds of memory in levels. The idea is that the CPU sees one fast and large memory.

Design

The levels are arranged from the top (nearest the CPU) to the bottom:

1. CPU registers: smallest and fastest, inside the processor.
2. Cache memory (SRAM): small and very fast, in one or more levels (L1, L2, L3).
3. Main memory (DRAM): medium speed, a few GB.
4. Secondary memory (disk, SSD): large and slow, holds all programs and data.
5. Tertiary memory (tape, optical): very large, very slow, used for backup.

Going down, the capacity and access time increase and the cost per bit falls. Going up, the reverse is true.

Basic concept: locality of reference

The design works because programs show locality of reference. Temporal locality means that a recently used item is likely to be used again soon. Spatial locality means that items near a used item are likely to be used next. So data in use is kept in the upper levels, and data moves between levels in blocks. When the CPU finds the data in the upper level it is a hit, and otherwise it is a miss and a block is brought from the lower level.

Performance

For a two-level system with hit ratio $h$, the average access time is

$$t_{avg} = h,t_1 + (1-h),t_2$$

With $h = 0.95$, $t_1 = 10$ ns and $t_2 = 100$ ns, $t_{avg} = 14.5$ ns. This is close to the speed of the fast level, but the size is that of the large level.

Data movement

Between cache and main memory, data moves in blocks and is managed by hardware. Between main memory and disk, data moves in pages and is managed by the operating system through virtual memory. Registers are loaded by the program instructions.

Locality of reference means that a program tends to use a small part of its memory addresses again and again over a short time. It has two forms. Temporal locality means that an item used now is likely to be used again soon, as in a loop. Spatial locality means that items near the one just used are likely to be used next, as in an array or in straight-line code. Caches use this idea to keep the active data close to the CPU.

A computer needs memory that is fast, large and cheap. No single technology gives all three, so memory is arranged as a hierarchy of levels. The fast, small and costly levels are near the CPU. The slow, large and cheap levels are far from the CPU.

The levels from top to bottom are the CPU registers, cache memory, main memory, secondary memory (magnetic disk, SSD) and tertiary memory (tape, optical disk).

Speed. Moving down the hierarchy, the access time increases. A disk is about a hundred thousand times slower than main memory.

Size. Moving down, the capacity increases by a large factor at each level.

Cost. Moving down, the cost per bit falls. Cache is costly per bit, so only a small amount is used.

Why it works

The hierarchy works because of the principle of locality of reference. Programs use the same data again soon (temporal locality) and use data near the data just used (spatial locality). So a small fast level can hold the data in use, and most accesses are served by it. When data is not found, a whole block is copied from the lower level to the upper level.

If the cache hit ratio is $h$, the cache time is $t_c$ and the main memory time is $t_m$, the average access time is

$$t_{avg} = h,t_c + (1-h),t_m$$

For $h = 0.95$, $t_c = 10$ ns and $t_m = 100$ ns, this is $0.95 \times 10 + 0.05 \times 100 = 14.5$ ns. This is near the speed of the cache, while the memory is as large as the main memory.

Data movement and the trade-off

The three requirements pull against each other. A fast memory needs costly technology, so it must be small. A large memory must use cheap technology, so it must be slow. The hierarchy solves this by placing a small amount of fast memory above a large amount of slow memory. The size of each level is about 100 to 1000 times that of the level above it. Each level holds a copy of the data of the level below that is likely to be used soon. A well chosen block size and a good replacement rule raise the hit ratio at every level.

Inclusion is another property. All data in the cache is also present in main memory, and all data in main memory is also present on the disk. So the lowest level always holds the complete set of data.

Result

The user gets a memory system with a speed close to the fastest level, a size equal to the largest level, and a cost near that of the cheapest level. Data moves between cache and main memory in blocks, and between main memory and disk in pages.

The cache is small, so the memory block that goes into a cache line must be decided by a rule. This rule is the mapping technique. To compare the three, take a 16-bit address, a block of 4 words, and a cache of 256 lines.

i. Direct mapping

Each memory block goes to one fixed cache line:

$$\text{line} = \text{block number} \bmod 256$$

The address has three fields: tag, line and word. The word field has 2 bits, the line field has 8 bits and the tag has the remaining bits:

$$16 - 8 - 2 = 6 \text{ bits}$$

The line field selects the cache line, and its stored tag is compared with the tag of the address. If they are equal, it is a hit. This needs only one comparator and no replacement rule, so it is simple and fast. But blocks that map to the same line replace each other again and again, so the hit ratio can be poor.

ii. Associative mapping

A memory block can be placed in any cache line. The address has only a tag and a word field. Here the tag has $16 - 2 = 14$ bits and the word has 2 bits. The tag is compared with the tags of all 256 lines at the same time, using associative memory. This is the most flexible and gives the highest hit ratio, because there are no conflict misses. But it needs 256 comparators, so it is costly and slow, and it needs a replacement algorithm such as LRU or FIFO.

iii. Set-associative mapping

The lines are grouped into sets. A block maps to one fixed set, but it can go to any line in that set. For a 4-way cache, there are $256/4 = 64$ sets. The set field has 6 bits, the word field has 2 bits and the tag has

$$16 - 6 - 2 = 8 \text{ bits}$$

Only the 4 tags of one set are compared. It reduces conflict misses and costs less than the associative method. A replacement rule is needed only inside the set.

Cache M1 has 16K words and memory M2 has 1M words. Let a block have 8 words. A set has 256 words, so it holds $256/8 = 32$ blocks, and the cache is 32-way set associative.

(i) Mapping between M2 and M1

The sizes are

$$\text{M1 blocks} = \frac{16384}{8} = 2048, \qquad \text{M1 sets} = \frac{16384}{256} = 64$$

$$\text{M2 blocks} = \frac{2^{20}}{8} = 131072$$

M2 has 1M words, which is $2^{20}$, so the address has 20 bits. The word field has $\log_2 8 = 3$ bits. The set field has $\log_2 64 = 6$ bits. The tag is

$$20 - 6 - 3 = 11 \text{ bits}$$

The block number of M2, taken modulo 64, gives the set of M1. So blocks $0, 64, 128, \ldots$ of M2 go to set 0, blocks $1, 65, 129, \ldots$ go to set 1, and so on. Each set of M1 is shared by $131072/64 = 2048$ blocks of M2, which is $2^{11}$, the number of different tags. Within the set, the block can be placed in any of the 32 places. The 11-bit tag stored with the block tells which of the 2048 blocks is present. To find a word, the set field picks the set. Then the 32 tags in that set are compared with the tag of the address in parallel.

 M2 blocks (131072)         M1 sets (64), 32 blocks each
 block 0, 64, 128 ... ---->  Set 0  [ b ][ b ] ... [ b ]
 block 1, 65, 129 ... ---->  Set 1  [ b ][ b ] ... [ b ]
 ...                         ...
 block 63, 127 ...    ---->  Set 63 [ b ][ b ] ... [ b ]

(ii) Effective memory access time

With hit ratio $h = 0.95$, $t_1 = 50$ ns and $t_2 = 400$ ns, when the cache and memory are accessed in parallel on a miss,

$$t_{eff} = h,t_1 + (1-h),t_2 = 0.95 \times 50 + 0.05 \times 400 = 47.5 + 20 = 67.5 \text{ ns}$$

Therefore the effective access time is 67.5 ns. If the memory is accessed only after the cache misses, the miss time is $50 + 400$ ns, and the time becomes $50 + 0.05 \times 400 = 70$ ns. Either way, it is close to the cache speed and much better than 400 ns.

Direct mapping

In direct mapping, each block of main memory can be placed in only one fixed line of the cache. The line number is given by

$$\text{line} = (\text{block number}) \bmod (\text{number of cache lines})$$

The main memory address is divided into three fields: tag, index (block or line) and word. The word field selects a word inside the block. The block field selects the cache line. The tag is the remaining high bits. It is stored with each cache line. It tells which of the many memory blocks that share the line is now present.

On a memory reference, the line field selects the line. The stored tag is compared with the tag of the address. If they are equal and the valid bit is 1, it is a hit, and the word is taken. Otherwise it is a miss. The whole block is read from main memory into that line, and the old block is overwritten. No replacement algorithm is needed.

Merits: simple, cheap, and fast, as only one tag comparison is needed. Demerit: if two active blocks map to the same line, they replace each other again and again (thrashing), though other lines are free.

Numerical

Main memory is $64\text{K} \times 16$, so the address has $\log_2 65536 = 16$ bits. The cache has 1K words, so the index has $\log_2 1024 = 10$ bits. A block has 4 words.

(i) The word field needs $\log_2 4 = 2$ bits. The cache has $1024/4 = 256$ lines, so the block field needs $\log_2 256 = 8$ bits. The tag is

$$16 - 8 - 2 = 6 \text{ bits}$$

(ii) The number of blocks the cache can hold is

$$\frac{1024}{4} = 256 \text{ blocks}$$

Therefore the fields are tag 6 bits, block 8 bits and word 2 bits, and the cache can hold 256 blocks. The main memory has $65536/4 = 16384$ blocks, so every cache line is shared by 64 memory blocks.

The hit ratio is the fraction of CPU memory references that are found in the cache. The miss ratio is the fraction that are not found, so

$$\text{hit ratio} + \text{miss ratio} = 1$$

For example, suppose the CPU makes 200 references and 180 are found in the cache. Then the hit ratio is $180/200 = 0.9$ and the miss ratio is $20/200 = 0.1$. On a miss, the block must be fetched from the slower main memory.

The cache has 256 blocks of 16 words each, so it holds $256 \times 16 = 4096$ words. Main memory is addressed by 16 bits, so it has $2^{16} = 65536$ words. With 16 words per block, main memory has $65536/16 = 4096$ blocks, which matches the 4K blocks given.

In set-associative mapping, the cache blocks are grouped into sets. A memory block maps to one set, and it can sit in any block of that set. The address is divided into tag, set and word fields.

Word field

A block has 16 words, so the word field must select one of 16 words:

$$\text{word} = \log_2 16 = 4 \text{ bits}$$

Set field

The cache is 2-way, so each set has 2 blocks. The number of sets is

$$\text{sets} = \frac{256}{2} = 128$$

so the set field has

$$\log_2 128 = 7 \text{ bits}$$

Tag field

The tag is what remains of the 16-bit address:

$$\text{tag} = 16 - 7 - 4 = 5 \text{ bits}$$

The address format is

Therefore the fields are TAG = 5 bits, SET = 7 bits and WORD = 4 bits.

Check

The tag and set bits together give the block number of main memory: $5 + 7 = 12$ bits, and $2^{12} = 4096$ blocks, which agrees with the given size. Each set receives $4096/128 = 32$ memory blocks, and the 5-bit tag tells which of those 32 blocks sits in a cache block. The set has only 2 places, so at most 2 of those 32 blocks can be present at one time.

Working

When the CPU gives an address, the set field picks one set. The tags of both blocks of that set are compared with the tag of the address at the same time. If one of them matches and its valid bit is 1, it is a hit, and the word field selects the word. If neither matches, it is a miss. The block is fetched from main memory into the set, replacing one of the two blocks by the LRU or FIFO rule.

Comparison with other mappings

For the same cache, direct mapping would use 256 lines, giving tag $= 16 - 8 - 4 = 4$ bits, line 8 bits and word 4 bits. Fully associative mapping would use a tag of $16 - 4 = 12$ bits and no set field. The 2-way scheme lies between the two. Going from direct to 2-way, the tag grows by one bit and the set field shrinks by one bit, because the number of sets halves.

A short example shows the use of the fields. Take a memory block whose 12-bit block number has tag 10110 and set field 0000101 (which is 5). This block can go only to set 5 of the cache, in either of its two blocks. Any block with the same last 7 bits, such as one with tag $00001$, also competes for set 5. The two together can stay in the cache, which would be impossible in direct mapping.

The 2-way scheme needs only two comparators, and it still removes many conflicts.

An associative memory is also called content addressable memory (CAM). A word is found by its content, not by an address. The search key is compared with all stored words at the same time, and the matching word is returned.

Advantages: the search is very fast, because all words are checked in parallel, and no address is needed. It is useful for cache tags and page tables.

Disadvantages: every cell needs its own comparison logic, so it is costly, takes more space, and is built only in small sizes.

Main memory is $64\text{K} \times 16$. Since $64\text{K} = 2^{16}$, the memory address has 16 bits and each word is 16 bits wide. The cache has 1K words, so it has $1\text{K} = 2^{10}$ words. A block holds 4 words.

In direct mapping, the address is split into a tag, an index and a word field. The index selects the cache location. The tag is stored with the data and is compared to find a hit.

I. Address fields

The word field selects one of 4 words in a block, so it has $\log_2 4 = 2$ bits. The cache has $1024 / 4 = 256$ blocks, so the block field has $\log_2 256 = 8$ bits. Together the word and block fields form the index of 10 bits, as the cache has 1K words. The tag takes the remaining bits:

$$\text{tag} = 16 - 10 = 6 \text{ bits}$$

So the address format is

The total is $6 + 8 + 2 = 16$ bits.

II. Bits in each cache word

Each cache word stores the 16-bit data, the 6-bit tag of the block it belongs to, and 1 valid bit. The valid bit tells whether the word holds real data or is still empty after power on. So

$$16 + 6 + 1 = 23 \text{ bits}$$

The 16 bits are the data, 6 bits are the tag used for the hit check, and 1 bit is the valid flag. The whole cache is therefore $1\text{K} \times 23$ bits.

III. Number of blocks

$$\text{blocks} = \frac{1024 \text{ words}}{4 \text{ words per block}} = 256$$

The cache can hold 256 blocks. Main memory has $65536 / 4 = 16384$ blocks, so every cache block is shared by $16384/256 = 64$ memory blocks. These 64 blocks differ only in their tag value.

The tag is stored along with the data so that the cache can tell which of the 64 memory blocks is now present at an index. Without the tag, two different memory blocks with the same index could not be told apart. A new block replaces the old one directly, because direct mapping gives only one possible place.

Working example

Take the address $\text{0x1234}$. Its upper 6 bits give tag $= 4$. The next 8 bits give block number $= 141$, and the last 2 bits give word $= 0$. The cache looks at index $564$ (block 141, word 0). If the valid bit is 1 and the stored tag is 4, it is a hit and the word is sent to the CPU. Otherwise it is a miss. The whole 4-word block is then read from main memory, and the tag is updated to 4.

Hit ratio is the fraction of memory accesses that find the needed data in the cache.

$$\text{Hit ratio } H = \frac{\text{number of hits}}{\text{total number of accesses}}$$

For example, if the CPU makes 1000 accesses and 950 are found in the cache, then $H = 950/1000 = 0.95$. The miss ratio is $1 - H = 0.05$. A higher hit ratio gives a lower average access time, because fewer accesses go to the slow main memory.

A cache is much smaller than main memory, so the system must decide which memory block goes to which cache line. This rule is the mapping technique. There are three kinds.

Direct mapping

Each main memory block can go to exactly one cache line, given by $\text{line} = \text{block number} \bmod \text{number of lines}$. The address is split into tag, line (index) and word fields. The line field picks the cache line, and the tag is compared with the stored tag to check for a hit. For example, with a 16-bit address, 4-word blocks and 256 cache lines, the fields are tag 6, line 8 and word 2 bits.

Merits: it is simple, cheap, fast, and needs only one comparator. No replacement rule is needed. Demerits: two blocks that map to the same line keep throwing each other out, even if other lines are empty. The hit ratio can fall badly.

Associative (fully associative) mapping

A block can be placed in any cache line. The address has only a tag and a word field. In the same example the tag is 14 bits and the word is 2 bits. The tag is compared with all stored tags at the same time, using associative (content addressable) memory.

Merits: it is the most flexible. Conflict misses do not occur, and the hit ratio is the highest. Demerits: it needs one comparator per line, so the hardware is costly and slower. A replacement algorithm such as LRU or FIFO is needed.

Set-associative mapping

The cache lines are grouped into sets. A block maps to one particular set, but it can go to any line inside that set. With $k$ lines per set it is called $k$-way. In the example, a 4-way cache has $256/4 = 64$ sets, so the fields are tag 8, set 6 and word 2 bits. Only the $k$ tags of one set are compared.

Merits: it is a good middle path. It removes most conflict misses and needs only $k$ comparators. Demerits: it needs more hardware than direct mapping, and a replacement rule is still required inside each set.

Comparison

A good mapping keeps useful blocks together and avoids needless replacement. It also keeps the tag comparison cheap, because the cache must answer in one or two clock cycles.

Direct mapping is the special case of 1-way set associative, and associative mapping is the case where one set holds all the lines.

In practice, most modern processors use set-associative caches with 2, 4 or 8 ways, because this gives a hit ratio close to full associativity at a much lower hardware cost.

2D organization

In 2D organization, the memory cells are arranged as an array in which each row is one word. A single decoder takes all $n$ address bits and activates one of the $2^n$ word lines. Then all the bits of that word are read or written together.

 Address (n bits) --> [ n to 2^n decoder ] --> word lines
                                                 |
                                       [ cell array: 2^n words ]
                                                 |
                                             data bits

Advantages: the structure is simple, the design is easy, and a whole word is accessed at once, so it is fast for small memories. Disadvantages: the decoder needs $2^n$ output lines. For $64\text{K}$ words, that is 65536 lines and gates. The decoder is large, costly and slow, so it is unsuitable for big memories.

2 1/2D organization

In 2 1/2D organization the cells are arranged in a square-like array. The address is split into a row part and a column part. A row decoder selects one row and a column decoder (with a multiplexer) selects one column. The cell at the crossing is accessed.

 Row address (n/2)  --> [ row decoder ] --> rows
                                              |
                                        [ cell array ]
                                              |
 Col address (n/2)  --> [ column decoder / mux ] --> data

For $64\text{K} \times 1$ bits, the array is $256 \times 256$. Each decoder has 256 outputs, so the total is

$$256 + 256 = 512$$

instead of 65536 in 2D.

Advantages: the decoder size is very small, so the cost and area are low. It suits large chips, and refresh of a whole row is easy for DRAM. Disadvantages: two decoding steps are needed, so the access control is a little more complex. One cell is selected at a time per array, so several arrays must be used in parallel to get a wider word.

Semiconductor RAM is built from cells arranged in rows and columns. It allows both reading and writing and is volatile. The two main types are SRAM and DRAM.

SRAM (static RAM)

An SRAM cell is a bistable flip-flop made of six transistors. Two cross-coupled inverters keep one of two stable states for 1 and 0, and two access transistors connect the cell to a pair of bit lines (b and b').

        word line
   ------+----------+------
         |          |
      [T5]        [T6]
   b ----+--[ flip-flop ]--+---- b'
          (T1 to T4)

To read, the word line is made high. The access transistors turn on and the cell state appears on the bit lines, where a sense amplifier detects it. To write, the data and its complement are put on the bit lines, and the word line forces the flip-flop into the new state. The data stays as long as power is on, and no refresh is needed. SRAM is very fast but costly, and it takes a large area. It is used in cache.

DRAM (dynamic RAM)

A DRAM cell has one transistor and one capacitor. The charge on the capacitor stands for the bit: charged is 1 and discharged is 0.

   bit line ----[ T ]----+
                 |       |
   word line ----+     ===  C
                         |
                        GND

To write, the word line turns on the transistor, and the bit line charges or discharges the capacitor. To read, the transistor is turned on and the charge is shared with the bit line. A sense amplifier detects the small change. This read destroys the stored charge, so the data is written back at once. The charge also leaks, so each row must be refreshed every few milliseconds. DRAM is slower, but cheap and dense. It is used as main memory. The address is given in two parts, the row address (RAS) and then the column address (CAS), which saves pins.

Comparison

In 2 1/2D memory organization, the cells are placed in a two-dimensional array of rows and columns. The address is split into two halves. A row decoder selects one row, and a column decoder selects one column. The cell at the crossing is accessed. Two small decoders of about $2^{n/2}$ outputs each are used, instead of one big decoder of $2^n$ outputs. This reduces the cost and area of the memory chip.

Both are semiconductor RAM, but they differ in how a bit is stored and in cost.

Because of these differences, a computer uses a little SRAM for speed and a large amount of DRAM for capacity.

SRAM and DRAM are both volatile semiconductor memories, but they differ as follows.

A RAM is built from a large array of storage cells. The way the cells are arranged and addressed decides the size of the decoder and the cost of the chip. The two common arrangements are 2D and 2 1/2D.

2D organization

In 2D organization the cells are arranged as a two-dimensional array of words. Each row is one word, and each word has its own word line. A single decoder takes all $n$ address bits and activates exactly one of the $2^n$ word lines. All bits of that word are then read or written through the bit lines.

 Address (n bits) --> [ n to 2^n decoder ]
                        | word line 0 ---> [ word 0 ]
                        | word line 1 ---> [ word 1 ]
                        | ...
                        | word line 2^n-1 > [ word 2^n-1 ]
                                               |  |  |
                                         bit lines to R/W circuit

The decoder is a big circuit. For a $64\text{K} \times 1$ memory, $n = 16$, so the decoder has $2^{16} = 65536$ output lines and 65536 AND gates. This is costly and slow, and it takes a large area. So 2D organization suits only small memories.

2 1/2D organization

Here the cells are arranged in a square-like array of rows and columns, and the address is split into two halves. A row decoder takes the upper half and selects one row. A column decoder takes the lower half and selects one column through a multiplexer (or a column selector). The cell at the crossing of the chosen row and column is read or written.

 Row address (n/2) --> [ row decoder ] --> row lines
                                              |
                                   +------------------+
                                   |   cell array     |
                                   |  (rows x cols)   |
                                   +------------------+
                                              |
 Col address (n/2) --> [ column decoder / mux ] --> data bit

For the same $64\text{K} \times 1$ memory, the cells form a $256 \times 256$ array. The row decoder has 8 inputs and 256 outputs, and the column decoder also has 256 outputs. The total number of decoder outputs is

$$256 + 256 = 512$$

compared with 65536 in the 2D scheme. The saving is large. The name "2 1/2D" is used because the structure is more than a plain 2D array but not a full 3D one.

Comparison

The 2 1/2D scheme is also easy to refresh, because DRAM can refresh a whole row in one step. This is why modern memory chips use it.

In short, the 2D scheme is easy to understand but wastes area on the decoder, and the 2 1/2D scheme saves that area by splitting the address, which is why large memory chips follow it.

(i) Memory of 1024 x 8

Each chip stores 1024 words of 1 bit. A word of 8 bits needs 8 bits in parallel, so

$$\text{chips} = \frac{1024 \times 8}{1024 \times 1} = 8$$

The memory has 1024 words, so it needs 10 address lines because $2^{10} = 1024$. All 10 address lines are connected in parallel to every one of the 8 chips. Each chip gives one bit of the word, so the data pin of chip 0 is bit 0, that of chip 1 is bit 1, and so on up to bit 7. The read/write line and the chip select line are also common to all chips. All 8 chips work together as one 8-bit wide memory.

Connection diagram for part (i)

 A9..A0 (10 lines) ---+----+----+--- ... ---+  (to all 8 chips)
 R/W, CS -------------+----+----+--- ... ---+
                      |    |    |           |
                   [chip0][chip1][chip2] .. [chip7]
                      |    |    |           |
                     D0   D1   D2   ...    D7

Here the lines D0 to D7 form the 8-bit data bus of the memory. Because the address lines are shared, a single address selects the same cell position in all 8 chips. The 8 bits read from them together form one memory word. This is called widening the word length. When the memory must be made deeper (more words), more groups are added, and the extra high address lines select one group, as shown below.

(ii) Memory of 16 KB

Take 1 byte as 8 bits. Then 16 KB is $16 \times 1024 = 16384$ words of 8 bits, that is $16384 \times 8 = 131072$ bits. Each chip holds 1024 bits, so

$$\text{chips} = \frac{16384 \times 8}{1024 \times 1} = 128$$

So 128 chips are needed. They form 16 groups of 8 chips, and each group is a $1024 \times 8$ block like the one in part (i).

The memory has 16384 words, so it needs 14 address lines because $2^{14} = 16384$. The lower 10 lines go to all chips in parallel. The upper 4 lines go to a $4 \times 16$ decoder. Each decoder output enables one group of 8 chips. In this way only one group works at a time.

For instance, the address with A13 to A10 equal to 0101 enables group 5. That group holds the words from $5 \times 1024 = 5120$ to $5120 + 1023 = 6143$. The other 15 groups stay idle, and their data outputs are in the high impedance state. This allows all 16 groups to share the same 8 data lines.

In short, adding chips side by side widens the word, and adding chip groups with a decoder increases the number of words.

SRAM (static RAM) stores each bit in a flip-flop made of about six transistors. It keeps the data as long as power is on and needs no refresh. It is fast but costly and takes more space, so it is used for cache memory.

DRAM (dynamic RAM) stores each bit as charge on a tiny capacitor with one transistor. The charge leaks, so every row must be refreshed within a few milliseconds. DRAM is slower, cheaper and denser, so it is used for main memory.

In 2D organization the cells form one array of rows and columns. A single decoder takes all $n$ address bits and drives one of $2^n$ word lines, so a whole word is selected at once. The decoder becomes very large for big memories.

In 2 1/2D organization the address is split into a row part and a column part. Two small decoders (row and column) select the cell, so each needs only about $2^{n/2}$ outputs. The total decoder size is much smaller, which makes it cheaper and the usual choice in real chips.

The chip stores $4096 \times 8$ bits, that is 4096 words of 8 bits each, or 4 KB.

Pins needed

Since $2^{12} = 4096$, the chip needs 12 address lines. It needs 8 data lines, which are bidirectional. There are 2 enable (chip select) lines and 1 read/write control line. These make

$$12 + 8 + 2 + 1 = 23$$

signal pins. Two more pins are needed for the power supply and ground, so the package has 25 pins in all.

Block diagram and labels

                 +----------------------+
  Address  12 -->|                      |
                 |    RAM 4096 x 8      |<--> Data (8)
  CS1 ---------->|                      |
  CS2 ---------->|                      |
  R/W ---------->|                      |
                 +----------------------+
                   Vcc, GND (power pins)

Inputs are the 12 address lines, the two enables CS1 and CS2, and the read/write line R/W. The 8 data lines are both input and output. The chip works only when both enables are active. Then R/W = 1 reads a word onto the data lines, and R/W = 0 writes the data lines into the addressed word. If the chip is not enabled, the data lines are in the high impedance state.

Inside the chip

The 12 address bits go to an internal decoder. The decoder selects one of the 4096 words in the cell array. The selected 8 cells are connected to the data lines through tri-state buffers. These buffers are on only when the chip is enabled, so many chips can share one data bus without clashing.

The total size follows from the pins:

$$2^{12} \times 8 = 4096 \times 8 = 32768 \text{ bits}$$

Two enable lines are given so that a larger memory can be built easily. One enable can come from the high address bits through a decoder, and the other can come from a control signal such as the memory-request line. For instance, if the chip is placed at the start of the address space, its address range is $\text{0x000}$ to $\text{0xFFF}$.

The same rule gives the pin count for any RAM chip. Address pins equal $\log_2$ of the number of words, data pins equal the word width, and a few control pins are added. A larger chip such as $8192 \times 8$ would need one more address pin, so 13, while its data pins would stay at 8.

Main feature of RAM

In a random-access memory, every location can be reached in the same time, whatever its position in the memory. The time does not depend on the address used. A RAM can be both read and written, and it is volatile, so it loses its data when power is switched off.

ROM (read-only memory) is a non-volatile memory, so it keeps its contents when the power is off. Its main purpose is to store programs and data that must always be present and need not change. Examples are the bootstrap loader that starts the computer, the BIOS or firmware, and fixed tables such as character codes. The CPU can only read it during normal work. ROM is also used to hold microprograms in the control unit and to implement lookup tables and combinational logic.

Auxiliary (secondary) memories hold large amounts of data permanently, at a low cost per bit. They are not directly accessed by the CPU. Their data is first brought into main memory. They are slow, but non-volatile.

Magnetic disk

A magnetic disk has circular platters coated with magnetic material. The platters spin, and a read/write head moves over them. Data is stored in tracks and sectors. It is a direct access device. The access time is seek time plus rotational latency plus transfer time. It has a large capacity (hundreds of GB to TB), a reasonably low cost and a fast transfer rate. It is used as the main storage for the operating system, programs and files. It is also the base of virtual memory. Its drawbacks are moving parts, noise, and damage from shocks.

Magnetic tape

A magnetic tape is a long plastic strip coated with magnetic material, held in reels or cartridges. Data is written in tracks along the tape. It is a sequential access device. To reach a record, the tape must be run past all earlier records, so the access is slow. But it has a very low cost per bit and a very high capacity, and it is easy to store. It is used for backup, archives and bulk data. A record can be read only in order, so it is not suitable for random access.

Optical disk

An optical disk stores data as pits and lands on a spiral track. A laser reads them by the difference in reflected light. CD-ROM holds about 700 MB, DVD about 4.7 GB, and Blu-ray about 25 GB. Read-only, write-once and rewritable forms exist. Optical disks are cheap, light and long lasting, and they are good for distributing software, music and movies. They are slower than a magnetic disk and have less capacity.

Comparison

The functions of these memories are permanent storage, backup, data exchange between machines, and extending the main memory through virtual memory.

Classification by method of access

Construction of a magnetic disk

A magnetic disk has one or more platters made of aluminium or glass, coated with magnetic material. They are fixed on a spindle which rotates at a constant speed, such as 7200 rpm. Each surface is divided into concentric circles called tracks. Each track is divided into sectors, and a sector is the smallest unit that can be read or written (often 512 bytes). The tracks at the same position on all surfaces form a cylinder. A read/write head is placed over each surface, and all heads are fixed on one arm assembly that moves together. A disk controller drives the arm and moves data.

Working

To write, the head sends a current through its coil, which magnetizes a tiny spot on the surface in one of two directions, standing for 1 and 0. To read, the moving magnetized spots induce a small current in the head, which is sensed as bits. To reach a sector, the arm moves the heads to the right cylinder. Then the disk turns until the sector is under the head. Then the data is transferred.

Components of disk access time

$$T_{access} = T_{seek} + T_{rotation} + T_{transfer} + T_{controller}$$

1. Seek time is the time to move the head to the required track. It is the largest part, a few milliseconds.
2. Rotational latency is the time for the needed sector to come under the head. On average it is half a rotation, $\frac{60}{2 \times \text{rpm}}$ seconds. For 7200 rpm it is $60/(2 \times 7200) = 4.17$ ms.
3. Transfer time is the time to read the sector bytes, equal to the data size divided by the transfer rate.
4. Controller overhead is the small time used by the disk controller for commands and checks.

Magnetic disk

A magnetic disk is the main secondary storage of a computer. It has one or more circular platters coated with magnetic material. The platters spin at a fixed speed, such as 7200 rpm. Each surface is divided into concentric circles called tracks, and each track is divided into sectors, which are the smallest units read or written. A read/write head floats over each surface on an arm. The head magnetizes spots to write and senses them to read.

The disk is a direct access device. The head first moves to the right track, and then it waits for the sector. The access time is

$$\text{access time} = \text{seek time} + \text{rotational latency} + \text{transfer time}$$

The seek time is the time to move the arm to the track. Rotational latency is the wait for the sector to come under the head, on average half a rotation. At 7200 rpm one rotation takes $60/7200 = 8.33$ ms, so the average latency is about $4.17$ ms. Disks are cheap, large and non-volatile, but slow compared to memory.

Magnetic tape

A magnetic tape is a long plastic strip coated with magnetic material, wound on reels or in a cartridge. Data is written in tracks along the length of the tape. It is a sequential access device. To reach a record, the tape must be wound past all the records before it. So the access is slow, but once the right position is reached the data transfer is fast. Tape is very cheap per bit and holds a large amount of data. It is used for backup and archives. Its drawback is that random access is not possible.

Optical disk

An optical disk stores data as tiny pits and flat areas (lands) along a spiral track. A laser beam is focused on the surface. The reflected light is different for a pit and a land, and a sensor reads this as 0 or 1. Common types are as follows.

Optical disks are cheap, easy to carry and last long, which is good for software and movies. They are slower than a magnetic disk.

All three are non-volatile, so data stays when power is off. Magnetic media can also be rewritten many times, but they can be damaged by strong magnetic fields, heat and dust.

Comparison

In a computer system, the disk is used as the main file store, the tape as an off-line backup, and the optical disk to carry and share software and media.

Virtual memory is a technique that gives a program the feeling of a very large main memory, bigger than the real RAM. The program uses virtual addresses. The system keeps the active parts in main memory and the rest on the disk, and it moves parts in and out as needed. The address translation is done by hardware, using a page table, so the programmer does not need to manage it.

This is a segmented-paged system. The logical address is divided into a segment number, a page number and a word number. The physical address is divided into a block number and a word number.

Logical address format

There are 128 segments, so the segment field needs $\log_2 128 = 7$ bits. Each segment has up to 32 pages, so the page field needs $\log_2 32 = 5$ bits. Each page has 4K words, so the word field needs $\log_2 4096 = 12$ bits. The logical address is

$$7 + 5 + 12 = 24 \text{ bits}$$

Physical address format

Physical memory has 4K blocks, so the block field needs $\log_2 4096 = 12$ bits. Each block has 4K words, so the word field needs 12 bits. The physical address is

$$12 + 12 = 24 \text{ bits}$$

Check of sizes

The logical space is $128 \times 32 \times 4096 = 2^{24}$ words. The physical memory is $4096 \times 4096 = 2^{24}$ words. Both are 16M words.

The two sizes can also be seen as counts. The logical space has $128 \times 32 = 4096$ pages in total, and the physical memory has 4096 blocks. So each logical page can in the best case have its own block, but a program uses far fewer pages than this at one time.

How the mapping works

The page size and the block size are both 4K words, so the 12 word bits are copied unchanged from the logical address to the physical address. Only the segment and page numbers must be translated into a block number.

The segment number selects an entry in the segment table. That entry gives the address of the page table of that segment. Each segment has its own page table with 32 entries. The page number selects an entry in this page table, and the entry holds a 12-bit block number. This block number is joined with the 12-bit word to give the physical address.

 Logical: [ Segment 7 ][ Page 5 ][ Word 12 ]
              |            |          |
        Segment table   Page table    |
              |------->  (32 entries) |
                          |           |
 Physical:           [ Block 12 ][ Word 12 ]

The mapping needs two table reads, one in the segment table and one in the page table, so it is slower than plain paging. A TLB is used to keep the recent translations and avoid these reads. Protection bits in the segment table also allow each segment to be marked read only or executable.

For example, if the entry of page 3 in the page table of segment 5 holds block 100, then the logical address (segment 5, page 3, word 20) maps to physical block 100 with word 20.

(a) Mapping of a virtual address to a physical address

A virtual (logical) address is the address made by the program. It must be changed to a physical address in main memory. This is done by the memory management unit (MMU) with the help of a page table. The virtual address is divided into a page number and an offset. The page table is stored in main memory. It has one entry for each page, and the entry holds the frame (block) number and a valid bit.

The page number is used as an index into the page table. If the valid bit is 1, the frame number is read from the entry. This frame number is joined with the offset to make the physical address. The offset is copied unchanged, because pages and frames have the same size. If the valid bit is 0, a page fault occurs and the operating system loads the page from disk.

A page table lookup costs one more memory access. So a small and fast memory called the translation lookaside buffer (TLB) holds the recent page-to-frame translations. The MMU looks at the TLB first. A TLB hit gives the frame number at once, and only a TLB miss needs the page table.

 Virtual address [ page no. | offset ]
                      |          |
                    TLB / page table
                      |          |
 Physical address [ frame no. | offset ]

(b) Methods of writing into cache

When the CPU writes, the cache and the main memory can become different. Two main policies solve this.

Write-through. Every write goes to the cache and to main memory at the same time. Main memory always holds the latest data, so it is simple and safe for I/O devices and multiple processors. The disadvantage is that every write is slow because it uses the main memory, and it creates a lot of bus traffic. A write buffer is often used to hide this delay.

If a program changes the same variable 100 times, write-through sends 100 writes to main memory. The next policy sends just one.

Write-back (copy-back). A write goes only to the cache, and the block is marked dirty with a modified bit. Main memory is updated only when the dirty block is removed from the cache. This gives fewer memory writes and faster operation: the 100 changes above cost only one write, made when the block is replaced. The disadvantage is that main memory may hold old data for some time, so it is more complex to keep consistent.

When a write misses, there are two choices. In write-allocate, the block is first brought into the cache, and then written. In no-write-allocate, the data is written straight to main memory. Write-back is usually used with write-allocate, and write-through with no-write-allocate.

A page fault is an event that occurs when a program refers to a page that is not present in main memory. The page table entry of that page has its valid bit as 0, so the hardware raises a trap to the operating system. The operating system then loads the page from disk into a free frame (removing another page if needed), updates the page table, and restarts the instruction. A page fault costs a lot of time, because a disk access is very slow compared to a memory access.

The reference string has 20 page numbers and there are 4 frames. A page fault happens when the needed page is not in any frame.

FIFO removes the page that has been in memory the longest. The frames below are listed from the oldest to the newest page.

LRU removes the page that was used least recently. The frames below are listed from the least recently used to the most recently used.

Counting the faults in each column gives

$$\text{FIFO faults} = 14, \qquad \text{LRU faults} = 10$$

The first four faults in both are compulsory, because the frames are empty at the start. FIFO has 6 hits, so its hit ratio is $6/20 = 0.30$. LRU has 10 hits, so its hit ratio is $10/20 = 0.50$.

Therefore, with 4 frames, FIFO gives 14 page faults and LRU gives 10 page faults. LRU does better here because it keeps the pages 1, 2 and 3, which are used again and again. FIFO throws out a page just because it is old, even when it is still in use. For example, FIFO removes page 2 and page 1 early, and has to fetch them again.

LRU needs extra hardware or counters to track the last use, while FIFO needs only a simple queue. LRU is also free from Belady's anomaly, where more frames can give more faults under FIFO.

A larger number of frames normally lowers the page faults, so with 4 frames both algorithms do better than they would with 3 frames on the same string.

Virtual memory is a technique that lets a program use an address space larger than the real main memory. The programmer writes addresses in a big virtual (logical) address space. The hardware and the operating system keep only the needed parts in main memory and the rest on disk. The program feels that a large, continuous memory is available.

It is useful for three reasons. A program bigger than RAM can still run. Many programs can stay in memory together. The programmer need not care where the program is loaded.

How paging helps

In paging, the virtual address space is cut into equal fixed-size blocks called pages. The main memory is cut into blocks of the same size called frames. Any page can be placed in any free frame. So there is no external fragmentation, and finding space is easy. Only the pages in use are brought into memory, and this is called demand paging.

Address translation

A virtual address has two parts: the page number and the offset inside the page. A table called the page table is kept in main memory. It has one entry per page. Each entry holds the frame number, a valid (present) bit, a modified bit and protection bits. The page number selects the entry. If the valid bit is 1, the frame number is joined with the offset to form the physical address.

Virtual address        Page table            Physical address
+-----------+--------+                      +-----------+--------+
| page no.  | offset |                      | frame no. | offset |
+-----------+--------+                      +-----------+--------+
      |         |         +-------------+        ^           ^
      +-------->+-------->| valid|frame |--------+           |
                |         +-------------+                    |
                +--------------------------------------------+

For example, take a page size of 4 KB, so the offset has 12 bits. In a 32-bit virtual address the page number has 20 bits. The virtual address $\text{0x00003ABC}$ has page number 3 and offset $\text{0xABC}$. If page 3 sits in frame 7, then the physical address is $\text{0x00007ABC}$.

Page fault

If the valid bit is 0, the page is not in memory and a page fault occurs. The operating system finds the page on disk and picks a free frame. If no frame is free, it removes a victim page using a replacement rule such as FIFO or LRU. A modified victim is first written back to disk. The new page is loaded, the page table is updated and the instruction is restarted.

Speeding up with a TLB

Reading the page table costs one extra memory access for every reference. A small, fast cache of recent translations, called the translation lookaside buffer (TLB), avoids most of these extra accesses.

Merits and limits

Paging gives a large virtual space, easy memory sharing and protection, and good memory use. Its costs are the space taken by page tables and the time lost when page faults are frequent. Too many faults cause thrashing, where the system spends more time moving pages than doing useful work.