BCSE205L

Computer Architecture and Organization

Module 4 – Memory System Organization
and Architecture
Memory Unit
• Memory unit is essential component of digital
computer since it is needed for storing programs
and data.
• Memory unit that communicates directly with
CPU is called Main memory.
• Only programs and data currently needed by processor
reside in the main
memory
• Devices that provide backup storage is called
Auxiliary (Secondary) Memory
• All other information is stored in auxiliary memory
and transferred to main memory when needed.
• The binary information may be instructions
and data
Memory Capacity
• Number of bytes that can be stored
Memory Hierarchy
Memory Characteristics
• Location • Performance
– CPU –Access time
– Internal (main) –Cycle time
– External (secondary) –Transfer rate
• Capacity
• Physical Type
– Word size (in Bytes)
– Semiconductor
– Number of words (Blocks)
• Unit of transfer
– Magnetic surface
– Word – Optical
– Block • Physical Characteristics
• Access methods – Volatile / Non-Volatile
– Sequential access – Erasable / Non-erasable
– Direct access
– Random access
– Associative access
Memory Characteristics
1.Location of memories
• CPU
• Registers – used by CPU as its local memory
• Internal memory
• Main memory
• Cache memory
• External memory
• Peripheral devices – disk, tape – accessible to CPU
via I/O controllers
Memory Characteristics
2. Capacity & 3. Unit of Transfer
• Word (Internal Memory)
The capacity of the internal memory is typically expressed in terms of
bytes or words
• Word length
For the internal memory, the unit of transfer is equal to the number of
data lines into and out of the main memory module (word Length). The
common word lengths are 8,16 and 32 bits.
Total memory = number of words × word length
• Block (External Memory)
External memory capacity is expressed in terms of blocks. For
external memory, the data often transferred in much longer units than a word,
and these are referred to as Blocks.
Memory Characteristics
3. Access Methods
Sequential Access
• Accesses the memory in predetermined sequence
• Shared read/write head is used, and this must be moved its
current location to the desired location, passing and
rejecting each intermediate record.
• Memory is organized into units of data, called Records.
Access must be made in a specific linear sequence
• The time to access data in this type of method depends on
the location of the data. So, the time to access an arbitrary
record is highly variable
• Ex: Magnetic Tapes, data in memory array
• Slower than random access memory
Memory Characteristics
3. Access Methods
Random access
• In random access method, data from any location of the
memory can be accessed randomly.
• The access to any location is not related with its physical
location and is independent of other locations.
• There is a separate access mechanism for each location.
• Main memory systems are a random access
• Storage locations can be accessed in any order
• Example of random access: Semiconductor memories like
RAM, ROM use random access method.
Memory Characteristics
3. Access Methods
Direct access Random Access
• Direct access method can be seen as combination of
sequential access method and random access method. It is
also referred as semi random access memory
• Magnetic hard disks contain many rotating storage tracks.
• Here each tracks has its own read or write head and the
tracks can be accessed randomly. But access within each
track is sequential.
• Access is accomplished by general access to reach a
Sequential
general vicinity plus sequential searching, counting, access
waiting to reach the final location.
• Example of direct access: Memory devices such as
magnetic hard disks.
Memory Characteristics
3. Access Methods
Associate Access
• Word is retrieved based on portion of its contents rather
than its address
• This enables one to make a comparison of desired bit
locations within a word for specific match
• Has own addressing mechanism
• Retrieval time is constant
• Access time is independent of location or prior access
patterns
• Example: Cache memories
Memory Characteristics
4. Performance
Access time
• The time required to read / write the data from / into desired record
• Depends on the amount of data to be read / write
• If the amount data is uniform for all records then the access time is same for all records.
• Time from the instant that an address is presented to the memory to the instant that data have been
stored or made available for use.
Memory Cycle time
• Access time + time required before a second access can commence
• For Random access method ,this memory cycle time is same for all records
• The sequential access and direct access ,the memory cycle time is different
Transfer rate / Throughput
• Rate at which the data can be transferred into or out of a memory unit
• Random access memory: 1/cycle time
• Non-Random access memory
Tn = Ta + (N/R), where
Tn– average time to read or write N bits
Ta – average access time
N – Number of bits
R – Transfer rate in bits per second (BPS)
Memory Characteristics
Memory Performance Parameters
Memory Characteristics
5. Physical type
Semiconductor
• Semiconductor memory uses semiconductor-
based integrated circuits to store information.
Magnetic surface
• Magnetic storage uses different patterns
of magnetization on a magnetically coated surface to store
information.
• Example: Magnetic disk, Floppy disk, Hard disk drive
Optical
• The typical optical disc, stores information in deformities
on the surface of a circular disc and reads this information
by illuminating the surface with a laser diode and
observing the reflection.
Memory
6. Physical characteristics
Characteristics
Erasable/non erasable
• Erasable memory
• Erase the stored information by writing new information
• Ex: Magnetic storage is erasable
• Non-erasable memory
• Cannot be altered, except by destroying the storage unit (ROM)
• A practical non-erasable memory must also be non-volatile
• Ex: CD-R, Flash Memories
Volatile/non volatile
• Volatile
• Volatile Memory Requires constant power to maintain the stored information.
• Information decays naturally or lost when electrical power is switched off
• A type of volatile semiconductor memory is random access memory
• Non-Volatile
• Once recorded is retained until deliberately changed
• No electrical power is needed to retain information
• Magnetic storage is non-volatile.
• A type of non-volatile semiconductor memory known as flash memory
Memory Organization
• Physical arrangement of bits to form words

• 2 types
• 1 dimensional
• 2 dimensional

• Basic element = memory cell

• Properties of Memory cell:

- They exhibit two stable states, which can be used to represent binary 1 and 0.

- They are capable of being written into (at least once) to set the state.

- They are capable of being read to sense the state.

Memory Organization
1 – dimensional organization
Memory Organization
2 – dimensional organization
Byte Storage Methods
• Two ways to store a string of data (Bytes) in computers:
• Big Endian
• Little Endian

• Least Significant Byte (LSB) is the right-most bit in a string - because it has the least
effect on the value of the binary number.
• Most Significant Byte (MSB) - the left-most byte that carries the greatest numerical
value.

• In Big Endian, the MSB of the data is placed at the byte with the lowest address. (First
byte stored in the memory first)

• In Little Endian, the LSB of the data is placed at the byte with the lowest address. (Last
byte stored in the memory first)
Byte Storage Methods
• In Big Endian, the MSB of the data is placed at the byte with the lowest address. (First
byte stored in the memory first)

• In Little Endian, the LSB of the data is placed at the byte with the lowest address. (Last
byte stored in the memory first)
Byte Storage Methods
• Big Endian - the most common format in data networking (TCP, UPD, IPv4 and IPv6 are using
Big endian order to transmit data)

• Little Endian - on microprocessors

Byte Storage Methods
• Big-Endian
• Assigns MSB to least address and LSB to highest address
• Ex: 0 × DEADBEEF

Memory Location Value

Base Address + 0 DE
Base Address + 1 AD
Base Address + 2 BE
Base Address + 3 EF
Byte Storage Methods
• Little Endian
• Assigns MSB to highest address and LSB to least address
• Ex: 0 × DEADBEEF

Memory Location Value

