Fully-Associative vs Direct-Mapped vs Set-Associative Cache

- 캐시 메모리 시리즈 모아보기 - 
https://microelectronics.tistory.com/102

캐시 메모리의 매핑 종류

1. Fully-Associative Cache (완전 연관 사상 방식 캐시 메모리)

1.1 Block 배치 방식

CPU가 메모리 주소에 접근할 때, 모든 캐시 라인의 태그를 찾는 방식의 캐시메모리이다.

예를들어, cache line(block)이 16B 인 128B 사이즈의 캐시가 있다고 가정해보자.

16B는 2^4 로, 주소의 하위 4비트는 라인 내부의 어드레싱에 사용되니, TAG 사이즈는 주소의 상위 28비트면 충분하다.

 

1.2 하드웨어 구현과 이로인한 단점

캐시의 모든 block을 검색하는 것은 비효율적이다. 모든 block을 한 번에 검색하려면 각 entry마다 comparator와 AND gate가 필요하며, 이는 하드웨어 비용이 너무 많이 든다.

만약, 모든 block을 순차적으로 검색하면 여러 cycle이 소모되며 즉각적인 결과를 얻기 어렵다.

 

장점은, 메모리 데이터가 어떤 캐시 라인에도 존재할 수 있지만, 위에서 언급한 비교기의 비용문제(단점)으로 인해, 정말 작은 사이즈의 캐시가 아니라면 장점은 있으나 마나이다. 

2. Direct-Mapped Cache (직접 사상 방식 캐시 메모리)

2.1 Block 배치 방식

Direct-mapped cache는 각 주소를 하나의 고정된 캐시 block에 매핑한다. 이를 위해 modulo 연산을 사용해 주소를 캐시의 특정 위치로 매핑한다.

예를 들어, 8개의 entry가 있는 캐시(캐시 라인은 4바이트, 1 word 라고 가정)에서 메모리 주소 Z 는 Z % 8 의 결과(나머지 연산)에 따라 entry에 매핑된다.
주소 1의 경우 1 % 8의 결과는 1이므로, 1번  entry에 매핑된다. 마찬가지로 주소 8은 8 % 8의 결과가 0이므로 0번 entry에 다시 매핑된다.

즉, 메모리 데이터가 캐시의 '지정된 하나의 line' 으로만 적재된다.

 

2.2 하드웨어 구현

주소의 하위 비트를 활용해 block 위치를 결정하고, 나머지 비트는 tag로 사용된다. 

16B 캐시라인의 128B 캐시를 예로 들면, 라인 엔트리(개수) 는 8개가 될 것이다. (2^7/2^4=2^3)

그러니까 address 의 [6:4]에 해당하는 3비트를 비교기로 비교하여 적재될 라인 넘버를 찾는다. (하위 4비트는 라인 내부 어드레싱)

 

그럼 태그는 상위 25비트에 해당한다. (32비트 - 비교 비트 3비트 - 라인 내부 어드레싱 비트 4비트 = 25비트)

이 방식은 block 위치를 쉽게 찾을 수 있게 해주며, tag 비교를 통해 데이터가 캐시에 있는지를 판단할 수 있다.

 

2.3 장점 : 간단한 검색

주소를 통해 modulo 연산으로 한 번에 데이터 위치를 확인할 수 있어 검색이 쉽고 빠르다.

즉, 비교기 하나로 특정 메모리 주소의 cache hit/miss 여부를 확인 할 수 있다. (물론, 주소와 태그의 비교는 따로 해야한다.)

따라서 하드웨어 설계가 단순해지고, 빠른 검색이 가능하다.

 

2.4 단점 : 비유연성

같은 캐시 block에 매핑되는 여러 주소가 충돌할 경우 하나의 데이터만 저장할 수 있어 캐시의 활용 효율이 떨어질 수 있다. 이러한 충돌은 캐시의 다른 공간이 비어 있어도 발생할 수 있으며, 이를 캐시의 conflict miss라고 한다.

16B 캐시라인의 128B 캐시를 예로 들면, 

• 0x00000000 의 [6:4] 는 000으로 라인넘버 0에 적재될 것이다.
• 0x00000080 의 [6:4] 는 000으로 라인넘버 0에 적재 될 것이다.
• 즉 0x00000000과 0x00000080 를 계속 분기한다면 캐시 효율이 저하된다.

따라서 동일한 modulo 연산을 통해 매핑된 여러 주소가 충돌할 경우, 캐시 공간을 효율적으로 사용하지 못한다.

 

3. Set-Associative Cache

Set-associative cache는 fully-associative cache의 유연성과 direct-mapped cache의 효율성을 결합한 캐시 구조다.

기본적으로 캐시를 몇개의 Set 과 몇개의 Way 로 구분한다.

각 메모리 주소는 하나의 set에만 매핑되지만, 각 set은 여러 개의 block을 포함할 수 있어 유연성이 증가한다.

