Disclamer

현 자료는 우리들의 대선배 Scott Meyers 님의 2014년 강연인 Cpu Caches and Why You Care 발표 자료 내용에 대한 개인 정리분 입니다.

거의 모든 내용은 영상과 관련 문서를 찾아 보면서 작성 하였으며, 본인 개인의 공부 목적으로 정리한 내용이라, 부정확하거나 생략된 정보가 존재할 수 있으니 이점 유념하여 봐주시길 바랍니다.

부정확한 정보는 댓글로 바로잡아주시면 정말 감사하겠습니다!

Intro

프로그래머는 프로그래밍 언어를 이용해 코드를 짜는 직업이다.

코드 짠다는 것은 대부분의 경우 Software(소프트웨어) 를 만드는 것을 의미한다.

하지만 모든 소프트웨어 는 Hardware(하드웨어) 를 통해 우리가 하고자 하는 것을 실행시키는 것이다.

그러므로 프로그래머들은 동작하는 코드를 작성하는 것을 넘어 하드웨어에 대해 이상적으로 작동하는 코드를 작성하는 것 또한 중요히 여겨야 한다.

한정된 하드웨어 자원에서 가장 최대한의 성능을 낼 수 있도록 하는 것이 어떻게 보면 또다른 프로그래머의 사명이라고 생각해야할 것이다. (따흐흑…)

우리는 이처럼 프로그램의 성능을 끌어올리는 작업들을 통틀어 최적화 (Optimization) 작업이라고 한다.

어떤 언어를 사용하던지 상관없이, 모든 소프트웨어는 기계어를 통해 결정적으로 하드웨어에 어떤 명령을 어떻게 내리느냐에 따라 프로그램의 작동 방식과 속도가 변할 수 있다.

그러므로 하드웨어의 동작방식을 이해하고, 하드웨어가 어떤 코드를 좋아하는지 한 번 알아보자.

Row / Column Major Traversals

프로그래밍을 배우며 한 번쯤은 for문이나 while 문을 사용해 배열을 순회해본 경험이 있을 것이다.

DFS나 BFS 같은 알고리즘을 사용해 2차원 배열을 탐색하며 최단거리를 찾거나 할때도 상하좌우를 계속 탐색하며 길을 찾아나가거나 할 것이다.

아니면 아주 간단하게 배열에 있는 모든 값의 합이나 소수의 개수 등을 알아보고 싶다면 결국 전체 탐색을 해야하는 상황이 온다.

2차원 배열을 탐색하는 상황을 가정하고 행을 기준으로 탐색하는 것과 열을 기준으로 탐색하는 상황을 예로 들어보겠다.

Row Major (행 우선) 와 Column Major (열 우선) 방식에 따라 어떤 차이가 존재하는 것일까?

동일한 메모리를 순회하는 것인데 무엇이 다른 것일까? 한 번 알아보자.

일반적으로 알고있는 행렬은 아래와 같이 정의된다.

행(Row) 은 가로축, 열 (Column) 은 세로축을 기준으로 아래와같이 순서를 붙여 말한다.

컴퓨터 메모리는 메모리 주소가 쭈우우욱 이어진 형태이지만, 2차원 배열을 순회한다고 생각해보면 아래와같은 표로 나타낼 수 있다. 이는 행렬로 표현되었다고 볼 수 있다.

행을 우선한다는 것은 행에 대한 요소들을 먼저 계산하겠다는 것이다.

제1행 연산에 대한 모든 요소들에 대한 처리가 끝나면 그 다음 행인 제2행에서 처리를 시작한다.

열을 우선한다는 것은 행을 우선하는 것과 같이 열에 대한 요소들을 먼저 계산하겠다는 것이다.

모든 행에서 제1열에 대한 처리가 끝나면 다시 모든 행에 대해 제2열에 대한 처리를 시작한다.

두 동작은 실질적으로 같은 의미이다. 결국 2차원 배열을 모두 순회하겠다는 뜻이다.

