L1 캐시 미스 비용은 얼마입니까?

L1 캐시 미스 비용은 얼마입니까?

편집: 참고용으로 (누군가 이 질문을 우연히 발견했을 경우) Igor Ostrovsky는 캐시 누락에 대한 훌륭한 글을 썼습니다.이 문서에서는 몇 가지 다른 문제에 대해 설명하고 예시 번호를 나타냅니다.편집 종료

는 몇 가지 .<long story goes here>성능 차이는 메모리 캐시 누락 때문인지 궁금해요.다음 코드는 이 문제를 나타내며 중요한 타이밍 부분으로 요약합니다.다음 코드에는 랜덤 순서로 메모리를 방문한 후 주소 오름차순으로 메모리를 방문하는 루프가 몇 개 있습니다.

XP 머신(VS2005: cl/O2)과 Linux 박스(gcc – Os)에서 실행했습니다.둘 다 비슷한 시기를 연출했다.이러한 시간은 밀리초 단위입니다.모든 루프가 실행되고 있으며 최적화되어 있지 않다고 생각합니다(그렇지 않으면 "즉시" 실행됩니다).

*** 20000 노드 테스트총 주문일 : 888.822899총 랜덤 시간: 2155.846268

이자자 이이? ??? ???이 차이는 주로 L1 캐시 누락 때문입니까, 아니면 다른 문제 때문입니까?에는 20, 가 , 미스일 약 3.2입니다.20,000^2 " " " " " " " " " " " " " " , " " " " " " " " " " " " " " " " " " " " " " " 3.2 " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " "" " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " "."은 3입니다.GHz kb 32KB 、 L1 、 512KB 、 L2 、엔트리가 20,000(80KB)이면 L2 누락은 그다지 많지 않을 것입니다....(3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss내가 보기엔 높은데.아아 、 내내 、 내내 、 있내있 。VTune BSOD.라이센스 서버(grrr)에 접속할 수 없게 되었습니다.

typedef struct stItem
{
   long     lData;
   //char     acPad[20];
} LIST_NODE;



#if defined( WIN32 )
void StartTimer( LONGLONG *pt1 )
{
   QueryPerformanceCounter( (LARGE_INTEGER*)pt1 );
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2, llFreq;

   QueryPerformanceCounter( (LARGE_INTEGER*)&t2 );
   QueryPerformanceFrequency( (LARGE_INTEGER*)&llFreq );
   *pdMS = ((double)( t2 - t1 ) / (double)llFreq) * 1000.0;
}
#else
// doesn't need 64-bit integer in this case
void StartTimer( LONGLONG *pt1 )
{
   // Just use clock(), this test doesn't need higher resolution
   *pt1 = clock();
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2 = clock();
   *pdMS = (double)( t2 - t1 ) / ( CLOCKS_PER_SEC / 1000 );
}
#endif



long longrand()
{
   #if defined( WIN32 )
   // Stupid cheesy way to make sure it is not just a 16-bit rand value
   return ( rand() << 16 ) | rand();
   #else
   return rand();
   #endif
}

// get random value in the given range
int randint( int m, int n )
{
   int ret = longrand() % ( n - m + 1 );
   return ret + m;
}

// I think I got this out of Programming Pearls (Bentley).
void ShuffleArray
(
   long *plShuffle,  // (O) return array of "randomly" ordered integers
   long lNumItems    // (I) length of array
)
{
   long i;
   long j;
   long t;

   for ( i = 0; i < lNumItems; i++ )
      plShuffle[i] = i;

   for ( i = 0; i < lNumItems; i++ )
      {
      j = randint( i, lNumItems - 1 );

      t = plShuffle[i];
      plShuffle[i] = plShuffle[j];
      plShuffle[j] = t;
      }
}



