CPU Cache에 대해 학습하며 작성된 글입니다. 학습 과정에서 작성된 글이기 때문에 잘못된 내용이 있을 수 있으며, 이에 대한 지적이나 피드백은 언제든 환영입니다.
1. CPU Cache
CPU 캐시는 CPU가 메인 메모리에서 데이터에 접근하는 평균 비용(시간 또는 자원)을 줄이기 위해 사용하는 하드웨어 캐시입니다. 이는 CPU 코어에 가깝게 있는 작고 빠른 메모리로, 자주 사용하는 데이터의 복사본을 메인 메모리로부터 복사해 저장합니다. CPU 캐시는 CPU가 데이터에 접근할 때, 먼저 캐시를 검사해 필요한 데이터가 존재하는지 확인하는 방식으로 동작하며, 해당 데이터가 캐시에 있으면 이를 반환합니다.
대부분의 현대 CPU는 L1, L2, L3 등과 같은 여러 계층의 캐시를 포함합니다. 각 계층의 캐시는 크기와 속도가 다르며 서로 다른 특징을 가지는데, 이에 대해 하나씩 살펴보겠습니다.
캐시는 주로 SRAM(Static RAM)으로 구현되지만, 모든 캐시 레벨에서 SRAM이 독점적으로 사용되는 것은 아닙니다. 일부 레벨에서는 eDRAM과 같은 다른 메모리 유형도 사용될 수 있습니다.
1-1. L1 Cache
L1 캐시는 CPU 내부에 위치하며 각 CPU 코어마다 별도로 존재합니다. 이는 데이터 캐시와 명령어 캐시로 구성되어 있는데, 데이터 캐시는 처리된 데이터를 저장하고, 명령어 캐시는 CPU가 실행해야 할 명령어와 관련된 정보를 저장합니다. L1 캐시의 크기는 CPU 모델에 따라 다르며, 일반적으로 256KB 정도의 용량을 가지지만, 특정 모델에서는 더 큰 크기를 가지는 경우도 있습니다. L1 캐시는 CPU 코어와 밀접하게 연결되어 있으며, 빠른 액세스를 통해 메모리 액세스 속도를 향상시키고 작업 효율성을 높입니다. 하지만 L1 캐시는 크기가 작기 때문에 데이터와 명령어의 효율적인 관리가 중요합니다.
L1 캐시는 CPU 성능 향상과 관련된 핵심 요소 중 하나로, 다른 캐시 계층과 협력하여 전체 시스템 성능을 최적화합니다.
1-2. L2 Cache
L2 캐시는 CPU의 고속 메모리 중 하나로, L1 보다 큰 용량을 가집니다. 이는 L1 캐시에서 필요한 데이터를 찾지 못했을 때 사용되며, 메인 메모리보다 훨씬 빠르게 데이터를 읽을 수 있습니다. 최신 CPU에서는 L2 캐시가 CPU 안에 있고, 여러 CPU 코어가 이를 공유하기도 합니다. 하지만 이는 CPU 마다 다른데, 아닌 경우라면 각 코어마다 자신만의 L2 캐시를 가질 수 있습니다. L2 캐시의 크기는 CPU 모델마다 다르지만, 일반적으로 코어당 256KB ~ MB 사이입니다.
1-3. L3 Cache
L3 캐시는 L1 및 L2 캐시와 함께 CPU의 계층적 캐시 시스템을 구성합니다. 이는 L1 또는 L2 캐시보다 훨씬 큰 용량을 가질 수 있으며, 일반적으로 모든 CPU에서 공유됩니다. 이러한 특성 때문에 데이터 교환 및 코어 간의 통신에 중요한 역할을 하게 됩니다. 일부 CPU에는 L3 캐시가 포함되지 않을 수 있지만, 고성능 및 멀티코어 CPU에서큰 L3 캐시를 볼 수 있습니다. 이 캐시 레벨은 코어 간 데이터 공유를 허용하며, 용량은 프로세서 모델에 따라 다르지만, 코어당 2MB 등 다양한 크기를 가질 수 있습니다.
캐시 메모리 용량에 따른 성능 차이는 대부분 벤치마크 테스트에서는 측정 가능하지만, 실제 사용 시에는 미미한 경우가 많아서 사용자가 직접 체감하기 어려울 수 있습니다. 그래서 CPU를 선택할 때 캐시 메모리 용량은 중요한 요소 중 하나지만, 절대적인 성능 판단을 하기 위해서는 다른 중요한 요소들과 함께 고려해야 합니다. CPU의 성능은 캐시 메모리 용량 이외에도 코어의 수, 클럭 속도, 아키텍처, 하이퍼스레딩 등 여러 가지 다른 요소에 영향을 받습니다.
참고로 system_profiler 명령어를 통해 대략적인 캐시 용량 정보를 볼 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$ system_profiler SPHardwareDataType
Hardware:
Hardware Overview:
Model Name: MacBook Pro
Model Identifier: MacBookPro16,1
Processor Name: 8-Core Intel Core i9
Processor Speed: 2.3 GHz
Number of Processors: 1
Total Number of Cores: 8
L2 Cache (per Core): 256 KB
L3 Cache: 16 MB
Hyper-Threading Technology: Enabled
Memory: 32 GB
System Firmware Version: 1968.100.17.0.0 (iBridge: 20.16.4252.0.0,0)
OS Loader Version: 577~129
Serial Number (system): ${SERIAL_NUMBER}
Hardware UUID: ${HARDWARE_UUID}
Provisioning UDID: ${PROVISIONING_UUID}
Activation Lock Status: Enabled
1
2
3
4
5
6
$ sysctl hw.l1icachesize hw.l1dcachesize hw.l2cachesize hw.l3cachesize
hw.l1icachesize: 32768
hw.l1dcachesize: 32768
hw.l2cachesize: 262144
hw.l3cachesize: 16777216
sysctl -a | grep cache 명령어를 사용하면 더 상세한 정보를 볼 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
$ sysctl -a | grep cache
......
debug.didevice_cache_fully_satisfied: 0
debug.didevice_cache_spared_bytes: 0
debug.didevice_cache_size_default: 33554432
debug.didevice_enable_cache: 1
hw.perflevel0.l1icachesize: 32768
hw.perflevel0.l1dcachesize: 32768
hw.perflevel0.l2cachesize: 262144
hw.perflevel0.l3cachesize: 16777216
hw.cacheconfig: 16 2 2 16 0 0 0 0 0 0
hw.cachesize: 34359738368 32768 262144 16777216 0 0 0 0 0 0
hw.cachelinesize: 64
hw.l1icachesize: 32768
hw.l1dcachesize: 32768
hw.l2cachesize: 262144
hw.l3cachesize: 16777216
machdep.cpu.cache.linesize: 64
machdep.cpu.cache.L2_associativity: 4
machdep.cpu.cache.size: 256
......
1-4. CPU와 메모리 사이의 통신
CPU와 메모리 사이의 통신은 주로 메모리 버스를 통해 이루어집니다. 메모리 버스는 CPU와 주 메모리 간의 전기적 연결로 데이터, 주소, 그리고 제어 신호의 전송을 담당하며, 메모리 버스의 속도와 대역폭은 전체 시스템 성능에 결정적인 영향을 미칩니다. CPU와 메인 메모리 사이의 직접적인 통신은 상대적으로 느릴 수 있기 때문에, 지연 시간을 최소화하기 위해 앞서 살펴본 CPU 캐시를 사용합니다.
멀티코어 프로세서의 메모리 구조에서 각 코어는 개별적인 L1 캐시를 가지며, 모든 코어들은 공유 버스를 통해 공통의 L2 캐시에 접근합니다. 이러한 프로세서는 메모리 버스를 통해 메인 메모리와 연결되어 있는데, L2 캐시 미스가 발생할 경우, 메인 메모리에서 데이터를 가져옵니다.
2. Cache Placement Policies
캐시 배치 정책은 메모리 블록이 CPU 캐시의 어느 위치에 들어갈지 결정하는 정책입니다. 캐시의 공간은 제한적이기 때문에 어떤 메모리 블록이 어떤 위치에 저장될지 결정해야 하며, Direct-Mapped Cache, Set-Associative Cache, Fully Associative Cache, Write-through & Write-back, Prefetching 등과 같은 캐시 배치 정책에 따라 캐시 라인이나 그 집합 중 특정 위치에만 배치될 수 있습니다.
2-1. Direct-Mapped Cache
Direct-Mapped Cache는 CPU 캐시의 특정 매핑 기법으로, 메인 메모리의 각 블록이 캐시 내의 단 하나의 위치에만 직접 매핑됩니다. Direct-Mapped Cache의 장점은 구조의 간결함과 빠른 검색 속도입니다. 그러나 여러 메모리 블록이 같은 캐시 라인에 할당될 가능성이 있으며, 이로 인한 캐시 미스와 충돌 문제로 성능 저하의 원인이 될 수 있습니다.
메모리 주소는 태그, 캐시 인덱스, 바이트 오프셋의 세 부분으로 나뉘어 처리됩니다. 캐시 인덱스는 주소 내에서 해당 데이터가 캐시의 어떤 위치에 저장될지 결정하는 부분이며, 태그는 저장된 데이터가 찾고자 하는 데이터와 일치하는지 확인하는 부분입니다. 주소의 태그 부분이 캐시 라인의 태그와 일치하면 캐시 히트가 되며, 그렇지 않으면 캐시 미스로 처리됩니다.
이를 자바 코드로 살펴보겠습니다. 아래 코드는 메모리 주소를 간단한 정수로 표현하며, cacheIndex는 메모리 주소를 4로 나눈 나머지로 결정됩니다. 즉 주소를 CACHE_SIZE로 나누면 0부터 3 사이의 값을 얻을 수 있는데, 이를 통해 모든 주소가 캐시 내의 특정한 위치로 매핑됩니다. 이를 통해 어떤 주소든지 캐시의 크기 범위 내의 인덱스로 변환될 수 있습니다. 나머지 연산을 통해 주소를 캐시의 인덱스로 변환하면 메인 메모리의 각 블록이 캐시의 정확한 하나의 위치에만 매핑될 수 있게 됩니다.
1
2
3
4
5
6
7
8
public class Entry {
private int tag;
private String data;
......
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class DirectMappedCache {
private static final int CACHE_SIZE = 4;
private Entry[] cache;
public DirectMappedCache() {
init();
}
private void init() {
this.cache = new Entry[CACHE_SIZE];
for (int index = 0; index < CACHE_SIZE; index++) {
cache[index] = new Entry(-1, null);
}
}
public String getCache(int address) {
int cacheIndex = address % CACHE_SIZE;
Entry entry = cache[cacheIndex];
// Cache Hit
if (entry.getTag() == address) {
return entry.getData();
} else {
// Cache Miss
return null;
}
}
public void putCache(
int address,
String data
) {
int cacheIndex = address % CACHE_SIZE;
Entry entry = cache[cacheIndex];
entry.register(address);
entry.register(data);
}
}
간략한 구현을 위해 메모리값을 정수로 표현했지만, 실제 하드웨어에서는 주소의 일부 비트로 인덱스를 결정합니다.
DirectMappedCache의 특징을 파악하기 위해 간단히 테스트를 하면 다음과 같은 결과가 나옵니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
@DisplayName("[UnitTest] DirectMappedCache 단위 테스트")
class DirectMappedCacheUnitTest {
private DirectMappedCache directMappedCache;
@BeforeEach
void setUp() {
directMappedCache = new DirectMappedCache();
}
@Test
@DisplayName("캐시는 일정 위치에 매핑된다.")
void cache_mapping_test() {
for (int index = 0; index <= 100_000; index++) {
directMappedCache.putCache(index, "Data:" + index);
assertNotNull(directMappedCache.getCache(index));
}
}
@Test
@DisplayName("캐시가 존재하더라도 이를 덮어쓸 수 있다.")
void cache_overwrite_test() {
directMappedCache.putCache(0, "Hello World.");
directMappedCache.putCache(0, "Changed Data.");
assertEquals("Changed Data.", directMappedCache.getCache(0));
}
}
2-2. Set-Associative Cache
Set-Associative Cache는 CPU 캐시를 여러 세트로 나눠 각 세트 안에 데이터를 저장하며, 특정 데이터 위치를 빠르게 찾아 효율적인 캐시 접근을 가능하게 하는 전략입니다. 메모리 블록은 특정 캐시 세트에 매핑되며 세트 내의 어떤 라인에 저장될지는 런타임에 결정됩니다. 적절한 세트와 라인의 크기 선택을 통해 높은 캐시 히트율을 유지할 수 있지만, 구현 복잡성과 캐시 검색 시간이 약간 늘어날 수 있는 단점도 있습니다.
이를 자바 코드로 살펴보겠습니다. 아래 코드는 2-way Set Associative Cache를 간단하게 구현한 코드로, 다양한 캐시 라인이 하나의 세트에 그룹화되어 있습니다. 메모리 블록이 캐시에 저장될 때 특정 세트에 배치되지만, 그 세트 내의 특정 라인은 선택적입니다.
1
2
3
4
5
6
7
8
public class CacheLine {
private int tag;
private String data;
......
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class SetAssociativeCache {
private static final Logger log = LoggerFactory.getLogger(SetAssociativeCache.class);
private static final int NUMBER_SET_SIZE = 16;
private static final int LINES_PER_SET_SIZE = 8;
private CacheLine[][] cache;
public SetAssociativeCache() {
init();
}
private void init() {
cache = new CacheLine[NUMBER_SET_SIZE][LINES_PER_SET];
for (int set = 0; set < NUMBER_SET_SIZE; set++) {
for (int line = 0; line < LINES_PER_SET_SIZE; line++) {
cache[set][line] = new CacheLine(-1, null);
}
}
}
public String getCache(int address) {
int setIndex = (address % NUMBER_SET_SIZE);
int tag = address / NUMBER_SET_SIZE;
for (int lineIndex = 0; lineIndex < LINES_PER_SET_SIZE; lineIndex++) {
// Cache Hit
if (cache[setIndex][lineIndex].getTag() == tag) {
return cache[setIndex][lineIndex].getData();
}
}
// Cache Miss
return null;
}
public void putCache(
int address,
String data
) {
int index = (address % NUMBER_SET_SIZE);
int tag = address / NUMBER_SET_SIZE;
// Runtime에 결정
int randomLine = (int) (Math.random() * LINES_PER_SET_SIZE);
log.info(() -> String.valueOf(randomLine));
cache[index][randomLine].register(tag);
cache[index][randomLine].register(data);
}
}
Direct-Mapped Cache의 심플함과 Fully Associative Cache의 유연성 사이의 중간점을 제공합니다.
이를 테스트하려면 Math.random을 모킹처리해야 하므로 간략히 랜덤으로 라인이 저장되는지만 살펴보겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SetAssociativeCache {
private static final Logger log = (Logger) LoggerFactory.getLogger(SetAssociativeCache.class);
......
public void putCache(
int address,
String data
) {
int index = (address % NUMBER_SET_SIZE);
int tag = address / NUMBER_SET_SIZE;
// Runtime에 결정
int randomLine = (int) (Math.random() * LINES_PER_SET);
log.info(String.valueOf(randomLine));
cache[index][randomLine].register(tag);
cache[index][randomLine].register(data);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@DisplayName("[UnitTest] SetAssociativeCache 단위 테스트")
class SetAssociativeCacheUnitTest {
private SetAssociativeCache setAssociativeCache;
@BeforeEach
void setUp() {
setAssociativeCache = new SetAssociativeCache();
}
@Test
@DisplayName("캐시 라인은 랜덤으로 저장된다.")
void cache_put_log_test() {
for (int index = 0; index < 16; index++) {
setAssociativeCache.putCache(index, "Cache: " + index);
}
}
}
결과를 보면 라인은 랜덤으로 배치되는 것을 볼 수 있습니다.
2-3. Fully Associative Cache
Fully Associative Cache는 하나의 캐시 세트에 모든 캐시 라인을 포함해 데이터를 어디든지 저장할 수 있는, 유연한 메모리 접근을 통해 최적화를 하는 매핑 전략입니다. 이는 캐시의 전체 라인을 단일 캐시 세트로 보며, 어떤 메모리 블록도 캐시의 모든 라인 중 하나에 저장될 수 있습니다.
이는 캐시 내의 모든 라인을 데이터 저장 장소로 활용할 수 있어 충돌 확률이 낮아집니다. 데이터 검색 시 메모리 주소의 태그를 통해 캐시 내 전체 라인을 검색하며, 일치하는 태그가 있으면 캐시 히트로, 없다면 캐시 미스로 처리합니다. Fully Associative Cache의 장점은 캐시 내 어디에든 메모리 블록을 배치할 수 있어 캐시 활용도가 높아진다는 점입니다. 이를 통해 높은 캐시 히트율을 달성할 수 있고, 다양한 교체 알고리즘을 적용할 수 있습니다. 그러나 모든 캐시 라인과의 태그 비교가 필요하기 때문에 검색 속도가 느려진다는 단점이 있습니다.
이를 자바 코드로 살펴보겠습니다. 아래 코드는 캐시에 데이터를 저장할 때, 먼저 valid bit을 확인하여 사용 가능한 라인을 찾습니다. 사용 가능한 라인이 없으면 캐시 교체 정책에 따라 한 라인을 선택하여 그곳에 데이터를 저장합니다. 데이터 검색 시 메모리 주소의 태그와 캐시 라인의 모든 태그를 비교하며, 태그가 일치하면 캐시 히트, 일치하지 않으면 캐시 미스가 발생합니다.
1
2
3
4
5
6
7
8
9
public class CacheLine<E, V> {
private boolean valid;
private E tag;
private V data;
......
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class FullyAssociativeCache<K, E, V> {
private static final Logger log = LoggerFactory.getLogger(FullyAssociativeCache.class);
private final int CACHE_SIZE;
private final LinkedHashMap<K, List<CacheLine<E, V>>> cache;
public FullyAssociativeCache(int cacheSize) {
this.CACHE_SIZE = cacheSize;
this.cache = new LinkedHashMap<>(
CACHE_SIZE,
0.75f,
true
) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, List<CacheLine<E, V>>> eldest) {
return size() > CACHE_SIZE;
}
};
}
public V getCache(
K key,
E tag
) {
List<CacheLine<E, V>> lines = cache.get(key);
if (lines != null) {
for (CacheLine<E, V> cacheLine : lines) {
log.info(() -> String.valueOf(cacheLine));
if (cacheLine.isValid() && cacheLine.getTag() == tag) {
return cacheLine.getData();
}
}
}
return null;
}
public void putCache(
K key,
E lineKey,
V value
) {
CacheLine<E, V> newLine = new CacheLine<>(lineKey, value);
List<CacheLine<E, V>> cacheLines = cache.getOrDefault(key, new ArrayList<>());
cacheLines.add(newLine);
cache.put(key, cacheLines);
}
}
마찬가지로 간략히 로그를 찍어 전체를 탐색하는지만 살펴보겠습니다. 로그를 보면 모든 라인을 탐색하며 캐시를 찾는 것을 볼 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@DisplayName("[UnitTest] FullyAssociativeCache 단위 테스트")
class FullyAssociativeCacheTest {
private FullyAssociativeCache<Integer, Integer, String> fullyAssociativeCache;
@BeforeEach
void setUp() {
fullyAssociativeCache = new FullyAssociativeCache<>(8);
}
@Test
@DisplayName("캐시를 찾기 위해 모든 라인을 탐색한다.")
void cache_full_search_test() {
fullyAssociativeCache.putCache(1, 1, "1");
fullyAssociativeCache.putCache(1, 2, "2");
fullyAssociativeCache.putCache(1, 3, "3");
fullyAssociativeCache.getCache(1, 3);
}
}
2-4. Write-through & Write-back
Write-through는 데이터가 캐시에 쓰일 때 동시에 주 메모리에도 즉시 반영됩니다. 이는 캐시와 메인 메모리 사이의 데이터 일관성을 높이며, 애플리케이션 서버의 다운과 같은 예기치 못한 상황에도 데이터의 안정성을 보장합니다. 그러나 모든 쓰기 연산이 주 메모리에도 즉시 반영되므로 쓰기 성능에 영향을 줄 수 있습니다.
In a write-through cache, every write to the cache causes a write to main memory.
Write-back은 데이터가 캐시에 기록될 때 메인 메모리에 즉시 반영되지 않습니다. 대신, 캐시 항목이 수정되었음을 나타내는 dirty bit가 설정됩니다. 메인 메모리로 실제로 쓰기가 이루어지는 것은 특정 조건 하에서만 발생하며, 이를 통해 쓰기 연산의 성능을 향상시키고 메인 메모리의 쓰기 트래픽을 줄일 수 있습니다. 그러나 캐시와 메인 메모리 사이의 데이터 일관성 문제와 예기치 않은 상황에서의 데이터 손실 위험이 존재할 수 있습니다.
Write-through를 자바 코드로 살펴보겠습니다. 아래 코드는 캐시를 저장한 후 바로 메인 메모리에 반영합니다. 이를 통해 캐시와 메인 메모리의 동기화를 할 수 있으며, 예기치 못한 상황에서도 데이터의 안전성을 보장합니다.
1
2
3
public class MainMemory {
public static final int[] mainMemory = new int[128];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class WriteThroughCache {
private static final int CACHE_SIZE = 16;
private final int[] cache = new int[CACHE_SIZE];
public int getCache(int cacheIndex) {
return cache[cacheIndex];
}
public void putCache(
int cacheIndex,
int value
) {
cache[cacheIndex] = value;
mainMemory[cacheIndex] = value;
}
}
테스트 결과는 다음과 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@DisplayName("[UnitTest] WriteThroughCache 단위 테스트")
class WriteThroughCacheUnitTest {
private WriteThroughCache writeThroughCache;
@BeforeEach
void setUp() {
writeThroughCache = new WriteThroughCache();
}
@Test
@DisplayName("캐시를 저장하면 메인메모리에도 동기화가 된다.")
void cache_sync_test() {
writeThroughCache.putCache(1, 1);
int cache = writeThroughCache.getCache(1);
int mainMemoryCache = MainMemory.mainMemory[1];
assertEquals(mainMemoryCache, cache);
}
}
Write-back은 캐시를 저장해도 flag만 바꿀 뿐 곧바로 메인 메모리에 동기화가 되지 않습니다. 하지만 flush를 하면 메인 메모리와 동기화가 됩니다.
1
2
3
public class MainMemory {
public static final int[] mainMemory = new int[128];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class WriteBackCache {
private static final int CACHE_SIZE = 16;
private final int[] cache = new int[CACHE_SIZE];
private boolean[] dirtyBit = new boolean[CACHE_SIZE];
public void putCache(int cacheIndex, int value) {
cache[cacheIndex] = value;
dirtyBit[cacheIndex] = true;
}
public int getCache(int cacheIndex) {
return cache[cacheIndex];
}
public void flush(int cacheIndex) {
if (dirtyBit[cacheIndex]) {
mainMemory[cacheIndex] = cache[cacheIndex];
dirtyBit[cacheIndex] = false;
}
}
}
테스트 결과는 다음과 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
@DisplayName("[UnitTest] WriteBackCache 단위 테스트")
class WriteBackUnitTest {
private WriteBackCache writeBackCache;
@BeforeEach
void setUp() {
writeBackCache = new WriteBackCache();
}
@Test
@DisplayName("캐시를 저장해도 메인메모리에도 동기화가 되지 않는다.")
void cache_sync_test() {
writeBackCache.putCache(2, 2);
int cache = writeBackCache.getCache(2);
int mainMemoryCache = MainMemory.mainMemory[2];
assertNotEquals(mainMemoryCache, cache);
}
@Test
@DisplayName("캐시를 저장하고 Flush를 하면 메인메모리에도 동기화가 된다.")
void cache_flush_test() {
writeBackCache.putCache(1, 1);
writeBackCache.flush(1);
int cache = writeBackCache.getCache(1);
int mainMemoryCache = MainMemory.mainMemory[1];
assertEquals(mainMemoryCache, cache);
}
}
2-5. Prefetching
Prefetching은 CPU의 성능을 향상시키기 위해 메모리 액세스의 지연 시간을 최소화하는 최적화 기법 중 하나입니다. 이는 CPU가 앞으로 필요한 데이터를 예측하고, 그 데이터를 캐시에 미리 로드하는 방으로 동작합니다. 이를 통해 CPU는 대기 시간 없이 필요한 데이터를 캐시에서 즉시 접근할 수 있으며, 연산을 지속적으로 빠르게 수행할 수 있게 됩니다. 이는 애플리케이션의 접근 패턴과 이전 메모리 접근 히스토리에 의존합니다.
Prefetching은 메모리 지연 시간의 감소로 CPU 성능을 향상시키지만, 예측 알고리즘의 정확도에 크게 의존합니다. 따라서 예측이 부정확할 경우, 캐시 리소스가 불필요한 데이터로 인해 비효율적으로 사용될 수 있으며, CPU가 실제로 필요로 하는 데이터의 접근을 방해하고 성능 저하를 초래할 수 있습니다.
3.Cache Replacement Policies
캐시 교체 정책(Cache Replacement Policy)은 캐시 메모리가 가득 찼을 때 새로운 데이터를 저장하기 위해 어떤 데이터 또는 항목을 캐시에서 제거할지 결정하는 정책을 말합니다. 여기에는 LRU, FIFO, Random Replacement, Optimal Replacement 등의 정책이 존재합니다.
3-1. LRU(Least Recently Used)
LRU 알고리즘은 페이지 교체 시에 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘을 말합니다. 이는 캐시/메모리에 모든 데이터를 올릴 수 없기에, 효과적으로 메모리를 관리하기 위해 사용됩니다.
LRU는 과거의 참조 기록을 기반으로 다가올 참조를 예측합니다. 예를 들어, 어떤 페이지가 최근에 사용되지 않았다면, 앞으로도 그 페이지가 사용될 확률이 낮다는 가정하에 그 페이지를 교체합니다.
이를 자바 코드로 보면 다음과 같습니다. LinkedHashMap은 엔트리가 추가되거나 접근될 때마다 순서를 유지하기 때문에, 가장 오래된 엔트리는 맵의 마지막에 위치합니다. 이를 통해 맵의 크기를 초과할 때 가장 오래된 항목을 제거하도록 한 것입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LRUCache<K, V> {
private final int capacity;
private final Map<K, V> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
};
}
public V get(K key) {
return map.get(key);
}
public void put(K key, V value) {
map.put(key, value);
}
}
실제로는 bit를 사용해 저수준에서 LRU를 구현해야 하지만 이해를 돕기 위해 자바 코드로 간략히 작성한 것입니다. 또한 LRU를 변형시킨 추가 알고리즘이 여럿 있는데, 이에 대해서는 별도로 학습하실 것을 권장드립니다.
이를 테스트하면 다음과 같이 가장 오래 전에 참조된 값이 제거되는 것을 볼 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
@DisplayName("[UnitTest] LRU 단위 테스트")
class LRUUnitTest {
private LRUCache<Integer, Integer> lruCache;
@BeforeEach
void setUp() {
lruCache = new LRUCache<>(4);
}
@Test
@DisplayName("지정된 캐시 크기를 초과하면 가장 오래된 캐시가 삭제된다.")
void lru_remove_test() {
lruCache.put(1, 1);
lruCache.put(2, 2);
lruCache.put(3, 3);
lruCache.put(4, 4);
lruCache.put(5, 5);
assertAll(
() -> assertEquals(4, lruCache.size()),
() -> assertNull(lruCache.get(1))
);
}
}
3-2. FIFO(First-In, First-Out)
FIFO(First-In, First-Out)는 가장 먼저 들어온 항목이 가장 먼저 나가는 방식으로 동작합니다. 캐시의 각 항목은 순서대로 저장되며, 캐시가 가득 찼을 때 새 항목을 추가하려고 하면 가장 먼저 저장된 데이터가 교체됩니다.
이를 자바 코드로 보면 다음과 같습니다. 더 이상 공간이 없을 때 가장 오래된 캐시를 제거합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class FIFOCache<K, V> {
private final int capacity;
private final Map<K, V> map;
private final Queue<K> queue;
public FIFOCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>(capacity);
this.queue = new LinkedList<>();
}
public V get(K key) {
return map.get(key);
}
public void put(K key, V value) {
if (!map.containsKey(key)) {
if (queue.size() == capacity) {
K oldestKey = queue.poll();
map.remove(oldestKey);
}
queue.add(key);
}
map.put(key, value);
}
}
테스트 결과를 보면 다음과 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@DisplayName("[UnitTest] FIFO 단위 테스트")
class FifoUnitTest {
private FIFOCache<Integer, Integer> fifoCache;
@BeforeEach
void setUp() {
fifoCache = new FIFOCache<>(4);
}
@Test
@DisplayName("지정된 캐시 크기를 초과하면 가장 먼저 들어온 캐시가 삭제된다.")
void fifo_remove_test() {
fifoCache.put(1, 1);
fifoCache.put(2, 2);
fifoCache.put(3, 3);
fifoCache.put(4, 4);
fifoCache.put(5, 5);
assertNull(fifoCache.get(1));
}
}
3-3. Random Replacement
Random Replacement는 교체될 항목을 무작위로 선택하는 방식입니다. 간단하게 구현할 수 있으며, 규칙적이지 않은 참조 패턴에서는 상대적으로 효과적일 수 있지만, 대체로 다른 전략들에 비해 성능이 낮습니다.
3-4. Optimal Replacement
Optimal Replacement는 페이지나 캐시 항목 교체 시 미래의 참조를 예측하여 가장 나중에 참조될 항목을 교체하는 알고리즘입니다. 실제 시스템에서는 미래의 참조를 예측할 수 없어 구현이 어렵지만, 이론적인 최적성을 분석할 때 자주 사용됩니다.
4. 캐시 사용 시 발생할 수 있는 문제점
캐시는 CPU의 연산 속도와 메인 메모리 사이의 속도 차이를 최소화하기 위한 중요한 메모리 구성요소지만, 캐시를 사용할 때 다음과 같은 여러 문제점이 있습니다. 이 중 Miss, Cache Pollution는 잠시 제외하고 멀티 쓰레드 환경에서 발생할 수 있는 캐시 관련 이슈에 대해 살펴보겠습니다.
- Cache Miss
- Cache Pollution
- False Sharing
- Coherence Traffic
- Cache Thrashing
- Memory Synchronization Overheads
4-1. False Sharing
False Sharing은 멀티쓰레드 환경에서 발생하는 성능 저하 문제로, 여러 쓰레드가 같은 캐시 라인의 다른 메모리 위치를 동시에 수정하려 할 때 발생합니다. 같은 라인에 위치한다는 것은 두 개 이상의 데이터가 이 같은 캐시 라인 내에 저장된다는 것을 의미하는데, 예를 들어, 64byte 크기의 캐시 라인이 있을 때, 첫 번째 바이트와 마지막 바이트에 각각 변수가 저장된 경우, 두 변수는 서로 다른 메모리 주소에 위치하지만, 같은 캐시 라인 내에 있습니다.
1
✅ㅁㅁㅁㅁㅁㅁㅁ| ...... |ㅁㅁㅁㅁㅁㅁㅁㅁ| ...... |ㅁㅁㅁㅁㅁㅁㅁ✅ <- 동일 캐시 라인(64byte)
캐시 라인이라는 단위로 나누는 것은 캐시의 크기가 제한적이기 때문입니다. 여기서 문제가 발생하는데, 한 쓰레드가 캐시 라인을 수정하면 해당 라인을 참조하는 다른 CPU의 캐시는 무효화되며, 데이터를 메인 메모리에서 다시 읽어와야 합니다. 멀티 쓰레드 환경일 경우 캐시 미스가 자주 발생하면, 이로 인해 성능 저하가 발생할 수 있습니다.
캐시 라인에 대해 추가적으로 해당 글을 읽어보실 것을 권장드립니다.
이를 해결하는 방법 중 하나로 패딩(Padding)이 존재합니다. 이는 변수들 사이에 의도적으로 빈 공간을 추가하여 각 변수가 독립된 캐시 라인에 위치하도록 설계하는 기법입니다. 이를 통해 한 쓰레드에서 변수를 수정할 때, 캐시 라인 충돌로 인한 성능 저하를 방지할 수 있습니다.
C 코드를 통해 패딩이 있을 때와 없을 때의 성능을 측정해보겠습니다. 아래 두 개의 쓰레드로 패딩이 있는 경우/없는 경우를 구분해 배열의 값을 증가시키고 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <pthread.h>
#include <stdio.h>
#include <sys/time.h>
#define NUM_THREADS 2
long dataWithoutPadding[2] = {0, 0};
struct PaddedLong {
long value;
char padding[56];
};
struct PaddedLong dataWithPadding[2] = { {0}, {0} };
void* workWithoutPadding(void* arg) {
long tid = (long)arg;
for (int index = 0; index < 10000000; index++) {
dataWithoutPadding[tid]++;
}
pthread_exit(NULL);
}
void* workWithPadding(void* arg) {
long tid = (long)arg;
for (int index = 0; index < 10000000; index++) {
dataWithPadding[tid].value++;
}
pthread_exit(NULL);
}
int main() {
pthread_t threads[NUM_THREADS];
struct timeval startOverall, endOverall;
struct timeval start, end;
long elapsed;
gettimeofday(&startOverall, NULL);
printf("Running without padding.\n");
gettimeofday(&start, NULL);
for (long index = 0; index < NUM_THREADS; index++) {
pthread_create(&threads[index], NULL, workWithoutPadding, (void *) index);
}
for (long index = 0; index < NUM_THREADS; index++) {
pthread_join(threads[index], NULL);
}
gettimeofday(&end, NULL);
elapsed = (end.tv_sec - start.tv_sec) * 1000000 + end.tv_usec - start.tv_usec;
printf("Without Padding took: %ld microseconds\n", elapsed);
printf("dataWithoutPadding[0] = %ld, dataWithoutPadding[1] = %ld\n\n", dataWithoutPadding[0], dataWithoutPadding[1]);
printf("Running with padding.\n");
gettimeofday(&start, NULL);
for (long index = 0; index < NUM_THREADS; index++) {
pthread_create(&threads[index], NULL, workWithPadding, (void *) index);
}
for (long index = 0; index < NUM_THREADS; index++) {
pthread_join(threads[index], NULL);
}
gettimeofday(&end, NULL);
elapsed = (end.tv_sec - start.tv_sec) * 1000000 + end.tv_usec - start.tv_usec;
printf("With Padding took: %ld microseconds\n", elapsed);
printf("dataWithPadding[0] = %ld, dataWithPadding[1] = %ld\n", dataWithPadding[0].value, dataWithPadding[1].value);
gettimeofday(&endOverall, NULL);
elapsed = (endOverall.tv_sec - startOverall.tv_sec) * 1000000 + endOverall.tv_usec - startOverall.tv_usec;
printf("\nTotal Execution time: %ld microseconds\n", elapsed);
return 0;
}
결과를 보면 패딩으로 인해 성능이 약 4배 가까이 빨라진 것을 볼 수 있습니다. 즉 캐시라인을 의도적으로 분리해서 충돌로 인한 성능 저하를 방지한 것입니다.
4-2. Cache Coherence
Cache Coherence란 공유 메모리 시스템에서 각 클라이언트(혹은 프로세서)가 가진 로컬 캐시 간의 일관성을 의미합니다. 여러 CPU가 공유된 메모리 위치를 읽거나 쓸 때 캐시 간에 데이터가 항상 최신 상태를 유지하는 것을 말합니다. 이를 위해서는 Data Consistency Mechanism, Cache Coherence Protocol, Cache Interconnect, Atomic Operation 등 다양한 기술과 규칙이 사용됩니다.
이를 자바 코드로 살펴보겠습니다. 아래 코드를 실행하면 프로그램이 종료되지 않는 경우가 발생하게 됩니다. 이는 JVM 캐시와 메모리 가시성(Visibility), JIT 컴파일러 때문인데, 첫 번째 쓰레드는 flag 값을 확인할 때 자신만의 로컬 캐시에서 값을 읽지만, 두 번째 쓰레드가 flag 값을 변경하면, 변경 사항이 해당 쓰레드의 로컬 캐시에만 반영될 수 있기 때문입니다. 따라서 첫 번째 쓰레드는 flag의 변경 사항을 감지하지 못할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Main {
private static boolean flag = false;
public static void main(String[] args) {
new Thread(() -> {
while (true) {
if (flag) {
System.out.println("Thread 1 TRUE 변경 감지");
break;
}
}
}).start();
new Thread(() -> {
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
e.printStackTrace();
}
flag = true;
System.out.println("Thread 2 FLAG 변경: FALSE -> TRUE");
}).start();
}
}
또한 JIT 컴파일러는 런타임에 코드를 최적합니다. 첫 번째 쓰레드에서 flag 값이 변경되지 않은 것을 감지하면, 이를 무한 루프로 최적화할 가능성도 있기 때문에 컴파일러의 최적화 또한 의심해봐야 합니다.
이를 해결하기 위해서는 자바에서는 volatile 키워드를 사용해야 합니다. 이는 값이 바뀌면 이를 메모리에 반영해 동기화 시켜주는 것입니다. CPU에서 발생하는 캐시 일관성 문제는 주로 메모리에서 발생하며, 다중 처리 시스템의 CPU 간에 발생하기 때문에 쓰레드를 기반으로 하는 자바와는 조금 다를 수 있지만 캐시/데이터 일관성에 관한 문제가 발생할 수 있다는 점을 항상 숙지해야 합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Main {
// volatile 키워드 사용
private static volatile boolean flag = false;
public static void main(String[] args) {
new Thread(() -> {
while (true) {
if (flag) {
System.out.println("Thread 1 TRUE 변경 감지");
break;
}
}
}).start();
new Thread(() -> {
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
e.printStackTrace();
}
flag = true;
System.out.println("Thread 2 FLAG 변경: FALSE -> TRUE");
}).start();
}
}
이 외에도 MSI Protocol과 같은 동기화 방법이 있습니다.
여기서 예외 케이스가 하나 있습니다. 같이 공부하는 Youl이 공유해준 내용인데, 아래와 같이 while문 내부에 print문을 넣으면 volatile 키워드가 없더라도 while문은 종료가 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class CPUCacheTest {
static Boolean flag = true;
public static void main(String[] args) throws InterruptedException {
Thread thread1 = new Thread(() -> {
long count = 0;
while (flag) {
count++;
System.out.println(flag);
}
System.out.println("thread1 end!! count : " + count);
});
Thread thread2 = new Thread(() -> {
try {
Thread.sleep(100);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
flag = false;
System.out.println("thread2 flag = " + flag);
});
thread1.start();
thread2.start();
}
}
이는 Context Switching 때문인데, 프로세스에서 운영체제를 호출하기 위해서는 순서가 필요하므로 내부적으로 synchronized 블럭을 사용합니다. synchronized 블럭에 쓰레드가 진입하는 찰나의 순간 Context Switching이 발생하며, threadA가 원래 자신이 작업하고 있던 CPU의 코어와 작업을 할 수도, 안 할 수도 있습니다. 따라서 캐싱 된 값을 읽을 수도, 안 읽을 수도 있으므로 일정 시간이 지나면 volatile을 붙인 것과 비슷한 결과를 가져옵니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class PrintStream extends FilterOutputStream implements Appendable, Closeable {
......
public void println(String x) {
synchronized (this) {
print(x);
newLine();
}
}
......
}
이 부분이 이해가 잘 안 돼서 한 참을 헤맸는데요, 확실하게 이해할 수 있게 도와준 Youl에게 감사드립니다. 😊
4-3. Cache Thrashing
Cache Thrashing은 프로그램이 데이터에 접근할 때 발생하는 현상으로, CPU 캐시가 효율적으로 사용되지 않아 성능 저하가 발생하는 것을 말합니다. 캐시에 데이터가 없어서 메인 메모리로부터 데이터를 읽어오는 것을 캐시 미스라 하는데, 캐시 미스가 발생하면 CPU는 메인 메모리에 접근해야 하므로 프로그램의 실행 속도가 저하됩니다.
이를 자바 코드로 살펴보겠습니다. 아래 코드는 행/열 단위 접근으로 데이터를 읽어오는 속도를 비교하고 있습니다. 캐시는 라인 단위로 읽히는데, 즉 한 라인에 대해 순차적으로 접근하면 한 번의 메모리 로드로 많은 데이터 요소를 캐시에 가져올 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Main {
private static final int SIZE = 10_000;
private static final int[][] array1 = new int[SIZE][SIZE];
private static final int[][] array2 = new int[SIZE][SIZE];
public static void main(String[] args) {
long start, end;
// Cache Thrashing X
start = System.nanoTime();
for (int row = 0; row < SIZE; row++) {
for (int column = 0; column < SIZE; column++) {
array1[row][column]++; // 로우 기준 접근
array2[row][column]++;
}
}
end = System.nanoTime();
System.out.println("No Cache Thrashing Time: " + (end - start) / 1_000_000 + " ms");
// Cache Thrashing O
start = System.nanoTime();
for (int row = 0; row < SIZE; row++) {
for (int column = 0; column < SIZE; column++) {
array1[column][row]++; // 컬럼 기준 접근
array2[column][row]++;
}
}
end = System.nanoTime();
System.out.println("Cache Thrashing Time: " + (end - start) / 1_000_000 + " ms");
}
}
이를 실행하면 다음과 같은 결과가 나타납니다. 이는 CPU 캐시가 데이터를 캐시 라인 단위로 읽어오는 방식과 유사합니다. 즉 한 행의 데이터에 순차적으로 접근하면 이는 연속적인 메모리 위치에 접근해 데이터를 읽어오기 때문에 읽기 속도가 빠릅니다. 반면 열을 기준으로 배열에 접근하면 메모리상에서 서로 떨어진 위치들을 참조하게 되며, 이런 접근이 자주 발생하면 캐시 미스로 캐시 데이터가 빠르게 쫓겨납니다.
4-4. Overheads
CPU 캐시를 사용할 때 다른 코어와 데이터를 공유하거나 동기화하는 경우 오버헤드가 발생할 수 있습니다. 이러한 오버헤드는 성능 저하를 초래하므로, 멀티코어 프로그래밍에서는 이러한 문제점을 고려하여 최적화된 코드를 작성하는 것이 중요합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NUM_THREADS 2
long counter_with_lock = 0;
long counter_without_lock = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
typedef struct {
double time_taken;
} ThreadResult;
void* worker_with_lock(void* arg) {
ThreadResult* result = (ThreadResult*)malloc(sizeof(ThreadResult));
clock_t start = clock();
for (int index = 0; index < 10000000; index++) {
pthread_mutex_lock(&mutex);
counter_with_lock++;
pthread_mutex_unlock(&mutex);
}
result->time_taken = ((double) (clock() - start)) / CLOCKS_PER_SEC;
return (void*)result;
}
void* worker_without_lock(void* arg) {
ThreadResult* result = (ThreadResult*)malloc(sizeof(ThreadResult));
clock_t start = clock();
for (int index = 0; index < 10000000; index++) {
counter_without_lock++;
}
result->time_taken = ((double) (clock() - start)) / CLOCKS_PER_SEC;
return (void*)result;
}
int main() {
pthread_t threads[NUM_THREADS];
ThreadResult* results[NUM_THREADS];
// Threads with lock
for (long index = 0; index < NUM_THREADS; index++) {
pthread_create(&threads[index], NULL, worker_with_lock, NULL);
}
for (long index = 0; index < NUM_THREADS; index++) {
pthread_join(threads[index], (void**)&results[index]);
printf("Time taken by thread %ld with lock: %f seconds\n", index, results[index]->time_taken);
free(results[index]);
}
printf("Counter with lock = %ld\n", counter_with_lock);
// Threads without lock
for (long index = 0; index < NUM_THREADS; index++) {
pthread_create(&threads[index], NULL, worker_without_lock, NULL);
}
for (long index = 0; index < NUM_THREADS; index++) {
pthread_join(threads[index], (void**)&results[index]);
printf("Time taken by thread %ld without lock: %f seconds\n", index, results[index]->time_taken);
free(results[index]);
}
printf("Counter without lock = %ld\n", counter_without_lock);
return 0;
}
이를 실행해 보면 약 25배 가까이 성능 차이가 발생하는 것을 볼 수 있습니다.
5. 정리
CPU 캐시와 캐시 배치 알고리즘, 캐시 교체 알고리즘, 주의할 점에 대해 살펴보았습니다. 이는 CPU 캐시뿐 아니라 캐싱 메커니즘 전반에 사용되기 때문에 반드시 숙지하고, 잘 응용할 수 있어야 합니다.