Base Address + 0 EF
Base Address + 1 BE
Base Address + 2 AD
Base Address + 3 DE
Byte Storage Methods
• Little Endian
• Intel × 86 family
• Digital equipment corporation architectures (PDP – 11, VAX, Alpha)
• Big Endian
• Sun SPARC
• IBM 360 / 370
• Motorola 68000
• Motorola 88000
• Bi-Endian (The ability to switch between big endian and little endian ordering.)
• Power PC
• MIPS
• Intel’s 64 IA - 64
Conceptual View of Memory Design
• Revisiting Logic Gates
Conceptual View of Memory Design
A Single
RAM
Memory Cell
Conceptual View of Memory Design
Conceptual View of Memory Design
2-4 Decoder Circuit
Conceptual View of Memory Design

A typical chip Layout

Memory Interleaving
Main Memory Structure:
• If the Main Memory is structured as collection of physically separate
modules - each with it’s own Address Buffer Register (ABR) and Data
Buffer Register (DBR), memory access operations….
• It may proceed in more than one module at the same time.
• Hence, aggregate rate of transmission of words to and from the memory
can be increased.
Memory Interleaving
Interleaving:
• Memory Interleaving is an abstraction technique.
• Designed to compensate for core memory by spreading memory addresses
evenly across memory banks.
• Divides memory into a number of modules
such that successive words in the address
space are placed in the different module.
• To implement interleaved structure,
there must be 2k modules.
(k=lower order k bits)
Memory Interleaving
Distribution Methods in
Memory system
• Consecutive words in a
module
• When consecutive locations are
accessed, as happens when a
block of data is transferred to a
cache, only one module is
involved.
Memory Interleaving
Distribution Methods in Memory
system
• Consecutive words in a Consecutive
module
• This method is called memory
interleaving
• Parallel access is possible. Hence, faster
• Higher average utilization of the memory
system
Memory Interleaving
Usage of Memory Interleaving:
• Main memory is relatively slower than the cache.
• So to improve the access time of the main memory, interleaving is
used.
• This method uses memory effectively.
Classification of Memory Interleaving: (Two address formats for
Memory Interleaving)
• High Order Interleaving
• Low Order Interleaving
Memory Interleaving
High Order Interleaving:
• In high-order interleaving, the most significant bits of the address
select the memory chip.
• The least significant bits are sent as addresses to each chip.
• The maximum rate of data transfer is limited by the memory cycle
time.
Memory Interleaving
Low Order Interleaving:
• In low-order interleaving, the least significant bits select the memory
bank (module).
• In this, consecutive memory addresses are in different memory
modules.
• This allows memory access at much faster rates than allowed by the
cycle time.
Memory Interleaving
Benefits of Memory Interleaving
• It allows simultaneous access to different modules of memory.
• Interleave memory is useful in the system with pipelining and vector
processing.
• In an interleaved memory, consecutive memory addresses are spread
across different memory modules.
• Reduce the memory access time by a factor close
to the number of memory banks.
Memory Interleaving
Interleaving DRAM
• Main memory is usually composed of a
collection of DRAM (Dynamic random-
access memory) memory chips grouped
together to form a memory bank.
• The memory banks will be interleaved.
• Memory accesses to different banks can
proceed in parallel with high throughput.
• Memory banks can be allocated a
contiguous block of memory addresses,
gives an equal performance and access
gives far better performance in interleaved
layouts.
Design of scalable memory using RAM’s

Memory -
Block Diagram
Design of scalable memory using RAM’s
RAM Chips
Design of scalable memory using RAM’s
• The logic 1 and 0 are normal digital signals.
RAM Chips • High impedance state behaves like an open circuit, which means
that the output does not carry a signal and has no logic
significance.
• The unit is in operation only when CS1 = 1 and CS2 = 0. The bar on
top of the second select variable indicates that this input is enabled
when it is equal to 0.
• If the chip select inputs are not enabled, or if they are enabled but
the read or write inputs are not enabled, the memory is inhibited
(temporarily inaccessible) and its data bus is in a high-impedance
state (the output of a buffer is disconnected from the output bus).
• When CS1 = 1 and CS2 = 0, the memory can be placed in a write or
read mode.
• When the WR input is enabled, the memory stores a byte from the
data bus into a location specified by the address input lines.
• When the RD input is enabled, the content of the selected byte is
placed into the data bus. The RD and WR signals control the
memory operation as well as the bus buffers associated with the
bidirectional data bus .
Read Only Memory (ROM)
ROM Types
Read Only Memory (ROM)
• A ROM chip is organized externally in a similar manner.
ROM Chips However, since a ROM can only read, the data bus can only
be in an output mode
• For the same-size chip, it is possible to have more bits of
ROM than of RAM, because the internal binary cells in ROM
occupy less space than in RAM.
• For this reason, the diagram specifies a 512-byte ROM, while
the RAM has only 128 bytes.
• The nine address lines in the ROM chip specify any one of
the 512 bytes stored in it.
• The two chip select inputs must be CS1 = 1 and CS2 = 0 for
the unit to operate. Otherwise, the data bus is in a high-
• No R/W signal – Default Read only. impedance state.
• Data Bus - unidirectional • There is no need for a read or write control because the unit
can only read. Thus when the chip is enabled by the two
select inputs, the byte selected by the address lines appears
on the data bus.
Construction of Larger Size memory
• Mix of RAM and ROM
• Decoder Circuit
• Address Lines
• Data Lines
• SELECT signal
Memory Connection to CPU

Address Lines – specifies the No. Rows

Data Lines – Specifies the No. of Columns
Memory Design - Memory Interface
Address Map
• The designer of a computer system must calculate the amount of memory required for the particular
application and assign it to either RAM or ROM.
• The interconnection between memory and processor is then established from knowledge of the size of
memory needed and the type of RAM and ROM chips available.
• The addressing of memory can be established by means of a table that specifies the memory address
assigned to each chip.
• The table, called a memory address map, is a pictorial representation of assigned address space for each
chip in the system.

To demonstrate with a particular example,

assume that a computer system needs 512
bytes of RAM and 512 bytes of ROM.
The memory address map for this
configuration is shown in Table 1.
Memory Design - Memory Interface
Address Map
• The component column specifies whether a RAM or a ROM chip is used. The hexadecimal address column
assigns a range of hexadecimal equivalent addresses for each chip.
• The address bus lines are listed in the third column. Although there are 16 lines in the address bus, the table
shows only 10 lines because the other 6 are not used in this example and are assumed to be zero.
• The small x's under the address bus lines designate those lines that must be connected to the address inputs
in each chip. The RAM chips have 128 bytes and need seven address lines.
• The ROM chip has 512 bytes and needs 9 address lines. The x's are always assigned to the low-order bus
lines: lines 1 through 7 for the RAM and lines 1 through 9 for the ROM.
Memory Design - Memory Interface
Address Map
• It is now necessary to distinguish between four RAM chips by assigning to each a different address. For this particular
example we choose bus lines 8 and 9 to represent four distinct binary combinations.
• Note that any other pair of unused bus lines can be chosen for this purpose. The table clearly shows that the nine low-
order bus lines constitute a memory space for RAM equal to 29 = 512 bytes.
• The distinction between a RAM and ROM address is done with another bus line. Here we choose line 10 for this
purpose. When line 10 is 0, the CPU selects a RAM, and when this line is equal to 1, it selects the ROM.
• The equivalent hexadecimal address for each chip is obtained from the information under the address bus assignment.
The address bus lines are subdivided into groups of four bits each so that each group can be represented with a
hexadecimal digit.
• The first hexadecimal digit represents lines 13 to 16 and is always 0. The next hexadecimal digit represents lines 9 to 12,
but lines 11 and 12 are always 0.
• The range of hexadecimal addresses for each component is determined from the x's associated with it. These x's
represent a binary number that can range from an all-0's to an all-1's value.
Memory Design - Memory Interface
Address Map