int main( int argc, char* argv[] )
{
   long          *plDataValues;
   LIST_NODE     *pstNodes;
   long          lNumItems = 20000;
   long          i, j;
   LONGLONG      t1;  // for timing
   double dms;

   if ( argc > 1 && atoi(argv[1]) > 0 )
      lNumItems = atoi( argv[1] );

   printf( "\n\n*** Testing %u nodes\n", lNumItems );

   srand( (unsigned int)time( 0 ));

   // allocate the nodes as one single chunk of memory
   pstNodes = (LIST_NODE*)malloc( lNumItems * sizeof( LIST_NODE ));
   assert( pstNodes != NULL );

   // Create an array that gives the access order for the nodes
   plDataValues = (long*)malloc( lNumItems * sizeof( long ));
   assert( plDataValues != NULL );

   // Access the data in order
   for ( i = 0; i < lNumItems; i++ )
      plDataValues[i] = i;

   StartTimer( &t1 );

   // Loop through and access the memory a bunch of times
   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Ordered Time: %f\n", dms );

   // now access the array positions in a "random" order
   ShuffleArray( plDataValues, lNumItems );

   StartTimer( &t1 );

   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Random Time: %f\n", dms );

}

여기에서는 초콜릿 칩 쿠키를 굽는 것과 유사하게 캐시 누락의 상대적인 비용에 대한 통찰력을 제공하려는 시도가 있습니다.

손은 등록부입니다.초콜릿 칩을 반죽에 떨어뜨리는데 1초가 걸린다.

주방 카운터는 L1 캐시로 레지스터보다 12배 느립니다.카운터로 가서 호두 봉지를 집어들고 손에 비우는 데 12 x 1 = 12초 걸립니다.

냉장고는 L1보다 4배 느린 L2 캐시입니다.냉장고까지 걸어가서 열고, 어젯밤 먹다 남은 음식을 치우고, 계란 한 상자를 꺼내서, 상자를 열고, 3개의 달걀을 카운터에 놓고, 상자를 다시 냉장고에 넣는데 4 x 12 = 48초가 걸린다.

찬장은 L2보다 3배 느린 L3 캐시입니다.3 x 48 = 2분 24초 만에 찬장까지 세 걸음 가서 몸을 굽히고 문을 열고 베이킹 서플라이 깡통을 찾아 헤매고 찬장에서 꺼내어 열고 베이킹 파우더를 찾아 카운터에 올려 바닥에 흘린 쓰레기를 치운다.

메인 기억은요? 저기가 구멍가게야, L3보다 5배 느린 곳이야.지갑을 찾고, 신발과 재킷을 입고, 거리를 질주하고, 우유 1리터를 집어들고, 집으로 달려가고, 신발과 재킷을 벗고, 부엌으로 돌아가는 데 5 x 2:24 = 12분이 소요됩니다.

이러한 모든 액세스는 항상 복잡하지만(O(1)), 이러한 접근 간의 차이는 성능에 큰 영향을 미칠 수 있습니다.단순히 빅오(big-o)의 복잡성을 위해 최적화하는 것은 반죽 1에 초콜릿 칩을 한 번에 추가할지 10개씩 추가할지를 결정하는 것과 같습니다만, 식료품 리스트에 올리는 것을 잊는 것과 같습니다.

이 이야기의 교훈: 가능한 한 CPU가 식료품을 찾는 일이 거의 없도록 메모리 액세스를 구성합니다.

CPU Cache Flushing Error 블로그 투고에서 얻은 수치입니다.이는 2012년판 인텔 프로세서의 경우 다음과 같습니다.

