Chapter 5

Memory System

Basic Memory Concept

The Memory is the functional unit of the computer where the instructions and data are stored
and the execution can be performed.
The maximum size of the memory can be used by any computer determined by the addressing
scheme. For example, a 16-bit computer that generate 16-bit address is capable of addressing
up to 216 = 64K memory location. Similarly,
• For 32-bit computer generates 232 = 4G.
• For 64-bit computer generates 264 = 8G.

Figure 5.1: Connection of Memory to Processor.

The data transfer between the memory and the processor takes place through the two processor
registers MAR and MDR. If MAR is k bits long and MDR is n bits long, then the memory
unit may contain up to 2k addressable locations and during the memory cycle, n-bits of data
are transferred between memory and processor. This is carried out through the k-bit address
bus and n-bit data bus. The bus also includes the control lines Read/Write (R/W) and Memory
Function Complete (MFC) for coordinate data transfer.

Memory Cells
The memory is designed in the form of [Link] consisting of tiny cells which is capable of
storing 1 bit of data. Based upon the types of cells the memory is of two types:

35
36 CHAPTER 5. MEMORY SYSTEM

1. Static RAM

and

2. Dynamic RAM.

Static RAM

Figure 5.2: Static RAM Cell.

Memories that consist of circuit which are capable of retaining their state as long as the
power is applied are known as static memories. Figure 5.2 illustrate how the static RAM
(SRAM) may be implemented. Two inverter are cross-connected to form latch. The latch is
connected by two transistor T1 and [Link] transistors are act as switches that can be opened
and closed under the control fo the word [Link] the word line is at ground level the transis-
tors are turned off then the latch is retain its state.

Read Operation
During the Read Operation,Word line is activated to close switches T1 and T2 . If the cell is in
state 1; the signal on b line is high and the signal on b line is [Link] opposite is true if the cell
is in state [Link], b and b are always complements of each others.
The sense /write circuit at the end of the two bit line monitors their state and sets the
corresponding output accordingly.

Write Operation
While in Write Operation ,the Sense/Write circuit drives bit lines b and b, instead of sensing
their [Link] places the appropriate value on bit line b and its complement on b and activate the
word [Link] forces the cell into the corresponding state, which the cell retains when the word
line is deactivated.
5.1. BASIC MEMORY CONCEPT 37

Dynamic RAM Cell

Figure 5.3: Dynamic RAM Cell.

In Dynamic Random Access Memory CELL , transistor acts as a switch to Close (allowing
current to flow) when voltage applied in address line or Open (no current flow) when no voltage
applied in address [Link] Line also known as word line .Which use to signal the transistor
to close or open.

Read Operation
While in Reading Operation ,the instruction find the bit store using the address line to read the
data or [Link] the address line is selected ,the transistor turns on and the charge stored on
the capacitor is fled out onto a bit line and to sense amplifier. Sense amplifiers compare the
40 CHAPTER 5. MEMORY SYSTEM

capacitor voltage to reference value to determine the logic 1 or logic [Link] read out from cell
must be restored to complete the operation.

Write Operation
During the Write operation,a voltage is applied on the bit line and a signal applied to the address
line to close the [Link] the voltage applied on the bit line will transfer to capacitor and
store in the capacitor. However the capacitor has tendency to discharge and has to refresh to
maintain the bit.
The dynamic RAM is of two types:-

• SynchronousDynamic RAM(SDRAM)
• AsynchronousDynamic RAM

SynchronousDynamic RAM(SDRAM)
A relatively new and different kind of RAM, Synchronous DRAM or SDRAM differs from ear-
lier types in that it does not run asynchronously to the system clock the way older, conventional
types of memory do. SDRAM is tied to the system clock and is designed to be able to read or
write from memory in burst mode (after the initial read or write latency) at 1 clock cycle per ac-
cess (zero wait states) at memory bus speeds up to 100 MHz or even higher. SDRAM supports
5-1-1-1 system timing when used with a supporting chipset. SDRAM accomplishes its faster
access using a number of internal performance improvements, including internal interleaving,
which allows half the module to begin an access while the other half is finishing one.
SDRAM is rapidly becoming the new memory standard for modern PCs. The reason is
that its synchronized design permits support for the much higher bus speeds that have started
to enter the market. SDRAM doesn’t offer that much ”real world” additional performance over
EDO in many systems, due to the system cache masking much of that differential in speed,
and the fact that most systems are running on relatively slow 66 MHz or lower system bus
speeds. As 100 MHz bus system PCs become mainstream, SDRAM will largely replace older
technologies, since it is designed to work at these higher operating speeds and conventional
asynchronous DRAM is not.