여기서 어떤 차이를 찾을 수 있는 것일까?

관련된 코드를 구현해 한 번 확인해보자.

Row Major VS Column Major Test Code

#include <chrono>
#include <iostream>


template <typename T>
class Matrix final
{
public:
    Matrix(size_t InitRowSize, size_t InitColumnSize)
    {
        RowSize = InitRowSize;
        ColumnSize = InitColumnSize;

        MatrixData = new int* [ColumnSize];

        for (size_t i = 0; i < ColumnSize; i++)
        {
            MatrixData[i] = new int[RowSize];
        }
    }

    ~Matrix()
    {
        for (size_t i = 0; i < ColumnSize; i++)
        {
            delete[] MatrixData[i];
        }

        delete MatrixData;
    }

    T* operator[](std::ptrdiff_t Idx) const
    {
        return MatrixData[Idx];
    }

    inline size_t GetRowSize() const { return RowSize; }
    inline size_t GetColumnSize() const { return ColumnSize; }
    inline T** GetData() const { return MatrixData; }

private:
    size_t RowSize;
    size_t ColumnSize;
    T** MatrixData;
};

void SumMatrix_RowMajor(const Matrix<int>& TargetMatrix, long long int& OutSum)
{
    for (size_t RowIndex = 0; RowIndex < TargetMatrix.GetRowSize(); ++RowIndex)
    {
        for (size_t ColumnIndex = 0; ColumnIndex < TargetMatrix.GetColumnSize(); ++ColumnIndex)
        {
            OutSum += TargetMatrix[RowIndex][ColumnIndex];
        }
    }
}

void SumMatrix_ColumnMajor(const Matrix<int>& TargetMatrix, long long int& OutSum)
{
    for (size_t ColumnIndex = 0; ColumnIndex < TargetMatrix.GetColumnSize(); ++ColumnIndex)
    {
        for (size_t RowIndex = 0; RowIndex < TargetMatrix.GetRowSize(); ++RowIndex)
        {
            OutSum += TargetMatrix[RowIndex][ColumnIndex];
        }
    }
}

int main()
{
    static size_t RowSize = 20000;
    static size_t ColumnSize = 20000;

    std::cout << "Matrix 할당 시작" << std::endl;
    Matrix<int> OurMatrix(RowSize, ColumnSize);
    std::cout << "Matrix 할당 종료" << std::endl;

    srand(std::time(NULL));

    std::cout << "Matrix 랜덤 값 입력 시작 (" << RowSize*ColumnSize<<"개)" << std::endl;
    for (size_t Row = 0; Row < OurMatrix.GetRowSize(); Row++)
    {
        for (size_t Column = 0; Column < OurMatrix.GetRowSize(); Column++)
        {
            OurMatrix[Row][Column] = rand();
        }
    }
    std::cout << "Matrix 랜덤 값 입력 종료" << std::endl;
    std::cout << std::endl;

    std::cout << "Row Major 순회 시작" << std::endl;
    long long int RowMajorResult = 0;
    std::chrono::system_clock::time_point RowStartTime = std::chrono::system_clock::now();

    SumMatrix_RowMajor(OurMatrix, RowMajorResult);

    std::chrono::system_clock::time_point RowEndTime = std::chrono::system_clock::now();
    std::cout << "Row Major 순회 종료" << std::endl;

    std::chrono::milliseconds RowCalcTime = std::chrono::duration_cast<std::chrono::milliseconds>(RowEndTime - RowStartTime);

    std::cout << "Row Major 방식 걸린 시간 : " << RowCalcTime.count() << " ms" << std::endl;
    std::cout << std::endl;

    std::cout << "Column Major 순회 시작" << std::endl;
    long long int ColumnMajorResult = 0;
    std::chrono::system_clock::time_point ColumnStartTime = std::chrono::system_clock::now();

    SumMatrix_ColumnMajor(OurMatrix, ColumnMajorResult);

    std::chrono::system_clock::time_point ColumnEndTime = std::chrono::system_clock::now();
    std::cout << "Column Major 순회 종료" << std::endl;

    std::chrono::milliseconds ColumnCalcTime = std::chrono::duration_cast<std::chrono::milliseconds>(ColumnEndTime - ColumnStartTime);

    std::cout << "Column Major 방식 걸린 시간 : " << ColumnCalcTime.count() << " ms" << std::endl;
    std::cout << std::endl;

    bool bIsRowMajorFaster = RowCalcTime < ColumnCalcTime;
    std::cout << std::endl;

    std::cout << "빠른 방식 : " << (bIsRowMajorFaster ? "Row Major" : "Column Major") << " | " << "차이 : " << abs(ColumnCalcTime.count() - RowCalcTime.count()) << " ms" << std::endl;

    return 0;
}

