513x513 행렬 전치가 512x512 행렬 전치보다 빠른 이유는 무엇입니까?

512x512 및 513x513 행렬 크기에 대한 행렬 전치의 성능 차이 이해

다양한 크기의 정사각 행렬은 고유한 시간 차이를 나타냅니다. 그것들을 바꾸는 것. 흥미롭게도 2^n 차원의 행렬은 2^n 1 차원의 행렬에 비해 전치 시간이 느린 경향이 있습니다. 이러한 차이는 작은 n 값에서는 중요하지 않은 것처럼 보일 수 있지만 MATSIZE 512에서 알 수 있듯이 더 큰 차원에서는 중요해집니다. .

이러한 성과 격차의 근본 원인을 이해하기 위해 우리는 캐싱.

캐시 구성 및 세트 매핑

캐시는 세트와 라인으로 구성됩니다. 각 세트에는 데이터를 저장할 수 있는 여러 줄이 포함되어 있습니다. 특정 메모리 주소가 속한 세트를 찾으려면 다음 공식을 사용합니다.

set = (address / lineSize) % numberOfsets

결과적으로 메모리 주소는 다소 균일한 방식으로 세트에 매핑됩니다.

캐시 누락 및 라인 제거

메모리 위치에 액세스할 때 캐시는 데이터가 이미 존재하는지 확인합니다. 그렇지 않은 경우 캐시 미스가 발생하고 해당 라인을 메모리에서 읽어 캐시에 배치합니다. 그러나 캐시가 가득 차면 새 데이터를 수용하기 위해 LRU(Least Recent Used) 라인을 제거합니다.

Critical Stride

Critical Stride는 간격을 나타냅니다. 동일한 캐시 라인을 놓고 경합하는 변수 사이. 다음과 같이 계산됩니다.

criticalStride = numberOfSets * lineSize

Critical Stride 또는 그 배수만큼 간격을 둔 변수는 캐시 제거를 유발할 가능성이 더 높습니다.

Matrix Transposition 및 Critical Stride

8kB 캐시가 있는 64x64 매트릭스를 상상해 보세요. 세트당 4줄. 각 라인에는 8개의 64비트 정수가 포함될 수 있습니다. 이 시나리오에서 중요한 진전은 2048바이트이며 이는 행렬의 4개 행에 해당합니다.

행렬을 전치할 때 행과 열을 바꿉니다. 각 행을 처리하고 해당 열과 교환할 때 임계 스트라이드(4개 행)로 분리된 요소에 캐시 제거가 발생합니다. 이로 인해 상당한 수의 캐시 재로드가 발생하여 전치 속도가 느려집니다.

결론

512x512와 513x513 행렬 사이의 전치 시간 차이는 매트릭스 크기와 캐시의 중요한 진전. 임계 스트라이드의 배수가 아닌 차원을 가진 행렬은 캐시 제거가 줄어들고 결과적으로 전치 시간이 빨라집니다.

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