캐시 메모리는 어떻게 작동합니까?

Question

오늘 제가 컴퓨터 조직 수업에 있었을 때 교사는 나에게 흥미로운 것에 대해 이야기했습니다. 캐시 메모리가 작동하는 이유에 대해 이야기 할 때 그는 다음과 같이 말했습니다.

for (i=0; i<M; i++)
   for(j=0; j<N; j++)
      X[i][j] = X[i][j] + K; //X is double(8 bytes)

첫 번째 줄을 두 번째 줄로 바꾸는 것은 좋지 않습니다. 이것에 대한 당신의 의견은 무엇입니까? 그리고 왜 그런가요?

Answer 1

참조의 위치. 데이터는 행에 의해 저장되므로 각 행에 대해 J 열은 인접한 메모리 주소에 있습니다. OS는 일반적으로 메모리에서 캐시에 전체 페이지를로드하고 인접한 주소 참조는 동일한 페이지를 참조 할 수 있습니다. 내부 루프에서 행 색상으로 증가하면 이러한 행은 다른 페이지에있을 수 있으며 (각각 J 복용으로 분리되어 있기 때문에) 캐시는 참조대로 메모리 페이지를 지속적으로 가져 와서 버려야 할 수 있습니다. 자료. 이것을 스 래싱이라고하며 성능에 좋지 않습니다.

실제로 그리고 더 크고 현대적인 캐시를 사용하면 행/열의 크기가 작용하기 전에 합리적으로 커야하지만 여전히 좋은 연습입니다.

편집] 위의 답은 C에만 해당되며 다른 언어에 대해 다를 수 있습니다. 내가 아는 유일한 것은 Fortran입니다. FORTRAN은 열 순서에서 물건을 저장하고 (위의 것은 줄거리입니다) Fortran의 진술 순서를 변경하는 것이 맞습니다. 효율성을 원하거나 필요로하는 경우 언어가 데이터 저장소를 구현하는 방법을 아는 것이 중요합니다.

Answer 2

Red Hat과 Glibc 명성의 Ulrich Drepper의 아주 좋은 종이가 있습니다. 모든 프로그래머가 기억에 대해 알아야 할 것. 한 섹션에서는 캐시를 자세히 설명했습니다. 예를 들어, CPU가 수정 된 캐시 라인의 소유권을 앞뒤로 스 래시로 만들 수있는 SMP 시스템에는 캐시 효과가 있습니다.

Answer 3

그것은 지역과 같은 캐시를 발견하기 때문에 그런 것과 같습니다. 동일한 수의 메모리가 액세스되었지만 더 간격으로 간격을두면 캐시의 다른 "선"을 누르거나 캐시를 완전히 놓칠 수도 있습니다. 그러므로 선택이있을 때마다 데이터를 구성하여 시간에 서로 가까이있을 가능성이있는 액세스가 공간에서도 그렇게 할 수 있도록하는 것이 좋습니다. 이로 인해 캐시에 맞을 가능성이 높아지고 더 많은 성능을 제공합니다.

물론이 주제에 대한 풍부한 정보가 있습니다. 예를 들어 참조하십시오.참조 지역에 대한이 위키 백과 항목. 아니면, 당신의 코스 교과서라고 생각합니다. :)

Answer 4

C에서, N 차원 행렬은 행 메이저인데, 이는 매트릭스로의 마지막 인덱스가 메모리의 인접한 공간을 나타냅니다. 이것은 예를 들어 열 메이저 인 다른 언어 (예를 들어 포트란)와 다릅니다. Fortran에서는 다음과 같은 2D 행렬을 통해 반복하는 것이 더 효율적입니다.

do jj = 1,N
  do ii = 1,M
    x(ii,jj) = x(ii,jj) + K;
  enddo
enddo

Answer 5

캐시 메모리는 CPU에 가까운 매우 빠르고 매우 비싼 메모리입니다. CPU는 매번 RAM의 작은 데이터를 RAM에서 가져 오지 않고 많은 데이터를 가져와 캐시에 저장합니다. 베팅은 하나의 바이트를 읽는다면 다음 바이트가 읽을 수 있다는 것입니다. 이 경우 캐시에서 나올 수 있습니다.

당신이 가지고있는대로 루프를 배치함으로써, 당신은 그들이 메모리에 저장된 순서대로 바이트를 읽습니다. 이것은 그들이 캐시에 있고 CPU에 의해 매우 빨리 읽을 수 있음을 의미합니다. 1 행과 2 행 주위를 바꾸면 루프 주변에서 매번 모든 "n"바이트를 읽습니다. 당신이 읽고있는 바이트는 더 이상 메모리에 연속되지 않으므로 캐시에 있지 않을 수 있습니다. CPU는 (느린) RAM에서 가져와야하므로 성능이 줄어 듭니다.