ENGR 325 HOMEWORK 7.

ENGR 325 HOMEWORK 7. 1. (5) 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. Assume each word is a 32-bit integer. (P&H 5.1, §5.1) for (I=0; I8; I++) for (J=0; J8000; J++) A[I][J]=B[I][0]+A[J][I]; a. How many 32-bit integers can be stored in a 16-byte cache block? b. References to which variables exhibit temporal locality? c. References to which variables exhibit spatial locality? Locality is affected by both the reference order and data layout. The same computation can also be written below in Matlab, which differs from C by storing matrix elements within the same column contiguously in memory. for I=1:8 for J=1:8000 A(I,J)=B(I,0)+A(J,I); end end d. How many 16-byte cache blocks are needed to store all 32-bit matrix elements being referenced? e. References to which variables exhibit temporal locality? f. References to which variables exhibit spatial locality? SOLUTION: a. Each 32-bit integer requires 4 bytes to store, therefore FOUR 32-bit integers can be stored in the 16-byte block. b. Consider the access sequence: A[0][0] = B[0][0] + A[0][0] A[1][0] = B[0][0] + A[0][1] A[2][0] = B[0][0] + A[0][2] … A[7999][0] = B[0][0] + A[0][7999] A[0][1] = B[1][0] + A[1][0] … ⇒ Variables I, J, and B[I][0] exhibit temporal locality. This study source was downloaded by from CourseH on :50:37 GMT -05:00 P a g e | 2 c. Variables A[I][J] and B[I][0] exhibit spatial locality. d. Consider the access sequence: A(1,1) = B(1,0) + A(1,1) A(1,2) = B(1,0) + A(2,1) A(1,3) = B(1,0) + A(3,1) … A(1,8000) = B(1,0) + A(8000,1) A(2,1) = B(2,0) + A(1,2) A(2,2) = B(2,0) + A(2,2) … A(2,8000) = B(2,0) + B(8000,2) … A(8,1) = B(8,0) + A(1,8) A(8,2) = B(8,0) + A(2,8) … A(8,8000) = B(8,0) + A(8000,8) Matrix A begins as an 8-row by 8000-column matrix and is transformed into an 8000-row by 8- column matrix. So for the A matrices: Elements = 8 x 8000 = 64,000 Total elements in the beginning and ending matrix: 64000 x 2 = 128,000 Matrix elements per cache block: 4, as per 5.1.1. Total cache blocks: 128,000 ÷ 4 = 32,000 Note, however, that the “upper left” eight by eight elements overlap, so cache is not needed for those. Therefore we can subtract 8 x 8 ÷ 4 = 16 cache blocks. For the B matrix: Elements = 8 x 1 = 8 Matrix Elements per cache block: 4, as above Total cache blocks: 8 ÷ 4 = 2 Total 16-byte cache blocks = 32000 – 16 + 2 ⇒ 31,986 cache blocks are required. e. As in 5.1.2, variables I, J, and B(I,0) exhibit temporal locality. f. Unlike in C, in MATLAB matrix elements in the same column are stored contiguously. Therefore the variables A(J,I) and B(I,0) exhibit spatial locality. 2. (10) Caches are important to providing a high-performance memory hierarchy to processors. Below is a list of 32-bit memory address references, given as word addresses: 3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253 (P&H 5.2, §5.3) a. For each of these references, identify the binary address, the tag, and the index given a directmapped cache with 16 one-word blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty. This study source was downloaded by from CourseH on :50:37 GMT -05:00 P a g e | 3 b. For each of these references, identify the binary address, the tag, and the index given a directmapped cache with two-word blocks and a total size of 8 blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty. c. You are asked to optimize a cache design for the given references. There are three directmapped cache designs possible, all with a total of 8 words of data: C1 has 1-word blocks, C2 has 2-word blocks, and C3 has 4-word blocks. In terms of miss rate, which cache is the best? If the miss stall time is 25 cycles, and C1 has an access time of 2 cycles, C2 takes 3 cycles, and C3 takes 5 cycles, which is the best cache design? SOLUTION: a. Consider the table below. Direct Mapped Cache, 16 1-Word Blocks Address Tag Index Decimal Binary (low byte) Binary (low 4 bits) Decimal Binary Decimal Hit/Miss Miss Miss Miss Miss Miss Miss Miss Miss Miss Miss Miss Miss This study source was downloaded by from CourseH on :50:37 GMT -05:00 P a g e | 4 b. Consider the table below. Direct Mapped Cache, 8 2-Word Blocks Address Tag Index Decimal Binary (low byte) Binary (low 4 bits) Decimal Binary Decimal Hit/Miss 3 0000 0 001 1 Miss Miss Miss Hit Miss Miss Hit Miss 181 1011 11 010 2 Hit Miss Miss Miss c. Consider the table below. Address Tag C1 C2 C3 Dec Bin Dec Bin Index Hit/ Miss Index Hit/ Miss Index Hit/ Miss low byte 5 bits Bin Dec Bin Dec Bin Dec M 01 1 M 0 0 M M 10 2 M 1 1 M M 01 1 M 0 0 M M 01 1 M 0 0 M M 11 3 M 1 1 M M 00 0 M 0 0 M M 11 3 H 1 1 H M 11 3 M 1 1 M M 10 2 H 1 1 M M 00 0 M 1 1 M M 01 1 M 0 0 M M 10 2 M 1 1 M.