테스트 환경은 아래와 같다.

  • 테스트는 20000 by 20000 총 4억개의 int 형 데이터를 가진 Matrix 를 만들어 사용했다.
  • SumMatrix 함수를 RowMajor와 ColumnMajor 두 방식을 동시에 지원할 수 있도록 if 문으로 브랜칭을 할 수있겠으나, 미묘한 성능차이가 발생할 수도 있을 것 같아 하지 않았다.
  • 그래서 두 방식을 각각 SumMatrix_RowMajor, SumMatrix_ColumnMajor 로 나누어 순수하게 순회 및 Read-Modify-Write 작업만 하도록 하였다.
  • 실행 환경은 아래와 같다.
    • PC : Ryzen 7 3700X 8-Core (3.6 GHz), 64GB DDR4, SSD 1TB
      • x64 Debug Mode Build
    • 개인 노트북 : i7-10750H 6-Core (2.6GHz), 16GB SO-DIMM, NVMe 1TB
      • x64 Debug Mode Build

결과

PC

개인 노트북

PC 기준 Row Major 방식이 약 4초 정도 더 빠르다! 컴퓨터에게 있어 4초는 엄청난 시간이다.

그런데 더 심각한건 개인 노트북이다. 약 13초 정도 차이가 발생한다.

둘은 결과적으로 같은 2차원 배열 순회 요청을 했는데 성능상에 차이가 발생했다.

무슨일이 있었던 것일까?

Traversal Order Matters!

문제의 원인을 미리 알려주자면, 순회하는 방식이 달랐기 때문이다.

조금 더 자세히 말하면, CPU Cache (캐시) 의 이점을 잘 살렸는지 아닌지의 결과라고 할 수 있다.

CPU 캐시가 무엇이길레 이런 결과를 만들었을까?

CPU가 메모리를 사용하는 방식을 한 번 알아보자.

CPU Cache

CPU에서 캐시란 컴퓨터 시스템의 성능을 향상시키기 위해 별도로 탑재된 일종의 메모리이다.

캐시는 CPU 칩안에 들어가는 작고 아주 빠르고 아주 아주 비싼 메모리다.

프로세서가 메인 메모리에 접근해 데이터를 받아오면 시간이 오래 걸리기 때문에 캐시에 자주 사용하거나 최근에 사용한 데이터를 담아두고 해당 데이터가 필요할 때 프로세서가 메인 메모리 대신 캐시에 접근하도록해 처리 속도를 높인다.

기술의 발전으로 프로세서 속도는 빠르게 증가해온 반면에 아쉽게도 메모리는 프로세서의 발전 속도를 잘 따라가지 못했다.

프로세서가 아무리 빨라도 메모리의 처리 속도가 느리면 결과적으로 전체 시스템 속도는 느려진다.

이렇게 특정 부분이나 위치에서 데이터를 처리하는 속도 또는 대역폭 차이에 따라 전반적으로 성능의 지연이 일어나는 것을 병목 현상(Bottle Neck)이라고 한다.

