예비

최신 컴퓨터에서는 가장 낮은 수준의 메모리 구조 ( 레지스터 ) 만 단일 클록 주기로 데이터를 이동할 수 있습니다. 그러나 레지스터는 매우 비싸고 대부분의 컴퓨터 코어에는 수십 개 미만의 레지스터가 있습니다 ( 총 수백에서 수천 바이트 ). 메모리 스펙트럼 ( DRAM ) 의 다른 쪽 끝 에서, 메모리는 매우 저렴하지만 (즉, 문자 그대로 수백만 배 저렴 ) 데이터 수신 요청 후 수백 사이클이 걸린다. 캐시 메모리 는 초고가와 초고가 사이의 간격을 메우기 위해 사용 됩니다속도와 비용이 감소하면서 L1, L2, L3으로 명명되었습니다. 아이디어는 대부분의 실행 코드가 종종 작은 변수 세트에 충돌하고 나머지는 훨씬 더 큰 변수 세트에 자주 충돌한다는 것입니다. 프로세서가 L1 캐시에서 데이터를 찾을 수 없으면 L2 캐시를 찾습니다. 없는 경우 L3 캐시 및없는 경우 주 메모리. 이러한 각각의 “누락”은 시간이 많이 걸립니다.

(시스템 메모리가 너무 하드 디스크 스토리지이므로 캐시 메모리는 시스템 메모리와 유사합니다. 하드 디스크 스토리지는 매우 저렴하지만 매우 느립니다).

캐싱은 대기 시간 의 영향을 줄이는 주요 방법 중 하나입니다 . Herb Sutter의 말을 인용하려면 (아래 링크 참조) : 대역폭을 늘리는 것은 쉽지만 대기 시간을 벗어나는 길을 살 수는 없습니다 .

데이터는 항상 메모리 계층 구조를 통해 검색됩니다 (가장 작은 == 가장 빠름에서 가장 느림). 캐시 적중 / 미스는 일반적으로 CPU의 캐시의 최고 수준의 히트 / 미스를 말한다 – 최고 수준으로 내가 가장 큰 == 느린 것을 의미한다. 캐시 적중률은 모든 캐시 누락으로 인해 많은 시간 (RAM의 경우 수백 사이클, HDD의 경우 수천만 사이클 )이 걸리는 RAM에서 데이터를 가져 오거나 (또는 ​​더 나쁘게) 성능에 중요합니다 . 이에 비해 (가장 높은 수준의) 캐시에서 데이터를 읽는 것은 일반적으로 몇 번의 주기만 걸립니다.

최신 컴퓨터 아키텍처에서 성능 병목 현상은 CPU 다이를 떠나고 있습니다 (예 : RAM에 액세스). 시간이지나면서 악화 될뿐입니다. 프로세서 주파수의 증가는 현재 더 이상 성능 향상과 관련이 없습니다. 문제는 메모리 액세스입니다. 따라서 CPU의 하드웨어 설계 노력은 현재 캐시 최적화, 프리 페치, 파이프 라인 및 동시성에 중점을두고 있습니다. 예를 들어, 최신 CPU는 캐시에 약 85 %의 다이를 사용하고 데이터를 저장 / 이동하는 데 최대 99 %를 소비합니다!

이 주제에 대해 언급해야 할 것이 많이 있습니다. 다음은 캐시, 메모리 계층 및 적절한 프로그래밍에 대한 훌륭한 참고 자료입니다.

• 아그 너 안개의 페이지 . 그의 훌륭한 문서에서 어셈블리에서 C ++에 이르는 언어를 다루는 자세한 예제를 찾을 수 있습니다.
• 비디오에 관심이 있다면 머신 아키텍처 (YouTube)에 대한 Herb Sutter의 대화를 살펴 보는 것이 좋습니다 (특히 12:00 이상 확인).
• Christer Ericson (Sony @ 기술 책임자)의 메모리 최적화에 관한 슬라이드
• LWN.net의 기사 ” 모든 프로그래머가 메모리에 대해 알아야 할 사항 “

캐시 친화적 인 코드의 주요 개념

캐시 친화적 인 코드의 매우 중요한 측면은 로컬 성의 원칙에 관한 것이며 , 효율적인 캐싱을 위해 관련 데이터를 메모리에 가까이 배치하는 것이 목표입니다. CPU 캐시와 관련하여 캐시 라인을 알고 있어야 작동 방식을 이해할 수 있습니다. 캐시 라인은 어떻게 작동합니까?

캐싱을 최적화하려면 다음과 같은 특정 측면이 매우 중요합니다.

1. 시간적 지역성 : 주어진 메모리 위치에 액세스했을 때 가까운 시일 내에 같은 위치에 다시 액세스 할 가능성이 있습니다. 이상적으로이 정보는 여전히 그 시점에 캐시됩니다.
2. 공간적 위치 : 관련 데이터를 서로 가깝게 배치하는 것을 말합니다. 캐싱은 CPU뿐만 아니라 여러 수준에서 발생합니다. 예를 들어, RAM에서 읽을 때 일반적으로 프로그램이 해당 데이터를 곧 요구하기 때문에 특별히 요청한 것보다 더 큰 메모리 청크를 가져옵니다. HDD 캐시는 동일한 사고 방식을 따릅니다. 특히 CPU 캐시의 경우 캐시 라인 의 개념 이 중요합니다.

적절한 사용 C ++ 컨테이너

