[caching] CPU 캐시를 가장 잘 활용하여 성능을 향상시키는 코드는 어떻게 작성합니까?

캐시는 CPU가 메모리 요청이 이행 될 때까지 대기하는 횟수를 줄이고 (메모리 대기 시간을 피함 ) 두 번째 효과로, 전송해야하는 전체 데이터 양을 줄일 수 있습니다 (보존 메모리 대역폭 ).

메모리 페치 대기 시간으로 인한 고통을 피하는 기술은 일반적으로 가장 먼저 고려해야 할 사항이며 때로는 먼 길을 돕습니다. 제한된 메모리 대역폭은 특히 많은 스레드가 메모리 버스를 사용하려는 다중 코어 및 다중 스레드 응용 프로그램의 경우 제한 요소입니다. 후자의 문제를 해결하는 데 도움이되는 다양한 기술이 있습니다.

공간적 지역성을 개선 한다는 것은 각 캐시 라인이 캐시에 매핑 된 후에 전체적으로 사용되도록 보장한다는 것을 의미합니다. 다양한 표준 벤치 마크를 살펴보면, 캐시 라인이 제거되기 전에 놀랍도록 많은 부분이 페치 된 캐시 라인을 100 % 사용하지 못한다는 것을 알았습니다.

캐시 라인 활용도를 높이면 세 가지 측면에서 도움이됩니다.

• 캐시에 더 유용한 데이터를 넣는 경향이있어 유효 캐시 크기가 증가합니다.
• 동일한 캐시 라인에 더 유용한 데이터를 맞추는 경향이있어 요청 된 데이터가 캐시에서 발견 될 가능성이 높아집니다.
• 페치가 적으므로 메모리 대역폭 요구 사항이 줄어 듭니다.

일반적인 기술은 다음과 같습니다.

• 더 작은 데이터 유형 사용
• 정렬 구멍을 피하기 위해 데이터를 구성하십시오 (크기를 줄임으로써 구조체 멤버를 정렬하는 것이 한 가지 방법입니다)
• 표준 동적 메모리 할당자를 조심하십시오. 예열되면 구멍이 생겨 데이터가 메모리에 퍼질 수 있습니다.
• 모든 인접 데이터가 실제로 핫 루프에서 사용되는지 확인하십시오. 그렇지 않으면, 핫 루프가 핫 데이터를 사용하도록 데이터 구조를 핫 및 콜드 구성 요소로 분리하는 것을 고려하십시오.
• 불규칙한 액세스 패턴을 나타내는 알고리즘 및 데이터 구조를 피하고 선형 데이터 구조를 선호하십시오.

또한 캐시를 사용하는 것보다 메모리 대기 시간을 숨길 수있는 다른 방법이 있습니다.

최신 CPU : 종종 하나 이상의 하드웨어 프리 페 처가 있습니다. 그들은 캐시에서 미스를 훈련시키고 규칙 성을 발견하려고 노력합니다. 예를 들어, 후속 캐시 라인을 몇 번 놓친 후 hw 프리 페처는 애플리케이션의 요구를 예상하여 캐시 라인을 캐시로 가져 오기 시작합니다. 정기적 인 액세스 패턴이있는 경우 하드웨어 프리 페처는 일반적으로 매우 잘 수행됩니다. 또한 프로그램에 정기적 인 액세스 패턴이 표시되지 않으면 프리 페치 명령어를 직접 추가하여 상황을 개선 할 수 있습니다 .

캐시에서 항상 그리워하는 명령이 서로 가깝게 발생하도록 명령어를 다시 그룹화하면 CPU가 때때로 이러한 페치와 겹치므로 애플리케이션이 하나의 대기 시간 히트 ( 메모리 레벨 병렬 처리 ) 만 유지할 수 있습니다.

전체 메모리 버스 압력을 줄이려면 temporal locality 라는 문제를 해결해야 합니다. 이는 데이터가 여전히 캐시에서 제거되지 않은 동안 데이터를 재사용해야 함을 의미합니다.

동일한 데이터에 닿는 루프를 병합 ( 루프 융합 )하고 모든 타일링 또는 블로킹 이라는 재 작성 기술을 사용 하면 이러한 추가 메모리 페치를 피하기 위해 노력합니다.

이 재 작성 연습에는 몇 가지 규칙이 있지만 일반적으로 프로그램의 의미에 영향을 미치지 않도록 루프 전달 데이터 종속성을 신중하게 고려해야합니다.

이러한 것들이 멀티 코어 세계에서 실제로 지불하는 것인데, 일반적으로 두 번째 스레드를 추가 한 후에는 처리량이 크게 향상되지 않습니다.

답변

pseudocode
for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[j][i]

for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[i][j]