CHAPTER 4

MEMORY
UNIT
1
 OUTLINE
 Introduction
 Computer Memory System Overview
 Characteristics of Memory Systems
 The Memory Hierarchy
 Cache Memory
 Cache Memory Principles
 Elements of Cache Design
 Semiconductor Main Memory
 Organization
 Types of Semiconductor Memories
 Error Correction
 External Memory
 Magnetic Disk
 Optical Memory
 Magnetic Tape 2
 Solid State Drives
 PART 1

 Introduction

 Computer Memory System Overview

 Characteristics of Memory Systems

 The Memory Hierarchy

 Cache Memory
 Cache Memory Principles

 Elements of Cache Design

3
 4.1 INTRODUCTION
 Computer Memory
 exhibits the widest range of
 Type
 Technology
 Organization
 Performance
 Cost

 As a result a typical computer system 4

 Equipped with a hierarchy of memory subsystem

 4.2 COMPUTER MEMORY SYSTEM
OVERVIEW
 Characteristics of Memory Systems
 Classifying and studying memory systems using their
key characteristics
 Location

 Capacity

 Unit of transfer

 Access method

 Performance

 Physical type

 Physical characteristics

 Organisation

5
 CHARACTERISTICS OF MEMORY …
 Location
 Refers to whether memory is internal or external to
computer system
 Internal memory
 directly accessible by the processor
 Types of internal memory

 Main memory – often equated with internal memory

 Cache

 CPU registers

 Control memory

 External memory
 Accessible via the I/O module/controller
 Also called secondary memory

 Disks and tapes

6
 CHARACTERISTICS OF MEMORY …
 Capacity
 the amount of information that can be contained in a
memory unit
 For internal memory
 expressed in terms of bytes or words
 For external memory
 expressed in terms of bytes
 Terminologies
 Word
 natural unit of organization of memory
 Typical size

 instruction length

 Bits used to represent number

 Addressable unit
 Smallest location which can be uniquely addressed
 It could be

 A word
7

 Byte level
 CHARACTERISTICS OF MEMORY …
 Unit of Transfer
 For internal memory
 Usually governed by data bus width
 May be equal to a word
 Often larger : 64 ,128, or 256 bits

 For external memory

 Data transferred in much larger units than a word
 Usually a block which is much larger than a word
8
 CHARACTERISTICS OF MEMORY …
 Access Methods
 methods of accessing units of data
 different methods exist
 Sequential Access
 Start at the beginning and read through in order
 Access time depends on location of data and previous
location
 e.g. Tape drive units
 Direct Access
 Individual blocks have unique address
 Access is by jumping to vicinity plus sequential search
9
 Access time depends on location of data and previous
 CHARACTERISTICS OF MEMORY …
 Random Access
 individual addresses identify locations exactly
 Access time is independent of location or previous access
 e.g. RAM

 Associative Access
 Data is located by a comparison with contents of a
portion of the store
 access time is independent of location or previous
access
 e.g. Some cache memory units
10
 CHARACTERISTICS OF MEMORY …
 Performance
 Access time (latency)
 Time between presenting an address and getting
access to a valid data
 For Random Access Memory
 It is the time it takes to perform a read or write operation

 For Non Random Access Memory

 It is the time it takes to position the read –write mechanism at the
desired location

 Memory Cycle time

11
 applicable to RAM

 consists of access time + recovery time

 CHARACTERISTICS OF MEMORY …
 Transfer rate
 the rate at which data can be transferred into or out of a
memory unit

 For non-random access memory

 Tn --- average time to read or write N bits
 Tn = Ta + N/R

 Where
 Tn average time to read or write N bits
 Ta average access time
 N number of bits
12
 R transfer rate (bps)
CHARACTERISTICS OF MEMORY …

 Physical Types
 Semiconductor
 RAM

 Magnetic
 Disk & Tape

 Optical
 CD & DVD
13
 Magneto-optical
 CHARACTERISTICS OF MEMORY …
 Physical Characteristics
 Volatility
 Volatile memory
 Information is lost when electrical power is switched off
 Some semiconductor memories
 E.g RAM
 Non Volatile memory
 Information once recorded remains without deterioration
 Electrical power not needed to retain information
 E.g magnetic storage unit
 Non erasable memory
 cannot be altered
 ROM
14
CHARACTERISTICS OF MEMORY …

 Organisation
 Memory Modules
 Physical arrangement of bits to form words
 Not always obvious

15
 MEMORY HIERARCHY

Memory hierarchy
diagram 16
 MEMORY HIERARCHY...
 Memory hierarchy characteristics, going down the
diagram
 Decreasing cost per bit
 Increasing capacity
 Increasing access time
 Decreasing frequency of access of the memory by the
