COMPUTER ORGANIZATION

MODULE-II (MEMORY)

11/16/2024 1
 Memory Organization:
Memory Hierarchy:
Memory hierarchy in a computer system:
Main Memory : Memory unit that communicates directly with the CPU (RAM)
Auxiliary Memory : Device that provide backup storage (Disk Drives)
Cache Memory : Special very-high-speed memory to increase the processing speed
(Cache RAM)
Multiprogramming: Enable the CPU to process a number of independent program
concurrently
Memory Management System: Supervise the flow of information between auxiliary
memory and main memory
Memory Hierarchy is to obtain the highest possible access speed while minimizing the
total cost of the memory system
Auxiliary memory
Magnetic
tapes
Main
I/O processor
memory
Magnetic
disks

Cache
CPU
memory

5
 MAIN MEMORY
Random Access Memory (RAM):
Static RAM
•Consists of Flip-flops to store binary information.
•Static RAM is easier to use and having short Read/Write cycles
•Used mostly in Cache memory.

Dynamic RAM
Stores binary information in the form of electric charge stored inside the capacitor.
The capacitors are provided by MOS transistors.
Refreshing circuit is required to refresh the memory.
•Dynamic RAM offers reduced power consumption and large storage capacity.
•It is used to construct main memory.

5
RAM Chips:
 The common feature is a bidirectional data bus that allows the transfer of data
either from memory to CPU during a read operation, or from CPU to memory
during a write operation.
 A bidirectional bus can be constructed with three-state buffers. A three-state
buffer output can be placed in one of three possible states: a signal equivalent to
logic 1, a signal equivalent to logic 0, or a high impedance state.
 The high impedance state behaves like an open circuit, which means that the
output does not carry a signal and has no logic significance. (Inhibit:unable to act)
 The capacity of the memory is 128 words of eight bits (one byte) per word.
Chip select 1 CS1
Chip select 2 CS2
Read RD 128 x 8 8-bit data bus
RAM
Write WR
7-bit address AD 7

CS1 CS2 RD WR Memory function State of data bus

0 0 x x Inhibit High-impedence
0 1 x x Inhibit High-impedence
1 0 0 0 Inhibit High-impedence
1 0 0 1 Write Input data to RAM
1 0 1 x Read Output data from RAM
1 1 x x Inhibit High-impedence
5
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-impedance state

Chip select 1 CS1

Chip select 2 CS2
512 x 8 8-bit data bus
ROM
9-bit address AD 9

5
Memory Address Map:
 The table, called a memory address map, is a pictorial representation of assigned
address space for each chip in the system.
 Assume that a computer system needs 512 bytes of RAM and 512 bytes of ROM.

Hexadecimal Address bus

Component address 10 9 8 7 6 5 4 3 2 1
RAM 1 0000 - 007F 0 0 0 x x x x x x x
RAM 2 0080 - 00FF 0 0 1 x x x x x x x
RAM 3 0100 - 017F 0 1 0 x x x x x x x
RAM 4 0180 - 01FF 0 1 1 x x x x x x x
ROM 0200 - 03FF 1 x x x x x x x x x

 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.
 This configuration gives a memory capacity of 512 bytes of RAM and 512 bytes
of ROM.
5
Memory Address Map:

5
Memory Address Map:
 The particular RAM chip selected is determined from lines 8 and 9 in the address
bus. This is done through a 2 x 4 decoder whose outputs go to the CS1 input in
each RAM chip. Thus, when address lines 8 and 9 are equal to 00, the first RAM
chip is selected. When 01, the second RAM chip is selected, and so on.
 The RD and WR outputs from the microprocessor are applied to the inputs of
each RAM chip.
 The selection between RAM and ROM is achieved through bus line 10. The
RAMs are selected when the bit in this line is 0, and the ROM when the bit is 1.

Memory Connection to CPU:

 RAM and ROM chips are connected to a CPU through the data and address buses

 The low-order lines in the address bus select the byte within the chips and other
lines in the address bus select a particular chip through its chip select inputs.

5
Problems:
Q1. a) How many 128x8 RAM chips are needed to provide a memory capacity of
2048 bytes.
b) How many lines of the address bus must be used to access 2048 bytes of memory.
How many of these lines will be common to all chips.
c) How many lines must be decoded for chip select? Specify the size of decoders.

Q2. Extend the memory system of CPU to 4096 bytes of RAM and 4096 bytes of
ROM. List the memory-address map and indicate what size decoders are needed.