캐시메모리는 프로그램을 통해 직접적으로 읽거나 쓸 수는 없고, 하드웨어의 메모리 관리 시스템이 내부적으로 관리하며 제어한다.

프로그래머가 메모리를 필요에 의해 쓸때마다 CPU에 그 메모리 주소나 데이터 그리고 어떻게 해야되는지에 대한 인스트럭션 정보를 갖다주어야 한다.

이해를 조금 더 쉽게 해보기 위해 예를 들어 설명해보자면 이럴 것 같다.

주방과 도마 그리고 냉장고

요리를 하기 위해 재료들을 주방에 있는 도마위에 올리는 작업이라고 비유하면 조금 더 이해가 될 것 같다.

그리고 이 재료를 껍질을 까던지, 물에 담그던지 하는 것을 인스트럭션 이라고 한다.

프로그램은 다양한 재료(데이터)가 들어있는 거대한 냉장고와 레시피(인스트럭션)가 있는 구조라고 보면 된다.

냉장고에 매번 들러서 재료를 가지러 왔다갔다 하는 것은 귀찮고 힘들고 시간이 오래걸린다.

이런 문제를 해결하기 위해, 주방에 미니 냉장고를 하나 놔두고, 최근에 썼던 재료나 같이 가져온 재료들을 캐시 라고 볼 수 있다. 주방 근처에 있어 접근이 매우 빠를것이기 때문이다.

비유가 적절한지는 살짝 자신이 없긴한데 다시 돌아와서 CPU 관점에서 보도록 하겠다.

자주 접근 또는 사용하는 데이터 판단?

대부분의 프로그램에서 한 번 사용한 데이터를 다시 사용할 가능성이 높다.

그런데 자주 사용할 데이터들은 최대한 CPU에 가까이 있고 빨리 접근할 수 있는 곳에 있는게 좋지 않을까?

자주 사용하는 데이터를 가까이 두고 미리 위치를 알아두면 좋다는 것은 이제 어느정도 감이 왔을 것이다.

그런데 자주 사용하는 데이터를 어떻게 판단할 수 있을까?

Cache Locality

캐시 지역성이라고 하는 것이 위의 질문에 대한 대답을 해줄 수 있다.

캐시 지역성이란 메모리를 접근하는 경향에 따라 나눌 수 있다.

시간 지역성 (Temporal Locality)

시간 지역성은 최근에 접근한 데이터에 다시 접근하는 경향을 말한다.

예를 들어 아이템을 판매하기 위해 최종가격을 정하는 아래의 코드를 봐보자.

//Items는 100개의 원소를 보관중이라 가정한다.
for (int i = 0; i < Items.Size(); i++)
{
    TotalPrice += Items[i].GetPrice();
}

Items 라는 배열에서 아이템의 가격들을 가져와 TotalPrice 라는 변수에 계속 더해준다.

이때 TotalPrice 라는 변수는 for 루프가 아이템이 100개 있다고 가정했기 때문에 Size를 가져왔다면 100번 접근해 값을 추가해주고 다시 메모리에 써줘야한다.

그런데 메인 메모리에 있을 TotalPrice 메모리 주소에 대한 데이터를 저장해두고 있다면, 우리는 CPU에게 더 빨리 연산처리를 요청할 수 있게 된다.

for 루프를 돌려주는 i 변수도 그렇고 Items 배열에 대한 데이터도 루프가 도는 상황에서 매번 가져오기에는 시간이 아깝다.

그래서 CPU에 가까운 캐시메모리에 저장해두고 사용하면 더욱 빠르게 메모리를 읽어낼 수 있기 때문에 속도가 올라간다.

공간 지역성 (Spatial Locality)

공간 지역성은 최근 접근한 데이터의 주변 공간에 다시 접근하는 경향을 말한다.

아까 보았던 코드에서 Items 배열은 한 번에 할당(Allocate)된 메모리라고 하겠다.