캐시 친화적이고 캐시 비 친화적 인 간단한 예는 다음과 같습니다. C ++의 std::vector대 std::list. 의 요소는 std::vector연속 메모리에 저장되며, 액세스하는 방식은의 요소를 액세스하는 것 보다 캐시에 훨씬 친숙 std::list합니다. 이것은 공간적 지역성 때문입니다.

이 유튜브 클립 에서 Bjarne Stroustrup이 매우 멋진 그림을 제공 합니다 (링크에 @Mohammad Ali Baydoun에게 감사드립니다!).

데이터 구조 및 알고리즘 설계에서 캐시를 무시하지 마십시오

가능하면 캐시를 최대한 활용할 수있는 방식으로 데이터 구조와 계산 순서를 조정하십시오. 이와 관련하여 일반적인 기술은 캐시 차단 (Archive.org 버전) 인데, 이는 고성능 컴퓨팅 (예 : ATLAS 참조 ) 에서 매우 중요 합니다.

암시적인 데이터 구조 이해 및 활용

현장의 많은 사람들이 때때로 잊어 버린 또 다른 간단한 예는 열 주요입니다 (예 : 포트란,MATLAB) 대 행 순서 순서 (예 : 씨,C ++2 차원 배열을 저장합니다. 예를 들어 다음 매트릭스를 고려하십시오.

1 2
3 4

행 메이저 순서에서 이것은 메모리에 1 2 3 4; 열 주요 순서에서 이것은로 저장됩니다 1 3 2 4. 이 순서를 악용하지 않는 구현은 캐시 문제에 빠르게 발생한다는 것을 쉽게 알 수 있습니다. 불행히도, 나는 내 도메인 (기계 학습)에서 이와 같은 것들을 매우 자주 본다 . @MatteoItalia는이 예제를 그의 답변에서 더 자세히 보여주었습니다.

메모리에서 행렬의 특정 요소를 가져올 때 그 근처의 요소도 가져 와서 캐시 라인에 저장됩니다. 순서가 악용되면 메모리 액세스 횟수가 줄어 듭니다 (다음 계산에 필요한 다음 몇 개의 값이 이미 캐시 라인에 있기 때문에).

간단히하기 위해, 캐시는 2 개의 매트릭스 요소를 포함 할 수있는 단일 캐시 라인을 포함하고 주어진 요소가 메모리에서 페치 될 때 다음 요소도 있다고 가정합니다. 위의 예제 2×2 행렬의 모든 요소에 대해 합계를 가져오고 싶다고 가정 해 봅시다 M.

순서 활용 (예 : 열 색인을 먼저 변경) C ++) :

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

순서를 악용하지 않음 (예 : 행 색인을 먼저 변경) C ++) :

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

이 간단한 예에서, 순서를 이용하면 실행 속도가 약 두 배가됩니다 (메모리 액세스는 합계 계산보다 훨씬 많은주기를 필요로하기 때문에). 실제로 성능 차이는 훨씬 클 수 있습니다 .

예측할 수없는 가지를 피하십시오

최신 아키텍처는 파이프 라인을 특징으로하며 컴파일러는 메모리 액세스로 인한 지연을 최소화하기 위해 코드를 재정렬하는 데 매우 능숙 해지고 있습니다. 중요 코드에 예측할 수없는 분기가 포함 된 경우 데이터를 프리 페치하기가 어렵거나 불가능합니다. 이것은 간접적으로 더 많은 캐시 누락을 초래할 것입니다.

이 설명 아주 잘 여기 (링크에 대한 @ 0x90 덕분에) : 왜 빠른 정렬되지 않은 배열을 처리하는 것보다 정렬 된 배열을 처리?

가상 기능을 피하십시오

문맥 상에 C ++, virtual방법은 캐시 미스와 관련하여 논란의 여지가있는 문제를 나타냅니다 (성능 측면에서 가능한 경우 피해야한다는 일반적인 합의가 존재합니다). 가상 함수는 룩업 동안 캐시 미스를 유도 할 수 있지만,이 경우에만 발생하는 경우 이 일부에 의해 비 문제로 간주하므로, 특정 기능이 자주 호출되지 않습니다 (그렇지 않으면 가능성이 캐시 될 것이다). 이 문제에 대한 참조 는 C ++ 클래스에서 가상 메소드를 사용하는 데 드는 성능 비용은 얼마입니까?를 확인하십시오.

일반적인 문제

다중 프로세서 캐시를 사용하는 최신 아키텍처에서 흔히 발생하는 문제를 허위 공유 라고 합니다 . 이것은 각각의 개별 프로세서가 다른 메모리 영역에서 데이터를 사용하려고 시도하고 동일한 캐시 라인에 데이터를 저장하려고 할 때 발생합니다 . 이로 인해 다른 프로세서가 사용할 수있는 데이터가 들어있는 캐시 라인이 반복해서 덮어 쓰기됩니다. 효과적으로 다른 스레드는이 상황에서 캐시 누락을 유도하여 서로를 대기시킵니다. (링크에 @Matt 덕분에) : 캐시 라인 크기에 맞추는 방법과시기?

RAM 메모리에서 캐싱이 제대로 이루어지지 않는 경우 (이 문맥에서는 의미가 없을 수도 있음)를 스 래싱 이라고 합니다. 프로세스가 디스크 액세스가 필요한 페이지 폴트 (예 : 현재 페이지에없는 메모리에 액세스)를 지속적으로 생성 할 때 발생합니다.

답변

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k==;k<N;i++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k=0;k<N;k++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}