False Sharing

설명

단어를 그대로 보면 '거짓 공유' 이다.

거짓을 공유한다는 것은 말이 웃기다.

 

컴퓨터에서 False는 논리 연산의 결과에 사용되며 조건이 맞지 않다는 의미로 사용된다.

 

그럼 어떤 조건에 맞는 것을 누구한테 공유하는 것일까를 생각해보면 해당 개념을 더 쉽게 이해할 수 있다.

 

우선 여기서 조건에 맞지 않음은 데이터가 조건에 맞지 않음을 의미하며, 공유의 대상은 주로 LLC (Last Level Cache)이다. 물론 L2, L3 까지 캐시를 사용하는 CPU이면 L2에서도 발생할 수 있다.

즉 마지막 대상 캐시만 발생하는 것은 아니다.

 

더 풀어서 데이터가 조건에 맞지 않음은 캐시 일관성이 맞지 않음을 의미한다.

CPU는 메모리에서 데이터를 가져올 때 캐시라인 단위로 데이터를 가져온다. 캐시라인은 캐시 메모리에 데이터를 저장하는 단위이다. 주로 크기는 64Byte이며 캐시라인 단위로 데이터를 가져오는 것은 공간 지역성, 즉 근처의 공간에 접근할 확률이 높다는 것을 기반으로한다.

 

그렇다면 어떤 경우에 데이터가 일치하지 않게 될까?

 

예를들어 원소 1개당 8바이트인 long type의 배열이 있다고 가정하자. 사이즈는 편의상 매우 크다고 가정한다.

해당 배열의 0번 원소만 접근을 해도 7번 인덱스까지의 데이터를 가져오게 된다.

 

멀티스레딩 환경에서 데이터가 일치하지 않는 경우를 예를들어보면 1번 쓰레드가 해당 배열에 1번 인덱스를 접근하고 2번 쓰레드가 2번 인덱스를 접근할 때 위의 논리에 근거하여 첫 번째 쓰레드는 1 ~8 번 인덱스의 데이터를 가져오게 되고 2번 쓰레드는 2 ~ 9번 인덱스의 데이터를 가져오게 된다. (물론 개념 이해를 위한 것이지 정확히 일치하지는 않을 수 있다.)

 

두 쓰레드가 각기 다른 코어에 할당되고 마지막 캐시는 L3이며 해당 캐시는 공유 캐시로 사용된다고 했을 때 다음과 같은 상황이 발생한다.

 

1. 1번 쓰레드가 1번인덱스를 수정하고 메모리에 write 할려고 함

 

2. 해당 시점에 2번 쓰레드가 2번 인덱스를 수정하고 메모리에 write 하며 캐시에 데이터 수정

 

3. 1번 쓰레드는 7번 인덱스까지 데이터를 갖고있기 때문에 케시에서 write하기 이전 시점에 데이터 확인 시 2번 쓰레드의

 

데이터 불일치 발생 확인 (해당 과정은 캐시 일관성 프로토콜에 의해 진행 - 하드웨어 레벨)
이러한 이유는 캐시 라인을 메모리에 write하기 위해 가져 온 2번 인덱스도 write해야 하기 때문에 캐시에서 2번 인덱스를 가져오는 과정에서 해당 데이터 변경을 감지

 

4. 메모리에서 해당 데이터를 다시 Load후 write

 

이렇게 메모리에서 다시 로드하는 과정이 추가되기 때문에 '거짓 공유'는 성능 저하를 유발한다.

이 현상은 각 쓰레드가 공유되는 데이터를 사용해도 발생하고, 사용하지 않아도 발생한다. 이해를 돕기 위해 자바 코드를 추가한다.

코드 예시

public class FalseSharingExample implements Runnable {

    private static final int NUM_THREADS = 2; // 스레드 개수
    private static final long ITERATIONS = 10_000_000_00L;
    private final int arrayIndex;

    // 각 스레드가 접근하는 별도의 데이터
    private static volatile long[] data = new long[NUM_THREADS * 8];

    public FalseSharingExample(int arrayIndex) {
        this.arrayIndex = arrayIndex;
    }

    @Override
    public void run() {
        for (long i = 0; i < ITERATIONS; i++) {
            data[arrayIndex] = i; // 각 스레드는 자신의 배열 요소만 변경
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Thread[] threads = new Thread[NUM_THREADS];

        for (int i = 0; i < NUM_THREADS; i++) {
            threads[i] = new Thread(new FalseSharingExample(i));
        }

        final var start = System.currentTimeMillis();

        for (Thread t : threads) {
            t.start();
        }

        for (Thread t : threads) {
            t.join();
        }

        final var end = System.currentTimeMillis();

        System.out.println("It takes " + (end - start) + "ms");
    }
}

수행시간: 1680ms

개선방향

성능 저하의 원인이 메모리에 다시 접근하는 것이니 메모리에 다시 접근하지 않을 방법을 찾으면 개선할 수 있다.

 

캐시 라인 단위로 데이터를 가져왔을 때, 두 쓰레드에서 캐시 라인이 겹치지 않으면 멀티쓰레딩 환경에서 데이터 불일치는 발생하지 않으며 이는 메모리에서 데이터를 다시 로드하는 과정을 거치지 않을 것이다.

 

즉, 접근하는 데이터의 사이즈가 캐시라인의 크기에 맞게 패딩을 해주게 된다면 캐시 라인 사이즈로 데이터를 가져오게 될 것이다.

코드 예시

public class FalseSharingExample implements Runnable {

    private static final int NUM_THREADS = 2; // 스레드 개수
    private static final long ITERATIONS = 10_000_000_00L;
    private final int arrayIndex;

    // 각 스레드가 접근하는 별도의 데이터
    private static volatile long[] data = new long[NUM_THREADS * 8];

    public FalseSharingExample(int arrayIndex) {
        this.arrayIndex = arrayIndex;
    }

    @Override
    public void run() {
        for (long i = 0; i < ITERATIONS; i++) {
            data[arrayIndex] = i; // 각 스레드는 자신의 배열 요소만 변경
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Thread[] threads = new Thread[NUM_THREADS];

        for (int i = 0; i < NUM_THREADS; i++) {
            threads[i] = new Thread(new FalseSharingExample(i * 8));
        }

        final var start = System.currentTimeMillis();

        for (Thread t : threads) {
            t.start();
        }

        for (Thread t : threads) {
            t.join();
        }

        final var end = System.currentTimeMillis();

        System.out.println("It takes " + (end - start) + "ms");
    }
}

 

수행시간: 655ms