Memory System

Bipin Thapa Magar

[email protected]
Microcomputer Memory

→ Stores binary instructions and data for microcomputer

→ A single technology is not best for all memory requirements
→ The memory unit that communicates directly with the CPU is called main memory
→ Devices that provide backup storage are called auxiliary memory or secondary memory

Compiled By Bipin Thapa Magar and Baikuntha Acharya 2

Characteristics of Memory System
Access Method:
→ Based on location, capacity, unit of transfer, access method, 1. Sequential Access
performance, physical type, physical characteristics and → Start from beginning and read each
organization → Access time depends on position of record
Location: → Eg: Tape
1. Processor Memory 2. Direct Access
→ Inside the processor (Register) → Unique address for each block
2. Internal Memory → Jump to certain block and sequentially to record
→ Inside the CPU (Main Memory) → Eg: Disk
3. External Memory 3. Random Access
→ Peripheral Storage devices → Any location can be selected randomly and
→ Disk and Magnetic tape via I/O directly addressed and accessed
Capacity → Time to access independent of sequence and is
1. Word size: in terms of words or bytes constant
2. Number of words: common word lengths are 8, 16, 32, etc. → Eg: RAM
4. Associative Access
Unit of Transfer → Random access
1. Internal: equal to no of data lines in and out of memory → Enables one to make a comparison of desired bit
module locations within a word for a specified match.
2. External: transferred in block larger than word → Eg: Cache
Compiled By Bipin Thapa Magar and Baikuntha Acharya 3
Characteristics of Memory System
Performance:
1. Access time: Physical Types:
→ Time between presenting the address and getting the valid data 1. Semiconductor: RAM
→ For random access, it is time to perform read or write operation 2. Magnetic: Disk & Tape
→ For non-random access, it is time needed to position read/write 3. Optical: CD & DVD
at desired location 4. Others
2. Memory Cycle time:
Physical Characteristics:
→ Total time that is required to store next memory access 1. Decay: Information decay means data loss
operation from the previous memory access operation 2. Volatility: Information decay when power
→ Time may be required for the memory to “recover” before next is cut off
access 3. Erasable: Erasable means permission to
→ Cycle time is access + recovery erase
3. Transfer Rate: 4. Power Consumption: How much power
→ Rate at which data can be moved consumes
→ For random access, R = 1 / cycle time
Organization:
For non-random access, Tn = Ta + N / R;
1. Physical arrangement of bits into words
where, Tn=average time to read or write N bits, Ta=average access
2. Not always obvious (eg: interleaved)
time, N=number of bits, R=Transfer rate in bits per second (bps).
Compiled By Bipin Thapa Magar and Baikuntha Acharya 4
The Memory Hierarchy
→ Larger capacity, more application will get space to run smoothly.
→ Fast memory = Greater performance
→ Tradeoff between three: Cost, Capacity and Access time
→ If capacity increases, access time increases (slower) and due to
which cost per bit decreases.
→ If access time decreases (faster), capacity decreases and due to
which cost per bit increases
→ We use memory hierarchy to obtain highest performance while
minimizing total cost.

→ Memory Hierarchy obtains highest possible access speed while

minimizing total cost. Figure: Memory Hierarchy
→ Use low-cost storage as backup for unused data
Compiled By Bipin Thapa Magar and Baikuntha Acharya 5
The Memory Hierarchy
As we go down the hierarchy:
1. Cost per bit decreases
2. Capacity of memory increases
3. Access time increases
4. Frequency of access of memory by processor
decreases

Hierarchy List
1. Registers
2. L1 Cache
3. L2 Cache
4. Main memory
5. Disk cache
6. Disk
Figure: Memory Hierarchy
7. Optical
8. Tape
Compiled By Bipin Thapa Magar and Baikuntha Acharya 6
Internal Memory

→ Also called main memory

→ Large and fast memory to store programs and data
→ Semiconductor integrated circuits with basic element called memory cell
→ Memory cell has 3 fundamental terminals:
1. Select Terminal: select the cell
2. Data in/Sense Terminal: Put data into the cell
or read data from cell
1. Control Terminal: Control for read or write
Figure: Memory Cell

