False Sharing이란

false sharing이 일어나면 병렬 프로그래밍이 더 느린 상황이 일어날 수 있다!

#include <vector>
#include <array>
#include <thread>

std::array<int, 4> sums {0, 0, 0, 0};

int main() 
{
    std::vector<int> nums(10000);
    
    // 스레드 생성 및 작업 분리
    std::thread t1([&]() {
        for (int idx = 0; idx < 2500; idx++) {
            sums[0] += nums[idx];
        }
    });

    std::thread t2([&]() {
        for (int idx = 2500; idx < 5000; idx++) {
            sums[1] += nums[idx];
        }
    });

    std::thread t3([&]() {
        for (int idx = 5000; idx < 7500; idx++) {
            sums[2] += nums[idx];
        }
    });

    std::thread t4([&]() {
        for (int idx = 7500; idx < 10000; idx++) {
            sums[3] += nums[idx];
        }
    });

    // 스레드 동기화
    t1.join();
    t2.join();
    t3.join();
    t4.join();

    // 총합 계산
    const int sum = sums[0] + sums[1] + sums[2] + sums[3];

    return 0;
}

 

 

논리적으로는 저 sums는 같은 상태인데

물리적으로는 다른 상황이 벌어져서

cache line의 상태가 CPU 마다 다르다 == false sharing 이다! (CPU 끼리 sync 프로세스를 진행 -> false sharing은 멀티스레드 환경에서 발생할 수 있는 문제로, 여러 스레드가 동일한 캐시 라인에 있는 데이터를 업데이트하려고 할 때 성능이 저하되는 상황)

 

해결 방법 (Padding Solution)

false sharing 문제를 해결하려면, sums 배열의 요소 간에 패딩을 추가하거나, 각 스레드가 접근하는 데이터가 별도의 캐시 라인에 있도록 메모리 배치를 변경하면 된다. 

struct PaddedInt {
    int value;
    char padding[64]; // 캐시 라인 크기
};

std::array<PaddedInt, 4> sums {{}};

 

 

 

* 캐시 라인이란? 

캐시 라인(Cache Line)은 CPU 캐시 메모리의 데이터 전송 및 저장 단위입니다. CPU 캐시는 메모리의 데이터를 효율적으로 가져오기 위해, 데이터를 일정 크기의 블록으로 나누어 처리하는데, 이 블록 단위를 캐시 라인이라고 합니다.

캐시 라인의 특징

1. 크기: 일반적으로 캐시 라인의 크기는 32, 64, 또는 128 바이트입니다. 현대 프로세서에서는 64바이트가 가장 흔히 사용됩니다.
2. 연속적 데이터 처리: 캐시는 메모리에서 데이터를 가져올 때, 요청된 데이터뿐만 아니라 인접한 데이터도 함께 가져옵니다. 이를 **공간적 지역성(Spatial Locality)**이라고 합니다.
3. 정렬된 단위: 캐시 라인은 메모리의 특정 주소 범위를 기준으로 정렬되며, 정렬된 데이터 덩어리를 CPU 캐시에 로드합니다.

캐시의 계층 구조

CPU 캐시는 일반적으로 L1, L2, L3 캐시로 나뉘며, 각 계층은 다음과 같은 역할을 합니다:

• L1 캐시: 가장 빠르고 가장 작음 (보통 수십 KB).
• L2 캐시: L1보다 느리지만 더 큼 (수백 KB ~ 몇 MB).
• L3 캐시: CPU 코어 간 공유되는 캐시로 더 크고 느림 (몇 MB ~ 수십 MB).

캐시 라인의 중요성

CPU가 메모리에 접근할 때, 단일 데이터를 가져오는 대신 캐시 라인 단위로 데이터를 가져옵니다. 예를 들어, 특정 메모리 주소의 데이터를 요청하면, 그 주소를 포함한 64바이트 크기의 블록이 캐시에 저장됩니다. 이후 동일한 캐시 라인 내의 데이터에 접근하면 메모리 대신 캐시에서 빠르게 데이터를 읽을 수 있습니다.

 

---

 

Q. 자바에서도 False Sharing이 일어날 수 있는가?

 

