CA & CO Chapter 4 practice problem

for the hexadecimal main memory addresses 111111, 666666, BBBBBB, show the following information, in hexadecimal format:

• Tag, Line, and Word values for a direct-mapped cache, using the format of Figure 4.10
• Tag and Word values for an associative cache, using the format of Figure 4.12
• Tag, Set, and Word values for a two-way set-associative caches, using the format of Figure 4.15

• 111111h = 0001 0001 0001 0001 0001 0001(2)
• 666666h = 0110 0110 0110 0110 0110 0110 (2)
• BBBBBBh = 1011 1011 1011 1011 1011 1011 (2)

Direct mapping ( 8 : 14 : 2 )

• 111111h
  - Tag : 0001 0001 (11h)
  - Line : 00 0100 0100 0100 (0444h)
  - word : 01(1h)
• 666666h
  - Tag : 0110 0110 (66h)
  - Line : 01100110011001 (1999h)
  - Word : 10 (2h)
• BBBBBBh
  - Tag : 1011 1011 (BBh)
  - Line 1011 1011 1011 10 (2EEEh)
  - Word : 11 (3h)

Assicoative mapping( 22 : 2 )

• 111111h
  - Tag : 0001 0001 0001 0001 0001 00 (044444h)
  - word : 01 (1h)
• 666666h
  - Tag : 011001100110011001100 (199999h)
  - Word : 10 (2h)
• BBBBBBh
  - Tag : 1011 1011 1011 1011 1011 10 (2EEEEEh)
  - Word : 11 (3h)

2-way set-associative mapping( 9 : 13 : 2)

• 111111h
  - Tag : 000100010 (22h)
  - Set :  001 0001 0001 00 (0444h)
  - word : 01(1h)
• 666666h
  - Tag : 0110 0110 0(CCh)
  - Set : 110 0110 0110 01(1999h)
  - Word : 10 (2h)
• BBBBBBh
  - Tag : 101110111 (177h)
  - Set 10111011101110 (EEEh)
  - Word : 11 (3h)

 

---

Consider the following code:

for(i = 0 ; i < 20 ; i++)
	for(j = 0 ; j < 10 ; j++)
    		a[i] = a[i]*j

• Give one example of the spatial locality in the code
   - 공간적 지역성 : 특정 데이터와 가까운 주소가 순서대로 접근될 경우
   --> i 가 for 루프 명령어와 함께 수행된다.
• Give one example of the temporal locality in the code
  - 시간적 지역성 : 특정 데이터가 한번 접근 되었을 경우 가까운 미래에 또 한번 데이터에 접근 할 가능성이 높다.
  --> for 루프를 돌며 a 배열에 i*j번 access 한다.

---

Consider a computer with the following characteristics : total of 1MB of main memory: word size of 1 byte; block size of 16 bytes; and cache size of 64KB.

main memory : 1MB

word : 1byte

block : 16byte

cache : 64KB

16word per block

cache line = memory block

cache slot = 16 bytes

if caches is 64Kb --> 64Kb/16 = 4096 cache slot

to address 4096 cache slots, we need 12 bits 

• For the main memory addresses of F0010, 01234 and CABBE, give the corresponding tag, cache line address, and word offsets for a direct-mapped cache.
  
  1. 16 word per block --> 4bits needed(2^4)
  2. cache 64Kb --> 64kb/16 - 4096 cache slot
  3. to address 4096 cache slots, need 12 bits(2^12)
  4. main memory size = 2^20 --> 주소 총 길이 20 bits
  5. word : cache slot : tag = 4 : 12 : 4
     • F0010 = 1111 0000 0000 0001 0000
       - word : 0000 (0)
       - cache : 0000 0000 0001 (001)
       - tag : 1111 (F)
     • 01234 = 0000 0001 0010 0011 0100
       - word : 0100(4)
       - cache : 000100100011(123)
       - tag : 0000(0)
       
       
     • CABBE = 1100 1010 1011 1011 1110
       - word : 1110(E)
       - cache : 101010111011(ABB)
       - tag : 1100(C)
• Give any two main memory addresses with different tags that map to the same cache slot for a direct-mapped caches.
  example) 1111 1111 1111
  
  • word offset = 1110
  • tag = 0000
  • Address = 0000 1111 1111 1111 1110 (0FFFE)
    
    
  • word offset = 0001
  • tag = 0010
  • Address = 0010 1111 1111 1111 0001 (2FFF1)
• For the main memory addresses of F0010 and CABBE, give the corresponding tag and offset values for a fully-associative cache.
  • F0010
    - word : 0h
    - tag : F001h
  • CABBE
    - word : Eh
    - tag : CABBh
• For the main memory addresses of F0010 and CABBBE, give the corresponding tag, cache set, and offset valeus for a two-way set-associative cache.
  • F0010 = 1111 0000 0000 0001 0000
    - tag : 0000(0)
    - cache set : 000 0000 0001(001)
    - word offset : 11110 (1E)
  • CABBE = 1100 1010 1011 1011 1110
    - tag : 1110(E)
    - cache set : 010 1011 1011(2BB)
    - word offset : 1 1001(19)

---

A computer has a cache, main memory, and a disk used for virtual memory. If a referenced word is in the cache, 20 ns are required to access it. If it is in main memory but not in the cache, 60 ns are needed to load it into the cache, and then the reference is started again. If the word is not in main memory, 12 ms are required to fetch the word from disk, followed by 60 ns to copy it to the cache, and then the reference is started again. The cache hit ratio is 0.9 and the main memory hit ratio is 0.6. What is the average time in nanoseconds required to access a referenced word on this system?

• 캐시에 있으면 20ns
• 캐시에 없으면 60ns
• 메모리안에 없으면 디스크에서 가져오는데 12ms (캐시에 복사하는데 60ns)
• 캐시 hit ratio = 0.9
• 메인 메모리 hit ratio = 0.6
• access referenced word on system 에 걸리는 평균 시간은?

위치	확률	시간
캐시 안에 있을 때	0.9	20
캐시에 없고 메인 메모리에 있을 때	0.1*0.6	60+20
캐시나 메모리 둘다에 없을 때	0.1*0.4	12000000 + 60 + 20

평균 = 0.9 * 20 + 0.06 * 80 + 0.04 * 12000080 = 480026(ns)

---