→ Most main memory are made up of RAM but some might use ROM as well.

Compiled By Bipin Thapa Magar and Baikuntha Acharya 7

Internal Memory

RAM (Random Access Memory)

→ The process of locating a word in memory is the same and requires an equal amount of time no matter where
the cells are located physically in memory thus named 'Random access’.
→ Two types: SRAM and DRAM

1. Static RAM (SRAM):

→ Consists flipflops to store binary information
→ The stored information remains valid as long as power is applied to the unit.
→ T5 and T6 is controlled by address line. When a signal is applied to this line,
the two transistors are switched on allowing for read and write operation.
→ T1, T2, T3 and T4 are used to store information
→ In logic 1, C1 is high and C2 is low. So, T1 and T4 are off and T2 and T3 are on.
→ In logic 0, C1 is low and C2 is high. So, T1 and T4 are on and T2 and T3 are off.
→ For write, desired bit is sent to B and its complement in B’.
→ For read, bit value is read from line B. Figure: SRAM
Compiled By Bipin Thapa Magar and Baikuntha Acharya 8
Internal Memory
2. Dynamic RAM (DRAM):
→ Consists capacitor to store binary information in form of electrical charge
→ Capacitor must be periodically recharged since capacitor discharges with time.
→ It is called refreshing memory
→ Activate address line when it is to be read or write
→ The transistor acts as switch that is closed i.e. allowed current to flow, if voltage is
applied to the address line; and opened i.e. no current to flow, if no voltage is present in
the address line.
DRAM writing:
→ Address line is activated
→ Sense amplifier senses the data in bit line. If bus is low, bit line is connected to ground
and any charge in capacitor is addressed out
→ If bus is high, +5V is applied on bit line and voltage is passed and capacitor is charged
DRAM reading:
→ Address line is activated
→ If capacitor is charged, current flows through transistor and raise voltage in bit line. The
Figure: DRAM
amplifier stores the voltage and places 1 on data line.
→ If there is no charge, no current flows and sensor senses no current. Then amplifier
places 0 on data out line.
Compiled By Bipin Thapa Magar and Baikuntha Acharya 9
Internal Memory
SRAM vs DRAM
→ Both volatile (Power is needed)

SRAM DRAM
1. Uses flipflop to store information 1. Uses capacitor to store information
2. Needs more space 2. More dense (more cells per unit area)
3. Faster, digital device 3. Slower, analog device
4. Expensive, big in size 4. Less expensive, small in size
5. Don’t require refreshing circuit 5. Needs refreshing circuit
6. Used in cache memory 6. Used in main memory, larger memory units

Compiled By Bipin Thapa Magar and Baikuntha Acharya 10

Internal Memory

Read Only Memory (ROM)

→ Permanent pattern of data that cannot be changed.
→ Non-volatile
→ Normally, it is not possible to write new data onto ROM
→ It is created like other IC chip with data fabricated onto it
→ Two problems:
1. The data insertion step includes a relatively large fixed cost, whether one or thousands of copies of a
particular ROM are fabricated.
2. There is no room for error. If one bit is wrong, the whole batch of ROM must be thrown out.

Compiled By Bipin Thapa Magar and Baikuntha Acharya 11

Internal Memory
Types of ROM:
1. Programmable ROM (PROM):
→ Written only once.
→ The writing process is performed electrically.
→ Performed by a supplier or customer at a time later than the original chip fabrication.

2. Erasable Programmable ROM (EPROM):

→ Read and written electrically
→ Before write, UV is exposed to erase the data. Erasure is performed by shining an intense ultraviolet light
through a window that is designed into the memory chip
→ EPROM is optically managed and more expensive than PROM, but it has the advantage of the multiple update
capability.

Compiled By Bipin Thapa Magar and Baikuntha Acharya 12

Internal Memory

Read Only Memory (ROM)

Types of ROM:
3. Electrically Erasable Programmable ROM (PROM):
→ Can be written into at any time without erasing prior contents, only the byte or byte addresses are updated
→ The write operation takes considerably longer than the read operation, on the order of several hundred
microseconds per byte.
→ EEPROM is more expensive than EPROM and also is less dense, supporting fewer bits per chip.