Address Calculation
(From – To)
-calculated from 16 bit address Bus line 10 select RAM or ROM
- Hexadecimal format Bus lines 8 and 9 are used to
No. of Address line bits (x) is given by N=2x select one RAM out of 4 RAMs
No. of data bus = No. of columns (Word size)
Assumptions
RAM size: 128 * 8 ----- 7 bit address bits needed, No. of Data Lines --- 8
ROM size: 512 * 8 ------ 9 bit address bits required, No. of Data Lines --- 8
Memory Design - Memory Interface
Address Map

Address Calculation
(From Address) v v v v
-calculated from 16 bit address
- Hexadecimal formatSubstitute x=0 to get ‘From’ address X=0

If x=0 ‘From’ address is 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

Convert to hexadecimal value 0 2 0 0

So, from address for ROM 1 is 0200
Memory Design - Memory Interface
Address Map

Address Calculation
(To Address) v v v v
-calculated from 16 bit address
- Hexadecimal formatSubstitute x=1 to get ‘To’ address X=1

If x=1  ‘To’ address is 0000 0 0 1 1 1 1 1 1 1 1 1 1

Convert to hexadecimal value 0 3 F F

So, To address for ROM 1 is 03FF

Memory Design - Memory Interface
Address Map
• Considerations:
N – Number of Words in the chip available (Rows)
N’– Required Number of Words in the chip required
W – Width/size of a word in the chip available (Columns)
W’ – Required Width/size of a word in the chip required
Memory Design - Memory Interface
Address Map
• Hence,
• Available Memory chip Size: N × W (N – represents ROWS – No. of words) (W
– represents COLUMNS – word size)
• Required Memory chip size: N’ × W’,
where N’≥ N and W’≥ W (Required>Available)
• Required number of chips = p × q
where p = N’ / N (No. of rows reqd. )
and q = W’/ W (no. of Cols reqd.)
Address bits - required to map to the row
• Decoder used
No. of Address line bits (x) is given by
N=2x
No. of data bus = No. of columns (Word size)
Memory design - Memory Interface
Address Map
There are 3 types of organizations of N’ × W’ that can be formed using N
×W
• N’ > N and W’ = W => increasing the number of words (Rows - N) in
the memory
• N’ = N and W’ > W => increasing the word size) (Columns – W) of
the chip
• N’ > N and W’ > W => increasing both N & W (Rows & Columns)
the number of words and number of bits in each word.
There are different types of organization of N1 x W 1 –memory using N x W –bit
chips

How many 1024x 8 RAM chips are needed to provide a memory capacity of 2048 x 8?

Case 1: If NI > N & W I = W

NI
Increase number of words by the factor of p =
N
How many 1024x 4 RAM chips are needed to provide a memory capacity of 1024 x 8?

Case 2: If NI = N & W I > W

I
Increase the word size of a Memory by a factor of q = W
W

How many 1024x 4 RAM chips are needed to provide a memory capacity of 2048 x 8?

Case 3: If NI > N & W I > W

