Tutorial 4 PDF

Preview

Summary

Tutorial 4: WRES1201 Computer System Architecture What is the general relationship among access time, memory cost and capacity? As access time becomes faster, the cost per bit increases. As memory size increases, the cost per bit is smaller. Also, with greater capacity, the access time becomes slowe...

Description

Tutorial 4: WRES1201 Computer System Architecture 1. What is the general relationship among access time, memory cost and capacity? As access time becomes faster, the cost per bit increases. As memory size increases, the cost per bit is smaller. Also, with greater capacity, the access time becomes slower. 2. What are the differences among direct mapping, associative mapping and set associative mapping? Direct mapping maps each block of main memory into only one possible cache line. Associative mapping permits each main memory block to be loaded into any line of the cache. The set-associative mapping combines both methods while decreasing disadvantages. The cache consists of a number of sets, each of which consists of a number of line. 3. Consider a machine with a byte addressable main memory of 2 16 bytes and block size of 8 bytes. Assume that a direct mapped cache consisting of 32 lines is used with this machine. a. How is a 16-bit memory address divided into tag, line number, and byte number? Memory address=16 Total caches memory line =32 Size per lines=8byte 8=2^w W=3 32=2^r r=5 line=5bit bytenumber=3bit tag=8bit

b. Into what line would bytes with each of the following addresses be stored? i. 0001 0001 0001 1011 tag 0001 0001

line 00011 0000 0011=3h

Byte 011

ii. 1100 0011 0011 0100 tag line 1100 0011 00110 0000 0110=6h

Byte 100

iii. 1101 0000 0001 1101 tag line 1101 0000 00011 0000 0011=3h

Byte 101

iv. 1010 1010 1010 1010 tag line Byte 1010 1010 10101 010 1 1=15h v. c. Suppose the byte with address 0001 1010 0001 1010 is stored in the cache. What are the addresses of the bytes stored along with it? tag line Byte 0001 1010 00011 010 0001 1010=1Ah 0000 0011=3h 2h d. How many total bytes of memory can be stored in the cache? 256bytes e. Why is the tag also stored in the cache? Because two items with two different memory addresses can be stored in the same place in the cache.

4. A cache has 64KB capacity, 128byte per lines and is 4-way set-associative. The system containing the cache uses 32-bit addresses. How many lines and sets does the cache have? Cache Size = 64KB = 2^16 Bytes Line Size = 128 Bytes Number of Lines = 2^16 / 128 = 29 = 512 As cache is 4-way set associative. Number of sets = 512/4 = 128

5. Describes three method used by cache memory to do replacement policy? When a MM block needs to be brought in while all the CM blocks are occupied, one of them has to be replaced. The selection of this block to be replaced can be determined in one of the following ways. a. Optimal Replacement: replace the block which is no longer needed in the future. If all blocks currently in CM will be used again, replace the one which will not be used in the future for the longest time. b. Random selection: replace a randomly selected block among all blocks currently in CM. c. FIFO (first-in first-out): replace the block that has been in CM for the longest time. d. LRU: replace the block in CM that has not been used for the longest time, i.e., the least recently used (LRU) block.

6. What are the differences between write-through and write-back? Write-through: Write is done synchronously both to the cache and to the backing store. Write-back (or Write-behind): Writing is done only to the cache. A modified cache block is written back to the store, just before it is replaced. Write-through: When data is updated, it is written to both the cache and the back-end storage. This mode is easy for operation but is slow in data writing because data has to be written to both the cache and the storage. Write-back: When data is updated, it is written only to the cache. The modified data is written to the back-end storage only when data is removed from the cache. This mode has fast data write speed but data will be lost if a power failure occurs before the updated data is written to the storage. 7. Consider a direct mapping single-level cache with an access time of 2.5ns, a line size of 64 bytes, and a hit ration of H= 0.95. Main memory uses a block transfer capability that has first-word (4 bytes) access time of 50ns and an access time of 5 ns for each word thereafter. a. What is the access time when there is a cache miss? Assume that the cache waits until the line has been fetched from main memory and then reexecutes for a hit. b. Tmiss = 2.5 + 50 + (15)(5) + 2.5 = 130ns c. Suppose that increasing the line size to 128 bytes increases the H to 0.97. Does this reduce the average memory access time?

. Ts = (0.95)(2.5) + (0.05)(130) = 8.875ns After modification, Ts = (0.97)(2.5) + (0.03)(210) = 8.725ns Therefore average memory access time is reduced.

8.

For a system with two levels of cache, define T c1 = first level cache access time; Tc2 = second level cache access time; Tm = main memory access time; H 1 = first level hit ratio; H2 = combined first/second level hit ratio. Provide an equation for Ta for a read operation. Effective Access Time = Hit rate * Cache access time + Miss rate * Lower level access time Average access Time For Multilevel Cache:(Tavg) Tavg = H1 * C1 + (1 – H1) * (H2 * C2 +(1 – H2) *M )...