캐시 메모리 작동 방식

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가 두 배로 분리되어 있기 때문에). 캐시는 참조 할 때마다 메모리 페이지를 계속 가져 와서 버려야 할 수도 있습니다 자료. 이것은 스 래싱 (thrashing)이라고하며 성능에 좋지 않습니다.

실제로 더 크고 현대적인 캐시의 경우 행/열의 크기가 적당히 커야 만 정상적으로 작동하지만 여전히 좋은 습관입니다.

[편집] 위의 답변은 C에만 해당되며 다른 언어와 다를 수 있습니다. 내가 아는 유일한 사람은 FORTRAN입니다. FORTRAN은 항목을 주요한 순서대로 저장하고 (위의 행은 중요 함) FORTRAN에서 명령문의 순서를 변경하는 것이 옳습니다. 효율성을 원한다면 언어가 데이터 저장을 구현하는 방법을 알아야합니다.

Answer 2

캐시는 지역성과 비슷하기 때문에 그렇습니다. 액세스되는 메모리의 수는 같지만 더 멀리 떨어져 있으면 캐시의 다른 "라인"에 충돌하거나 캐시를 놓칠 수도 있습니다. 따라서 선택이있을 때마다 데이터를 구성하여 시간에 따라 서로 가까이에서 발생하는 가능성이있는 액세스를 공간에서 수행 할 수 있습니다. 이렇게하면 캐시 적중 가능성이 높아져 성능이 향상됩니다.

이 주제에 대한 풍부한 정보가 있습니다 (예 : this wikipedia entry on locality of reference 참조). 아니면 내 자신의 코스 교과서 같아. :)

Answer 3

C에서 n 차원 행렬은 행 길이가 있습니다. 행렬의 마지막 인덱스는 메모리의 인접한 공백을 나타냅니다. 이것은 다른 언어 인 FORTRAN (예 : 컬럼 주요)과 다릅니다. FORTRAN에서는이 같은 2 차원 매트릭스를 통해 반복하는 것이 더 효율적입니다 :

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

Answer 4

캐시 메모리는 CPU에 가까운 앉아 메모리 매우 빠르고 매우 비싸다. 매번 RAM에서 하나의 작은 데이터를 가져 오는 대신 CPU는 데이터 청크를 가져 와서 캐시에 저장합니다. 하나의 바이트 만 읽으면 다음에 읽는 바이트가 바로 뒤에 올 것입니다. 이 경우 캐시에서 가져올 수 있습니다.

루프를 배치 한대로 메모리에 저장된 순서대로 바이트를 읽습니다. 이는 캐시에 있음을 의미하며 CPU가 매우 빠르게 읽을 수 있습니다. 1 번과 2 번 라인을 바꾼다면 매번 "N"바이트마다 루프를 읽게 될 것입니다. 읽는 바이트는 메모리에서 더 이상 연속하지 않으므로 캐시에 없을 수 있습니다. CPU가 (느린) RAM에서 가져와야하므로 성능이 저하됩니다.

Answer 5

레드햇의 울리히 드레퍼 (Ulrich Drepper)와 glibc 명성 (What Every Programmer Should Know About Memory)으로 아주 좋은 논문이 있습니다. 한 섹션에서 캐시에 대해 자세히 설명했습니다. 예를 들어, CPU가 수정 된 캐시 라인의 소유권을 앞뒤로 뒤지고 앞뒤로 움직여 성능을 크게 저하시키는 SMP 시스템의 캐시 효과가 있습니다.