Increase number of words by the factor of p &
Increase the word size of a Memory by a factor of q
Memory Design - Memory Interface Address Map
Problem – 1 (CASE 2) – Increasing the word size (Columns)
• Design 128 × 16 (N’ × W’)- bit RAM using 128 × 4(N × W) - bit RAM
• Solution: p = 128 / 128 = 1;
q = 16 / 4 = 4
• Therefore, No. of chips required is calculated by,
p × q = 1 × 4 =4 (i.e. 4 memory chips of size 128 × 4 are required to construct 128 × 16 bit RAM)
x – Number of bits required Y- Number of bits required for Selecting
to represent the address the specific RAM. (p = 2y)
lines 128 x 4= 27 x 4 (by N=2x) 1= 20
x=7 bit address is required y=0 (since only one RAM)
Z – Number of bits to select the RAM or ROM or Interface…
No. of Types (T) = 1 X=7,Y=0,Z=0
Z=0 ((by T=2Z)
Memory Design - Memory Interface Address Map
Component Hexadecimal address Address Bus
From To 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

RAM 1.1 0000 007F x x x x x x x

RAM 1.2 0000 007F x x x x x x x

RAM 1.3 0000 007F x x x x x x x

RAM 1.4 0000 007F x x x x x x x

Z – Number of bits to select the RAM or ROM or Interface…

Z=0 address line 9 is empty

Y- Number of bits required for Selecting the specific RAM

Y=0 Only one RAM so address lines 7 and 8 are empty
X=7 7 bit address lines(from 0 to 6)
Memory Design - Memory Interface Address Map
Component Hexadecimal address Address Bus
From To 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

RAM 1.1 0000 007F x x x x x x x

RAM 1.2 0000 007F x x x x x x x

RAM 1.3 0000 007F x x x x x x x

RAM 1.4 0000 007F v v xv x x x x v x x

Substitute x=0 to get ‘From’ address X=0

If x=0 ‘From’ address is 0000 0 0 0 0 0 0 0 0 0 0 0 0

Convert to hexadecimal value 0 0 0 0

So, from address of RAM is 0000
Memory Design - Memory Interface Address Map
Component Hexadecimal address Address Bus
From To 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

RAM 1.1 0000 007F x x x x x x x

RAM 1.2 0000 007F x x x x x x x

RAM 1.3 0000 007F x x x x x x x

RAM 1.4 0000 007F v v x vx x x x v x x

Substitute x=1 to get ‘to’ address X=1

If x=1 ‘to’ address is 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1

Convert to hexadecimal value 0 0 7 F

So, to address of RAM is 007F
Memory Design - Memory Interface Address Map
Memory design – Increasing the word size
Design 128 × 16 (N’ × W’)- bit RAM using 128 × 4 (N × W) - bit RAM
Data Bus
16

4 4 4 4
Data (0-3) Data (0-3) Data (0-3) Data (0-3)

Address (0-6) Address (0-6) Address (0-6) Address (0-6)

128 × 4 128 × 4 128 × 4 128 × 4

RAM RAM RAM RAM

Address CS R/W CS R/W CS R/W CS R/W

Bus
7
Chip Select

Read/write Control

Since W is increased ---- the 4 chips should be arranged horizontally.

Memory Design - Memory Interface Address Map
Address Bus
Data r/w
6-0
16
7

128 x 4 128 x 4 128 x 4 128 x 4

RAM RAM RAM RAM

4 4 4 4
1
Memory Design - Memory Interface Address Map
Problem – 2 (CASE 1) – Increasing the number of words (Rows)
Design 1024 × 8 - bit RAM using 256 × 8 - bit RAM

Solution: p = 1024 / 256 = 4; q = 8 / 8 = 1

p × q = 4 × 1 = 4  4 memory chips of size 256 × 8 are required to
construct 1024 × 8 bit RAM
x – Number of bits required to Y- Number of bits for Z – Number of 0
represent the address lines Selecting the specific RAM. (select the RAM or
256 x 8= 28 x 4 (p = 2y) (p=422y ) y=2 ROM)
x=8 bit address is required

S.NO Memory NxW N1 x W1 P q p*q x y z Total

1024 ×
1 RAM 256 × 8 4 1 4 8 2 0 10
8
2
3
4
Memory Design - Memory Interface Address Map

X=8 8 bit address lines(from 0 to 7)

Y=2 address lines 8 and 9 will select one RAM among 4 RAM

Z=0 address line 10 is empty

Memory Design - Memory Interface Address Map

v v v v

Substitute x=0 to get ‘From’ address X=0

If x=0 ‘From’ address is 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0

Convert to hexadecimal value 0 3 0 0

So, from address of RAM is 0300

Memory Design - Memory Interface Address Map

v v v v

Substitute x=1 to get ‘To’ address X=1

If x=1 ‘To’ address is 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1

Convert to hexadecimal value 0 3 F F

So, from address of RAM is 03FF

Memory Design - Memory Interface Address Map
Data
8 Address Bus 256 × 8 Bus
Address Bus 8 RAM 8
A0 – A7 R/W
CS

Data
Address Bus 256 × 8 Bus
0 8 RAM 8
1
A8 CS R/W
2×4 2
A9 decoder
Data
3 Address Bus 256 × 8 Bus
8 RAM 8
CS R/W

Data
Address Bus 256 × 8 Bus
8 RAM 8
CS R/W
8 R/W
Data
Bus
Memory Design - Memory Interface Address Map
Data
8 Address Bus 256 × 8 Bus
Address Bus 8 RAM 8
A9 A8 A0 – A7 R/W
CS

Data
Address Bus 256 × 8 Bus
8 RAM 8
CS R/W

Data
Address Bus 256 × 8 Bus
8 RAM 8
CS R/W

Data
Address Bus 256 × 8 Bus
8 RAM 8
CS R/W
8 R/W
Data
Bus
256 × 8
Data
987-0 RAM 1 r/w

8
8

256 × 8
RAM 2

8
2×4
Decoder
256 × 8
3 2 1 0 RAM 3

256 × 8
RAM 4

8
Memory Design - Memory Interface Address Map
Problem – 3 (CASE 3) – Increasing the Words & Word size (Rows & Columns)
Design 256 × 16 – bit RAM using 128 × 8 – bit RAM chips

Solution: p = 256 / 128 = 2; q = 16 / 8 = 2

p×q=2× 2=4 4 chips are required, 2chips rows, 2chips columns

x – Number of bits required to Y- Number of bits for Z – Number of 0

represent the address lines Selecting the specific RAM. (select the RAM or
128 x 4= 27 x 4 (p = 2y) (p=221y ) y=1 ROM)
x=7 bit address is required

S.NO Memory NxW N1 x W1 P q p*q x y z Total

1 RAM 128 × 8 256 × 16 2 2 4 7 1 0 8

4
Memory Design - Memory Interface Address Map

v v v v

Substitute x=0 to get ‘From’ address X=0

If x=0 ‘From’ address is 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

Convert to hexadecimal value 0 0 8 0

So, from address of RAM is 0080

Memory Design - Memory Interface Address Map

v v v v

Substitute x=1 to get ‘To’ address X=1

If x=1 ‘To’ address is 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Convert to hexadecimal value 0 0 F F

So, from address of RAM is 00FF

Data
76-0 r/w

Address Bus
128 × 8 128 × 8
RAM 1.1 RAM 1.2
1×2
Decoder
1 0
16
8
8

128 × 8 128 × 8
RAM 2.1 RAM 2.2
16

8
8
Memory Design - Memory Interface Address Map
Problem – 4: Design 256 × 16 – bit RAM using 256 × 8 – bit RAM chips and 256 × 8 – bit ROM
using 128 × 8 – bit ROM chips.
RAM Chip calculation
Solution: p = 256 / 256 = 1; q = 16 / 8 = 2
p×q=1× 2=2 RAM2 chips are required 1 row  2 chips (cols)

x – Number of bits required to Y- Number of bits for Z – Number of 1

represent the address lines Selecting the specific RAM. (select the RAM or
256 x 8= 28 x 8 (p = 2y) (p=120y ) y=0 ROM)
x=8 bit address is required

S.NO Memory NxW N1 x W1 P q p*q x y z Total

1 RAM 256 × 8 256 × 16 1 2 2 8 0 1 9

2 Rom 128 × 8 256 × 8 2 1 2 7 1 1 9

4
Memory Design - Memory Interface Address Map
Problem – 4: Design 256 × 16 – bit RAM using 256 × 8 – bit RAM chips and 256 × 8 – bit ROM
using 128 × 8 – bit ROM chips.
ROM Chip calculation
Solution: p = 256 / 128 = 2; q=8/8=1
p×q=2× 1=2 ROM2 chips are required 2 chips(rows) , 1 column

x – Number of bits required to Y- Number of bits for Z – Number of 1

represent the address lines Selecting the specific RAM. (select the RAM or
128 x 8= 27 x 8 (p = 2y) (p=221y ) y=1 ROM)
x=7 bit address is required

S.NO Memory NxW N1 x W1 P q p*q x y z Total

1 RAM 256 × 8 256 × 16 1 2 2 8 0 1 9

2 Rom 128 × 8 256 × 8 2 1 2 7 1 1 9

4
Memory Design - Memory Interface Address Map

Z = 1 bit For RAM – No bits required – (No address line used)

Y = 1 bit --- For ROM (7 th address line is used)
Memory Design - Memory Interface Address Map

v v v v

Substitute x=0 to get ‘From’ address X=0

If x=0 ‘From’ address is 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0

Convert to hexadecimal value 0 1 8 0

So, from address of RAM is 0180

Memory Design - Memory Interface Address Map

v v v v

Substitute x=1 to get ‘To’ address X=1

If x=1 ‘To’ address is 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1

Convert to hexadecimal value 0 1 F F

So, from address of RAM is 01FF

Address Bus
128 × 8 Data
876-0 ROM 1
r/w

1×2 1×2 8
Decoder Decoder
1 0 1 0
128 × 8
ROM 2
●

256 × 8 256 × 8
RAM 1.1 RAM 1.2

16

8
8
Memory Design - Memory Interface Address Map
Problem – 5

• A computer employs RAM chips of 128 x 8 and ROM chips of 512 x 8. The computer system needs
256 x 8 of RAM, 1024 x 16 of ROM, and two interface units with 256 registers each. A memory
mapped I/O configuration is used. The two higher -order bits of the address bus are assigned 00 for
RAM, 01 for ROM, and 10 for interface registers.

• a. Compute total number of decoders are needed for the above system?

• b. Design a memory-address map for the above system

• c. Show the chip layout for the above design

Memory Design - Memory Interface Address Map
• A computer employs RAM chips of 128 x 8 and ROM chips of 512 x 8. The computer system needs
256 x 8 of RAM, 1024 x 16 of ROM, and two interface units with 256 registers each. A memory
mapped I/O configuration is used. The two higher -order bits of the address bus are assigned 00 for
RAM, 01 for ROM, and 10 for interface registers.

q = always 1 for Interfaces (Column)

Memory Design - Memory Interface Address Map
Solution: p = 256 / 128 = 2; q=8/8=1
1.RAM p×q=2× 1=2 RAM2 chips are required 2chips(row) 1(col)

x – Number of bits required to Z – Number of 2

Y- Number of bits for
represent the address lines (select the RAM or
Selecting the specific RAM.
128 x 8= 27 x 8 ROM or interface)
(p = 2y) (p=221y ) y=1
x=7 bit address is required
S.NO Memory NxW N1 x W1 P q p*q x y z Total

1 RAM 128 × 8 256 × 8 2 1 2 7 1 2 10

2 ROM 512 × 8 1024 × 16 2 2 4 9 1 2 12

3 Interface 256 2 1 2 8 1 2 11

4
Memory Design - Memory Interface Address Map
Solution: p = 1024 / 512 = 2; q = 16 / 8 = 2
2.ROM p×q=2× 2=4 RAM4chips are required 2chips(rows), 2chips(cols)

x – Number of bits required to Z – Number of 2

Y- Number of bits for
represent the address lines (select the RAM or
Selecting the specific RAM.
512 x 8= 29 x 8 ROM or interface)
(p = 2y) (p=221y ) y=1
x=9 bit address is required
S.NO Memory NxW N1 x W1 P q p*q x y z Total

1 RAM 128 × 8 256 × 8 2 1 2 7 1 2 10

2 ROM 512 × 8 1024 × 16 2 2 4 9 1 2 12

3 Interface 256 2 1 2 8 1 2 11

4
Memory Design - Memory Interface Address Map
3.Interface p = number of interfaces=2(input is given)
q is 1 always for interfaces. p*q= 2 * 1 = 2
Z – Number of 2 (select
2x = 256 (Number of registers) 2y = p=2
the RAM or ROM or
X= 8 y= 1
interface)
2 interfaces are required 2 interfaces(rows), 1 column
S.NO Memory NxW N1 x W1 P q p*q x y z Total

1 RAM 128 × 8 256 × 8 2 1 2 7 1 2 10

2 ROM 512 × 8 1024 × 16 2 2 4 9 1 2 12

3 Interface 256 2 1 2 8 1 2 11

4
Memory Design - Memory Interface Address Map
Component Hexadecimal Address Address Bus
From To 15 - 12 11 10 9 8 7 6 5 4 3 2 1 0

RAM1 0000 007F 0 0 0 x x x x x x x

RAM2 0200 027F 0 0 1 x x x x x x x

ROM1.1 0400 05FF 0 1 0 x x x x x x x x x

ROM1.2 0400 05FF 0 1 0 x x x x x x x x x

ROM2.1 0600 07FF 0 1 1 x x x x x x x x x

ROM2.2 0600 07FF 0 1 1 x x x x x x x x x

Interface1 0800 08FF 1 0 0 x x x x x x x x

Interface2 0A00 0AFF 1 0 1 x x x x x x x x

X=address lines(RAM7,ROM9,interface8
Y=1 Z=2
Address Bus
11 10 128 × 8 Data r/w
9876-0 RAM 1

128 × 8
RAM 2

0
1
512 × 8 512 × 8
ROM 1.1 ROM 1.2
3×8 2
Decoder
3
4 512 × 8 512 × 8
ROM 2.1 ROM 2.2
5

Select Interface 1
Ch. Address r/w Data

Select Interface 2
Ch. Address r/w Data
Memory Design - Memory Interface Address Map
Problem – 6
• Suppose that a 2M × 16 RAM memory is built using 256K × 8 RAM chips and 1K x 8 ROM
memory is build using 256 x 8 ROM chips with the word addressable memory, find the
following:
• a) How many RAM chips and ROM chips are necessary?
• b) If we were accessing one full word in RAM, how many chips would be involved?
• c) How many address bits are needed for each RAM chip?
• d) How many memory banks are required? Hint: number of banks are addressable units in
main memory and RAM chips
• e) If high-order interleaving is used, where would address (1B)16 be located? Also, for a
low-order interleaving?
Memory Design - Memory Interface Address Map
Problem – 6 - Solution
• a) 16 RAMS , 4 ROMS
• b) Each RAM chip is 256K × 8, so to access one full word (2 bytes), 2 RAM chips would be
involved.
• c) The 256K × 8 RAM chip has 18 address bits (2^18 = 256K), so each RAM chip would
need 18 address bits.
• d) 8
• e) module 0 – word 27
module 3 - word 3
Cache Memory