AsynchronousDynamic RAM
Asynchronous DRAM is an older type of DRAM used in the first personal computers. It is
called ”asynchronous” because memory access is not synchronized with the computer system
clock. Modern PCs typically use synchronized DRAM (SDRAM) that responds to read and
write operations in synchrony with the signal of the system clock.

Internal organization of Memory Chip

Memory cells are usually organized in the form of array, in which each cells capable of store
a bit of information. A possible organization is illustrated in Figure 5.4. Each row of cell
constitutes a memory word and all cells of a row are connected to a common line referred
to Word line, which is driven by address decoder on the chip. The cell in each column are
connected to a Sense/Write circuit by two bit lines.
The Sense/Write circuits are connected to the data input/output line of the chip. During the
5.3. STRUCTURE LARGER MEMORIES 39

Figure 5.4: Synchronous DRAM.

read operation, these circuits sense or read the information stored in the cell selected by a
word line and transmit this information to the output data lines. During the write operation,the
sense/write circuits receive input information and store in the cells of the selected word.

Figure 5.4 is an example of very small memory chip consisting of 16 words and 8 bits in
each. This is referred as 16 X 8 organization.
• It required 4 address line to access a word. And 8 data line.
• Two control line for sens/Write and for Chip Select(CS).
Therefore, in total it required 14 external lines and additional two lines for power and
• ground.

Now,consider a slightly larger memory circuit one that has 1K(1024)memory cells. this
circuit can be organized as a 128 X 8 memory, requiring total of 19 external connections.
Alternatively, the same chip can be organized into a 1K X 1 format. In this case, a 10-bit
address is needed, but there is only one data line resulting in 15 external connection is required.
Figure 5.5 shows an organization. the required 10-bit address is divided into two groups of 5-
bits each to form the row and column addresses for cell-array. A row selects 32 cells,all of
which are connected in parallel. However, according to the column address, only one of these
cells is connected to the external data line by the output multiplexer and input demultiplex.
Commercially available memory chips are having a much larger number of memory cells then
the above examples.

Structure Larger Memories

To design the structure of larger memory module we have to consider the size of the memory
module and the size of the memory chip used for the module. Which determines the array size
40 CHAPTER 5. MEMORY SYSTEM

Figure 5.5: Internal organization of Memory Chip.

for the memory module.

Arraysize = S ize o f Memory Module (5.1)

S ize o f the Chip
Consider the memory module of size of 2M X 32 by using the chip of size 512K X 8.

Array S ize = 2MX32 (5.2)

512KX8
21 X220 X232

= 29 X210 X23 (5.3)

(5.4)
Array S ize 221 X25
= 219 X23

Array S ize = 22X22 = 4X4 (5.5)

Here, it required 21-bits for accessing the memory module, from which 19-bits are re-
quired to select the chip and 2-bits are required to decode the row [Link] R/W inputs of
all the chip are tied together to provide a common Read/Write control.

Memory Controller
To reduce the number of pins the dynamic memory chips use multiplexed address is divided
into two parts. The High-order address bits selects the row in cell array, are provided first
latched into the memory chip under the control of RAS [Link] the Low-order address
bits, which select a column, are provided on the same address pins and latched using CAS
signal.
5.5. SPEED,SIZE AND COST 41

Figure 5.6: Internal organization of Memory Chip.

A typical processor issues all bits of an address at same time. The required multiplex-
ing of address bit is performed by memory controller circuit,which is interposed between the
processor and dynamic memory as shown tn the Figure 5.8.

Speed,Size and Cost

Memory is evaluated according to the following (incomplete list of) criteria:

Costs: Typically costs are expressed as a ratio of dollars per byte. Costs can be accounted
• for in different ways, such as purchase price, total costs of ownership, and in between
measures. For example, an enterprise that uses disks to store 1 Terabyte of data pays
more than just the 20 disks needed to store the data. The disks need to be placed in a
storage cabinet, and connected to the storage server. In addition to this hardware, there
are also the costs of administration and maintenance.

• Capacity: The amount of data that can be stored per unit.

Speed: The time it takes to access data. When we assess the speed of devices, we need
• to distinguish between the raw speed of the device (e.g. 50 nsec for RAM) and the speed
of data access using the technology embedded in the system (e.g. 200 nsec for accessing
main memory because of paging support). A device might react differently to request de-
pending on previous operations. For example, streaming from a disk drive yields higher
data rate (and hence higher access speed per byte) than true random accesses. Reading
from a RAM bank repeatedly is slower than reading from different RAM banks, etc.

