고성능 알고리즘 탐구

MSDN 메거진의 추천할 만한 글

----------------------------------------------------------------------------------------------------------------

고성능 알고리즘 탐구

(출처:http://msdn.microsoft.com/ko-kr/magazine/cc850829.aspx)

MSDN Magazine > Home > All Issues > 2008 > October > Windows With C++: 고성능 알고리즘 탐구

Windows With C++

고성능 알고리즘 탐구

Kenny Kerr

동시성 분야에서는 조율, 비동기 동작, 응답성, 그리고 확장성과 같은 문제에 주의가 집중됩니다. 이러한 각 항목은 개발자가 응용 프로그램을 설계할 때 고민하는 높은 수준의 주제입니다. 그러나 개발자는 경험 부족 또는 제대로 된 성능 도구의 부재로 인해 이와 대등하게 중요한 몇 가지 항목은 간과하는 경우가 많습니다. 그중 한 가지가 고성능 알고리즘입니다.

엔터프라이즈 수준에서 개발자는 분산 파일 시스템 및 캐시, 클러스터, 메시지 큐, 데이터베이스와 같은 부분에 대해 고민합니다. 그러나 근본적으로 알고리즘과 데이터 구조가 비효율적이라면 이러한 모든 것들이 무슨 의미가 있을까요?

알고리즘 효율성은 생각만큼 간단한 문제가 아닙니다. 단일 프로세서에서 실행되는 잘 설계된 알고리즘은 다중 프로세서에서 실행되는 비효율적인 구현보다 성능이 뛰어난 경우가 많습니다. 그러나 오늘날 잘 설계된 알고리즘이 되기 위해서는 다중 프로세서를 사용할 때 이에 상응하는 확장성과 효율성도 발휘해야 합니다. 또한 단일 프로세서에 최적화된 알고리즘은 병렬화하기 어려운 반면 효율성이 약간 떨어지는 알고리즘은 다중 프로세서에서 더 나은 성능을 제공하는 경우가 많다는 사실이 문제를 더욱 복잡하게 만듭니다.

예를 들기 위해 이 기사에서는 Visual C++를 사용하여 처음에는 간단해 보일지 몰라도 사실은 그렇지 않은 알고리즘을 개발하는 과정을 살펴보겠습니다. 구현해야 할 대상은 다음과 같습니다.

void MakeGrayscale(BYTE* bitmap,
                   const int width,
                   const int height,
                   const int stride);

bitmap 매개 변수는 픽셀당 32비트로 구성된 이미지를 가리킵니다. 이는 기사의 초점을 강조하기 위한 설정입니다. stride의 절대값은 메모리에 있는 하나의 픽셀 행에서 다음 행까지의 바이트 수를 나타냅니다. 각 행의 끝에는 여백이 존재할 수 있습니다. stride의 부호는 메모리에서 이러한 행이 하향식(양수 stride)인지, 상향식(음수 stride)인지 나타냅니다.

우선 기본적인 부분부터 살펴보겠습니다. 다음 구조를 사용하여 메모리 내의 픽셀을 나타낼 수 있습니다.

typedef unsigned char BYTE; // from windef.h

struct Pixel
{
    BYTE Blue;
    BYTE Green;
    BYTE Red;
    BYTE Alpha;
};

간단히 웹을 검색해 보니 빨간색 30%, 녹색 59%, 파란색 11%를 섞으면 지정된 컬러 픽셀을 위한 적절한 회색조 값을 얻을 수 있다고 합니다. 다음은 하나의 픽셀만 회색조로 변환하기 위한 간단한 함수입니다.

void MakeGrayscale(Pixel& pixel)
{
    const BYTE scale = static_cast<BYTE>(0.30 * pixel.Red +
                                         0.59 * pixel.Green +
                                         0.11 * pixel.Blue);

    pixel.Red = scale;
    pixel.Green = scale;
    pixel.Blue = scale;
}

비트맵 내 특정 픽셀의 바이트 오프셋은 가로 위치와 픽셀 크기의 곱을 계산하고 세로 위치와 stride의 곱을 계산한 다음 이 두 값을 더하면 구할 수 있습니다.

offset = x * sizeof(Pixel) + y * stride

그러면 MakeGrayscale 함수는 어떻게 구현할까요? 충분한 생각 없이 바로 구현한다면 그림 1의 알고리즘과 비슷한 형태가 될 것입니다. 얼핏 보기에는 괜찮은 알고리즘이고, 작은 비트맵을 전달해 봐도 잘 작동하는 것처럼 보입니다. 그러나 큰 비트맵인 경우에는 어떨까요? 예를 들어 20,000픽셀 x 20,000픽셀 크기의 비트맵에서도 문제가 없을까요?

그림 1 비효율적인 단일 스레드 알고리즘

void MakeGrayscale(BYTE* bitmap,
                   const int width,
                   const int height,
                   const int stride)
{
    for (int x = 0; x < width; ++x)
    for (int y = 0; y < height; ++y)
    {
        const int offset = x * sizeof(Pixel) + y * stride;

        Pixel& pixel = *reinterpret_cast<Pixel*>(bitmap + offset);

        MakeGrayscale(pixel);
    }
}

필자는 쿼드 코어 Intel Xeon X3210 프로세서를 탑재한 Dell PowerEdge를 사용합니다. 이 시스템은 2.13GHz의 클록 속도, 1066MHz의 FSB, 8MB의 L2 캐시를 비롯한 다양한 기능을 갖추고 있습니다. 물론 가장 최신의 Intel Xeon 프로세서는 아니지만 그다지 뒤떨어지지도 않습니다. 이 시스템은 64비트 버전의 Windows Server 2008로 구동되며 성능 테스트용으로는 충분합니다.

이러한 강력한 성능을 활용하여 필자는 20,000픽셀 너비에 20,000픽셀 높이의 비트맵에 그림 1의 알고리즘을 실행했습니다. 10회 반복에서 평균 소요 시간은 약 46초였습니다. 물론 이 비트맵은 약 1.5GB로 큰 편이지만 이 정도 크기는 문제가 되지 않아야 정상입니다. 필자의 서버 RAM은 4GB이므로 디스크 페이징이 발생하지 않습니다. 그러나 그림 2에서는 너무나 익숙한 프로세서 사용률 화면을 볼 수 있습니다.

그림 2 비효율적인 단일 스레드 알고리즘의 프로세서 사용률 (더 크게 보려면 이미지를 클릭하십시오.)

이 알고리즘은 열심히 일하지만 컴퓨터 처리 성능의 1/4밖에 사용하지 않습니다. 해결책은 간단합니다. 아니, 간단할까요? 이 문제에 대한 개발자의 가장 일반적인 반응은 더 많은 스레드를 투입하는 것입니다. 이는 합당한 조치입니다. 결국 이 알고리즘은 현재 상태로는 하나의 스레드만 사용하므로 테스트 시스템에 있는 4개의 코어 중 하나만 사용됩니다. 그림 3의 코드는 스레드를 추가합니다.

그림 3 비효율적인 다중 스레드 알고리즘

void MakeGrayscale(BYTE* bitmap,
                   const int width,
                   const int height,
                   const int stride) {
    #pragma omp parallel for
    for (int x = 0; x < width; ++x)
    for (int y = 0; y < height; ++y) {
        const int offset = x * sizeof(Pixel) + y * stride;

        Pixel& pixel = *reinterpret_cast<Pixel*>(bitmap + offset);

        MakeGrayscale(pixel);
    }
}

달라진 점은 OpenMP pragma가 추가되었다는 것뿐입니다. 이제 바깥쪽 for 루프가 여러 스레드로 분배되므로 스레드는 병렬로 실행되면서 각각 비트맵의 다른 부분을 변환할 수 있습니다. OpenMP는 기본적으로 프로세서당 하나의 스레드를 만듭니다. OpenMP 사용에는 너무 신경 쓰지 마십시오. 이는 여러 스레드로 for 루프를 분할하기 위한 극히 간단한 방법으로 사용되었을 뿐입니다. 사용 중인 컴파일러와 런타임에 따라 이 방법 외의 다른 여러 방법으로도 동일한 결과를 얻을 수 있습니다. 그림 4에서 볼 수 있듯이 이 작은 변경이 큰 차이를 만들어 냅니다.

그림 4 비효율적인 다중 스레드 알고리즘의 프로세서 사용률 (더 크게 보려면 이미지를 클릭하십시오.)

성능 개선 리소스

이 기사에서 다룬 주제에 대한 더 자세한 내용은 다음 리소스를 참조하십시오.

그러나 결과는 썩 훌륭하지 않습니다. 단일 스레드 버전이 46초를 소요한 데 비해 다중 스레드 알고리즘은 약 30초를 소요했습니다. 34%의 성능 향상은 300%의 리소스 소모량 증가에 비해 무척 초라해 보입니다. 효율적인 구현은 하나의 스레드로 이 작업을 약 2초에 끝낼 수 있고, 다중 스레드의 도움을 받을 경우 약 0.5초 만에 끝낼 수 있다고 하면 어떤가요? 물론 테스트 시스템은 동일합니다. 30초보다 훨씬 더 빠른 속도입니다.

이 구현은 생각보다 쉽습니다. 알고리즘이 실행되는 실제 하드웨어에 대해, 그리고 메모리에서 데이터가 구조화되는 방법에 대해 조금만 생각하면 됩니다. 개발자는 최종적으로 자신의 코드를 실행하는 하드웨어에 대해 무관심한 경우가 많습니다. 이제 효율적인 알고리즘을 공개한 후 이 알고리즘이 훨씬 더 효율적인 이유에 대해 설명하겠습니다.

그림 5을 살펴보십시오. 뜻밖에도 이 코드에서 달라진 점은 for 루프의 위치밖에 없습니다. 즉, 그림 3의 알고리즘을 변경하여 바깥쪽 루프가 Y 축에 대해 반복되고 안쪽 루프가 X 축에 대해 반복되도록 했습니다. 겉보기에는 시시한 이 변경이 어떻게 30초에서 1초 미만으로 시간을 줄일 수 있을까요? 알고리즘은 하드웨어의 특징뿐만 아니라 알고리즘이 동작하는 대상 데이터의 모양과 지역성에도 크게 영향을 받는다는 사실에 답이 있습니다.

그림 5 효율적인 알고리즘

void MakeGrayscale(BYTE* bitmap,
                   const int width,
                   const int height,
                   const int stride) {
    #pragma omp parallel for
    for (int y = 0; y < height; ++y)
    for (int x = 0; x < width; ++x) {
        const int offset = x * sizeof(Pixel) + y * stride;

        Pixel& pixel = *reinterpret_cast<Pixel*>(bitmap + offset);

        MakeGrayscale(pixel);
    }
}

이를 이해하기 위해서는 알고리즘이 동작하는 대상 데이터 구조를 다시 살펴볼 필요가 있습니다. 비트맵의 메모리 버퍼는 논리적으로 픽셀 행을 포함합니다. 물론 메모리는 테이블 형식이 아니지만 좌표가 지정된 픽셀을 쉽게, 효율적으로 처리할 수 있는 방법이 필요합니다. 행 관점에서 생각하면 이를 개념화하는 데 도움이 됩니다. 특히 인덱싱된 색상표가 있는 비트맵을 사용하는 경우 이러한 행에 각 행의 시작을 올바르게 정렬하는 데 필요한 여백이 포함될 수 있다는 점을 고려하면 이 추상화의 물리적 구현이 드러납니다(그림 6참조).

그림 6 행과 여백(상향) (더 크게 보려면 이미지를 클릭하십시오.)

Y 축의 방향은 음수 stride로 지정된 상향식 레이아웃을 보여 줍니다. 이론적으로 이 방향도 성능에 영향을 줄 수 있지만 정교한 도구 지원 없이는 그 영향을 측정하기는 어렵습니다.

경험에 근거한 동시성 규칙은 서로 멀리 떨어진 메모리는 하나의 프로세서에서 사용하면 안 되고, 서로 인접한 메모리는 여러 프로세서에서 사용하면 안 된다는 것입니다. 즉, 함께 사용되는 데이터는 서로 가깝게 붙여 놓고 각기 따로 사용되는 데이터는 충분히 멀리 떨어뜨려야 합니다. 이렇게 하면 하드웨어 캐시 관리자는 서로 다른 프로세서에서 사용되는 데이터를 경합 없이 캐시할 수 있습니다.

메모리 레이아웃이 성능에 미치는 영향을 평가하려면 메모리는 테이블 형식이 아니라 연속되는 형식이라는 점을 염두에 두어야 합니다. 가상 주소 공간은 평면입니다. 그림 7은 그림 3의 비효율적인 알고리즘을 사용하여 비트맵이 어떻게 분할되는지 보여 줍니다.

그림 7 비효율적인 데이터 분할 (더 크게 보려면 이미지를 클릭하십시오.)

이 알고리즘의 성능이 떨어지는 이유가 이제 명확히 드러납니다. 루프 전달에 의한 종속성은 없지만 하드웨어 캐시 수준에서 거의 필연적으로 경합이 발생하게끔 알고리즘이 병렬화됩니다. 큰 비트맵에서는 경합이 감소될 수 있지만 반복된 캐시 누락은 캐시 관리자가 캐시 라인을 지속적으로 다시 로드하도록 강제하고 이로 인해 성능이 떨어지게 됩니다. 캐시 라인의 데이터를 지속적으로 교체해야 하므로 단일 프로세서에서의 성능도 떨어집니다. 그림 8은 지역성에 문제가 있음을 더 명확히 보여 줍니다. 이 패턴은 비트맵에 있는 행의 수만큼 반복됩니다.

그림 8 비효율적인 데이터 분할(반복) (더 크게 보려면 이미지를 클릭하십시오.)

반면 그림 5의 효율적인 알고리즘은 Y 축을 따라 비트맵을 분할하므로 각 프로세서는 서로 인접해 있으면서 다른 프로세서에 의해 처리되는 픽셀과는 멀리 떨어진 픽셀 스트림을 처리할 수 있고, 따라서 캐시 관리자는 경합 없이 여러 프로세서에 걸쳐 비트맵을 공유할 수 있습니다(그림 9 및 10 참조). 특히 그림 10은 각 프로세스가 하나의 연속되는 메모리 블록만 처리하면 되므로 찾기 및 캐싱 성능이 비약적으로 향상됨을 보여 줍니다.

그림 9 효율적인 데이터 분할 (더 크게 보려면 이미지를 클릭하십시오.)

그림 10 효율적인 데이터 분할(반복되지 않음) (더 크게 보려면 이미지를 클릭하십시오.)

OpenMP에서 기본적으로 사용하는 정적 예약에서는 위에 언급된 0.5초 목표를 달성하기는 어렵습니다. OpenMP는 알고리즘에서 최후의 몇 밀리초까지 짜내는 데 사용할 수 있는 동적 예약 및 유도 예약 기능도 제공합니다. 근본적인 문제는 컴퓨터가 백그라운드에서 자잘한 작업을 수행하는 경우가 있기 때문에 가용한 각 프로세서로 완전히 똑같이 작업을 분할하는 것으로는 최상의 결과를 얻기 어렵다는 점입니다. 이 경우 일부 스레드가 다른 스레드보다 먼저 완료되어 나머지 스레드가 완료될 때까지 유휴 상태로 대기하는 현상이 발생할 수 있습니다.

한편 다른 알고리즘 또는 데이터 구조를 사용하여 속도를 더 높일 수도 있습니다. NUMA(Non-Uniform Memory Access) 시스템의 개별 노드에 있는 실제 메모리에 비트맵 파티션을 로드할 수 있습니다. 비트맵 파티션을 Windows Server HPC(고성능 컴퓨팅) 그리드로 전송할 수도 있습니다. 비효율적인 알고리즘으로는 이 두 가지 방법 모두 불가능합니다. 요점은 데이터 구조와 알고리즘에 대해, 그리고 실행 중인 하드웨어가 어떻게 성능에 영향을 미칠 수 있는지에 대해 조금만 생각하면 코드의 성능을 대폭 개선할 수 있다는 것입니다.

질문이나 의견이 있으시면 mmwincpp@microsoft.com으로 보내시기 바랍니다.

Kenny Kerr는 Windows용 소프트웨어를 전문적으로 개발하는 소프트웨어 개발자로, 프로그래밍과 소프트웨어 설계 분야에서 왕성한 집필 및 교육 활동을 하고 있습니다. 문의 사항이 있으면weblogs.asp.net/kennykerr를 방문하시기 바랍니다.

저작자표시 비영리 변경금지

소지영(몽인)

고성능 알고리즘 탐구

티스토리툴바