Q3. A computer employs RAM chips of 256x8 and ROM chips of 1024x8. The
computer system needs 2K bytes of RAM, 4K bytes of ROM, and four interface units
each with four registers. A memory-mapped I/O configuration used. The two highest-
order bits of the address bus are assigned 00 for RAM, 01 for ROM, and 10 for
interface registers.
a. How many RAM and ROM chips are needed.
b. Draw a memory-address map for the system.
c. Give the address range in hexadecimal for RAM, ROM and interface.

5
Solutions:
1. 24 = 16, 4 lines must be decoded for chip select.

2. Memory-address map:

5
Solutions:
3. RAM chips of 256x8 and ROM chips of 1024x8. The computer system needs 2K
bytes of RAM, 4K bytes of ROM, and four interface units each with four registers.
The two highest-order bits of the address bus are assigned 00 for RAM, 01 for ROM,
and 10 for interface registers.

5
Cache Memory:
Locality of Reference: The references to memory tend to be confined within a
few localized areas in memory
Cache Memory: a fast small memory
Keeping the most frequently accessed instructions and data in the fast cache
memory
Hit Ratio: The ratio of the number of hits divided by the total CPU references
(hits + misses) to memory
hit : the CPU finds the word in the cache
miss : the word is not found in cache (CPU must read main memory)

Main memory
CPU
32K×12 Cache memory
512×12

Problem: A computer with cache access time of 100ns, a main memory access
time of 1000 ns, a hit ratio of 0.9. Calculate average access time ?

Solution: H = 0.9, Tc = 100 ns Tm = 1000 ns

Average access time = HTc + (1-H) (Tc+Tm)

= 0.9x100 + (1-0.9)(100+1000) ns
= 90 + 110 = 200 ns 5
Types of Mapping of Cache Memory:
 The basic characteristic of cache memory is its fast access time. Therefore, very
little or no time must be wasted when searching for words in the cache.

Mapping: The transformation of data from main memory to cache memory is

referred to as a mapping process. Three types of mapping procedures are of practical
interest when considering the organization of cache memory.

1) Direct mapping (miss rate)

2) Associative mapping (Fully associate)
3) Set-associative mapping (K-way set-associate)

1) Direct mapping: Considering 128 words main memory is

mapping with 16 words cache memory with 4 bit word in each
section.
In main memory, sub parts are called block and in cache memory, they
are called line. Here, which block is mapping to which line is decided
by k mod n.
5
Direct mapping:

5
Associative mapping:

5
Set-Associative mapping:

5
Problems:

1. A two-way set associative cache memory uses blocks of four words. The cache can
accommodate a total of 2048 words from main memory. The main memory size is 128Kx32.
Formulate all pertinent information required to construct the cache memory. What is the size
of cache memory.

2. The access time of a cache memory is 100 ns and that of main memory is 1000 ns. It is
estimated that 80 percent of the memory requests are for read and the remaining 20 percent for
write. The hit ratio for read access only is 0.9. A write-through procedure is used. What is the
average access time of the system considering only memory read cycles. What is the average
access time of the system for both read and write requests. What is the hit ratio considering
the read requests also.

3. A computer has a memory unit of 64Kx16 and a cache memory of 1K words. The cache
uses direct mapping with a block size of four words. How many bits are there in the tag, index,
block, and words fields of the address format. How many bits are there in each word of cache,
and how are they divided into functions? Include a valid bit. How many blocks can the cache
accommodate?

5
Solutions:
1. Main memory address= 128k = 27 X 210 = 217 =17 bits
Cache memory address: 2048/2 = 1024 = 210 = 10 bits
Tag = 17-10 = 7
Index = 10
Block = 1024/4 = 256 = 28 = 8 bits
(4 words in each block and total 2048/2=1024 words)
The size of cache memory = horizontal X vertical = 1024 x 2 (7+32) = 1024 x 78
Given data size is 32.

5
Solutions:
2. The access time of a cache memory is 100 ns and that of main memory is 1000 ns.
It is estimated that 80 percent of the memory requests are for read and the remaining
20 percent for write. The hit ratio for read access only is 0.9.

Average access time = HTc + (1-H) (Tc+Tm)

5
Solutions:
3. A computer has a memory unit of 64Kx16 and a cache memory of 1K words. The
cache uses direct mapping with a block size of four words.

