Media applications that play audio or video files are part of a class of workkloads called "streaming" workloads (i.e., they bri
ng in large amounts of data but do not reuse much of it). Consider a video streaming workload that accesses a 512 KiB working set sequentially with the following word address stream:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ...
a) Assume a 64 KiB direct-mapped cache with a 32-byte block. What is the miss rate for the address stream above? How is this miss rate sensitive to the size of the cache or the working set? How would you categorize the misses this workload is experiencing, based on the 3C model?
b) Re-compute the miss rate when the cache block size is 16 bytes, 64 bytes, and 128 bytes. What kind of locality is this workoad exploiting?
c) "Prefetching" is a technique that leverages predictable address patterns to speculatively bring in additoinal cache blocks when a particular cache block is accessed. One example of prefetching is a stream buffer that prefetches sequentially adjacent cache blocks into a separate buffer when a particular cache block is brought in. If the data are found in the prefetch buffer, it is considered as a hit, moved into the cache, and the cache block is prefetched. Assume a two-entry stream buffer; and, assume that the cache latency is such that a cache block can be loaded before the computation of the previous cache block is completed. What is the miss rate for the address stream above?
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ...
a) Assume a 64 KiB direct-mapped cache with a 32-byte block. What is the miss rate for the address stream above? How is this miss rate sensitive to the size of the cache or the working set? How would you categorize the misses this workload is experiencing, based on the 3C model?
b) Re-compute the miss rate when the cache block size is 16 bytes, 64 bytes, and 128 bytes. What kind of locality is this workoad exploiting?
c) "Prefetching" is a technique that leverages predictable address patterns to speculatively bring in additoinal cache blocks when a particular cache block is accessed. One example of prefetching is a stream buffer that prefetches sequentially adjacent cache blocks into a separate buffer when a particular cache block is brought in. If the data are found in the prefetch buffer, it is considered as a hit, moved into the cache, and the cache block is prefetched. Assume a two-entry stream buffer; and, assume that the cache latency is such that a cache block can be loaded before the computation of the previous cache block is completed. What is the miss rate for the address stream above?
1 answer:
You might be interested in
Answer:
p(x,n)
1. if(n==0) [if power is 0]
2. then result =1.
3.else
4. { result=1.
5. for i=1 to n.
6. { result = result * x. } [each time we multiply x once]
7. return result.
8. }
Let's count p(3,3)
30, so come to else part.
i=1: result = result *3 = 3
i=2: result = result *3 = 9
i=2: result = result *3 = 27
Explanation:
here the for loop at step 4 takes O(n) time and other steps take constant time. So overall time complexity = O(n)