CO101 Principle of Computer Organization
Assignment 4
Due: Dec 2, 2016
Name: Student Number:
1. In this exercise we look at memory locality properties of matrix computation. The following code is written in C, where elements within the same row are stored contiguously.
for (J=0; J<8000; J++) for (I=0; I<8; I++) A[I][J]=B[J][0]+A[J][I]; 1) How many 32-bit integers can be stored in a 16-byte cache line? 2) References to which variables exhibit temporal locality? 3) References to which variables exhibit spatial locality? 2. For a direct-mapped cache design with a 32-bit address, the following bits of the address are used to access the cache. Tag Index Offset 31—12 11—6 5—0 1) What is the cache line size (in words)? 2) How many entries does the cache have? 3) What is the ratio between total bits required for such a cache implementation over the data storage bits? 3. Media applications that play audio or video files are part of a class of workloads called streaming workloads; i.e., they bring in large amounts of data but do not reuse much of it. Consider a video streaming workload that accesses a 512 KB working set sequentially with the following address stream: 2, 4, 6, 8, 10, 12, 14, 16, ... 1) Assume a 64 KB direct-mapped cache with a 32-byte line. 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? Every 16 access, there’s 1 miss. 1/16 = 0.062500; Not sensitive to cache size and working set; Compulsory. 2) Re-compute the miss rate when the cache line size is 16 bytes, 64 bytes, and 128 bytes. What kind of locality is this workload exploiting? Miss rates are: 2/16, 2/64 and 2/128. Spatial. 3) “Prefetching” is a technique that leverages predictable address patterns to speculatively bring in additional cache lines when a particular cache line is accessed. One example of prefetching is a stream buffer that prefetches sequentially adjacent cache lines into a separate buffer when a particular cache line is brought in. If the data is found in the prefetch buffer, it is considered as a hit and moved into the cache and the next cache line is prefetched. Assume a two-entry stream buffer and assume that the cache latency is such that a cache line can be loaded before the computation on the previous cache line is completed. What is the miss rate for the address stream above? close to zero as the next entry is always brought to cache before accessing it.