4. Flash Memory:
→ High speed of reprogramming, so called flash.
→ It is interpreted between EPROM and EEPROM in both cost and functionality.
→ Erased electrically in few seconds.
→ Possible to erase blocks of memory rather than entire chip.
→ Doesn't provide byte level erasure, a section of memory cells are erased in an action or 'flash’.

Compiled By Bipin Thapa Magar and Baikuntha Acharya 13

External Memory
→ Backup storage or auxiliary memory
1. Magnetic Tape
→ Strip of plastic coated with a magnetic recording medium
→ Data can be recorded and read as a sequence of character through read / write head.
→ can be stopped, started to move forward or in reverse or can be rewound
Figure: Magnetic Tape
→ Data on tapes are structured as number of parallel tracks running length wise
→ Earlier tape system typically used nine tracks: 1 byte and a parity
→ The recording of data in this form is referred to as parallel recording

2. Magnetic Disk Figure: Magnetic Disk

→ Circular plate constructed with metal or plastic coated with magnetic material often
both side of disk
→ Several disk stacked on one spindle which Read/write head available on each surface.
→ All disks rotate together at high speed
→ Bits are stored in magnetize surface in spots along concentric circles called tracks
Compiled By Bipin Thapa Magar and Baikuntha Acharya 14
External Memory
2. Magnetic Disk

→ The tracks are commonly divided into sections called sectors.

→ After the read/write head are positioned in specified track the system has to wait until
the rotating disk reaches the specified sector under read/write head.

→ Eg: Hard disk, Floppy Disk

3. Optical Disk

→ The disk is form from resin such as polycarbonate.

→ Digitally recorded information is imprinted as series of microscopic pits on the surface of poly
carbonate using LASER
Figure: Optical Disk
→ The pitted surface is then coated with reflecting surface usually aluminum or gold. The shiny
surface is protected against dust and scratches by the top coat of acrylic
Compiled By Bipin Thapa Magar and Baikuntha Acharya 15
External Memory

→ Information is retrieved by low power laser by checking intensity when

pit is encountered(lower light)

→ The areas between pits are called lands. A land is a smooth surface which
reflects back at higher intensity.

→ This is changed to digital signal.

→ DVD:
→ Multilayer
→ Very high capacity (4.7G per layer)
→ Full length movie on single disk using MPEG compression
→ Players only play correct region films
Figure: Optical Disk
Compiled By Bipin Thapa Magar and Baikuntha Acharya 16
Cache Memory Principles
Principles:
→ Intended to give memory speed approaching that of fastest memories available but with large size, at close to
price of slower memories
→ Cache is checked first for all memory references.
→ If not found, the entire block in which that reference resides in main memory is stored in a cache slot, called a line
→ Each line includes a tag (usually a portion of the main memory address) which identifies which particular block is
being stored
→ Locality of reference implies that future references will likely come from this block of memory, so that cache line
will probably be utilized repeatedly.
→ The proportion of memory references, which are found already stored in cache, is called the hit ratio.
→ When the processor attempts to read a word of memory, a check is made to determine if the word is in the cache.
If so, the word is delivered to the processor. If not, a block of main memory, consisting of fixed number of words is
read into the cache and then the word is delivered to the processor.
→ The locality of reference property states that over a short interval of time,
address generated by a typical program refers to a few localized
area of memory repeatedly
Compiled By Bipin Thapa Magar and Baikuntha Acharya 17
Cache Memory Principles
→ When the CPU needs to access memory, cache is examined. If the word is found in cache, it is read from the
cache and if the word is not found in cache, main memory is accessed to read word. A block of word containing
the one just accessed is then transferred from main memory to cache memory.

→ Cache connects to the processor via data control and address line.
The data and address lines also attached to data and address buffer
which attached to a system bus from which main memory is reached
→ When a cache hit occurs, the data and address buffers are disabled
and the communication is only between processor and cache with
no system bus traffic.
→ When a cache miss occurs, the desired word is first read into the
cache and then transferred from cache to processor. For later case,
the cache is physically interposed between the processor and main
Figure: Typical Cache Organization
memory for all data, address and control lines
Compiled By Bipin Thapa Magar and Baikuntha Acharya 18
Cache Operation Overview