• Special very high-speed memory

• used to speed up and synchronize with high-speed CPU
• Cache memory is costlier than main memory or disk memory but more
economical than CPU registers
• extremely fast memory type that acts as a buffer between RAM and the
CPU
• It holds frequently requested data and instructions so that they are
immediately available to the CPU when needed
• used to reduce the average time to access data from the Main memory
• The cache is a smaller and faster memory that stores copies of the data
from frequently used main memory locations
Cache Memory: Principles
• The intent of cache memory is to provide
the fastest access to resources without
compromising on size and price of the
memory.

• The processor attempting to read a byte

of data, first looks at the cache memory.

• If the byte does not exist in cache

memory, it searches for the byte in the
main memory.
Types of Cache Memory
• Primary Cache:
• very fast and its access time is similar to the
processor registers
• it is built onto the processor chip
• its size is quite small
• also known as a level 1 cache and is build using
static RAM (SRAM)
• Secondary Cache:
• The secondary cache or external cache is cache
memory that is external to the primary cache
• It is located between the primary cache and the
main memory
• It is also known as a level 2 cache
Cache Memory: Advantages &
Disadvantages
• Advantages of Cache Memory
• Faster
• Less access time
• Disadvantages of Cache Memory
• Expensive
• Limited capacity
Locality of Reference
⚫ An implication of locality is that we can predict with reasonable accuracy
what instructions and data a program will use in the near future based on
its accesses in the recent past.
No

Yes
Direct Mapping

Cache Memory Block Placement Set Associative

Fully Associative
Management
Techniques Block Identification
Tag

Index

Offset
Cache Memory Management
Techniques
FCFS

Block Replacement LRU, MRU

Optimal

Write Through

Write back
Update Policies
Write around

Write allocate
Direct Mapping

Cache Memory Block Placement Set Associative

Fully Associative
Management
Techniques Block Identification
Tag

Index

Offset
Cache Memory Management
Techniques
FCFS

Block Replacement LRU, MRU

Block Placement Optimal

Strategies – Write Through

Mapping Update Policies

Write back

Techniques Write around

Write allocate
Mapping - Basics

In SM to MM – The
terms Pages and
Frames are used.

In MM to CM – The
terms Blocks and
Lines are used.

Pages, Frames, Blocks, Lines

– Same

Blocks – MM Blocks
Cache Lines - Cache Blocks
Mapping - Basics 4 words per Block

Mapping 64 words of Main memory on to 16 words of Cache

• Main Memory Address

16 Blocks
Mapping - Basics 4 words per Block

Mapping 64 words of Main memory on to 16 words of Cache 0 1 2 3

• Main Memory Address

