Information Technology Reference
In-Depth Information
5. Consider the execution of the following program segment on a 4
10 array
A. The two-dimensional array A is stored in the main memory in a column-
major order. Assume that there are eight blocks in the cache, each is just
one word, and that the LRU is used for replacement. Show a trace of the con-
tents of the cache memory blocks for the different values of indices j and k
assuming three different cache memory organizations, that is, direct, associ-
ative, and set-associative mapping. Provide your observations on the results
obtained.
SUM:
¼
0
For j:
¼
0to9do
SUM:
¼
SUM
þ
A(0,j)
End for
AVE:
¼
SUM
/
10
For k:
¼
0to9do
A(0,k):
¼
A(0, k)
/
AVE
End for
6. Consider the case of a 4
8 two-dimensional array of numbers, A. Assume
that each number in the array occupies one word and that the array elements
are stored row-major in the main memory for location 1000 to location 1031.
The cache consists of eight blocks each consisting of four words. Assume also
that whenever needed, LRU replacement policy is used. We would like to
examine the changes in the cache if each of the above three mapping tech-
niques is used as the following sequence of requests for the array elements
is made:
a
0,0
, a
0,1
, a
0,2
, a
0,3
, a
0,4,
, a
0,5
, a
0,6
, a
0,7
a
1,0
, a
1,1
, a
1,2
, a
1,3
, a
1,4
, a
1,5
, a
1,6
, a
1,7
a
2,0
, a
2,1
, a
2,2
, a
2,3
, a
2,4
, a
2,5
, a
2,6
, a
2,7
a
3,0
, a
3,1
, a
3,2
, a
3,3
, a
3,4
, a
3,5
, a
3,6
, a
3,7
Show the status of the cache before and after the given requests were made, the
number of replacements made, and an estimate of the cache utilization.
7. A computer system has an MM consisting of 1 M 16-bit words. It also has a
4 K word cache organized in the block-set-associative manner, with four
blocks per set and 64 words per block. Assume that the cache is initially
empty. Suppose that
the CPU fetches 4352 words from locations 0, 1,
2,
, 4351 (in that order). It then repeats this fetch sequence nine more
times. If the cache is 10 times faster than the MM, estimate the improvement
factor resulting from the use of the cache. Assume that whenever a block is to
be brought from the MM and the correspondence set in the cache is full,
the new block replaces the least recently used block of this set. Repeat for
the case of using the most recently used replacement technique; that is, if
the cache is full, then the new block will replace the most recently used
block in the cache. Note: This example is quoted from Reference #3.
...
Search WWH ::
Custom Search