네, Java에서도 false sharing이 발생할 수 있습니다. Java는 CPU 캐시의 메커니즘을 직접 제어하지 않지만, JVM이 사용하는 메모리 레이아웃과 멀티스레드 환경에서의 데이터 접근 방식 때문에 false sharing 문제가 발생할 수 있습니다.

---

Java에서 false sharing의 발생 조건

1. 멀티스레드 환경: 여러 스레드가 동시에 실행 중이어야 합니다.
2. 공유된 데이터: 여러 스레드가 동일한 객체나 배열의 필드 또는 배열 요소를 업데이트해야 합니다.
3. 데이터가 동일한 캐시 라인에 존재: JVM이 객체 필드나 배열 요소를 메모리에 배치하는 방식 때문에, 여러 필드나 요소가 같은 캐시 라인에 들어갈 수 있습니다.

---

false sharing의 Java 예시

public class FalseSharingExample {
    public static int NUM_THREADS = 4; // 스레드 수
    public static long ITERATIONS = 50_000_000L; // 반복 횟수

    private static class SharedData {
        public volatile long value = 0L; // 공유되는 값
    }

    private static SharedData[] sharedDataArray;

    public static void main(String[] args) throws InterruptedException {
        sharedDataArray = new SharedData[NUM_THREADS];
        for (int i = 0; i < NUM_THREADS; i++) {
            sharedDataArray[i] = new SharedData();
        }

        Thread[] threads = new Thread[NUM_THREADS];
        for (int i = 0; i < NUM_THREADS; i++) {
            final int index = i;
            threads[i] = new Thread(() -> {
                for (long j = 0; j < ITERATIONS; j++) {
                    sharedDataArray[index].value++;
                }
            });
        }

        long start = System.nanoTime();
        for (Thread t : threads) t.start();
        for (Thread t : threads) t.join();
        long end = System.nanoTime();

        System.out.println("Execution Time: " + (end - start) / 1_000_000 + " ms");
    }
}

 

문제점

• sharedDataArray의 각 요소는 value 필드를 갖습니다.
• 각 스레드는 자신에게 할당된 value를 업데이트하므로 논리적으로는 독립적입니다.
• 그러나 JVM의 메모리 배치 방식에 따라 sharedDataArray의 요소들이 동일한 캐시 라인에 존재할 수 있습니다.
• 이로 인해 false sharing이 발생하고 성능이 저하될 수 있습니다.

---

false sharing 문제 해결 방법

1. Padding 사용
   False sharing을 방지하려면 각 필드가 별도의 캐시 라인에 배치되도록 설계해야 합니다. Java에서 이를 구현하기 위해 Padding을 사용합니다.

private static class PaddedSharedData {
    public volatile long value = 0L;
    // 캐시 라인 패딩
    public long p1, p2, p3, p4, p5, p6, p7; 
}

이 패딩은 value 필드와 다른 데이터가 같은 캐시 라인에 배치되지 않도록 보장합니다.

1. JVM 옵션 사용
   JVM은 런타임에 false sharing을 최적화하려고 노력하지만, -XX:-RestrictContended 옵션을 사용하여 개발자가 직접 메모리 레이아웃을 더 세부적으로 조정할 수 있습니다.
2. @Contended 어노테이션
   Java 8부터 @Contended 어노테이션을 사용할 수 있습니다. 이 어노테이션은 특정 필드가 별도의 캐시 라인에 배치되도록 JVM에 지시합니다. 사용하려면 JVM 옵션에 -XX:-RestrictContended를 추가해야 합니다.

import sun.misc.Contended;

public class ContendedExample {
    @Contended
    public volatile long value = 0L;
}

---

결론

Java에서도 false sharing이 발생할 수 있으며, 이는 멀티스레드 프로그램의 성능 저하로 이어질 수 있습니다. 이를 해결하려면 패딩을 추가하거나 @Contended를 사용하는 방식으로 데이터가 서로 다른 캐시 라인에 배치되도록 조정해야 합니다. Java의 멀티스레드 프로그램에서 false sharing을 최소화하면 성능을 크게 개선할 수 있습니다.