processor
• Fasteraccess time, greater cost per bit
• Greater capacity, smaller cost per bit 17
• Greater capacity, slower access time
 MEMORY HIERARCHY...

 Hierarchy List
 Registers L1 CacheL2 Cache  Main
memory Disk Optical Tape
 Locality of Reference Principle
 during the course of the execution of a program,
memory references by the processor tend to cluster
 e.g. Loops, tables and arrays

18
4.3 CACHE MEMORY
PRINCIPLES

19
 4.3 CACHE MEMORY
PRINCIPLES
 Cache memory
 Small amount of fast memory
 Sits between main memory and CPU
 May be located on CPU chip or module
 Contains copies of sections of main memory

20
 CACHE MEMORY PRINCIPLES...
 Cache operation – overview
 CPU requests contents of memory location
 Cache checked for this data
 If present, get from cache (fast)
 If not present, read required block from main
memory to cache
 Then deliver from cache to CPU
 Cache includes tags to identify which block of main memory
is in each cache slot
21
 CACHE MEMORY PRINCIPLES...
 Typical Cache Organization

22
 CACHE MEMORY PRINCIPLES...
 Cache/Main Memory Structure

23
CACHE READ OPERATION - FLOWCHART

24
 ELEMENTS OF CACHE DESIGN
 Basic elements used to classify cache design architectures:
# Size
# Mapping Function
# Replacement Algorithm
# Write Policy
# Line/Block Size
# Number of Caches
# Unified and Split

25
ELEMENTS OF CACHE DESIGN...

 Cache Size
 Small enough ---not to be costly or expensive
 Large enough so overall average access time is small
 Affected by the available chip and board area

26
 ELEMENTS OF CACHE DESIGN...
 Mapping Function
 No of cache lines <<< No of blocks in main memory
 Mapping function needed
 A method to map main memory blocks into cache lines
 Three mapping techniques used
 Direct
 Associative
 Set Associative
 Typical memory-cache organization
 Cache of 64 kBytes
 Organized as 16k lines of 4 bytes
 Cache block of 4 bytes
 16 MBytes main memory
 Byte addressable memory
27
 24 bit address
 (224=16M)
 ELEMENTS OF CACHE DESIGN
DIRECT MAPPING...
 Each block of main memory maps to only one cache
line
 i=j modulo m
 i=cache line number,
 j=main memory block number
 m=number of lines in the cache

 i.e. if a block is in cache, it must be in one specific place

 Mapping function implemented using main memory

address 28
 ELEMENTS OF CACHE DESIGN
DIRECT MAPPING...
 Address viewed as having three fields
 Word, line and tag identifier

 Least Significant w bits identify unique word in a

block
 Most Significant s bits specify one of 2s memory block
 The MSBs are split into
 a tag of s-r bits (most significant)
 Stored in the cache along with the data words of the line
 a cache line field of r bits
29
 Identifies one of m=2r lines of the cache
 ELEMENTS OF CACHE DESIGN
DIRECT MAPPING...
 Address Structure
Tag s-r Line or Slot r Word w
8 14 2

 24 bit address
 2 bit word identifier (4 byte block)
 22 bit block identifier
 8 bit tag (=22-14)
 14 bit slot or line
 No two blocks in the same line have the same Tag field
30
 ELEMENTS OF CACHE DESIGN
DIRECT MAPPING...
 Direct Mapping Cache Organization

31
 ELEMENTS OF CACHE DESIGN
DIRECT MAPPING...
 Direct Mapping Summary
 Address length = (s + w) bits
 Number of addressable units = 2(s+w) words / bytes
 Block size = line size = 2w words or bytes
 Number of blocks in main memory = 2(s+ w)/2w = 2s
 Number of lines in cache = m = 2r
 Size of tag = (s – r) bits

32
 ELEMENTS OF CACHE DESIGN
DIRECT MAPPING...
 Direct Mapping Advantage and Disadvantage
 Advantage
 Easy to implement
 Inexpensive to implement
 Easy to determine the right cache line
 Disadvantage
 Fixed location for given block
 If a program accesses 2 blocks that map to the same
line repeatedly, cache misses are very high 33
 ELEMENTS OF CACHE DESIGN
ASSOCIATIVE MAPPING

 Associative Mapping
 A main memory block can loaded into any line of
cache
 Memory address is interpreted as tag and word
 Tag field uniquely identifies a block of memory
 Every cache line’s tag is examined for a match
simultaneously

34
 ELEMENTS OF CACHE DESIGN
ASSOCIATIVE MAPPING...
 Associative Cache Organization

35
 ELEMENTS OF CACHE DESIGN
ASSOCIATIVE MAPPING...
 Address Structure