우리는 Items 배열의 Size만큼 Items를 순차적으로 탐색하며 가격을 가져올 것이다.

Items 배열을 그림으로 표현해보자면 다음과 같다.

배열과 같이 메모리 주소가 나열되어있는 컨테이너를 순회하는 상황은 대부분 선형적인 탐색을 통해 이뤄진다.

이처럼 근처 또는 바로 옆에 있는 메모리를 참조하는 상황들이 자주 발생하게 된다.

이런 경향을 공간 지역성이라고 한다.

Cache Line

아침먹으러 장봐오고 점심 먹을때 또 장봐오고 저녁 먹으려고 장을 봐오면, 3번이나 마트 또는 시장에 가야한다.

이왕 아침 점심 저녁을 다 먹을 것이니, 한 번 장보러 다녀올 때 아침 점심 저녁에 차릴 메뉴중 생각나는 재료들을 같이 가져오면 나중에 또 다시 장을 보러갈 확률을 줄일 수 있다.

이처럼 이후에 쓸 것이라 생각되는 데이터들을 묶어 한 번에 가져온 데이터들의 단위를 캐시 라인이라고 한다.

대부분의 CPU가 하나의 캐시라인을 64Byte 기준으로 읽어온다.

Cache Hit & Cache Miss

캐시 히트와 미스는 각각 메모리를 탐색하기 전 CPU 캐시 내부에서 원하는 정보가 있었는지 없었는지를 의미한다.

캐시에 원하는 데이터가 있다면 Cache Hit !

캐시에 원하는 데이터가 없다면 Cache Miss 이다.

Cache Hit가 발생한 경우는 CPU 캐시 내부에서 원하던 정보가 있었으므로 메인 메모리까지 갈 필요가 없어 빠르게 작업을 처리할 수 있게 된다.

왜냐하면 CPU는 연산을 할 준비가 만땅이라고 하더라도, 연산에 요청된 데이터가 늦게 도착한다면 열정적으로 대기하는수밖에 없기 때문이다.

캐시 미스가 발생하는 경우 이전에 말했듯 열정적으로 대기하는 상황이 발생하여 작업 처리 속도가 저하된다.

이전에 예로 들었던 Row & Column Major 방식에 대한 차이가 얼만큼 캐시 히트가 발생했는지에 따라 만들어진 차이였다.

미리 다음에 같이 연산될만한 데이터들에 정보를 담고있으면 캐시 히트 확률이 올라갈 것이다.

이 생각을 들게 만드는 공간 지역성의 경향은 근처에 있는 메모리 데이터도 함께 일단 가져와 보는 아이디어로 발전해서 현세대의 CPU는 캐시 라인(Cache Line) 이라고 불리는 일정 크기의 데이터 덩어리를 한 번에 가지고 온다.

대신 근처에 있는 데이터들을 묶어 가져오기 때문에, Row Major의 경우 순차접근시 다음에 있는 메모리등을 참조해 가져왔을 확률이 매우 높은데, Column Major의 경우 바로 옆에 있는 메모리가 아니라, Row 한줄만큼의 주소를 건너뛴 위치에 있는 메모리가 다음 조사 대상이므로 캐시 히트 확률이 매우 낮아지게 된다.

사소하다면 사소할 수 있는 이러한 순회 방식의 차이는 사실 CPU와 메모리의 데이터 이동 및 연산에 관점에서는 매우 중대한 차이였음을 이제 알 수 있게 되었다.

시간 지역성과 공간 지역성을 통해 우리는 프로그램 동작에 있어 특정한 경향을 파악할 수 있고 캐시히트와 미스가 성능에 어떠한 영향을 미치는지 코드를 통한 실험으로 설명과 증명까지 진행하였다.

지금까지 봐보니 CPU 캐시를 히트가 잘 나는 구조와 순서로 사용하면 좋다는 것은 알겠다.

그런데 지금까지 말한 CPU 캐시는 도대체 어디에 있는 것인가?

