The Basics of Caches
1. Definition
Cache Block
The basic unit for cache storage. May contain multiple bytes/words of data.
Cache Line
Same as cache block. Note that this is not the same thing as a "row" of cache
Cache Set
A "row" in the cache. The number of blocks per set is determined by the layout of the cache (e.g., direct mapped, set-associative, or fully associative)
Tag
A unique identifier for a group of data. Because different regions of memory amy be mapped into a block, the tag is used to differentiate between them.
Valid Bit
A bit of information that indicates whether the data in a block is valid (1) of not (0).
2. Locating data in the cache
특정 주소가 주어졌을 때, 해당 메모리 위치에 저장된 데이터가 cache에 있는지 여부를 확인할 수 있다. 이를 위해, 다음과 같은 절차를 사용한다.
- address가 어떤 cache set에 있어야 하는지를 결정하기 위해 set index를 사용한다.
- 해당 cache set 내의 각 cache block에 대해, 해당 block에 연관된 tag와 memory address에서 가져온 tag를 비교한다. 일치하는 경우, 다음 단계로 진행한다. 일치하지 않으면, data는 cache에 없는 것이다.
- data를 찾은 block에서 valid bit를 확인한다. valid bit이 1이면 data가 cache 안에 있고, 아니면 없다.
만약, 그 주소에 있는 data가 cache에 있다면, 해당 cache block에서 data를 찾기 위해, 그 주소의 block offset을 사용한다.
cache에서 data를 찾는 데 필요한 모든 정보는 주소에 포함되어 있다. Fig. 1은 cache에서 data를 찾는데 사용되는 주소의 일부를 보여준다. 가장 끝 bits는 block offset을 결정하는 데 사용된다. block size가 B 이면 b = log2 B bit가 주소에서 필요하다. 다음으로 높은 bit group은 set index이며, 어느 cache set을 찾아볼지 결정하는 데 사용된다. cache 내 set 수가 S이면 set index에는 s = log2 S bit가 필요하다. fully-associative cache의 경우, set가 하나뿐이므로 set index가 없다. 나머지 bit는 tag로 사용된다. ℓ 이 주소의 길이 (in bits)이면, tag bit는 t = ℓ - b - s 이다.
Loading data into the cache
Cache에서 요청한 주소를 찾을 수 없으면, memory에서 가져와 cache에 넣는다. 요청된 주소와 함께, 공간적 지역성을 활용하기 위해 그 주변에 있는 다른 주소들도 함께 가져온다. 어떤 주소들이 가져와질지 결정하기 위해서는, 가져올 범위의 시작 주소와 끝 주소를 찾아야 한다. (+참고 1) 시작 주소는 주소의 block offset 부분을 0으로 만들면 찾을 수 있다. 끝 주소는 block offset을 모두 1로 바꾸면 된다. 이 범위의 크기는 항상 cache block의 크기와 같다. 그 범위의 데이터는 cache의 하나의 block에 저장된다.
Cache organization에 따라, data를 저장할 수 있는 위치가 여러 개일 수 있다. Direct mapped cache에서는 data를 넣을 수 있는 cache block이 하나뿐이다. 반면에 set-associative cache와 fully-associative cache에서는 n개의 다른 block 중에서 선택해야 한다. n-way set-associative cache의 경우, 각 set마다 n개의 location이 있으며, fully-associative cache에서는 들어오는 data block을 cache 내의 어떤 위치에나 넣을 수 있다.
+ 참고 설명
(+참고 1) 시작 주소는 주소의 block offset 부분을 0으로 만들면 찾을 수 있다.
예를 들어, block size B = 64 bytes 와 set S = 8 인 cache가 있다고 가정하고 computer system은 32bit architecture로 가정하면 address space는 2^32 byte이다.
이제 memory address 0x12345678 의 data에 access하려고 한다. (+참고 2) 이 주소의 block offset은 가장 낮은 6bit (64 = 2^6 라서)이고, 0x18의 값을 제공한다.
요청된 주소와 함께 cache로 가져올 범위의 시작 주소를 찾으려면 block offset bit를 모두 0으로 만들어야 한다. (+참고 3) 따라서, 시작 주소는 0x12345678 & 0xFFFFFFC0 를 하면 찾을 수 있으며, 이는 0x12345640이다. 이것은 요청된 주소가 포함된 cache block의 시작 부분의 memory address이다.
마찬가지로, 범위의 끝 주소를 찾으려면 block offset bit를 모두 1로 바꿔야 한다. (+참고 4) 따라서 끝 주소는 0x12345678 | 0x3F로 찾을 수 있으며, 이는 0x1234567F이다. 이것은 요청된 주소를 포함하는 cache block의 끝 부분의 memory address이다.
이 memory address 범위를 cache에 가져올 때, 요청된 주소를 포함한 시작 주소와 끝 주소 사이의 모든 데이터를 가져온다. 이 경우 64 bytes의 cache block과 바로 뒤에 있는 64 cache block이 포함된다.
+
(+참고 2) 이 주소의 block offset은 가장 낮은 6bit (64 = 2^6 라서)이고, 0x18의 값을 제공한다.
0x12345678은 16진수 표기법으로 된 32bit address이다. 이를 2진수로 변환하면 다음과 같다 :
0001 0010 0011 0100 0101 0110 0111 1000
가장 낮은 6 bits를 가져오기 위해서는 2진수에서 가장 오른쪽 6 bits를 가져오면 된다. 그러면
11 1000
이 나온다. 이것을 16진수로 변환하면
0x38
따라서 0x12345678의 가장 낮은 6 bits는 0x38이다.
+
(+참고 3) 따라서, 시작 주소는 0x12345678 & 0xFFFFFFC0 를 하면 찾을 수 있으며, 이는 0x12345640이다.
block size가 64 bytes인 경우, 가장 낮은 6 bits가 해당 주소의 block offset이다. 따라서, 0x12345678의 가장 낮은 6 bit는 11 1000 또는 0x38이다.
시작 주소를 찾기 위해서는 해당 block offset bit를 0으로 만들어야 한다. 그러므로 하위 6 bits를 0으로 만들기 위해 0xFFFFFFC0를 비트 AND 연산을 하면, 가장 낮은 bit가 모두 0이 되기에 block offset 부분이 0으로 바뀌게 된다. 따라서 0x12345640이 시작 주소이다.
+
(+참고 4) 따라서 끝 주소는 0x12345678 | 0x3F로 찾을 수 있으며, 이는 0x1234567F이다.
참고 3과 같은 방식이지만 이번에는 범위의 끝 주소를 찾으려면 block offset인 6 bits를 1로 바꿔야한다. 0x3F 를 비트 OR 연산을 하면, 가장 낮은 bit가 모두 1이 된다. 따라서 끝 주소는 0x1234567F가 된다.
+