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

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

---

편집 : 참고 목적으로 (누군가이 질문을 우연히 발견하면) Igor Ostrovsky는 캐시 미스에 대한 훌륭한 게시물을 작성했습니다 . 여러 가지 문제를 논의하고 예제 번호를 보여줍니다. 편집 종료

몇 가지 테스트를 수행 <long story goes here>하고 성능 차이가 메모리 캐시 누락으로 인한 궁금합니다. 다음 코드는 문제를 보여주고 중요한 타이밍 부분으로 요약합니다. 다음 코드에는 임의의 순서로 메모리를 방문한 다음 오름차순 주소 순서로 방문하는 두 개의 루프가 있습니다.

XP 시스템 (VS2005로 실행했습니다 : cl / O2)과 Linux 박스 (gcc –Os)에서 실행했습니다. 둘 다 성적 시간을 생산했습니다. 이 시간은 밀리 초 단위입니다. 모든 루프가 실행 중이고 최적화되지 않았다고 생각합니다 (그렇지 "즉시"실행됩니다).

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

이 숫자가 의미가 있습니까? 차이점은 주로 L1 캐시 미스 때문입니까 아니면 다른 작업도 진행되고 있습니까? 20,000 ^ 2 개의 개의 메모리 액세스가 모든 액세스가 캐시 미스 인 경우 미스 당 약 3.2 나노초입니다. 내가 테스트 한 XP (P4) 컴퓨터는 3.2GHz이고 나는 의심하지만 (모르는) 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를 평가했습니다. 이제는 고도의 서버에 없습니다.

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 );

}

---

숫자가 의미가 있는지 여부에 대한 답변을 제공 할 수는 없지만 (캐시 지연 시간에 대해서는 잘 모르지만 기록을 위해 ~ 10주기 L1 캐시가 소리를 제대로 놓치지 못함) Cachegrind 를 제공 할 수 있습니다 . 두 테스트 간의 캐시 성능 차이를 실제로 확인하는 데 도움이되는 도구입니다.

Cachegrind는 캐시 및 분기 적중 / 실패를 프로파일 링하는 Valgrind 도구 (항상 사랑스러운 memcheck를 지원하는 프레임 워크)입니다. 프로그램에서 실제로 얼마나 많은 캐시 적중 / 실패가 발생하는지 알 수 있습니다.

---

다음은 초콜릿 칩 쿠키를 굽는 것과 유사하게 캐시 미스의 상대적 비용에 대한 통찰력을 제공하려는 시도입니다.

당신의 손은 당신의 레지스터입니다. 반죽에 초콜릿 칩을 떨어 뜨리는 데 1 초가 걸립니다.

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

냉장고는 L2 캐시로 L1보다 4 배 더 느립니다. 냉장고까지 걸어 가서 냉장고를 열고, 어젯밤 남은 음식을 옮기고, 계란 상자를 꺼내고, 상자를 열고, 카운터에 계란 3 개를 놓고, 상자를 다시 넣으려면 4 x 12 = 48 초가 걸립니다. 냉장고.

찬장은 L3 캐시로 L2보다 3 배 더 느립니다. 3 x 48 = 2 분 24 초 동안 찬장까지 3 걸음 이동하고, 구부리고, 문을 열고, 제빵 용 용기를 찾기 위해 뿌리를 내리고, 찬장에서 꺼내서 열고, 파서 베이킹 파우더를 찾습니다. , 카운터에 놓고 바닥에 흘린 엉망진창을 쓸어 내십시오.

그리고 메인 메모리? L3보다 5 배 느린 코너 스토어입니다. 지갑을 찾고, 신발과 재킷을 입고, 거리를 질주하고, 우유 한 리터를 들고, 집으로 돌진하고, 신발과 재킷을 벗고, 부엌으로 돌아가는 데 5 x 2:24 = 12 분이 걸립니다.

참고 모든 O (1) - - 이러한 접근은 일정 복잡하지만 그들 사이의 차이가있을 수 있습니다 엄청난 성능에 영향을. 순전히 big-O 복잡성에 맞게 최적화하는 것은 초콜릿 칩을 한 번에 1 개 또는 한 번에 10 개에 초콜릿 칩을 추가할지 여부를 결정하지만 식료품 목록에 넣는 것을 잊는 것과 같습니다.

