2D 배열의 관련 연산 최적화

CPU 캐시라인 

 

논문 제목 : OpenMP 병렬 프로그래밍과 Cache 친화적 프로그래밍을 통한 초분광 영상처리 최적화

 

 

2. Cache 친화적 프로그래밍

Modern Hardware Architecture

Modern comupter들은 아래 그림과 같은 구성을 가지고 있는데, CPU와 가까울 수록 Access time이 줄어든다. 특히 L1 Cache에 접근하기 위해서는 1 Clock만이 소요된다. 따라서 최대의 성능을 C++ application에서 얻기 위해서는 Cache과 친화적인 프로그래밍을 하는 것이 중요하다. 

 

그림 Modern Hardware Architecture

초분광 영상의 복사보정 처리를 하기 위해서는 여느 영상과 같이 C++ 2 차원 배열을 통해 영상을 처리한다. 본 연구에서는 열 단위가 아닌 행 단위로 접근하여 영상처리하는 Cache friendly한 코드로 성능을 극대화했다. 행에 인접한 요소는 같은 캐시라인에 영상 메모리가 있을 수 있기 때문에 성능이 좋다. 같은 캐시라인에 메모리가 있다면 위 그림 처럼 데이터 Access time이 매우 작아지기 때문이다.

대신 같은 열에있는 요소가 서로 메모리에서 멀리 떨어져 있기 때문에 이러한 요소에 열 방식으로 액세스하는 것은 같은 캐시라인에 pre-patch 되어있을 수 없고 이는 데이터 접근 시 여러번의 CPU와 먼 메모리로 접근하며 잠재적으로 메모리 근처의 요소를 검색하는 캐시의 노력을 낭비한다. 다음은 2차원 배열의 캐시 친화적 / 비친화적 코드의 예이다.

 

// Cache friendly programming

for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

// Cache-unfriendly programming 

 

 

for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

 

이 효과는 큰 배열로 작업하는 시스템에서 상당히 크게 나타난다. 이러한 이유로 수직 스캔을 많이해야하는 경우 이미지를 먼저 90도 회전하고, 나중에 다양한 분석을 수행하여 캐시 친화적이지 않은 코드를 회전으로 제한하는 것이 좋습니다.

 

그림 : tutorials.jenkov.com/java-performance/modern-hardware.html