03 Multiple Processor System(Multicore System)의 Cache 효율 높이기

kkamagui(까마귀, 한승훈) 2008. 4. 20. 23:51

2008. 4. 20. 23:51

Multiple Processor System(Multicore System)의 Cache 효율 높이기

원문 : http://kkamagui.springnote.com/pages/1092170

참고 1 : http://softwarecommunity.intel.com/articles/eng/2760.htm

참고 2 : http://minjang.egloos.com/1848130

들어가기 전에...

이 글은 kkamagui에 의해 작성된 글입니다.
마음껏 인용하시거나 사용하셔도 됩니다. 단 출처(http://kkamagui.tistory.com, http://kkamagui.springnote.com)는 밝혀 주십시오.
기타 사항은 mint64os at gmail.com 이나 http://kkamagui.tistory.com으로 보내주시면 반영하겠습니다.
상세한 내용은 책 "64비트 멀티코어 OS 구조와 원리"를 참고하기 바랍니다.

OS 개발에 관한 서적

하위 페이지에 있는 자료들은 OS를 개발하면서 관련된 자료들을 일부 정리해 놓은 것이다. OS 개발에 대한 보다 자세한 내용은 "64비트 멀티코어 OS 원리와 구조"를 참고하기 바란다.

<64비트 멀티코어 OS 원리와 구조>

0.시작하면서...

이 글은 Multiple Processor System에서 발생할 수 있는 Shared Cache의 문제를 어떻게 해결할 수 있는지를 설명하는 문서이다. 참고 자료의 내용 중에 테스트 가능한 부분만 요약하고 추가적인 내용을 덧붙였으니, 원문이 궁금하면 참고 1(http://softwarecommunity.intel.com/articles/eng/2760.htm) 문서를 보면 된다.

1.Processor, Core, Cache

최근의 Processor는 Core를 2개 이상 탑재하는 방식으로 제작되고 있으며, 그에 따라 Cache의 중요성이 점점 높아지고 있다. CPU 업계를 이끌어 나가는 INTEL과 AMD는 Cache 구성에 대해 서로 다른 정책을 펴고 있으나, 공통적으로 Cache의 크기를 점차 넓혀가는 추세이다.

Processor에 포함된 Core가 많고 Cache의 크기가 커지면 커질수록 성능이 배로 좋아질 것 같지만, 실제로는 각 Cache Level(L1, L2, L3)간의 동기화 문제가 발생하기때문에 정비례하지 않는다. 다시말하면 Core 0와 Core 1이 동일한 Data에 접근하거나 같은 Cache Line에 있는 데이터에 접근해서 Read/Write를 하게 될 경우, 각 Cache Level의 Data를 Syncronization(동기화)해야하기 때문에 성능이 저하되는 것이다. 이에대한 자세한 내용은 다음 장에서 살펴보자.

아래는 2개의 Core를 가지는 Processor 2개를 연결한 그림이다. Processor 0에 L2 Cache가 Core 0와 Core 1에 공통으로 사용되고 있으며, L1 Cache는 각 Core에 할당되어 공유되지 않음을 볼 수 있다. L1 Cache 공유되지 않기 때문에 위에서 언급했던 L1 Cache와 L2 Cache간에 Syncronization 문제가 발생하게 된다.

<2 Dual Core Processor>

그럼 지금부터 Cache를 효율적으로 사용할 수 있는 몇가지 방법에 대해 알아보자.

2.Cache Optimization Tip

2.1 Processor Affinity

Multithread 프로그램의 경우, 개별 Thread는 개별 Core에 할당되서 동시에 실행될 수 있다. Core에 할당되는 Thread는 Scheduling Algorithm에 따라 달라지며, 하나의 Core에서 실행되거나 여러 Core를 돌며 실행될 수 있다. Thread A가 Core A와 Core B에서 교대로 실행되는 경우, Thread A가 사용하는 Data를 매번 L2 Cache에서 L1 Cache로 옮겨오는 최악의 상황이 발생할 수 있으며 그로 인해 성능이 저하될 수 있다.

이러한 경우 Thread를 특정 Core에 할당해서 실행함으로써 Overhead를 줄일 수 있다. 또한 각 Thread가 Data를 공유하지 않는다면, 개별 Thread를 특정 Core에서만 수행되도록 할당함으로써 성능을 높이는 것이 가능하다.

Windows 환경과 Linux 환경에서는 아래의 2가지 API를 사용해서 Thread와 Process의 Processor Affinity를 설정할 수 있다.

// Windows API
BOOL SetProcessAffinityMask(
HANDLE hProcess,
DWORD_PTR dwProcessAffinityMask
);
DWORD_PTR SetThreadAffinityMask(
HANDLE hThread,
DWORD_PTR dwThreadAffinityMask
);
// Linux API
/* Get the CPU affinity for a task */
extern int sched_getaffinity(
pid_t pid,
size_t cpusetsize,
cpu_set_t *cpuset
);
/* Set the CPU affinity for a task */
extern int sched_setaffinity(
pid_t pid,
size_t cpusetsize,
const cpu_set_t *cpuset
);

하지만 Affinity가 좋은 점만 있는 것은 아니다. 할당된 Core에 Load가 몰리는 경우, Scheduling 순서를 기다리느라(Waiting Queue에 대기) 오히려 더 지연 될 수 있으니 주의해야 한다.

2.2 Cache Blocking(Data Tiling)

Cache Blocking 또는 Data Tiling 기법은 Loop를 수행할 때, Loop에서 사용되는 Data가 Cache Line에 존재하도록하는 기법이다. 만약 Data Block이 크다면, Cache에 Load된 Data가 Loop시에 한번만 사용되고 버려지고 현상이 반복될 수 있다. 이러한 최악의 상황은 Cache의 Hit Ratio를 떨어뜨리며 성능을 저하시키는 요인이 된다. 이러한 현상을 해결하는 좋은 방법은 Data를 Tile 처럼 잘게 쪼개서 작은 Loop로 처리하는 것이다.

아래의 그림과 같이 (A)와 같이 큰 Data를 사용하는 Loop를 (B)처럼 작은 Data를 사용하는 Loop로 나눔으로써, Data Block을 Cache에 올려 성능을 높일 수 있다.

<Cache Blocking(Data Tiling)>

2.3 Hold Approach

Hold Approach는 빈번하게 Read/Write하는 것을 Local Copy를 사용하여 줄임으로써 Cache 효율을 높이는 방법이다. Thread Local Storage나 Local Variable을 사용하여 작업한 후, 결과를 Reporting하는 것이 이에 해당한다. 아래의 그림은 Hold Approach를 그림으로 표현한 것이다.

<Holding Approach>

좌측의 (A)와 같이 빈번하게 Read/Write하던 것을 Local Copy를 통해 (B)와 같이 줄여서 효율을 높일 수 있다.

2.4 Avoid False Sharing

False Sharing이란 Multiple Processor System의 유명한 문제이다. 각 Core에서 수행중인 Thread간의 공유하는 Data가 없지만, 동일한 Cache Line에 있는 Data를 접근함으로써 매번 Evict와 Load가 반복되는 현상이다. 실제로는 Cache Coherency Problem(협업 문제)가 전혀 발생하지 않지만, Cache의 정보가 변경되었으므로 어쩔 수 없이 L1 Cache의 내용을 L2 Cache에 옮기고 다시 다른 Core의 L1 Cache로 옮겨야 한다. 아래의 그림은 Flase Sharing을 그림으로 표현한 것이다.

<False Sharing>

Core 0의 Thread 0와 Core 1의 Thread 1은 서로 공유하는 Data가 없지만 동일한 Cache Line에 위치함으로 Evict와 Load가 반복되게 된다.

이러한 False Sharing을 피하는 방법은 아래와 같다.

공유되지 않는 Data는 다른 Cache Line에 둔다. 즉 Padding Data를 두거나 다른 Memory Address에 할당한다. 단, 너무 많은 Cache Line을 할당하지 않도록 Data를 잘 묶어서 적당히 배열한다.
Hold Approach와 마찬가지로 Data를 Local 영역에 저장하고 필요할때만 Read/Write하여 Evit/Load 회수를 줄인다.
Thread의 Affinity를 설정하여 Thread 0와 Thread 1이 동일한 Core에서 수행되도록 한다.

3.Test

아래는 Cache Optimazation Test에 사용한 간단한 코드이다. 윈도우즈 환경에서 VC++ 6.0으로 테스트했으며 Release 모드에서 Optimization 옵션은 Debug 모드와 같이 사용하지 않는 것으로 설정하고, 8Byte Aling, MultiThread DLL을 사용하도록 설정했다.

테스트에 사용된 PC는 INTEL Core 2 Duo 2.6GHz에 4G의 RAM으로 구성되어있다.

3.1 Affinity & Cache Blocking Test

아래는 Affinity와 Cache Blocking을 테스트하는 간단한 코드이다.

#include <windows.H>
#include <stdio.H>
#include <tchar.H>
#define UNIT 32
#define MULTIPLE 200000
#define MAX_DATA UNIT * MULTIPLE
#define MAX_LOOP 200
// 계산할 데이터가 들어있는 배열
volatile int g_iData[ MAX_DATA ] = { 1, 2, };
// 실제 메인 함수
int main(int argc, char* argv[])
{
    DWORD dwSum;
    int i;
    int j;
    int k;
    int l;
    DWORD dwStartTime;
    DWORD dwEndTime;
    DWORD dwTimeSum;
// Processor High Priority로 만든다.
SetPriorityClass( GetCurrentProcess(), HIGH_PRIORITY_CLASS );
// Affinity 설정
SetProcessAffinityMask( GetCurrentProcess(), 0x1 );
    // 카운팅 시작
    dwSum = 0;
    dwTimeSum = 0;
    printf( "Start Processing...\n" );
    for( l = 0 ; l < 20 ; l++ )
    {
        dwStartTime = GetTickCount();

        // Normal Loop
        for( j = 0 ; j < MAX_LOOP ; j++ )
        {
            for( i = 0 ; i < MAX_DATA ; i++ )
            {
                dwSum += g_iData[ i ];
            }
        }
        /*
        // Cache Blocking
        for( k = 0 ; k < MULTIPLE ; k++ )
        {
            for( j = 0 ; j < MAX_LOOP ; j++ )
            {
                for( i = k * UNIT ; i < ( k + 1 ) * UNIT ; i++ )
                {
                    dwSum += g_iData[ i ];
                }
            }
        }
        */

        //결과 출력
        dwEndTime = GetTickCount() - dwStartTime;
        dwTimeSum += dwEndTime;
        printf( "%d Time = %d ms\n", l + 1, dwEndTime );
    }
printf( "Average Time = %0.2f\n", dwTimeSum / 20.0 );
return 0;
}

아래는 위의 코드를 이용해서 테스트한 결과이다.

Normal Loop
- Affinity 미사용
  - Average Time = 4225.00
  - Average Time = 4201.55
- Affinity 1 사용 - 하나의 Core에서만 동작시킴
  - Average Time = 4275.00
  - Average Time = 4256.25
Cache Blocking
- Affinity 미사용
  - Average Time = 3836.70
  - Average Time = 3818.70
- Affinity 1 사용 - 하나의 Core에서만 동작시킴
- - Average Time = 3875.80
  - Average Time = 3860.90

테스트 결과 Data Block 크기가 클수록, 즉 Cache Evit가 발생할 확률이 높으면 높을수록 Cache Blocking의 효과가 커졌다. Processor Affinity 부분은 오히려 Affinity를 적용한 결과가 근소하게 더 느리게 나왔다. 이것은 Thread가 Core를 옮겨다니며 Cache를 Reflesh하는 시간 보다 할당 받은 Core의 Wait Queue에서 대기하는 시간이 더 길기 때문에 발생한 듯하다. 이 결과는 어디까지나 테스트 프로그램의 결과이고, 만약 더 큰 Data에 접근하고 보다 복잡한 코드로 이루어져 있다면 충분히 달라질 수 있는 부분이다.

3.2 Affinity & Avoid False Sharing Test

아래는 Affinity와 False Sharing을 테스트하는 간단한 코드이다.

#include <windows.H>
#include <stdio.H>
#include <tchar.H>
// 각 스레드에서 사용하는 전역 변수
volatile int g_iData1 = 0;
volatile int g_iData2 = 0;
// Cache line을 맞추기위해 정의한 구조체
// 강제로 공간을 할당한다.
typedef struct dataStruct
{
    volatile int iData1;
    int viData[32];
    volatile int iData2;
} DATA;
// Cache line 정렬용 구조체
DATA g_stData = { 0, {0,}, 0 };
// 테스트 Thread 1
DWORD CALLBACK TestThread1( void* pData )
{
    /*
    // 지역변수 사용
    int i;
    int iTemp;
iTemp = g_iData1;
    for( i = 0 ; i < 0x1FFFFFFF ; i++ )
    {
        iTemp = iTemp + 1;
    }
    g_iData1 = iTemp;
    return g_iData1;
    */
    /*
    // 바로 접근
    int i;
    for( i = 0 ; i < 0x1FFFFFFF ; i++ )
    {
        g_iData1 = g_iData1 + 1;
    }
    return g_iData1;
    */
    // False Sharing
    int i;
    for( i = 0 ; i < 0x1FFFFFFF ; i++ )
    {
        g_stData.iData1 = g_stData.iData1 + 1;
    }
    return g_stData.iData1;
}

// 테스트 Thread 1
DWORD CALLBACK TestThread2( void* pData )
{
    /*
    // 지역변수 사용
    int i;
    int iTemp;
iTemp = g_iData2;
    for( i = 0 ; i < 0x1FFFFFFF ; i++ )
    {
        iTemp = iTemp + 1;
    }
    g_iData2 = iTemp;
    return g_iData2;
    */
    /*
    // False Sharing
    int i;
    for( i = 0 ; i < 0x1FFFFFFF ; i++ )
    {
        g_iData2 = g_iData2 + 1;
    }
    return g_iData2;
    */
// False Sharing
int i;
    for( i = 0 ; i < 0x1FFFFFFF ; i++ )
    {
        g_stData.iData2 = g_stData.iData2 + 1;
    }
    return g_stData.iData2;
}

// 실제 메인 함수
int main(int argc, char* argv[])
{
    HANDLE vhThread[2];
    int i;
    DWORD dwStartTime;
    DWORD dwEndTime;
    DWORD dwTimeSum;
// Processor High Priority로 만든다.
SetPriorityClass( GetCurrentProcess(), HIGH_PRIORITY_CLASS );
    dwTimeSum = 0;
    printf( "Start Processing...\n" );
    for( i = 0 ; i < 20 ; i++ )
    {
        // Thread 생성
        vhThread[0] = CreateThread( NULL, 0, TestThread1, ( LPVOID ) 0, CREATE_SUSPENDED, NULL );
        vhThread[1] = CreateThread( NULL, 0, TestThread2, ( LPVOID ) 0, CREATE_SUSPENDED, NULL );
        // Affinity 설정
        SetThreadAffinityMask( vhThread[ 0 ], 0x1 );
        SetThreadAffinityMask( vhThread[ 1 ], 0x1 );
        // 카운팅 시작
        dwStartTime = GetTickCount();
        ResumeThread( vhThread[ 0 ] );
        ResumeThread( vhThread[ 1 ] );
// Thread 종료
WaitForMultipleObjects( 2, vhThread, TRUE, INFINITE );
        //결과 출력
        dwEndTime = GetTickCount() - dwStartTime;
        printf( "%d Time = %d ms\n", i + 1, dwEndTime );
        dwTimeSum += dwEndTime;
    }
printf( "Average Time = %0.2f\n", dwTimeSum / 20.0 );
return 0;
}

아래는 위의 코드를 이용해서 각 옵션으로 테스트한 결과이다.

Global Variable에 직접 접근
- Affinity 미사용
  - Average Time = 2841.40
  - Average Time = 2842.20
- Affinity 1, 1 사용 - 하나의 Core에서만 동작시킴
  - Average Time = 2653.15
  - Average Time = 2651.55
- Affinity 1, 2 사용 - 각각 Core에 할당해서 동작시킴
  - Average Time = 2842.95
  - Average Time = 2843.75
Cache Line 정렬을 통한 Avoid False Sharing
- Affinity 미사용
  - Average Time = 1514.10
  - Average Time = 1514.80
- Affinity 1, 1 사용 - 하나의 Core에서만 동작시킴
  - Average Time = 3043.75
  - Average Time = 3042.20
- Affinity 1, 2 사용 - 각각 Core에 할당해서 동작시킴
  - Average Time = 1520.30
  - Average Time = 1519.55
Local Variable을 사용한 Hold Approach
- Affinity 미사용
  - Average Time = 1330.50
  - Average Time = 1332.00
- Affinity 1, 1 사용 - 하나의 Core에서만 동작시킴
  - Average Time = 2671.85
  - Average Time = 2672.65
- Affinity 1, 2 사용 - 각각 Core에 할당해서 동작시킴
- - Average Time = 1335.95
  - Average Time = 1335.95

위의 굵은 숫자는 가장 해당 파트에서 가장 빠른 수행 결과를 나타낸 것이다. 결과는 당연히 Local Variable(Hold Approach)을 사용하는 것이 가장 빠르게 나왔다. 첫번째 Global Variable에 직접 접근하는 결과에서는 두 Thread 모두 Core 0에 할당해서 수행한 결과가 제일 빨랐다. 이는 Thread 수행 시에 발생하는 Cache Evit/Load가 상당하기 때문에 발생한 결과인 듯 하다. 다른 테스트의 경우는 하나의 Core에 할당한 결과가 가장 느렸다.

이 테스트에서 눈 여겨볼 것은 Avoid False Sharing 테스트이다. Cache Line 정렬을 사용한 것과 하지 않은 것의 차이가 거의 1.8 배의 속도 차이가 난다. 다시 말하면 Data Structure를 손보는 것 만으로도 MultiCore 환경에서의 Performance를 1.8배 향상 시킬 수 있는 것이다. Performance가 중요시되는 프로그램이라면 Cache Line 정렬은 충분히 고려해 볼만 하다.

4.결론

Processor Affinity는 윈도우즈 환경에서 기대만큼 큰 효과를 발휘하지 못했지만, Cache Blocking과 Hold Aproach 및 Avoid False Sharing 기법은 충분히 효과적인 것으로 나타났다. Processor Affinity가 윈도우즈 환경에서 큰 효과를 발휘하지 못하는 것은 윈도우즈의 Scheduler가 Affinity를 어느정도 보장해주며, Wait Queue에서 대기하는 시간이 Cache Evit & Laod 시간보다 더 길기 때문인 것으로 추측된다.

테스트 결과 Cache Blocking과 Avoid False Sharing은 성능 향상에 충분한 효과가 있는 것으로 나타났다. Cache Blocking과 Avoid Flase Sharing은 Data Structure와 밀접한 관련이 있으며, 이는 Data Structure를 Cache-Friendly 하게 설계하는 것이 Multiple Processor의 성능을 향상시키는 좋은 포인트임을 말해주는 것이다. 따라서 Multiple Processor System에서 Cache-Friendly한 Data Structure를 사용하면 프로그램의 성능을 일정 수준 이상 높일 수 있다.

5.마치면서...

이미 우리는 Multiple Processor의 시대에 살고 있다. 프로그래머에게 또 하나의 장을 열어준 Multiple Processor System, Multiple Processor-Friendly한 Architecture로 프로그램의 Performance를 높이자.

이 글은 스프링노트에서 작성되었습니다.

'OS Kernel > MINT64 OS' 카테고리의 다른 글

VMWare 부팅 후 APIC와 IO APIC의 관계는 ? (0)	2008.07.01
APIC와 I/O APIC... 그 설명의 모호함.. @0@)/~!!! (2)	2008.06.29
Multiple Processor Control... 파면 팔수록 미궁입니다. ㅜ_ㅜ (10)	2008.03.11
드디어 잠자고 있던 다른 하나의 CPU를 동작 시켰습니다!!! (0)	2008.03.09
낮에는 일하랴 밤에는 Multiple Processor 분석하랴... 좀 피곤하군요. ㅜ_ㅜ (0)	2008.03.07

kkamagui의 작업실