• 액세스 등록 = 사이클당 4개의 명령
• L1 레이텐시 = 3 사이클(12 x 레지스터
• L2 레이텐시 = 12 사이클(4 x L1, 48 x 레지스터)
• L3 레이텐시 = 38 사이클(3 x L2, 12 x L1, 144 x 레지스터)
• 3GHz CPU의 DRAM 레이텐시 = 65 ns = 195 사이클 (5 x L3, 15 x L2, 60 x L1, 720 x 레지스터)

이 토픽에 대해서는, 「프로세서 캐시 효과의 갤러리」를 참조해 주세요.

이 숫자들이 타당한지에 대해서는 답변할 수 없지만(캐시 지연 시간은 잘 모르지만 10사이클까지의 L1 캐시의 누락은 정확합니다), 두 테스트 간의 캐시 성능 차이를 실제로 확인할 수 있는 툴로서 Cachegrind를 제공할 수 있습니다.

Cachegrind는 Valgrind 툴(항상 사랑스러운 memcheck를 지원하는 프레임워크)로 캐시 및 분기 히트/오류를 프로파일링합니다.프로그램에서 실제로 캐시 적중/실패 수를 파악할 수 있습니다.

L1 캐시 미스에 대한 3.2ns는 전적으로 타당합니다.비교를 위해 특정 최신 멀티코어 PowerPC CPU에서 L1의 오차는 약 40사이클입니다.일부 코어는 L2 캐시와의 거리에 따라 다르지만 다른 코어에 비해 약간 길어집니다(실제로).L2 미스는 최소 600 사이클입니다.

캐시가 퍼포먼스의 전부입니다.CPU는 메모리보다 훨씬 고속이기 때문에 코어가 아닌 메모리 버스에 최적화할 수 있습니다.

L1 캐시 누락이 주된 원인인 것 같습니다.

L1 캐시 미스 10 사이클은 합리적으로 들립니다(아마도 약간 낮은 편일 것입니다).

RAM의 판독치는 사이클의 100초 또는 1000초(지금 당장 계산을 시도하기에는 너무 피곤함)가 될 수 있으므로 여전히 큰 이점이 있습니다.

캐시그린드를 사용할 계획이라면 캐시 적중/불량 시뮬레이터일 뿐입니다.항상 정확한 것은 아닙니다.예를 들어, 어떤 메모리 위치에 액세스 했을 경우(예를 들어 루프에서 1000회 0x1234), 캐시그린드는 다음과 같은 캐시 미스(첫 번째 액세스)가 1개밖에 없었다는 것을 항상 나타냅니다.

루프에 clflush 0x1234를 입력합니다.

x86에서는 1000개의 캐시 누락이 모두 발생합니다.

3.4의 경우 몇 가지 수치라발리스 에베레스트에서 GHz P4:

• L1 dcache는 8K(캐시라인 64바이트)입니다.
• L2는 512K
• L1 가져오기 지연 시간은 2 사이클입니다.
• L2 가져오기 레이텐시는 20 사이클의 약 2배입니다.

자세한 사항은 이쪽:http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt

(지연에 대해서는 페이지 하단을 참조해 주세요)

더 많은 테스트를 거치지 않고는 확실하게 말하기 어렵지만, 제 경험상 이러한 차이는 CPU L1 및/또는 L2 캐시에 기인합니다.특히 랜덤 액세스 시나리오에서는 더욱 그렇습니다.각 액세스가 마지막 액세스로부터 최소 어느 정도의 거리를 유지하도록 하면 상황을 더욱 악화시킬 수 있습니다.

가장 쉬운 방법은 타깃 CPU의 스케일링된 사진을 찍어 코어와 레벨 1 캐시 사이의 거리를 물리적으로 측정하는 것입니다.그 거리에 구리 단위로 전자가 초당 이동할 수 있는 거리를 곱합니다.그런 다음 동시에 몇 개의 클럭 사이클을 가질 수 있는지 계산해 보십시오.이는 L1 캐시 누락으로 낭비되는 최소 CPU 사이클 수입니다.

또한 RAM에서 데이터를 가져오는 데 드는 최소 비용도 동일한 방법으로 낭비되는 CPU 사이클 수로 계산할 수 있습니다.놀라실 수도 있어요.

여기에 표시되는 것은 캐시 미스(L1 또는 L1과 L2)와 분명히 관련이 있습니다.일반적으로 캐시는 같은 캐시 라인상의 데이터에 액세스 하면 RAM으로의 트립이 적어지기 때문입니다.

다만, RAM(랜덤 액세스 메모리라고 불리고 있습니다만)은 여전히 리니어 메모리 액세스를 선호하고 있습니다.

언급URL : https://stackoverflow.com/questions/1126529/what-is-the-cost-of-an-l1-cache-miss