Each word (0 to 63) – has data – (needs to be transferred)
Hence, Main Memory Address(Physical Address)
– should point to the individual word in a block.
No. of bits needed to store 64 words
16 Blocks

Main Memory Address bits (Physical Address Bits – PA Bits): 6 bits

Mapping - Basics
Mapping 64 words of Main memory on to 16 words of Cache

• Main Memory Address No. of words in the memory: 64 words

No. of bits needed to store 64 words = 6 bits No. of bits needed to identify the block (total 16 blocks)

No. of bits to identify a block

in 16 blocks = 4 bits
No. of bits to identify a single word
in the identified block = 2 bits
Mapping - Basics
Mapping 64 words of Main memory on to 16 words of Cache
Word
• Main Memory Address 0 1 2 3
If the PA is 011111,
Then,
the corresponding block and
the word in that block can be
identified with the first 4 bits and
last 2 bits respectively.
Mapping - Basics
Mapping 64 words of Main memory on to 16 words of Cache

• Cache Memory Organization No. of Cache Blocks (Lines) = 4

No. of bits needed to store 4 lines (Cache Blocks) = 2 bits

In Main memory,

MM Size – 16 blocks
Cache Size – 4 blocks(Lines)

Hence, Mapping is Required

Cache - Memory Mapping Techniques

• Cache mapping defines how a block

from the main memory is mapped to
the cache memory in case of a cache
miss
• Cache mapping is a technique by
which the contents of main memory
are brought into the cache memory.
• Direct mapping
• Associative mapping
• Set-Associative mapping
Cache - Memory Mapping Techniques
• Direct Mapping
• Many to One Mapping
• Map to a fixed Cache Line

• Associative Mapping
• Many to Many Mapping
• Map to any Cache Line

• Set Associative Mapping

Mapping Techniques - Direct Mapping
• A particular block of main memory can map only to a particular line
of the cache
• Assign each memory block to a specific line in the cache
• If a line is previously taken up by a memory block when a new block
needs to be loaded, the old block is trashed
Cache line number = ( MM Block Address ) % (Number of CM lines)
Mapping Techniques - Direct Mapping
Mapping 64 words of Main memory on to 16 words of Cache

• Mapping – Direct Mapping

MM Size – 16 blocks
Cache Size – 4 blocks(Lines)

Hence, Mapping is Required

Mapping Techniques - Direct Mapping
Cache line number = ( MM Block Address ) % (Number of CM lines)
Mapping Techniques - Direct Mapping
Mapping 64 words of Main memory on to 16 words of Cache
Mapping – Direct Mapping
MM Blocks

How a block is
identified in 2 bits identifies a word in a Block
cache with Cache
MM Address Blocks/Lines Many–to–One
bits? Relationship
Main Memory
Block is identified by Cache
first 4 bits of PA Memory
Mapping Techniques - Direct Mapping
Mapping 64 words of Main memory on to 16 words of Cache
Mapping – Direct Mapping
MM Blocks

How a block is
identified in 2 bits identifies a word in a Block
cache with Cache Blocks/
Lines
MM Address
bits?
Main Memory
Block is identified by Cache
first 4 bits of PA Memory
Mapping Techniques - Direct Mapping
Mapping 64 words of Main memory on to 16 words of Cache
Tag bits MM Blocks Line Number/Index
How a Word in
a block is TAG BITS LINE 2 bits
identified in Cache Blocks/ NUMBER identifies a
cache with Lines word in
MM Address both
MM/CM
bits? Block
Main Memory
Word is identified by Cache
last 2 bits of PA Memory
Mapping Techniques - Direct Mapping
Mapping 64 words of Main memory on to 16 words of Cache
Tag bits MM Blocks Line Number(Index)

Cache Blocks/
Lines

2 bits identifies a word in a Block

(LINE OFFSET)
Mapping Techniques - Direct Mapping
Why called TAG bits?
Tag Bits
Direct Mapping – Calculation of PA Bits
needed
PA = MM Size = 2N
N BITS

No. of Blocks = 2X Block Size/Line size = 2Y

X bits Y bits

Tag Line Number Word / Offset

=MM Size/ Cache Size =Cache Size/ Line Size=Line Size in powers of 2
in powers of 2 in powers of 2

No. of Blocks = MM Size/ Block Size

Mapping Techniques - Direct Mapping
• Consider a cache consisting of 128 blocks of 16 words each, for total of
2048(2K) words
• Assume that the main memory is addressable by 16 bit address.
• Main memory is 64K which will be viewed as 4K (4×1024=4096) blocks of 16
words each.
• In this block J of the main memory maps on to block J modulo 128 of the
cache. Thus main memory blocks 0,128,256,….is loaded into cache is stored
at block 0. Block 1,129,257,….are stored at block 1 and so on.

PA Bits Calculation:
MM Words = 4096*16 words = 65536 words, So, No. of PA bits => 216 => 16 bits
BLOCK / LINE bits:
No. of MM blocks : 4096, So, No. of bits to represent a block =>212 => 12 bits (Block bits + Tag Bits)
LINE OFFSET (WORD) Bits:
Each Block – 16 words => No. of bits for 16 words = 24 => 4 bits
TAG Bits & Block Bits:
No. of Lines in cache (128 blocks) = CACHE size/Block Size = 2048 / 16 = 128.
Block bits (128 lines/blocks) => 27 => 7 bits.
Tag Bits => Total Block bits – Block bits = 12-7 = 5 bits
Mapping Techniques - Direct Mapping

Need of Replacement Algorithm-

In direct mapping,

There is no need of any replacement algorithm.

This is because a main memory block can map only to a
particular line of the cache.
Thus, the new incoming block will always replace the
existing block (if any) in that particular line.
Mapping Techniques - Direct Mapping -
Problems

Solution: Main Memory:

Calculation of PA bits:

Calculation of Block &

Word(offset) bits:
Cache Memory:
Calculation of Cache Block/ Physical Address Split:
Line Number/Index bits:

Calculation of TAG bits

Mapping Techniques - Direct Mapping -
Problems

Logic: Not Required

Mapping Techniques - Direct Mapping -
Problems
Parameters of Cache memory
⚫ Cache Hit
⚫ A referenced item is found in the cache by the processor

⚫ Cache Miss
⚫ A referenced item is not present in the cache

⚫ Hit ratio
⚫ Ratio of number of hits to total number of references = > number of hits/(number of hits + number of
Miss)

⚫ Miss penalty
⚫ Additional cycles required to serve the miss
⚫ Time required for the cache miss depends on both the latency and bandwidth
⚫ Latency – time to retrieve the first word of the block
⚫ Bandwidth – time to retrieve the rest of this block
Types of Cache Miss
• Compulsory Miss / Cold Miss
• Conflict Miss/ Collision miss/ Interference miss
• Capacity Miss – Not because of mapping techniques … because of size of cache.
Mapping Techniques - Direct Mapping -
Drawbacks
• Drawback – Conflict Miss

Compulsory
Miss