Wor
Tag 22 bit
d 2
bit
 22 bit tag stored with each 32 bit block of data
 Compare tag field with tag entry in cache to check for hit
 Least significant 2 bits of address identify which 8 bit word
is required from 32 bit data block

36
 ELEMENTS OF CACHE DESIGN
ASSOCIATIVE MAPPING...
 Associative Mapping Summary
 Address length = (s + w) bits
 Number of addressable units = 2(s+w) words / bytes
 Block size = line size = 2w words or bytes
 Number of blocks in main memory = 2(s+ w)/2w = 2s
 Number of lines in cache = undetermined
 Size of tag = s bits

The principal disadvantage of associative mapping is the complex 37

circuitry required to examine the tags of all cache lines in parallel.

 ELEMENTS OF CACHE DESIGN
SET ASSOCIATIVE MAPPING
 Set Associative Mapping
 Compromise between direct and associative
 Cache is divided into a number of sets
 v sets
 Each set contains a number of lines
 k lines
 The following relationship holds:
 M=v*k
 i= j modulo v

 i=cache set number, j=main memory block number and

M=number of lines in the cache
 A given block maps to any line in a given set
 e.g. Block B can be in any line of set i
 Assume that k=2 --- 2 lines per set
 2 way associative mapping
37
 A given block can be in one of 2 lines in only one set
 ELEMENTS OF CACHE DESIGN
SET ASSOCIATIVE MAPPING...
 Set Associative Mapping
 memory address viewed as three fields
 Tag, set and word fields

 Use set field (d bits) to determine cache set to look in

 Compare tag field (s-d MSB bits) to see if we have a
hit
 Address Structure
Wor
Tag 9 Set 13 bit d
2 bit
bit
 For 24 bit address
39
 ELEMENTS OF CACHE DESIGN
SET ASSOCIATIVE MAPPING...
 K-Way Set Associative Cache Organization

40
 ELEMENTS OF CACHE DESIGN
SET ASSOCIATIVE MAPPING...
 Set Associative Mapping Summary
 Address length = (s + w) bits
 Number of addressable units = 2s+w words / bytes
 Block size = line size = 2w words or bytes
 Number of blocks in main memory = 2s
 Number of lines in set = k
 Number of sets = v = 2d
 Number of lines in cache = kv = k * 2d
 Size of tag = (s – d) bits 41
 ELEMENTS OF CACHE DESIGN...
REPLACEMENT ALGORITHMS
 Replacement Algorithms
 determine which existing block should be replaced when a
new block is brought into the cache
 There are a number of algorithms
 LRU, FIFO, LFU…

 Direct mapping
 No choice, no algorithm needed
 Each block only maps to one line
 Replace that line 42
 ELEMENTS OF CACHE DESIGN
REPLACEMENT ALGORITHMS...
 Least Recently used (LRU)
 Most effective
 Replaces a block not used recently
 For a 2 way set associative
 Which of the 2 blocks
 Each line includes a USE bit

 First in first out (FIFO)

 replace a block that has been in cache longest
 Least frequently used
 replace block which has had fewest hits
 counter associated with each cache line
 Random
42
 pick a line at random
 ELEMENTS OF CACHE DESIGN...
WRITE POLICY
 Write Policy
 Update original copy of a line in main memory before it is
overwritten
 If some word changed

 different write polices exist

 Write policy complex
 If multiple CPUs each with its own cache exist
 If I/O devices addresses main memory directly
44
 ELEMENTS OF CACHE DESIGN
WRITE POLICY...
 Write through
 All writes go to main memory as well as cache
 Both copies always agree
 Lots of traffic
 Multiple CPUs can monitor main memory traffic to keep
local cache up to date
 Write back
 Updates initially made in cache only
 Update bit for cache slot is set when update occurs
 If block is to be replaced, write to main memory only if update bit
is set
45
 Other caches get out of sync
 I/O must access main memory through cache
 ELEMENTS OF CACHE DESIGN...
LINE SIZE

 Line Size
 Howmuch data should be transferred from main
memory to the cache in a single memory reference
 Complex relationship between
 Block size
 Hit ratio

46
 ELEMENTS OF CACHE DESIGN...
NUMBER , UNIFIED AND SPLIT
 Number of Caches
 Single versus 2 level
 L1 provides best performance gains
 L2 off-chip cache
 L3 cache

 Unified versus Split

 Unified cache
 Stores data and instruction in one cache

 Split cache 47

 Uses 2 caches
 CACHE MEMORY
EXAMPLE
 Pentium 4 Cache
 80386 – no on chip cache

 80486 – 8k using 16 byte lines and four way set

associative organization
 Pentium (all versions) – two on chip L1 caches
 Data & instructions
 Pentium III – L3 cache added off chip
 Pentium 4
 L1 caches
 8k bytes
 64 byte lines

 four way set associative

 L2 cache
 Feeding both L1 caches
 256k
