Computer Architecture

The format of this document is as follows: First, I give a practice problem for which the solution is also provided. In bold italic font, I slightly modify the problem for your homework.

5) Given a byte-addressable memory with 256 bytes, suppose a memory dump yields the results shown below. The address of each memory cell is determined by its row and column. For example, memory address 0x97 is in the 9th row, 7th column, and contains the hexadecimal value 43. Memory location 0xA3 contains the hexadecimal value 58.

The system from which this memory dump was produced contains 4 blocks of cache, where each block consists of eight bytes. Assume the following sequence of memory addresses take place: 0x2C, 0x6D, 0x86, 0x29, 0xA5, 0x82, 0xA7, 0x68, 0x80, and 0x2B.

(5 pts) How many blocks of main memory are there?

SOLUTION: We know that we have 256 bytes of main memory and each (memory and cache) block is 8 bytes, 256/8 = 32 blocks of main memory

b) (10 pts) Assuming a direct mapped cache:

i) Show the format for a main memory address assuming direct mapped cache.

SOLUTION: 3-bit tag / 2-bit block / 3-bit offset

ii) What does cache look like after the ten memory accesses have taken place? Draw the cache and show contents and tags.

SOLUTION:

Block #	Tag	Data
00	100	CD,80,64,B3,8D,81,A7,DB
01	001	18,3C,9D,1F,2F,78,44,1E
10
11

iii) What is the hit rate for this cache on the given sequence of memory accesses?

SOLUTION:

2C: miss, loaded into block 01

6D: miss, loaded into block 01

86: miss, loaded into block 00

29: miss, loaded into block 01

A5: miss, loaded into block 00

82: miss, loaded into block 00

A7: miss, loaded into block 00

68: miss, loaded into block 01

80: miss, loaded into block 00

2B: miss, loaded into block 01

Hit rate is 0%

c) (10 pts) Assuming a fully associative cache:

i) Show the format for a main memory address.

SOLUTION:

5-bit tag / 0-bit block or set / 3-bit offset

ii) Assuming all cache blocks are initially empty, blocks are loaded into the first available empty cache location, and cache uses a first-in-first-out replacement policy, what does cache look like after the ten memory accesses have taken place?

SOLUTION:

FIFO tells us which block in the cache will be used to load a recently needed memory block into the cache. It advances from 0 to 3 and then restarts from 0 (thus evicting the oldest block from the cache whenever a new memory block is read due to a cache miss)

2C: miss, loaded into block 00

6D: miss, loaded into block 01

86: miss, loaded into block 10

29: hit, uses cache block 00 that has the same tag (00100)

A5: miss, loaded into block 11

82: hit, uses cache block 10 that has the same tag (10000)

A7: hit, uses cache block 11 that has the same tag (10100)

68: hit, uses cache block 01 that has the same tag (01101)

80: hit, uses cache block 10 that has the same tag (10000)

2B: hit, uses cache block 00 that has the same tag (00101)

Block #	Tag	Data
00	00101	18,3C,9D,1F,2F,78,44,1E
01	01101	B4,C2,53,FB,E3,8C,0C,9B
10	10000	CD,80,64,B3,8D,81,A7,DB
11	10100	52,57,A3,58,55,0F,E8,F6

iii) What is the hit rate for this cache on the given sequences of memory accesses?

SOLUTION: Hit rate is 6/10 = 60%

HW PROBLEM 5: Redo the question for the case that each cache block consists of four bytes

--OSEFB ABC2772-656 EE1750-9BD64404A0 00 | 6 4 9 9 5 C 4 1 F B C A 8C2 3843E709AC8EEFF3 2A8B23CCA3DDE-495 8A7C9886_DB43FC1 C-54F3-273E10 91739D B0297-E2-CFB-217A 4BFF88B7EA9F8-32 7E1B84F9B51DC77F 7EDE56396D3C0F58 399C8B5D67C7AF6D 1AC50427A70-26A55 D93C22CDBOF-9740 3D1E83B4FC9985c CBD165B0B36ED6FF AB6E7206D4FEDD36 (o | 0 8 2 8 A 1 E 9 7 2 8 B E A 36 699-BB2200-AAE75863 CD500 | 7 A 0 A 8 4 5 3 6 6 6 E 3-7D ,9 7 6 A D F 3 4 8 6 CC44 7F5E5F19BD5C2485 C3392840|4D3C590D 92F20AC365A-FA-72 2 5 2 4 7 9 6 B F O 8 7 1 D5B6 DE-B6-12A8255034|E c9AEB90-ID-2620BB D | 3 4 6 B 4 3 C 6 5 2 2 5 1 A 0123456789ABCDEF