Figure: Cache/Main Memory Structure Figure: Flowchart of cache read operation

Compiled By Bipin Thapa Magar and Baikuntha Acharya 19

Cache Operation Overview
Locality of Reference:
→ The reference to memory at any given interval of time tends to be confined within a few localized area of memory.
This property is called locality of reference.
→ This is possible because the program loops and subroutine calls are encountered frequently. When program loop is
executed, the CPU will execute same portion of program repeatedly. Similarly, when a subroutine is called, the CPU
fetched starting address of subroutine and executes the subroutine program. Thus loops and subroutine localize
reference to memory
→ This principle states that memory references tend to cluster over a long period of time, the clusters in use changes
but over a short period of time, the processor is primarily working with fixed clusters of memory references.

Spatial Locality:
→ It refers to the tendency of execution to involve a number of memory locations that are clustered.
→ It reflects tendency of a program to access data locations sequentially, such as when processing a table of data.

Temporal Locality:
→ It refers to the tendency for a processor to access memory locations that have been used frequently. For e.g.
Iteration loops executes same set of instructions repeatedly

Compiled By Bipin Thapa Magar and Baikuntha Acharya 20

Elements of Cache Design
1. Cache Size:
→ Size of the cache to be small enough so that the overall average cost per bit is close to that of main memory alone and large
enough so that the overall average access time is close to that of the cache alone
→ The larger the cache, the larger the number of gates involved in addressing the cache
→ Large caches tend to be slightly slower than small ones – even when built with the same integrated circuit technology and put
in the same place on chip and circuit board.
→ The available chip and board also limits cache size.

2. Mapping function:
→ The transformation of data from main memory to cache memory is referred to as memory mapping process.
→ Because there are fewer cache lines than main memory blocks, an algorithm is needed for mapping main memory blocks into
cache lines.
→ Example assume:
→ The cache can hold 64 Kbytes
→ Data is transferred between main memory and the cache in blocks of 4 bytes each. This means that the cache is
organized as 16Kbytes = 214 lines of 4 bytes each.
→ The main memory consists of 16 Mbytes with each byte directly addressable by a 24 bit address (224 = 16Mbytes). Thus,
for mapping purposes, we can consider main memory to consist of 4Mbytes blocks of 4 bytes each.

Compiled By Bipin Thapa Magar and Baikuntha Acharya 21

 Elements of Cache Design
2.1 Direct Mapping:
→ Simple technique, one block of main memory to only one possible cache line
i = j modulo m
i = cache line number; j = main memory block number; m = no of lines in cache
→ The least significant w bits identify a unique word or byte within a block of main memory.
→ The remaining s bits specify one of the 2s blocks of main memory.
→ The cache logic interprets these s bits as a tag of (s-r) bits most significant position and a line field of r bits. The latter field
identifies one of the m = 2r lines of the cache.
• Address length = (s + w) bits • Address length = 24 bits
• Number of addressable units = 2s+w words or bytes • Block size = line size = 22 = 4 bytes
• Block size = line size = 2w words or bytes • 22 bit block identifier
• Number of blocks in main memory = 2s+ w/2w = 2s • 8 bit tag (22-14), 14 bit slot or line
• Number of lines in cache = m = 2r • No two blocks in the same line have the same Tag field
• Size of tag = (s – r) bits • Check contents of cache by finding line and checking Tag

Figure: Cache Address

Compiled By Bipin Thapa Magar and Baikuntha Acharya 22
Elements of Cache Design
2.1 Direct Mapping:
Cache line Main Memory blocks held → All locations in single block of memory has same higher order bits (s)
0 0, m, 2m, 3m … 2s-m → Lower (w) bits are used to find particular word in block
1 1, m+1, 2m+1 … 2s-m+1 → Within the higher, r bits follow the modulo and determine the cache
. . line number
m-1 m-1, 2m-1, 3m-1 … 2s-1 → The remaining bits are tag which is used to separate one block from
another that fit into same cache line

Compiled By Bipin Thapa Magar and Baikuntha Acharya 23

Elements of Cache Design
2.1 Direct Mapping:

Figure: Direct Mapping