Memory = 64K = 26 x210 = 216 = 16 bits address

Cache = 1K = 210 = 10 bits
TAG = 16-10 = 6
Index = 10
Block = 1024/4 = 256 = 28 = 8 bits

5
PAGE REPLACEMENT:
Replacement Algorithm : cache miss or full
1) LRU (Least Recently Used)
2) Random Replacement
3) FIFO (First-In First-Out)

Writing to Cache:
1) Write-through: To update main memory with every memory write
operation with catch memory updated in parallel.
2) Write-back: Only the cache location is updated during a write
operation.
Cache Initialization
Cache is initialized:
1) When power is applied to the computer.
2) When main memory is loaded with a complete set of programs from
auxiliary memory.
3) Cache is initialized by clearing all the valid bits to 0.
Valid bit:
Indicate whether or not the word contains valid data

5
Virtual Memory:
 In a memory hierarchy system, programs and data are first stored in auxiliary memory.
Portions of a program or data are brought into main memory as they are needed by the CPU.
 Virtual memory is a concept used in some large computer systems that permit the user to
construct programs as though a large memory space were available, equal to the totality of
auxiliary memory.
 Each address that is referenced by the CPU goes through an address mapping from the so-
called virtual address to a physical address in main memory.
 Virtual memory is used to give programmers the illusion that they have a very large
memory at their disposal, even though the computer actually has a relatively small main
memory.
 Virtual Memory solves the Main Memory (MM) Capacity requirements with a mapping
association to Secondary Memory i.e Hard Disk, while Cache solves the speed up
requirements in memory access by CPU.
 An address used by a programmer will be called a virtual address, and the set of such
addresses the address space. An address in main memory is called a location or physical
address. The set of such locations is called the memory space.
address space memory space

virtual address Mapping

physical address
(logical address)

address generated by programs actual main memory address 5

Virtual Memory:
Address Space (Logical) and Memory Space (Physical):
 Consider a computer with a main-memory capacity of 32K words (K=1024).
Fifteen bits are needed to specify a physical address in memory since 32K=215.
Suppose that the computer has available auxiliary memory for storing 220=1024K
words.
 Thus auxiliary memory has a capacity for storing information equivalent to the
capacity of 32 main memories. Denoting the address space by N and the memory
space by M, we then have for this example N = 1024K and M = 32K.

5
Virtual Memory:
 Address Mapping:
Memory Mapping Table for Virtual Address -> Physical Address

5
Address Mapping Using Pages:
 Address Space and Memory Space are each divided into fixed size group of words
called blocks or pages.
 Consider a computer with an address space of 8K and a memory space of 4K. If
we split each into groups of 1K words we obtain eight pages and four blocks.

Address space and memory space split into groups of lK words:

5
PAGE REPLACEMENT ALGORITHMS:
 Two of the most common replacement algorithms used are the first-in first-out
(FIFO) and the least recently used (LRU).
 The FIFO algorithm selects for replacement the page that has been in memory the
longest time.
 The LRU policy is more difficult to implement but has been more attractive on the
assumption that the least recently used page is a better candidate for removal than
the least recently loaded page as in FIFO.

FIFO (3 pages):

Page Hit: 5 (Hit Ratio: (No. of hits / Total no. of references) * 100)
= (5/20)*100 = 25 %
Page Fault (Miss): 15 (Page Fault Ratio: (No. of faults / Total no. of references)*100)
= (15/20)*100 =75% 5
PAGE REPLACEMENT ALGORITHMS:
Optimal Replacement (OPT) (3 pages): Lowest page fault rate of all algorithms.
 Replace that page which will not be used for the longest period of time.
 Forward Look.

LRU (3 pages): OPT is difficult to implement since it requires future knowledge.

 In LRU replace that page which has not been used for the longest period of time
 Backward Look.

5
Problems:
1. A virtual memory system has an address space of 8K words, a memory space of
4K words and page & block sizes are of 1K words. The following page is
referenced in memory: 4 2 0 1 2 6 1 4 0 1 0 2 3 5 7. Determine the four pages
that are resident in main memory after each page reference change if page
replacement algorithm is : FIFO, LRU, Optimal.
Solution:

5
Problems:
2. An address space is specified by 24 bits and the corresponding memory space by
16 bits. How many words are there in the address space. How many words are there
in the memory space. If a page consists of 2K words, how many pages and blocks are
there in the system?
Solution:

5
11/16/2024 30