Conflict Miss
Mapping Techniques – (Fully) Associative
Mapping
• To reduce Conflict Miss ----- Associative Mapping
Many–to–Many
• A block of main memory can map to any Relationship
line of the cache that is freely available
at that moment.
• This makes fully associative mapping
more flexible than direct mapping.
• All the lines of cache are freely
available.
• When all the cache lines are occupied,
then one of the existing blocks will have
to be replaced.
Mapping Techniques – (Fully) Associative
Mapping
• Entire block number bits are used as
TAG bits --- (Fully Associative)
• No need of specifying the block number. Many–to–Many
Relationship
PA Address Calculation - Direct &
Associative
Direct Mapping Associative Mapping
Mapping Techniques – (Fully) Associative
Mapping
Disadvantages: Need of Replacement Algorithm:
• A replacement algorithm is required. • A replacement algorithm is
• During retrieval, all the blocks needs to required.
be checked for the data. • Replacement algorithm suggests the
block to be replaced if all the cache
lines are occupied.
• Thus, replacement algorithm like
FCFS Algorithm, LRU Algorithm etc is
employed.
Associative Mapping – Calculation of PA
Bits needed
PA = MM Size = 2N
N BITS

No. of Blocks = 2X Block Size/Line size = 2Y

X bits Y bits

Tag Word / Offset

No. of Blocks = MM Size/ Block Size =Line Size in powers of 2

Mapping Techniques – (Fully) Associative
Mapping
Example
Consider a fully associative mapped cache of size 16 KB with block size 256 bytes. The size of main
memory is 128 KB.
Number of Bits in Physical Address-
1. Number of bits in tag
Size of main memory
2. Tag directory size
= 128 KB
Given
= 217 bytes
Cache memory size = 16 KB
Thus, Number of bits in physical address = 17 bits
Block size = Frame size = Line size = 256 bytes
Main memory size = 128 KB
We consider that the memory is byte addressable.
Mapping Techniques – (Fully) Associative
Mapping
Number of Bits in Block Offset-
Block size
= 256 bytes
= 28 bytes
Thus, Number of bits in block offset = 8 bits
Number of Bits in Tag-
Number of bits in tag= Number of bits in physical address – Number of bits in block offset
= 17 bits – 8 bits
= 9 bits
Thus, Number of bits in tag = 9 bits
Mapping Techniques – (Fully) Associative
Mapping
Number of Lines in Cache
Total number of lines in cache= Cache size / Line size
= 16 KB / 256 bytes
= 16 x 1024 bytes / 256 bytes
= 64 lines
Tag Directory Size
= Number of lines in cache x Number of bits in tag
= 64 x 9 bits
= 576 bits
= 72 bytes
Thus, size of tag directory = 72 bytes
Mapping Techniques – Set Associative
Mapping
• Combination of direct and associative mapping technique
• Cache blocks are grouped into sets and mapping allow block of main memory reside into
any block of a specific set
Mapping Techniques – Set Associative
Mapping
• Hence contention problem of direct mapping is eased , at the same time ,
hardware cost is reduced by decreasing the size of associative search.
• For a cache with two blocks per set. In this case, memory block 0, 64,
128,…..,4032 map into cache set 0 and they can occupy any two block
within this set.
• Having 64 sets means that the 6 bit set field of the address determines
which set of the cache might contain the desired block.
• The tag bits of address must be associatively compared to the tags of the
two blocks of the set to check if desired block is present. This is two way
associative search.
Cache set number = ( MM Block Address ) % (Number of sets in Cache)
Mapping Techniques – Set Associative
Mapping
Mapping Techniques – Set Associative
Mapping - Problems
Mapping using Set Associative Block number (MM) % number of sets
Mapping Techniques – Set Associative
Mapping
• k = 2 suggests that each set contains two cache lines. It is called as 2-way
set associative mapping

• Since cache contains 6 lines, so number of sets in the cache = 6 / 2 = 3 sets.

• Block ‘j’ of main memory can map to set number (j mod 3) only of the cache.
• Within that set, block ‘j’ can map to any cache line that is freely available at
that moment.

• If all the cache lines are occupied, then one of the existing blocks will have
to be replaced.
Mapping Techniques – Set Associative
Mapping

PA Bits Calculation:
MM Words = 4096*16 words = 65536 words, So, No. of PA bits => 216 => 16 bits
BLOCK / LINE bits:
No. of MM blocks : 4096, So, No. of bits to represent a block =>212 => 12 bits (Block bits + Tag Bits)
LINE OFFSET (WORD) Bits:
Each Block – 16 words => No. of bits for 16 words = 24 => 4 bits
TAG Bits & Block Bits:
No. of Lines in cache (128 blocks) = CACHE size/Block Size = 2048 / 16 = 128.
No. of lines = 128 =>(2-way set associative)=> No. sets =128/2 = 64 sets… No. of bits for representing Set = 26 = 6 bits.
Tag Bits => Total Block bits – Block bits = 12-6 = 6 bits
Mapping Techniques – Set Associative
Mapping
• If k = 1, then k-way set associative mapping becomes direct mapping i.e

• 1-way Set Associative Mapping ≡ Direct Mapping

• If k = Total number of lines in the cache, then k-way set associative mapping
becomes fully associative mapping.

Need of Replacement Algorithm:

• Set associative mapping is a combination of direct mapping and fully associative mapping.

• It uses fully associative mapping within each set.

• Thus, set associative mapping requires a replacement algorithm.

Set Associative Mapping – Calculation of
PA Bits needed
PA = MM Size = 2N
N BITS

No. of Blocks = 2X Block Size/Line size = 2Y

X bits Y bits

Tag Set Number Word / Offset

=K * (MM Size/ Cache Size) =No. of sets in powers of 2 =Line Size in

(No. of Lines=Cache Size/ Line Size powers of 2
in powers of 2 No. of Sets (S)= No.of Lines/K)

No. of Blocks = MM Size/ Block Size

Mapping Techniques – Set Associative
Example 1
Mapping - Problems

Solution: Main Memory:

Calculation of PA bits:

Calculation of Block &

Word(offset) bits: Physical Address Split:
Cache Memory:
Number of lines and sets

Calculation of TAG bits PA-(set no+offset) 7-(2+2)=3

Mapping Techniques – Set Associative
Mapping - Problems
Example 1 - Elaborated
Mapping Techniques – Set Associative
Mapping - Problems
Example 1 - Elaborated
Mapping Techniques – Set Associative
Mapping - Problems
Example 1 - Elaborated
Mapping Techniques – Set Associative
Mapping - Problems
Example 1 - Elaborated
Mapping Techniques – Set Associative
Mapping - Problems
Example 2
Mapping Techniques – Set Associative
Mapping - Problems
Example 2
Mapping Techniques – Set Associative
Example 3 Mapping - Problems
1.P.A split?
2.Tag directory size?
3.Show the format of main memory
address

Solution: Main Memory:

Calculation of PA bits:
Physical Address Split:
Calculation of Block &
Word(offset) bits:
Cache Memory:
Number of lines and sets

Calculation of TAG bits PA-(set no+offset) 28-(12+7)=9

Mapping Techniques – Set Associative
Example 4 Mapping - Problems

Solution:
Calculation of PA bits:

Calculation of Block &

Physical Address Split:
Word(offset) bits:
Mapping Techniques – Set Associative
Example 4 Mapping - Problems

Solution: Physical Address Split: Tag Bits =K * (MM Size/ Cache Size)
in powers of 2
Cache Memory:
Number of lines and sets