Compiled By Bipin Thapa Magar and Baikuntha Acharya 24
 Elements of Cache Design
2.1 Direct Mapping:

Pros and Cons:

→ Simple
→ Inexpensive
→ Fixed location for given block

→ If a program accesses 2 blocks that map to the same line repeatedly,

cache misses are very high

Explanation:
→ 0000 to FFFF is mapped onto line i.e. 65536 = 216 memory
→ Taking block of size 4, 216/4 = 214 lines in cache (14 bits for cache line)
→ If we consider 00 to FF= 256 = 28 such division of main memory, we
need 8 bits to separate (tag bits)
→ Mapping of main memory to cache line:
FFFC / 4 = 3FFF
(FFFC to FFFF is squeezed onto 1 line at 3FFF)
Figure: Direct Mapping Example
Compiled By Bipin Thapa Magar and Baikuntha Acharya 25
 Elements of Cache Design
2.2 Associative Mapping:
→ Each main memory block can be loaded into any line of cache.
→ A tag and word field
→ Tag identifies block of memory
→ Cache control logic must simultaneously examine every line’s tag for a match which requires fully associative memory
→ very complex circuitry, complexity increases exponentially with size
→ Cache searching gets expensive

• Address length = (s + w) bits • 22 bit tag stored with each 32 bit block of data
• Number of addressable units = 2s+w words or bytes • Compare tag field with tag entry in cache to check
• Block size = line size = 2w words or bytes for hit
• Number of blocks in main memory = 2s+ w/2w = 2s • Least significant 2 bits of address identify which 16
• Number of lines in cache = undetermined bit word is required from 32 bit data block
• Size of tag = s bits

Compiled By Bipin Thapa Magar and Baikuntha Acharya 26

Elements of Cache Design
2.2 Associative Mapping:

Figure: Associative Mapping

Compiled By Bipin Thapa Magar and Baikuntha Acharya 27
Elements of Cache Design
2.2 Associative Mapping:

Example:

Address Tag Data Cache Line

FFFFFC FFFFFC 24682468 3FFF

Explanation:
→ Mapping:
16339C / 4 = 058CE7
(4 bits squeezed to single line)
→ It is mapped to line 0001 since we can map
anywhere in associated mapping

Compiled By Bipin Thapa Magar and Baikuntha Acharya 28

 Elements of Cache Design
2.3 Set Associative Mapping:
→ Compromise between the earlier two
→ Cache is divided into v sets, each of which has k lines; number of cache lines = vk
m=vXk
I = j modulo v
Where, i = cache set number; j = main memory block number; m = number of lines in the cache
→ A block will map directly to a particular set, but can occupy any line in that set (or any set but particular line in each set)
→ The most common set associative mapping is 2 lines per set, and is called two-way set associative. It significantly improves hit
ratio over direct mapping, and the associative hardware is not too expensive.
• Address length = (s + w) bits • 13 bit set number
• Number of addressable units = 2s+w words or bytes • Block number in main memory is modulo 213
• Block size = line size = 2w words or bytes • 000000, 00A000, 00B000, 00C000 … map to same set
• Number of blocks in main memory = 2d • Use set field to determine cache set to look in
• Number of lines in set = k • Compare tag field to see if we have a hit
• Number of sets = v = 2d
• Number of lines in cache = k v = k * 2d
• Size of tag = (s – d) bits

Compiled By Bipin Thapa Magar and Baikuntha Acharya 29

Elements of Cache Design
2.3 Set Associative Mapping:

Figure: Set Associative Mapping (Fixed Set Changeable Line)

Compiled By Bipin Thapa Magar and Baikuntha Acharya 30
 Elements of Cache Design
2.3 Set Associative Mapping:

Example:

Address Tag Data Set

Number
1FF 7FFC 1FF 24682468 1FFF
001 7FFC 001 11223344 1FFF

Explanation:
→ Mapping:
02C 339C
02C = tag
339C/4= 0CE7 (cache set)
Can store in any of the two lines in the set

(Fixed Line Changeable Set)

Compiled By Bipin Thapa Magar and Baikuntha Acharya 31
Elements of Cache Design
3. Replacement Algorithm
→ When all lines are occupied, bringing in a new block requires that an existing line be overwritten.
→ For direct, we have no choice as only one line for each block
→ For Associative and Set Associative Mapping:

1. Least Recently used (LRU)

→ Replace that block in the set which has been in cache longest with no reference to it
→ Implementation: with 2-way set associative, have a USE bit for each line in a set. When a block is read into cache, use the line
whose USE bit is set to 0, then set its USE bit to one and the other line’s USE bit to 0.
→ Probably the most effective method
2. First In First Out (FIFO)
→ Replace that block in the set which has been in the cache longest
→ Implementation: use a round-robin or circular buffer technique (keep up with which slot’s “turn” is next)
3. Least-frequently-used (LFU)
→ replace that block in the set which has experienced the fewest references or hits
→ Implementation: associate a counter with each slot and increment when used
4. Random
→ replace a random block in the set
→ Interesting because it is only slightly inferior to algorithms based on usage
Compiled By Bipin Thapa Magar and Baikuntha Acharya 32
 Elements of Cache Design
2. Write Back
4. Write Policy
→ When an update occurs, an UPDATE bit associated with
→ If a block has been altered in cache, it is necessary to write it
that slot is set, so when the block is replaced it is
back out to main memory before replacing it with another block
written back first
→ When a line is to be replaced, must update the original copy of
→ Only change contents of cache during update and
the line in main memory if any addressable unit in the line has
update main memory when cache line is to be replaced
been changed
→ Causes “cache coherency” problems -- different values
→ Overwrite cache only when main memory is up to date
for the contents of an address are in the cache and the
→ I/O modules may be able to read/write directly to memory
main memory
→ Multiple CPU’s may be attached to the same bus, each with their
→ Accesses by I/O modules must occur through the cache
own cache
→ To avoid cache coherency between multiple caches
a. Bus Watching with Write Through - other caches
1. Write Through
monitor memory writes by other caches (using write
→ All write operation to both cache and memory
through) and invalidates their own cache line if a match
→ Other CPU monitor traffic to main memory to keep cache
b. Hardware Transparency - additional hardware links
updated
multiple caches so that writes to one cache are made
→ High memory traffic and can lead to bottleneck
to the others
→ Need to change in both cache and memory after each write
c. Non-cacheable Memory - only a portion of main
which causes a lot of writes to memory
memory is shared by more than one processor, and it is
→ Multiple CPUs can monitor main memory traffic to keep local (to
non-cacheable
CPU) cache up to date but has a lot of trafficCompiled
and slows
By Bipinspeed
Thapa Magar and Baikuntha Acharya 33
 Elements of Cache Design
1. Unified Cache
5. Number of Caches
→ Single cache contains both instructions and data. Cache is
flexible and can balance “allocation” of space to
1. L1 Cache (On Chip Cache)
instructions or data to best fit the execution of the
→ It is the cache memory on the same chip as the processor, the
program.
on-chip cache. It reduces the processor's external bus activity
→ Has a higher hit rate than split cache, because it
and therefore speeds up execution times and increases overall
automatically balances load between data and
system performance.
instructions (if an execution pattern involves more
→ Requires no bus operation for cache hits
instruction fetches than data fetches, the cache will fill up
→ Short data paths and same speed as other CPU transactions
with more instructions than data)
→ Only one cache need be designed and implemented
2. L2 Cache (Off Chip Cache)
2. Split Cache
→ It is the external cache which is beyond the processor.
→ Cache splits into two parts first for instruction and second
→ If there is no L2 cache and processor makes an access request
for data. Can outperform unified cache in systems that
for memory location not in the L1 cache, we need to access
support parallel execution and pipelining (reduces cache
RAM which slows performance.
contention)
→ If an L2 SRAM cache is used, then frequently the missing
→ Trend is toward split cache because of superscalar CPU’s
information can be quickly retrieved.
→ Better for pipelining, pre-fetching, and other parallel
→ It can be much larger
instruction execution designs
→ It can be used with a local bus to buffer the CPU cache-misses
→ Eliminates cache contention between instruction
from the system bus Compiled By Bipin Thapa Magar and Baikuntha Acharya 34
processor and the execution unit (which uses data)