Set 내에 속한 block(line)의 개수를 Way 라고 한다.

 

3.1 Block 배치 방식

메모리 주소는 modulo 연산을 사용해 특정 set에 매핑된다.

예를 들어, 8개의 entry로 구성된 캐시에서 4개의 set이 있다고 가정하면, 각 set에는 2개의 block이 있다.

위 그림과 같이 1 word 캐시 라인 사이즈의 경우를 예로 들면

• 주소 0x0은 0 %  4 의 결과로 set 0에 매핑된다. 주소 0x8도 동일하게 set 0에 매핑된다.
• 주소 0x1은 1 %  4 의 결과로 set 1에 매핑되며, 주소 0x는 2 % 4의 결과 set 2에 매핑된다.

 

3.2 하드웨어 구현

예를 들어, 128B캐시에 16B라인이면 라인 개수는 8개이다.

이를 2개의 line 으로 구성된 4개의 set 으로 분할한다면 4-set 2-way 구조가 된다.

주소에 따라 해당 메모리 영역은 고정된 set 에 적재되지만 way는 자유롭게 배정 가능하다. 그러니까 Set 내의 line들은 fully-associative cache 처럼 동작한다는 것이다.

메모리 주소의 비트에 대해서 구체적으로 얘기해보면

4set 이니까 address의 [5:4] 은 set 을 지정하는 비트이고, 태그는 메모리 주소의 상위 26비트에 해당한다.

그리고 비교기는 way개수만큼만 존재하면 된다.

• 0x00000000 의 [5:4]는  00 으로 set 0에 저장되고 그 내부의 아무 line에 저장됨.
• 0x00000020 의 [5:4] 는 10 으로 set 3에 저장되고 그 내부의 남은 line에 저장됨.
• 0x00000021 의 [5:4] 는 10 으로 set 3에 저장되고 그 내부의 남은 line에 저장됨.

3.3 장점

간단한 검색: 특정 주소의 set을 찾고, 해당 set의 block을 검색하면 되기 때문에 검색이 상대적으로 쉽다.

유연성: 같은 set 내에서는 데이터가 어떤 block에든 적재될 수 있어 충돌 미스(conflict miss)가 줄어든다.

 

3.4 단점

제한된 유연성: fully-associative cache처럼 모든 위치에 데이터를 저장할 수 있는 것은 아니며, set 내에서만 유연성이 제공된다.

복잡성 증가: direct-mapped cache보다 복잡하며, set 내의 모든 block을 검색해야 하므로 하드웨어 설계가 더 복잡해질 수 있다.

 

4. 프로세서의 캐시 구성 예시

4.1 Intel Ivy Bridge 프로세서 (2012,  4-core, x86 )

반응형

• L1 I-cache 와 D-cache 각각 32KB, 8-way set associative, 64-byte line.
• L2 캐시는 256KB, 8-way set associative, 64-byte line.
• L3 캐시는 8MB, 16-way set associative, 64-byte line.
• 특징 : 모든 계층의 line 사이즈가 동일해 데이터 이동이 용이하다.

4.2 Qualcomm Krait 프로세서 (2012, 4-core, ARM)

• L0 I-cache 와 D-cache 각각 4KB, direct-mapped
• L1 I-cache 와 D-cache 각 16KB, 4-way set associative, 64-byte line
• L2는 1MB, 8-way set associative, 64-byte line
• 특징 : L0 캐시는 에너지 절감을 위해 설계된 필터 캐시(filter cache)로, 간단하고 효율적이다. 큰 캐시일수록 더 높은 associativity를 가지며, 이는 충돌 가능성을 줄이기 위함이다.

결론

Direct-mapped cache는 단순성과 빠른 검색 속도를 제공하지만, 충돌로 인한 cache miss가 발생할 수 있다.

Fully-associative cache는 높은 유연성으로 충돌 문제를 줄일 수 있으나, 하드웨어적인 비용이 매우 비싸다.

Set-associative cache는 이 두 가지의 장점을 적절히 결합해 유연성과 효율성을 모두 제공하며, 현대 캐시 설계에서 가장 흔히 사용되는 방식이다.

 

Reference

• https://www.youtube.com/watch?v=HEbihdxoam8&list=PL9YOoYsOKCKA-r0uYHnG53jgU0xyScAdh&index=6
• https://www.youtube.com/watch?v=X2R1dzk0vRY&list=PL9YOoYsOKCKA-r0uYHnG53jgU0xyScAdh&index=7
• https://www.youtube.com/watch?v=vIj3wOefI98&list=PL9YOoYsOKCKA-r0uYHnG53jgU0xyScAdh&index=8
• https://www.extremetech.com/computing/182899-snapdragon-805-detailed-benchmarked-kraits-last-hurrah-and-the-arrival-of-a-new-gpu-king