이야기의 도덕 : CPU가 가능한 한 드물게 식료품을 구입하도록 메모리 액세스를 구성합니다.

숫자는 CPU 캐시 플러싱 오류 블로그 게시물 에서 가져온 것으로, 특정 2012 년 인텔 프로세서의 경우 다음 사항이 참임을 나타냅니다.

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

프로세서 캐시 효과의 갤러리 도이 주제에 대한 좋은 읽을 수 있습니다.

---

L1 캐시 미스의 경우 3.2ns는 전적으로 그럴듯합니다. 비교를 위해, 하나의 특정 최신 멀티 코어 PowerPC CPU에서 L1 미스는 약 40 주기입니다 .L2 캐시에서 얼마나 멀리 떨어져 있는지에 따라 일부 코어의 경우 약간 더 길어집니다 (정말 그렇습니다). L2 미스는 최소 600 주기입니다.

캐시는 성능의 모든 것입니다. CPU는 이제 메모리보다 훨씬 빠르기 때문에 코어 대신 메모리 버스를 거의 최적화하고 있습니다.

---

네, 그것은 주로 L1 캐시 미스 일 것 같습니다.

L1 캐시 미스에 대한 10주기는 합리적으로 들리지만 아마도 약간 낮은 편입니다.

RAM에서 읽기는 100 초 정도 걸리거나 심지어 1000 초 (지금은 수학을 시도하기에는 너무 피곤해;))주기가 될 수 있으므로 여전히 큰 승리입니다.

---

cachegrind를 사용하려는 경우 캐시 적중 / 실패 시뮬레이터 일뿐입니다. 항상 정확하지는 않습니다. 예를 들어, 루프에서 0x1234와 같은 메모리 위치에 1000 번 액세스하는 경우 cachegrind는 다음과 같은 경우에도 항상 캐시 미스 (첫 번째 액세스)가 하나만 있음을 표시합니다.

루프에서 0x1234를 clflush합니다.

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

---

Lavalys Everest의 3.4GHz P4에 대한 일부 수치는 다음과 같습니다.

• L1 dcache는 8K (cacheline 64 바이트)
• L2는 512K입니다.
• L1 가져 오기 지연 시간은 2주기입니다.
• L2 가져 오기 지연 시간은 현재보고있는 것의 약 두 배입니다. 20주기

추가 정보 : http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt

(대기 시간은 페이지 하단을 참조하십시오)

---

더 많은 테스트없이 확실하게 말하기는 어렵지만 내 경험상 차이의 규모는 특히 무작위 액세스 시나리오에서 CPU L1 및 / 또는 L2 캐시에 기인 할 수 있습니다. 각 액세스가 마지막 액세스로부터의 최소 거리 이상인지 확인하면 상황을 더욱 악화시킬 수 있습니다.

---

가장 쉬운 방법은 대상 CPU의 배율 사진을 찍고 코어와 레벨 1 캐시 사이의 거리를 물리적으로 측정하는 것입니다. 그 거리에 전자가 구리에서 초당 이동할 수있는 거리를 곱하십시오. 그런 다음 같은 시간에 얼마나 많은 시계주기를 가질 수 있는지 알아 내십시오. 이것이 L1 캐시 미스에 낭비하게 될 최소 CPU주기 수입니다.

또한 동일한 방식으로 낭비되는 CPU주기 수와 관련하여 RAM에서 데이터를 가져 오는 최소 비용을 계산할 수 있습니다. 놀랄 수도 있습니다.

여기서보고있는 것은 캐시 누락 (L1 또는 L1 및 L2 둘 다)과 확실히 관련이 있습니다. 일반적으로 캐시는 필요한 캐시 라인에있는 항목에 액세스하면 동일한 캐시 라인에서 데이터를 가져옵니다. RAM으로의 이동이 적습니다.

그러나 아마도 RAM (Random Access Memory라고도 함)이 여전히 선형 메모리 액세스를 선호한다는 사실을 알게 될 것입니다.

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