Reliability: Increasingly important, reliability in the strict sense measures the time from
• initialization to the first/next failure event. It is measured in mean time to failure (MTTF).
If a module can be repaired, we can calculate or statistically determine the mean time to
repair (MTTR). Availability in the strict sense is the proportion of time that a device is
42 CHAPTER 5. MEMORY SYSTEM

Figure 5.7: Organization of 2M X 32 memory module using 512K X 8 static Memory chip.

Figure 5.8: Use of Memory Controller.

up and running, or - in an alternative interpretation - the probability of finding a device

up and running. Availability equals MTTF / (MTTF + MTTR).

• Other characteristics such as volatility (does the device retain data after powering down),
or transportability.

Cache Memories
The main memory is slower than processor, to maintain speed gap between main memory and
the processor a small but faster memory is used which called Cache Memory.

The cache memory stores the frequently referred instructions,which is executed by the
processor.
5.6. CACHE MEMORIES 47

Figure 5.9: Memory Hierarchy.

Figure 5.10: Cache Memory.

A particular portion of code/instruction is localized for the frequent referral this concept
is known as Locality of reference. The cache memory is uses this concept to make the execution
of instruction. The locality of reference is of two types:

1. Temporal Locality of Reference,

2. Spatial Locality of Reference.

Temporal Locality of Reference

In this approach the recently executed instruction is likely to be execute again very soon.

Spatial Locality of Reference

In this approach the instructions in close proximity to a recently executed instruction are also
likely to be executed very soon.
48 CHAPTER 5. MEMORY SYSTEM

Cache Mapping Policies

The cache memory is using the instructions which are required frequently from main mem-
ory, for which it is using a technique called cache mapping. The cache mapping is using the
mapping functions, based upon which there are three types of Mapping Policies.

1. Direct Mapping,

2. Associative Mapping, and

3. Set-Associative Mapping.

The different placement policies (the mapping functions) are illustrated below by an ex-
ample with these parameters:
Block size: 24 = 16 words;
Cache memory: 211 = 2048 words = 27 = 128 blocks;
Main memory: 216 = 64K words = 212 = 4096 blocks;

The 4096 memory blocks can be mapped to the 128 cache blocks in three different ways:

Direct Mapping
To avoid the search through all CM blocks needed by associative mapping, this method only
allows 212/27 = 4096/128 = 25 = 32 MM blocks to be mapped to each CM block. A tag of 5
bits need to be attached to each CM block to identify which of the 25 = 32 MM blocks is
currently in there. There are two ways to map the MM blocks to the CM blocks:

Figure 5.11: Direct Mapping.

• Continuous Mapping (high-order):

The first 32 consecutive MM blocks (0 through 31) are mapped to the first CM block, the
second 32 MM blocks (32 through 63) are mapped to the second CM block, etc.
Addressing process: The 16-bit address is divided into 3 fields, the 7 MSBs to identify
the CM block, the middle 5 bits to match with the 5-bit tag of the block, and the 4 LSBs
to select the word in the block in case of a match.
5.6. CACHE MEMORIES 47

Example: For the 16-bit address A5B216 = 10100101101100102, the top 7 bits (1010010)
indicate CM block 82, the next 5 bits (11011) is to match with the tag of the block.

• Interleaved Mapping (low-order):

The first 128 consecutive MM blocks are mapped, respectively, to the 128 CM blocks,
so that the first CM block takes one of these 32 MM blocks: 0, 128, 256, ..., 4064, the
second CM block takes one of these MM blocks: 1, 129, 257, ..., 4065, etc.
Addressing process: The 16-bit address is divided into 3 fields, the 5 MSBs to match
with the 5-bit tag of the CM block identified by the middle 7 bits, and the 4 LSBs to
select the word in the block in case of a match.
Example: For the 16-bit address A5B216 = 10100101101100102, the top 5 bits (10100)
are to be matched with the tag of CM block 91, identified by the next 7 bits (1011011).
Which of the two methods is better in light of the spatial locality nature of memory
usage?
Advantage: Direct mapping is faster than the associative mapping as it avoids searching
through all the CM tags for a match.
Disadvantage: But it lacks mapping flexibility. For example, if two MM blocks mapped
to same CM block are needed repeatedly (e.g., in a loop), they will keep replacing each
other, even though all other CM blocks may be available.

Associative Mapping
Associative Mapping: a block in the MM can be mapped to any block in the CM available (not
already occupied). A tag of 12 bits is attached to each of the 128 CM blocks to identify which
of the 212 MM blocks is currently in there.

Advantage: Flexibility. An MM block can be mapped anywhere in CM.

