Homework 4 ("Due" Friday, Dec 10 at 5:00 PM)

This assignment, while not required, will help you understand how caches with different geometries work and what the trade-offs between cache geometries are. We will post the solution for this assignment on Monday Dec. 13th for you to review and study before Wednesday's final exam. If you submit this assignment before we post the solution, we will treat your submission as additional work which can be used to raise the homework portion of your grade.

 

Run the following list of memory accesses against three different caches. Record the sequence of cache operations in three files as described below.

Cache Geometries

  • Direct Mapped: 2 word lines, 8 lines. Name this file dm.txt.

  • Fully Associative: 4 word lines, 4 lines. Name this file fa.txt.
    Fill empty spaces from top to bottom and use a LRU replacement algorithm. Use numbers to indicate which line in the (single) set you're referencing.

  • 2-Way Set Associative: 4 word lines, 2 lines. Name this file sa.txt.
    Name each set A and B respectively. For cache lines write the line then the set; for example, a reference to line 1 in set A would be written 1A. Fill in set A first, and use a LRU replacement algorithm.

For each cache, fill in the memory reference table with the cache lines that each address maps to, along with whether it is a hit or miss and whether a writeback occurs. You may assume each cache employs writeback and allocate-on-write policies. After you have done this, create a file with one line per reference with the format

 

<line number> <whitespace> <H or M> <whitespace> <1 or 0>

 

An example line in a file might look like (cache line 1, hit, no write-back):

 

1 H 0

 

Zip up the three files and submit them to the course dropbox


Memory references

 

This is a program of memory operations you will run against each cache.

Type

Data

Address

Cache Line number

Hit/Miss (H or M)

Writeback (1 or 0)

Load

 

0x100000A0

 

 

 

Load

 

0x10000000

 

 

 

Store

Life

0x10000044

 

 

 

Load

 

0x10000054

 

 

 

Load

 

0x10000050

 

 

 

Store

Is

0x100000B8

 

 

 

Load

 

0x10000064

 

 

 

Load

 

0x1000003C

 

 

 

Store

Not

0x10000090

 

 

 

Load

 

0x10000084

 

 

 

Store

Cert

0x100000AC

 

 

 

Load

 

0x1000001C

 

 

 

Load

 

0x10000038

 

 

 

Load

 

0x1000006C

 

 

 

Store

1st

0x10000020

 

 

 

Store

Dess

0x10000060

 

 

 

                               

The memory

 

Each English word is stored in a four-byte word in memory. In this table, the (32-bit) address of each word is given by the sum of the number on the left and the number on the top, so the word "four" is stored in the 32-bit word stored starting at byte 0x1000001C and ending at byte 0x1000001F.

Address

0x0

0x4

0x8

0xC

0x10000000

yes

i

have

a

0x10000010

drem

that

my

four

0x10000020

litl

chil

will

grow

0x10000030

up

in

an

amer

0x10000040

wher

they

are

judg

0x10000050

not

by

the

colr

0x10000060

of 

ther

skin

but

0x10000070

by

the

cont

of

0x10000080

ther

char

...

free

0x10000090

at

last

free

at

0x100000A0

last

free

at

last

0x100000B0

mart

luth

king

jr