assignment # 8

Q1

(a) Draw labeled diagram (showing block address(in hex) and tag bits of each block of main
memory (in

logical rectangular/linear form, assume data bus 8-bit) of main memory as per given cache
organization-

(i) cache capacity- 64B, cache-line 16B and Main memory 64KB (a)full associative (b) direct
mapped,

(For direct mapped-draw the logical rectangle diagram of main memory showing set-bits and tag-
bits as discussed in the class)

(ii) cache capacity- 1KB, cache-line 16B, 8-way associative , Main memory 64KB

(iii)cache capacity- 4KB, cache-line 256B and Main memory 4MB for all possible associative cases

(b) Calculate the overall cache capacity and percent overhead(of control data bits) of total(useful)
capacity of Q1(a), assume write back

(c) How the address field will be interpreted if CPU reads data, from cache of Q1(a), as -

(i) 16-bits data (ii) 128-bits data

Q2. Identify compulsory, capacity and conflict miss for cache of Q1a(i) and Q1a(ii) but main
memory of size 4KB.

The CPU generated 12-bit addresses are-

333 ,CF2, 801, A08, 748 ,ACA, C4A, 4A6, 8A5, 884, 8CF, 48A,

111, A0C, 4FF, 678, 3FC, 008, A65, 1CF, 243, 33F, 9AC, FF9

using replacement algorithm (assume initially cache is blank, all valid bits are 0 )

(i)FIFO (ii) LRU

Q3.Calculate the number of cache hit and miss for accessing given integer(32-bit) array.

Address generated by 12-bit CPU. MM is 4Ki Bytes, Block size is 16 Bytes,cache (data)size is 64
Bytes.

array start address is 0x800; declared as int a[10];

cache controller splits the CPU address as |set|tag|block-offset|

(b) for(i=0;i<10;i++)a[9-i]=a[i]

Can you suggest a modification in the cache organization which improves the cache hit for above
expressions?

Q4. The lower level memory is page-mode dual channel SDRAM (takes 80ns to fetch first 16B chunk
and rest

16B chunks each takes 30ns to fill a cacheline. Hint: this gives main memory access time) .

(a) How much time it takes to fill a cache line if size of cache line is (i) 256B (ii)2KB

(b)If the cache hit time is 10ns and cache hit rate is 96%, calculate the average cache access time
for (a).

Q5. Calculate the average cache access time for following-

(a)Level hit time(ns) (local) miss-rate

1 8 6%

2 34 8%

3 220 0

(b)Level hit time(ns) (local) miss-rate miss-penalty

1 8 6% 42ns

2 - 8% 254ns

Q6(a).Calculate total memory access time for following cache write algorithms-

(i) write through when write hit

(ii) write around when write miss

(iii) write back when write hit

(iv) write allocate when write miss (No cacheline replacement)

(v) write allocate when write miss (50% cacheline replacement)

(vi) write bypass(mark the cacheline if,data in cache. In next read for that data,it is treated
cachemiss, and replace with newer one)

case 1- use write algorithm (i) and (ii)

case 3- use write algorithm (iii) and (v)

case 4- use write algorithm (vi)

It is given single level cache memory having access time(read or write) is 10ns and main memory
access time(read or write) is 100ns.

CPU generates 1000 request of which 800 for read and 200 for write. 95% cache hit and 100% main
memory hit.

(b) Calculate performance enhancement (ratio of withoutcache to withcache ) ( calculate memory

Q7. In a system with cache of 256B with 32B cache-line ,the given programme segment is executed
.

Calculated hit rate if cache organization is -

(i) Direct mapped (ii) 2-way set associative (iii) 4-way set associative (iv) 8-way set associative

All variables are integer(4-byte) and array storage address starts from B000 .(storage of variables i,j
neglected)

(First array a elements are stored and element of array d in the last)

at 0xB000<-a[0][0];0xB004<-a[0][1];...0xB024<-a[0][9];0xB028<-a[1][0];.........0xB18C<-a[9][9];

0xB190<-b[0][0];....0xB31C<-b[9][9];0xB320<-c[0][0];....0xB4AC<-c[9][9];

0xB4B0<-d[0][0];....0xB62C<-d[9][9];

(a)row-wise(row major) storage of array

for(i=0;i<10;i++)a[i][0] +=b[i][0]+c[i][0]; where int a[10][10],b10][10],c10][10],d10][10]

for(i=9;i>=0;i--)d[0][i] =a[0][i]+b[0][i]+c[0][i];

(b)row-wise storage of array where int a[10],c[10],b[10],d[10]

for(i=0;i<10;i++)

a[i] +=b[i]+c[i];

for(i=0;i<10;i++)
d[i] =a[i]+b[i]+c[i];

(i) without loop merge (ii) with loop merge

(c) Calculate hit ratio for following Addresses for organization Q7(i) to Q7(iv)

0xB004,
0xB014,0xB008,0xB204,0xB084,0xB104,0xB02C,0xB220,0xB604,0xB560,0xB32C,0xB11C,0xB1F0,
0xB2CC,0xB628

0xB5C4,
0xB314,0xB444,0xB274,0xB394,0xB10C,0xB030,0xB2F0,0xB368,0xB088,0xB350,0xB20C,0xB150,0
xB33C,

(d) Repeat Q6(c) but all these address are arranged (re-coded; optimized by compiler) in ascending
order.