(OR)
Cache size
Mapping Techniques – Set Associative
Mapping - Problems
Example 5
Mapping Techniques – Set Associative
Mapping - Problems
Example 6
Mapping Techniques – Set Associative
Mapping - Problems
Example 7
Mapping Techniques – Set Associative
Mapping - Problems
Example 8
Mapping Techniques – Set Associative
Mapping - Problems
Example 9

• Consider a 32-bit microprocessor that has an on-chip 16-kB four-way

set-associative cache. Assume that the cache has a line size of four
32-bit words. Draw a block diagram of this cache showing its
organization and how the different address fields are used to
determine a cache hit/miss. Identify the set number in cache for
mapping the given memory address ABCDE8F8.
Mapping Techniques – Set Associative
Mapping - Problems
Example 9 – Solution
• Given: 16 Kb cache size. - 4 way set associative.
Hence, Line size = 4*32 bit = 16 bytes.

• Here, in the question "word" is mentioned and even "Where in the cache is the word from
memory location“ is asked. So, word addressing is in use.
So, offset bits = 2 for 4 words.
• No. of sets=no of lines/p(way)
• No. of lines=cache size /line size

tag(22 bit) sets( 8 bit) block size(2 bit)

• Identifying the Set Number: Address -- ABCDE8F8
its binary from is :1010 1011 1100 1101 1110 1000 1111 1000
<1010 1011 1100 1101 1110 10> <00 1111 10> <00>
• it is mapped to set number 62 in cache.
Direct Mapping

Cache Memory Block Placement Set Associative

Fully Associative
Management
Techniques Block Identification
Tag

Index

Offset
Cache Memory Management
Techniques
FCFS

Block Replacement LRU, MRU

Block Optimal

Replacement Write Through

Strategies Update Policies

Write back

Write around

Write allocate
Cache : Block Replacement Policies
• Cache memory size < main memory size
• Processor fetches data from cache memory to perform execution operation
• So, when required block is not found within cache, then main memory block is transferred
to cache and previously present block is replaced---- Cache replacement policies are
needed….
• Replacement policies – used in
• Set-associative cache
• Fully – Associative/ Associative Cache
• Cache Replacement Policies:
• FIFO
• Optimal Algorithm
• LRU
• MRU
Cache : Block Replacement Policies - FIFO
Cache : Block Replacement Policies - FIFO
Cache : Block Replacement Policies - Optimal
Cache : Block Replacement Policies - Optimal
Cache : Block Replacement Policies - LRU
Cache : Block Replacement Policies - LRU
Cache : Block Replacement Policies - MRU
Most Recently Used

Most Recently Used (MRU)

Cache : Block Replacement Policies - MRU
Direct Mapping

Cache Memory Block Placement Set Associative

Fully Associative
Management
Techniques Block Identification
Tag

Index

Offset
Cache Memory Management
Techniques
FCFS

Block Replacement LRU, MRU

Update Policies Optimal

Write Through

Write back
Update Policies
Write around

Write allocate
Cache Memory – Update Policies
• Update policy - determines how a cache & Main Memory is updated
after an operation.
• Write through
Used on Write HIT
• Write back

• Write around
Used on Write MISS
• Write Allocate
Update Policy - Write-through
• Correspond to items currently in the cache (i.e. write Hit)
• Systems that write to main memory each time as well as to cache
• It's the easiest policy to implement, but it lowers the cache's
performance.
• It's used when there are no frequent writes to the cache.

CPU Cache Main Memory

Update Policy - Write-Back/Copy Back
• Correspond to items currently in the cache (i.e. write Hit)
• Updating main memory until the block containing the altered item is
removed from the cache
On Replacement
of cache line

CPU Cache Main Memory

Update Policy - Write-Around
• Correspond to items not currently in the cache (i.e. write misses)
• The item could be updated in main memory only without affecting
the cache.

CPU Cache Main Memory

Update Policy - Write-Allocate
• Correspond to items not currently in the cache (i.e. write misses)
• Update the item in main memory and bring the block containing the
updated item into the cache.

CPU Cache Main Memory

Cache Update Policy - Summary
• Update policies
• Write Through
• On write hit, Update cache as well as Main Memory simultaneously
• Write Back
• On write hit, Update cache instantly and update main memory on cache line
replacement
• Write –Around
• On write miss, Update main memory without affecting Cache
• Write-Allocate
• On write miss, Update main memory and copy updated block into Cache
Performance Metrics
• Cache Hit
• Hit Ratio
• Cache Miss
• Miss Ratio
• Miss Penalty
• Average Memory Access Time
Performance Metrics
• Hit Ratio:
• Number of references found in the cache against Total number of references
𝑵𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒓𝒆𝒇𝒆𝒓𝒆𝒏𝒄𝒆𝒔 𝒇𝒐𝒖𝒏𝒅 𝒊𝒏 𝒕𝒉𝒆 𝑪𝒂𝒄𝒉𝒆
• Hit Ratio (h)= 𝒕𝒐𝒕𝒂𝒍 𝒏𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒎𝒆𝒎𝒐𝒓𝒚 𝒓𝒆𝒇𝒆𝒓𝒆𝒏𝒄𝒆𝒔
• Miss Ratio (m) =1- Hit Ratio
• Hit Ratio + Miss Ratio=1
• TC is the average cache access time
• TM is Mean memory access time
• TA is average access time
Mean Memory Access Time (MMAT)
• Average Memory Access Time
= Hit ratio * Cache Memory Access Time
+
(1 – Hit ratio) * (Cache Memory Access Time + Time required to access a
block of main memory)
Look through
• The cache is checked first for a hit, and if a miss occurs then the
access to main memory is started
TC is the average cache access time
TM is Mean memory access time

TAvg = (TC ) + (1-h) × TM On Miss

CPU Cache Main Memory
Example
Assume that a computer system employs a cache with an access time
of 20ns and a main memory with a cycle time of 200ns. Suppose that
the hit ratio for reads is 90%,
a) what would be the average access time for reads if the cache is a
“look-through” cache?
The average read access time
TAvg = (TC ) + (1-h) × TM

= 20ns + 0.10 * 200ns = 40ns

Look aside
• Access to main memory in parallel with the cache lookup

Cache Memory Access Time during Cache Hit (Tc ) =Tc

Cache Memory Access Time during Cache miss (Tc ) =0

TC is the average cache access time

TM is Mean memory access time

TAvg = (h × TC ) + (1-h) × TM

CPU Cache Main Memory

Example
Assume that a computer system employs a cache with an access time
of 20ns and a main memory with a cycle time of 200ns. Suppose that
the hit ratio for reads is 90%,
b) what would be the average access time for reads if the cache is a
“look-Aside” cache?
The average read access time in this case
TAvg = (h × TC ) + (1-h) × TM

= 0.9*20ns + 0.10 * 200ns = 38ns

A computer system employs a write-back cache with a 90% hit ratio for writes. The cache operates in
"Look Through" and has a 80% read hit ratio. Reads account for 60% of all memory references and
writes account for 40%.If the main memory cycle time is 300ns and the cache access time is 30ns, what
would be the average access time for all references (reads as well as writes)?
A computer system employs a write-back cache with a 90% hit ratio for writes. The cache operates in
"Look Aside" and has a 80% read hit ratio. Reads account for 60% of all memory references and writes
account for 40%.If the main memory cycle time is 300ns and the cache access time is 30ns, what would
be the average access time for all references (reads as well as writes)?
Ans: