512x512 행렬을 전치하는 것이 513x513 행렬을 전치하는 것보다 훨씬 느린 이유는 무엇입니까?

512x512 행렬 전치가 513x513 행렬 전치보다 느린 이유

다양한 크기의 행렬에 대한 실험을 수행한 후 행렬 전치에 대한 특이한 관찰이 발생했습니다. 차원이 2^인 행렬을 전치하는 것입니다. n은 차원 2^n 1을 전치하는 것보다 계산 비용이 더 많이 듭니다. n이 512일 때 불일치가 커집니다.

전치 연산을 위해 제공되는 코드는 다음과 같습니다.

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

MATSIZE 매크로를 변경하여 행렬의 크기를 수정할 수 있습니다. 다음 벤치마크는 극명한 차이를 보여줍니다.

• 크기 512: 평균 2.46ms
• 크기 513: 평균 0.75ms

캐시 경합 및 임계 스트라이드

이러한 변칙의 원인은 다음과 같습니다. 캐시 동작 및 캐시 경합의 개념. 자세한 내용은 다음과 같습니다.

• 캐시는 세트와 라인으로 구성됩니다. 특정 순간에 하나의 세트에만 액세스되며 해당 세트 내의 모든 회선을 활용할 수 있습니다. 총 캐시 크기는 라인 수에 각 라인의 크기를 곱하여 결정됩니다.
• 특정 메모리 주소가 속한 세트를 계산하려면 다음 공식이 사용됩니다. 세트 = ( 주소 / 라인 크기 ) % numberOfsets.
• 여러 메모리 주소가 동일한 세트에 액세스하면 캐시 충돌이 발생합니다. 이러한 시나리오에서는 세트에서 가장 최근에 사용된 라인을 새로 검색된 데이터로 덮어씁니다.
• 캐시 충돌을 초래하는 메모리 액세스 수를 나타내는 임계 스트라이드는 importantStride = numberOfSets로 계산됩니다. * lineSize.
• 8kb 캐시가 있는 64x64 행렬의 경우 임계 보폭은 행렬의 행과 완벽하게 정렬되어
• 그러나 매트릭스 크기를 65x65로 늘리면 임계 스트라이드가 더 이상 완벽하게 정렬되지 않아 캐시 충돌 빈도가 줄어들고 성능이 향상됩니다.

따라서 캐시 경합으로 인해 차원이 2^n의 배수인 행렬의 경우 전치 작업이 상당히 느려집니다.

위 내용은 512x512 행렬을 전치하는 것이 513x513 행렬을 전치하는 것보다 훨씬 느린 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!