Computer Organization and Architecture: Chapter 4: Memory and IO
Memory and IO: Important Example Solved Problems
Computer Organization and Architecture
Computer Organization and Architecture: Chapter 4: Memory and IO: Anna University Solved Problems, Assignment Problems and Important Solved Problems
Computer
Organization and Architecture
Chapter 4: Memory and IO
Important
Example Solved Problems
Example: 1
A bipolar RAM chip is arranged as 16 words. How many bits are stored in the chip?
Solution:
16 × 8 = 128 bits.
One word = 8 bits.
Example: 2
How many address bits are needed to operate a 2 K × 8 ROM?
Solution :
2 K memory locations = 2048 locations
Since 211 = 2048, we need 11 address lines.
Example: 3
How many locations are addressed using 18 address bits ?
Solution: The number of locations addressed = 218 = 262144.
Cache Memories
Example: 1
The application program in a computer system with cache uses 1400 instruction acquisition bus cycle from cache memory and 100 from main memory. What is the hit rate? If the cache memory operates with zero wait state and the main memory bus cycles use three wait states, what is the average number of wait states experienced during the program execution
Solution :
Hit rate = 1400 / (1400 + 100) × 100 = 93.3333 %
Total wait states = 1400 x 0 + 100 × 3 = 300
Average wait states = Total wait states / Number of memory bus cycles = 300 /1500 = 0.2
Example : 2
Consider a cache consisting of 256 blocks of 16 words each, for a total of 4096 (4 K) words and assume that the main memory is addressable by a 16‒bit address and it consists of 4 K blocks. How many bits are there in each of the TAG, BLOCK/SET and word fields for different mapping techniques ?
Solution : We know that memory address is divided into three fields. We will now find the exact bits required for each field in different mapping techniques.
a) Direct‒mapping
Word bits: We know that each block consists of 16 words. Therefore, to identify each word we must have (24 = 16) four bit reserved for it.
Block bits: The cache memory consists of 256 blocks and using direct‒mapped technique, block k of the main memory maps onto block k modulo 256 of the cache. It has one to one correspondence and requires unique address for each block. To address 128 block we require (28 = 256) eight bits.
Tag bits: The remaining 4 (16‒4‒8) address bits are tag bits which stores the higher address of the main memory.
The main memory address for direct‒mapping technique is divided as shown below :
b) Associative‒mapping
Word bits : The word length will remain same i.e. 4 bits.
• In the associative‒mapping technique, each block in the main memory is identified by the tag bits and an address received from the CPU is compared with the tag bits of each block of the cache to see if the desired block is present. Therefore, this type of technique does not have block bits, but all remaining bits (except word bits) are reserved as tag bits.
Block bits: 0
Tag bits: To address each block in the main memory (212 = 4096) 12 bits are required and therefore, there are 12 tag bits.
The main memory address for direct mapping technique is divided as shown below :
c) Set‒associative mapping
Let us assume that there is a 2‒way set‒associative mapping. Here, cache memory is mapped with two blocks per set. The set field of the address determines which set of the cache might contain the desired block.
Word bits : The word length will remain same i.e. 4 bits.
Set bits: There are 128 sets (256/2). To identify each set (27 = 128) seven bits are required.
Tag bits: The remaining 5 (16‒4‒7) address bits are the tag bits which stores higher address of the main memory.
The main memory address for 2‒way set associative mapping technique is divided as shown below:
Example: 3
A block set‒associative cache consists of 64 blocks divided into 4 block sets. The main memory contains 4096 blocks, each consists of 128 words of 16 bits length:
i) How many bits are there in main memory?
ii) How many bits are there in each of the TAG, SET and WORD fields?
Solution :
i) Number of bits in main memory:
= Number of blocks × Number of words per block × Number of bits per word
= 4096 × 128 × 16
= 8388608 bits
ii) Number of bits in word field:
There are 128 words in each block. Therefore, to identify each word (27 = 128) 7 bits are required.
iii) Number of T bits in set field:
There are 64 blocks and each set consists of 4 blocks.
Therefore, there are 16 (64/4) sets. To identify each set (24 = 16) four bits are required.
iv) Number of bits in tag field:
The total words in the memory are :
4096 × 128 = 524288
To address these words we require (219 = 524288) 19 address lines. Therefore, tag bits are eight (19‒7‒4).
Example: 4
A digital computer has a memory unit of 64 K × 16 and a cache memory of 1 K words. The cache uses direct mapping with a block size of four words. How many bits there in the tag index, block and word field of the address format ?
Solution:
Word bits: Number of word bits = log2 4 = log2 22 = 2‒bits
Block bits: Number of block = Cache size / Words in each block = 1K / 4 = 256
Number of block bits = log2 256 = log2 28 = 8 bits
Tag bits: Number of bits to address main memory
= log2 64 K = log2 216 = 16 bits
Number of Tag bits = 16‒8‒2 = 6 bits
Example: 5
A two way set associative cache memory uses block of four words. The cache can accommodate a total of 2048 words from main memory. The main memory size is 128 K × 32.
i) How many bits are there in the tag index, block and word field of address format?
ii) What is size of cache memory?
Solution:
Number of bits in main memory address = log2 128 K = log 217 = 17 bits
Number of blocks in the cache memory = 2048 /4 = 512 blocks
Number of sets in the cache memory = 512 /2 = 256 sets
Number of bits in set field = log2 256 = log2 28 = 8 bits
Number of bits in word field = log2 4 = log2 22 = 2 bits
Number of bits in tag field = 17‒8‒2 = 7 bits
Example: 6
A direct mapped cache has the following parameters : cache size = 1 K words, Block size = 128 words and main memory size is 64 K words. Specify the number of bits in TAG, BLOCK and WORD in main memory address.
Solution:
Word bits = log2 128 = 7‒bits
Number of blocks = Cache size / Words in each block = 1 K / 128 = 8
Number of block bits = log2 8=3‒bits
Number of address bits to address main memory = log2 64 K = log2 216 = 16‒bits
Tag bits = 16‒3‒7 = 6‒bits
Example : 7
How many total bits are required for a direct‒mapped cache with 16 kB of data and 4‒word blocks, assuming a 32‒bit address ?
Solution :
16 kB = 4K words = 212 words
Block size of 4 words = 210 blocks
Each block has 4 × 32 = 128 bits of data + tag + valid bit
Tag + valid bit = (32‒10‒2‒2) + 1= 19
Total cache size = 210 (128 +19) = 210 × 147
Therefore, 147 kB are needed for the cache.
Example : 8
You have been asked to design a cache with the following properties:
1) Data words are 32 bits each.
2) A cache block will contain 2048 bits of data.
3) The cache is direct mapped.
4) The address supplied from the CPU is 32 bits long.
5) There are 2048 blocks in the cache.
6) Addresses are to the word.
In the below Fig. 4.3.11, there are 8 fields (labeled a,b,c,d,e,f,g and h), you will need to indicate
the proper name or number of bits for a particular portion of this cache configuration.
Solution :
f. (name) ‒ You are being asked to show what part of a physical address form the index, offset and tag. < f > refers to the most significant bits of the address ‒so this is the tag.
g. (name) ‒ It follows that the next part of the address is the index.
h. (name) ‒ The least significant bits form the offset.
c. (name) ‒ There are 211 bits / block and there are 25 bits / word. Thus there are 26 words / block so we need 6 bits of offset.
b. (name) ‒ There are 211 blocks and the cache is direct mapped (or "1‒way set associative"). Therefore, we need 11 bits of index.
a. (name) ‒ The remaining bits form the tag. Thus, 32‒6‒11 = 15 bits of tag.
d. (name) ‒ Field< d > refers to the fact that a tag must be stored in each block. Thus, 15 bits are kept in each block.
e. (number) = Field< e > asks you to specify the total number of bits / block. This is 2048.
• We need to compare the valid bit associated with the block, the tag stored in the block and the tag associated with the physical address to determine if the cache entry is useable or not. The tags should be the same and the valid bit should be 1.
Cache size
• There are 2048 blocks in the cache and there are 2048 bits / block. There are 8 bits / byte. Thus, there are 256 bytes/block
2048 blocks × 256 bytes / block = 219 bytes (or 0.5 MB)
Example : 9
Consider web browsing application. Assuming both client and server are involved in the process of web browsing application, where can caches be placed to speed up the process? Design a memory hierarchy for the system. Show the typical size and latency at various levels of the hierarchy. What is the relationship between cache size and its access latency? What are the units‒of data transfers between hierarchies? What is the relationship between the data location, data size and transfer latency?
Solution :
a) Assuming both client and server are involved in the process of web browsing application, caches can be placed on both sides ‒ web browser and server.
b) Memory hierarchy for the system is as follows:
1. Browser cache, size = Fraction of client computer disk, Latency = Local disk latency.
2. Proxy cache, size = Proxy disk, Latency = LAN+ Proxy disk latencies
3. Server‒side cache, Size = Fraction of server disk,
Latency = WAN + Server disk
4. Server storage, size = server storage, latency = WAN + Server storage. Latency is not directly related to cache size.
c) The units of data transfers between hierarchies are pages.
d) Latency grows with page size as well as distance.
Measuring and Improving Cache Performance
Example: 1
Assume the miss rate of an instruction cache is 2% and the miss rate of the data cache is 4%. If a processor has a CPI of 2 without any memory stalls and the miss penalty is 100 cycles for all misses, determine how much faster a processor would run with a perfect cache that never missed. Assume the frequency of all loads and stores is 36%.
Solution :
The number of memory miss cycles for instructors in terms of the instruction count (I) is
Instruction miss cycle = I × 2% × 100 = 2.00 × I
As the frequency of all loads and stores is 36 %, we can find the number of memory miss cycles for data references:
Data miss cycles I × 36% × 4 % × 100 = 1.44 × I
The total number of memory‒stall cycles is 2.00 I + 1.44 I = 3.44 I. This is move than three cycles of memory stall per instruction. Accordingly, the total CPI including memory stalls is 2 + 3.44 = 5.44. Since there is no change in instruction count or clock rate, the ratio of the CPU execution times is
CPU time with stall / CPU time with perfect cache = [I × CPIstall × clock cycle] / [I × CPI perfect × clock cycle]
= CPI stall / CPI perfect = 5.44 / 2
The performance with the perfect cache is better by 5.44 / 2 = 2.72
• Hit time is the time to access the upper level of the memory hierarchy, which includes the time needed to determine whether the access is a hit or miss.
• Hit time cannot be the factor for determining the performance of the cache. The increase in hit time means increase in the access time of the memory system thus increasing the processor cycle time.
• If a larger cache is used, there is increase in the access time i.e. the hit time. But at a certain point, the increase in hit time due to larger cache results into decrease in miss rate i.e. the hit rate increases and so the cache performance also increases.
• Average Memory Access Time (AMAT) is the average time to access memory considering both hits and misses and the frequency of different accesses.
AMAT = Time for a hit + Miss rate × Miss penalty
• AMAT is used as way to examine alternative cache design.
Example : 2
Calculate AMAT for a processor with a 1 ns clock cycle time, a miss penalty of 10 clock cycles, a miss rate of 0.05 misses per instruction and a cache access time (including hit detection) of 1 clock cycle. Assume that the read and write miss penalties are the same and ignore other write stalls.
Solution:
AMAT = Time for a hit + Miss rate × Miss penalty
= 1 + 0.05 × 10
AMAT = 1.5 clock cycles = 1.5 ns
Reducing cache misses by more flexible placement of blocks
• In direct mapping, the position of a memory block is given by
(Block number) modulo (Number of blocks in the cache)
Thus, direct mapping has one‒to‒one associativity.
• In set‒associative mapping, there is set that contains the memory block and it is given as (Block number) modulo (Number of sets in the cache)
• Thus, to access a particular data all the tags of all the elements within the particular set must be searched.
• In a fully associative mapping as the block goes anywhere, all the tags of all the blocks must be searched.
• The increase in associativity decreases the miss rate and hence increases the performance of the cache. Since fully associative mapping has maximum flexibility in placing the blocks, it gives maximum performance.
Virtual Memory
Example : 1
The logical address space in a computer system consists of 128 segments. Each segment can have up to 32 pages of 4 K words each. Physical memory consists of 4 K blocks of 4 K words in each. Formulate the logical and physical address formats.
Solution :
Number of bits for segment address = log2 128 = log2 27 = 7 bits
Number of bits for page address = log2 32 = log2 25 = 5 bits
Number of bits for word address = log2 4096 = log2 212 = 12 bits
Number of bits for block address = log2 4096 = log2 212 = 12 bits
Example : 2
An address space is specified by 32 bits and corresponding memory space by 24 bits.
i) How many words are there in the address space?
ii) How many words are there in the memory space?
iii) If a page consists of 4 K words, how many pages and blocks are there in the systems.
Solution :
i) Words in the address space = 232 = 4 G words
ii) Words in the memory space = 224 = 16 M words
iii) Number of pages = Words in address space / Words per page = 4 G words / 4 K words
= 1 M pages
iv) Number of blocks = Words in address space / (Words per page/block)
= 16 M words / 4 K blocks = 4 K words
Example : 3
An address space is specified by 24 bits and the corresponding memory space by 16 bits. How many words are there in the virtual memory and in the main memory?
Solution :
Words in the address space, i.e., in the virtual memory
= 224= 16 M words
Words in the memory space, i.e., in the main memory
=224 = 64 K words
Example : 4
Calculate the effective address time if average page‒fault service time of 20 milliseconds and a memory access time of 80 nanoseconds. Let us assume the probability of a page fault 10%
Solution :
Effective access time is given as
= (1 − 0.1) × (80) + 0.1 (20 milliseconds)
= (1 − 0.1) × 80 + 0.1 × 20,000,000 = 72 + 2,000,000 (nanoseconds)
= 2,000,072 (nanoseconds)
Example : 5
Explain page replacement algorithms. Find out page fault for following string using LRU method
60 12 0 30 4 2 30 321 20 15
Consider page frame size = 3.
Solution :
Total page faults = 09
Example : 6
Explain page replacement algorithm. Find out page fault for following string using LRU method. Consider page frame size 3.
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1.
Solution : Reference string
Total page faults = 15
Computer Organization and Architecture: Chapter 4: Memory and IO : Tag: Computer : Computer Organization and Architecture - Memory and IO: Important Example Solved Problems
Computer Organization and Architecture: Chapter 4: Memory and IO
Under Subject
Computer Organization and Architecture
CW25201 3rd Semester IT department. | 2025 Regulation | 3rd Semester 2025 Regulation
Related Subjects
Discrete Mathematics
MA25C14 3rd Semester CSE,IT,CY,AIDS departments. | 2025 Regulation | 3rd Semester 2025 Regulation
Data Structures
CS25C08 3rd Semester CSE,IT,CY,AIDS departments. | 2025 Regulation | 3rd Semester 2025 Regulation
Computer Organization and Architecture
CW25201 3rd Semester IT department. | 2025 Regulation | 3rd Semester 2025 Regulation
Object Oriented Programming
CS25C07 3rd Semester IT department. | 2025 Regulation | 3rd Semester 2025 Regulation
Web Technologies
IT25301 3rd Semester IT department. | 2025 Regulation | 3rd Semester 2025 Regulation
English Communication Skills Laboratory I
EN25C03 3rd Semester all department. | 2025 Regulation | 3rd Semester 2025 Regulation
Skill Development Course I
3rd Semester all department. | 2025 Regulation | 3rd Semester 2025 Regulation