Disadvantage: Slow or expensive. A search through all the 128 CM blocks is needed to
check whether the 12 MSBs of the 16-bit address can be matched to any of the tags.
Addressing process: The 16 bits in the address are divided into 2 fields, the 12 MSBs are
compared with the 12-bit tag of each of the blocks, and if there is a match, then the 4 LSBs
select the word in the block.

Figure 5.12: Associative Mapping.

48 CHAPTER 5. MEMORY SYSTEM

Example:
For a 16-bit address A5B216 = 10100101101100102, the top 12 bits (101001011011) are
matched with the 12-bit tag of each of the 128 CM blocks. If a match is found, the last 4 bits
(0010) select word 2 (the 3rd word) of the block with a matching tag.

Set-Associative Mapping
This is a trade-off between associative and direct mappings. The 128 CM blocks are divided
into 25 = 32 sets each containing 27/25 = 128/32 = 4 blocks. By direct mapping, every 212/25
= 4096/32 = 27 = 128 MM blocks are mapped to each CM set. A 7-bit tag is attached to each
CM block to identify the current MM block. By associative mapping, an incoming MM block
can use any of the 4 blocks in the set, so long as it is available.
Again, either continuous or interleaving direct mapping can be used to map MM blocks to
the CM sets. But the latter is better (why?).
Addressing process (interleaving): The 16-bit address is divided into 3 fields of 7, 5 and 4
bits, respectively (from MSB to LSB). (a) The middle 5 bits select one of the 25 = 32 sets, (b)
the top 7 bits are compared with the 7-bit tag of each of the 4 blocks in the set, if there is a
match, (c) the last 4 bits find the needed word in the block. Example:

Figure 5.13: Associative Mapping.

In the 16-bit address A5B216 = 10100101101100102, the middle 5 bits (11011) identifies
set 27, the top 7 bits (1010010) are compared with the tag of each of the 4 blocks in the set. If
a match is found, the last 4 bits (0010) select word 2 in the block.

Performance Consideration
The cache memory performance is measured by the following parameters:
• Memory Interleaving
• Cache Hit Rate and Miss Penalty
5.6. CACHE MEMORIES 47

Memory Interleaving
In general, the CPU is more likely to need to access the memory for a set of consecutive words
(either a segment of consecutive instructions in a program or the components of a data structure
such as an array, the interleaved (low-order) arrangement is preferable as consecutive words
are in different modules and can be fetched simultaneously. In case of high-order arrangement,
the consecutive words are usually in one module, having multiple modules is not helpful if
consecutive words are needed.
Example: A memory of 216 = 64k words (n=16) with 24 = 16 modules (m=4) each containing
2n−m = 212 = 4k words: See figure 5.15.

Figure 5.14: Addressing multiple-module memory system.

Figure 5.15: Memory Interleaving Example.

48 CHAPTER 5. MEMORY SYSTEM

Hit Rate/Ratio and Miss penalty

• Hit: If a block of main memory is searched and it is found is call hit/ cache hit.
• Miss: If a block of main memory is searched and it is not found is call miss/ cache miss.
Hit/miss Rate/ Ratio: The number hit or miss occurred during the several access of cache
• memory is called Hit/miss Rate/ Ratio.

• Miss Penalty: The additional access time is required to access main memory.

The average access time can be calculated using cache for main memory
tavg = hC + (1 − h)M

Virtual Memory
Virtual memory is usually implemented through paging: main memory is divided into
• fixed sized blocks called p programs are divided into fixed size blocks called pages

The same size as a page frame pages are brought into main memory from disk when need
• pages (and therefore programs) can be stored out-of-omemory so the cpu uses a virtual
address to access memory

• Which is mapped onto a physical (real) address

Translation Look-Aside Buffer

• we’ve just seen that for every data request two accesses to memory are required:
one to look in the page table
and one to fetch the actual data

• the page table is accessed very often

• and within the page table certain rows are likely to be accessed more often
• so it makes sense to store their references in cache
• and that’s effectively what the TLB does:
• stores most recent page lookup values in a table held in cache:
• each row contains a pairing: (virtual page number, physical page number)

Replacement Algorithm
In computing, cache algorithms (also frequently called cache replacement algorithms or cache
replacement policies) are optimizing instructionsor algorithmsthat a computer program or a
hardware-maintained structure can follow in order to manage a cache of information stored on
the computer. When the cache is full, the algorithm must choose which items to discard to
make room for the new ones.
 REPLACEMENT ALGORITHM 49

Figure 5.16: Virtual Memory Address Translation.

There are several types of replacement algorithms, these following are few of them:

• FIFO(First In First Out)

• LRU(Least Recently Used)

• Optimal

FIFO(First In First Out)

See the example in the figure- 5.17(Middle).

Figure 5.17: Replacement Algorithms.