Solved CS 219 Ch 5 Worksheet 1 Spring 2026

Description

Purpose: Become familiar with MIPS cache implementation

Points:100 points

Reading/References: Chapter 5 (5.1, 5.2, 5.3, 5.4)

• Here is a series of address references given as words addresses:

13, 64, 48, 19, 2, 3, 11, 16, 21, 11, 3, 22, 4, 27, 6, 12, 4, 7, 8, and 24.

Show the hits and misses and cache contents (including previous, over-written values) for a two-way set-associative cache with one-word blocks and a total size of 16 words. You do not need to show the tag field.  Assume LRU replacement.  When done, include the hit ratio.               [25 pts]

Way 0                                Way 1

Set #	V	Address		Set #	V	Address
000				000
001				001
010				010
011				011
100				100
101				101
110				110
111				111

 

 

 

 

 

Table 1: Reference address to cache mapping

Address Decimal	Address Binary	Line ID/ Cache Set	Hit/Miss
Hit Ratio
Comments

1. b) Show the hits and misses and cache contents (including previous, over-written values) for a four-way set-associative cache with one-word blocks and a total size of 16 words. You do not need to show the tag field. Assume LRU replacement. When done, include the hit ratio. [25 pts]

Way 0                                                                    Way 1

Set #	V	Address		Set #	V	Address
00				00
01				01
10				10
11				11

 

Way 2                                                                        Way 3

Set #	V	Address		Set #	V	Address
00				00
01				01
10				10
11				11

 

 

 

 

 

 

 

 

 

 

 

 

Table 1: Reference address to cache mapping

Address Decimal	Address Binary	Line ID/ Cache Set	Hit/Miss
Hit Ratio
Comments

 

• Find the total bits required for given data size and calculate overhead in percentage:

 

1. i) How many total bits are required for a direct-mapped cache with 8KiB of data and 4-word blocks, assuming a 32-bit address? [15 pts]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. ii) What is the overhead (additional space required) for the 8KiB of data, expressed as a percentage (i.e., overhead / total required)? [10 pts]

Total Overhead bits=

Total Bits= data bits + overhead bits

% of overhead= overhead/total bits

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

• Explain the following with their locality principle and what are the advantages of each implementation:      [25 pts]

1. Direct-mapped cache with one-word per block
2. Direct-mapped cache with four-words per block

• Set-Associative Cache. (2-way or 4-way)

(Note: You can copy the figures from PPT or textbook as required)