L1, L2, L3 Caches

현대적인 CPU 칩의 구조를 보면 위와 같다.

CPU 칩의 면적에서 적어도 50% 정도는 캐시가 차지한다.

캐시 메모리는 대부분 CPU 칩 내부에 존재한다. 프로세서와 가까우면 가까울 수록 낭비되는 시간이 적어지기 때문이다.

사진을 자세히 보면 코어가 나란히 붙어있고 그 내부 아주 작고 소중한 L1 (Level-1)캐시가 있다.

그 근처에 또 L2 (Level-2) 캐시가 있다.

그리고 모든 코어가 공유하는 L3 (Level-3) 캐시가 있다.

이렇게 캐시의 계층 구조(Cache Hirerarchy) 또는 레벨 구조 라고 한다.

이렇게만 이야기하면 반도체 사진만 보고있어야할 것이다. 조금 더 쉬운 사진을 가져와보겠다.

CPU와 Cache 그리고 Main Memory는 지금까지 한 번 들어는 봤다.

Level 1,2,3 캐시는 그럼 도대체 무엇일까?

Level3 Cache

L3 캐시는 멀티 코어 시스템에서 여로 코어가 공유하는 캐시이다.

CPU 내부에 존재하는 가장 큰 캐시 메모리이다.

용량이 큰 만큼 여러 코어에서 지금까지 사용한 캐시 메모리들을 지역성에 원리에 따라 담아두고있다.

Level2 Cache

L2 캐시는 각각의 코어가 가지고 있는 캐시 메모리이다.

이 또한 L1에서 캐시된 정보들을 지역성의 원리에 따라 어느정도 담아두고 있다.

L1 캐시보다는 용량이 더 크다.

Level1 Cache

L1 캐시는 대부분 프로세서인 코어와 가장 가까운 위치에 존재하는 캐시 메모리이다.

연산 속도를 위해 Instruction Cache (I$) 와 Data Cache (D$) 로 나뉜다.

각각의 설명을 해보자면 아래와 같다.

  • Instruction Cache ( I$) : 메모리의 TEXT (코드) 영역 데이터를 다루는 캐시
  • Data Cache (D$) : 메모리의 TEXT 영역을 제외한 모든 데이터를 다루는 캐시

다른 사진으로 보자면 아래와 같다고도 할 수 있다.

Cache Coherence

캐시 일관성이란 공유 메모리 시스템에서 각 프로세서(또는 코어)가 가진 로컬 캐시 간의 일관성을 의미한다.

각 코어가 자신만의 로컬 캐시(L1, L2) 를 가지고 다른 여러 코어와 메모리를 공유하고 있을 때

각각의 로컬 캐시가 일관된 데이터를 가지고 있다면, 추가적인 수정 절차 없이 바로 데이터를 이용할 수 있다.

예를들어 위에 사진에서 Core1과 Core2에 로컬 캐시에서 변수 X 라는 데이터가 캐시되어있고 값은 두 로컬 캐시상에서 모두 0이었다고 하자.

그런데 연산중 Core1에서 변수 X의 값을 1로 바꿨다고 해보자.

그럼 Core2에 캐시되어있는 변수 X의 데이터는 0이고 Core1에서 바뀐 변수 X의 값은 1로 불일치가 발생한다.

Core2에 있는 변수도 캐시 히트가 발생하긴 해서 읽어 쓸 수 있다고 생각할 수는 있지만 그러면 안된다.

이렇게 작업이 계속 진행될 경우 데이터의 무결성을 보장받을 수 없기 때문에, 특정 메모리가 변경될 경우 오염되었다는 Dirty 처리를 통해 즉각적으로 데이터의 값을 바뀐 값으로 업데이트해주거나, 잠시 연산을 멈추고 변수의 변경점을 업데이트해 Dirty 처리를 해제해야한다.

캐시 일관성은 다시 말하면 항상 최신으로 업데이트 되어있는 내용을 읽을 수 있도록 해주도록 지원해야하는 것이라고 볼 수 있다.

캐시의 일관성이 잘 유지되면 유지될수록 데이터의 Dirty 처리를 해결하는데 필요한 연산력이나 자원 또는 시간이 낭비되는 것을 막을 수 있다.

캐시 일관성을 유지하기 위해서는 다른 프로세서가 갱신한 캐시 값을 즉시 혹은 지연시켜 다른 프로세서에서 사용할 수 있도록 해주어야한다.

False Sharing

거짓 공유란 캐시 일관성(Cache Coherence) 때문에 시스템이 실제로 공유되고 있지 않은 캐시 데이터를 동기화하며 발생하는 문제를 의미한다.

이 문제는 멀티 스레드 환경에서 쓰기 동작을 할 경우 일어날 가능성이 매우 높아지게 되는데 다음 사진을 보면 감이 온다.

이전에 말했듯 CPU 에서는 캐시라인 단위로 메모리에서 데이터를 읽어온다.

CPU0의 스레드가 캐시라인의 첫번째 블록 메모리를 읽고 썼다고 하겠다.

CPU1은 CPU0이 캐싱한 캐시라인의 두번째 블록 메모리를 읽고 쓰려고 한다.

이럴 경우 CPU0의 쓰기 동작이 두번째 블록에 있는 데이터를 건들이지 않았다고 하더라도, 캐시라인 자체는 Dirty 처리가 되어있다.

그래서 CPU1은 캐시 일관성을 유지하기 위해 현재 저장한 캐시라인을 통째로 버리고 다시 캐시라인을 읽어들인다.

일종의 동기화를 맞추기 위한 작업이 Race를 일으키며 계속 성능을 저하시키는 문제다.

동기화를 맞추기 위해 메모리를 계속 다시 왔다갔다해야한다.

어떻게보면 두 스레드가 돌며 동일한 변수를 변경시킬때 발생하는 문제를 막기위해 Lock을 걸어 한 스레드만 접근할 수 있도록 만드는 Critical Section이 떠오르는 동기화 방식이다.

False Sharing을 어떻게 막을 수 있을까?

False Sharing의 근본적인 문제는 서로 다른 캐시가 같은 캐시라인을 점유하며 한 곳에서 변조된 값을 다른 곳에 알려주고 다시 메모리에 다녀와 캐시값의 동기화를 맞춰주는 시간에서 오는 것이다.

위에 대한 문제를 예로 들어보겠다.

위와같이 거대한 Datas 라는 큰 데이터 배열의 범위를 나누어 멀티 스레드로 합하는 작업이라고 했을 때, Result 배열에 Datas계산된 값을 모두 넣는다고 하자.

이때 계산에 대한 결과를 만드는 방식을 2가지로 나눠보겠다.

  • 덧셈을 할 때 마다 각각의 스레드에서 Result 배열에 매번 접근하여 값을 더하는 방식
  • 덧셈을 스레드 내부에서 로컬 변수로 계산하고, Result 배열에 결과만 넣는 방식

코드를 짜보면 아래와 같다.

False Sharing Test Code

#include <iostream> 
#include <thread> 
#include <chrono> 


using namespace std;

using int64 = long long int;

constexpr int64 DATASIZE = 1000000000LL;

volatile int64 Result[3];

void KeepUpdateJob(int Index)
{
    for (int64 i = 0; i < DATASIZE; ++i)
    {
        Result[Index] += 1LL;
    }
}

void OneTimeUpdateJob(int Index)
{
    volatile int64 LocalResult = 0;

    for (int64 i = 0; i < DATASIZE; ++i)
    {
        LocalResult += 1LL;
    }

    Result[Index] = LocalResult;
}

int main()
{
    Result[0] = 0;
    Result[1] = 0;
    Result[2] = 0;

    cout << "Keep Update Job 1~3 Start" << endl;
    auto K_BeginTime = chrono::high_resolution_clock::now();

    std::thread K_Task1(KeepUpdateJob, 0);
    std::thread K_Task2(KeepUpdateJob, 1);
    std::thread K_Task3(KeepUpdateJob, 2);

    K_Task1.join();
    K_Task2.join();
    K_Task3.join();

    auto K_EndTime = chrono::high_resolution_clock::now();

    chrono::duration<double> K_ElapsedTime = K_EndTime - K_BeginTime;

    cout << "Keep Update Job 1~3 Ended" << endl;

    cout << Result[0] << endl;
    cout << Result[1] << endl;
    cout << Result[2] << endl;

    cout << "Time : " << K_ElapsedTime.count() << "s" << endl;
    cout << endl;

    Result[0] = 0;
    Result[1] = 0;
    Result[2] = 0;

    cout << "One Time Update Job 1~3 Start" << endl;
    auto OT_BeginTime = chrono::high_resolution_clock::now();

    std::thread OT_Task1(OneTimeUpdateJob, 0);
    std::thread OT_Task2(OneTimeUpdateJob, 1);
    std::thread OT_Task3(OneTimeUpdateJob, 2);

    OT_Task1.join();
    OT_Task2.join();
    OT_Task3.join();

    auto OT_EndTime = chrono::high_resolution_clock::now();

    chrono::duration<double> OT_ElapsedTime = OT_EndTime - OT_BeginTime;

    cout << "One Time Update Job 1~3 Ended" << endl;

    cout << Result[0] << endl;
    cout << Result[1] << endl;
    cout << Result[2] << endl;

    cout << "Time : " << OT_ElapsedTime.count() << "s" << endl;
    cout << endl;

    bool bIsOneTimeFaster = OT_ElapsedTime < K_ElapsedTime;
    cout << "빠른 방식 : " << (bIsOneTimeFaster ? "One Time Update" : "Keep Update") << endl;
    cout << "시간 차이 : " << abs(K_ElapsedTime.count() - OT_ElapsedTime.count()) << endl;

    return 0;
}

결과는 다음과 같다.

이전에 RowMajor와 Column Major의 비교때와 같이 동일한 작업을 했지만, 성능상에 큰 차이가 발생했다.

지금 비교에 경우엔 거의 6~11배 정도의 시간 차이가 발생했다.

Result는 배열로 만들었기 떄문에 메모리가 연속적으로 나란히 잡혀있을 것이다.

그럼 캐시라인상에서 같은 위치에 존재할 가능성이 매우매우높다.

3가지 스레드는 서로 다른 Result 배열의 인덱스를 쓰지만, 같은 캐시라인을 캐시하고있을 것이다.

한 스레드가 Result의 특정 인덱스에 쓰기 작업을하면, 그 데이터가 있는 캐시라인은 Dirty 처리가 된다.

그럼 같은 캐시라인을 캐싱한 곳들은 일관적인 데이터를 사용할 수 없게 되므로 Dirty 처리된 캐시라인을 버리고 다시 메인메모리로 접근해 최신 데이터로 업데이트를 해야한다.

그동안에 CPU 사이클 비용이 발생하고 이게 누적되어 저렇게 큰 결과를 낳게 된 것이다.

매번 접근해 값을 바꿔 캐시라인의 일관성을 해치지말고 가능하다면 스레드 내부에서 처리할 수 있는 것들은 스레드 내부에서 처리해 결과만 뽑아와 사용하는 것이 좋을 것 같다.

참고자료

https://www.aristeia.com/TalkNotes/codedive-CPUCachesHandouts.pdf

https://namu.wiki/w/CPU/구조와

https://namu.wiki/w/캐시_메모리

https://ko.wikipedia.org/wiki/변환_색인_버퍼

https://www.drdobbs.com/parallel/maximize-locality-minimize-contention/208200273?cid=RSSfeed_DDJ_ArchitectDebug

한솔님!