47
 128 byte lines

 8 way set associative

 L3 cache on chip
 4.4 SEMICONDUCTOR MAIN MEMORY
ORGANIZATION
 Organization
 Basic element of a semiconductor memory
 A memory cell

 All memory cells share certain properties

 Exhibit two stable states --- used to represent binary 1/0
 Capable of being written into --- set the state
 Capable of being read from --- sense the state

49
 SEMICONDUCTOR MAIN MEMORY
ORGANIZATION…

 Operation of a memory cell

 The cell has three functional terminals
 Select terminal
 Selects a memory cell for a read or write operation

 Control terminal

 Indicates read or write operation

50
 SEMICONDUCTOR MAIN MEMORY
ORGANIZATION…
 Operation of a memory cell
 For writing
 the third terminal provides an electrical signal that
sets the state of the cell to 1 or 0
 For reading
 The third terminal is used to output the cell’s state

51
 SEMICONDUCTOR MEMORY TYPES

 Table above lists different types of semiconductor Memories

The most common memory is referred to as RAM 51
 SEMICONDUCTOR MEMORY TYPES...
RAM

 RAM
 Misnamed as all semiconductor memory is random
access
 What should be its name?
 Possible to Read/Write
 Volatile
 Can be used only as a temporary storage

 Two types of technologies can be used to built

53
RAM
 Static RAM (SRAM)
 SEMICONDUCTOR MEMORY TYPES
RAM...

 Dynamic RAM (DRAM)

 Bits stored as charge in capacitors
 Charges leak
 Need refreshing even when powered
 Need refresh circuits

 Simpler construction and Smaller per bit (dense)

 Less expensive
 Slower 54

 Used for main memory

 SEMICONDUCTOR MEMORY TYPES
RAM...
 Dynamic RAM Structure

55
 SEMICONDUCTOR MEMORY TYPES
RAM...
 DRAM Operation
 Address line active when bit read or written
 Transistor switch closed (current flows)
 Write
 Voltage to bit line
 High for 1, low for 0
 Then signal address line
 Transfers charge to capacitor
 Read
 Address line selected
 transistor turns on
 Charge from capacitor fed via bit line to sense amplifier
Compares with reference value to determine 0 or 1


 Capacitor charge must be restored

55
SEMICONDUCTOR MEMORY TYPES
RAM...
 Static RAM
 Bits stored using flip flops, on/off switches
 No charges to leak
 No refreshing needed when powered
 More complex construction
 Larger per bit
 More expensive
 Faster
57
 Used for cache memory
SEMICONDUCTOR MEMORY TYPES
RAM...
 Static RAM Structure

58
 SEMICONDUCTOR MEMORY TYPES
RAM...
 Static RAM Operation
 Transistor arrangement gives stable logic state
 State 1
 C1 high, C2 low
 T1 T4 off, T2 T3 on

 State 0
 C2 high, C1 low
 T2 T3 off, T1 T4 on

 Address line transistors T5 & T6 is switch

59
 Write – apply value to B & compliment to B
 Read – value is on line B
SEMICONDUCTOR MEMORY TYPES
RAM...
 SRAM v DRAM
 Both volatile
 Power needed to preserve data
 Dynamic cell
 Simpler to build, smaller
 More dense

 Less expensive

 Needs refresh

 Static
 Faster
 Cache

60
 SEMICONDUCTOR MEMORY TYPES...
TYPES OF ROM

 Read Only Memory (ROM)

 Contains a permanent pattern of data that can not be
Changed
 Nonvolatile
 Read but cannot write
 Used for
 Microprogramming, Library subroutines – for frequently used
functions, system programs (BIOS), function tables
 Written during fabrication 61
 SEMICONDUCTOR MEMORY TYPES
TYPES OF ROM…
 Programmable ROM (PROM)
 Programmed only once
 Special equipment required for programming
 Read “mostly” memory
 Erasable Programmable (EPROM)
 Cells erased by using UV radiation before programming

 Electrically Erasable (EEPROM)

 Cells don’t need to be erased before programming
 Cells programmed in place without special equipment

 Flash memory 61
 Can erase selected block rather than the entire memory

 SEMICONDUCTOR MEMORY TYPES…
ERROR CORRECTION
 Errors in semiconductor memory categorized as
 Hard Failure
 Permanent physical defect

 Soft Error
 Random, non-destructive
 No permanent damage to memory
 Caused by power supply problems

 Detected using Hamming error correcting code

63
SEMICONDUCTOR MEMORY TYPES
ERROR CORRECTION…
 Error Correcting Code Function

64
End
of P
a rt
1

65