Strassen 매트릭스 배율이 왜 그렇게 빠른가요?

Question

실험으로 Strassen Matrix Multiplication Algorithm을 구현하여 큰 n에 대해 더 빠른 코드로 이끌어 낼 수 있는지 확인했습니다. 놀랍게도

https://github.com/wcochran/strassen_multiplier/blob/master/mm.c

는 더 빨리 큰 N에 대한 방법이었다. 예를 들어 n = 1024 인 경우 은 기존 방법을 사용하여 17.20 초가 걸리는 반면 Strassen 메서드 (2x2.66 GHz Xeon)를 사용하는 경우에만 1.13 초인 이 필요했습니다. 무엇 - 15x 속도 향상!? 조금 더 빨라야합니다. 사실, 작은 32x32 매트릭스에서도 좋은 것처럼 보였습니다!

내가 설명하는 유일한 방법은 알고리즘이 캐시 친화적 인 것입니다. 즉, 매트릭스의 작은 부분에 초점을 맞추고 데이터가보다 현지화되어 있습니다. 어쩌면 나는 가능하면 모든 매트릭스 계산을 단편적으로 수행해야한다.

다른 이유에 대한 다른 이론은 왜 그렇게 빠른가요?

Answer 1

첫 번째 질문은 "결과가 맞습니까?"입니다. 그렇다면 "기존"방법이 좋은 구현이 아닐 가능성이 큽니다.

전통적인 방법은 3 개의 중첩 된 FOR 루프를 사용하여 수학 수업에서 배운 순서로 입력을 스캔하지 않는 것입니다. 한 가지 간단한 개선 사항은 행이 아니라 일관된 열을 사용하여 메모리에 놓 이도록 행렬을 오른쪽으로 옮기는 것입니다. 이 대체 레이아웃을 사용하도록 곱셈 루프를 수정하면 큰 행렬에서 훨씬 빠르게 실행됩니다.

표준 매트릭스 라이브러리는 데이터 캐시의 크기를 고려한 훨씬 많은 캐시 친화적 인 방법을 구현합니다.

또한 표준 매트릭스 제품의 재귀 버전을 구현할 수도 있습니다 (절반 크기의 2x2 매트릭스 매트릭스로 세분화). 이것은 strassen이 재귀 적으로되는 최적 캐시 성능에 더 가깝게 제공합니다.

그래서 잘못하고 있거나 기존 코드가 최적화되어 있지 않습니다.

Answer 2

Strassen의 반복적 인 성격은 그림의 일부가 될 수있는 더 나은 메모리 지역성을 갖습니다. 재귀 일반 행렬 곱셈은 아마도 과 비교할만한 합리적인 것입니다.

Answer 3

기존 곱셈의 루프 순서는 무엇입니까?

for (int i = 0; i < new_height; ++i) 
{ 
    for (int j = 0; j < new_width; ++j) 
    { 
     double sum = 0.0; 
     for (int k = 0; k < common; ++k) 
     { 
      sum += lhs[i * common + k] * rhs[k * new_width + j]; 
     } 
     product[i * new_width + j] = sum; 
    } 
} 

그렇다면 비 일관적인 방식으로 오른쪽 행렬에 액세스하기 때문에 캐쉬가 좋지 않을 것입니다. 재정렬 후

for (int i = 0; i < new_height; ++i) 
{ 
    for (int k = 0; k < common; ++k) 
    { 
     double const fixed = lhs[i * common + k]; 
     for (int j = 0; j < new_width; ++j) 
     { 
      product[i * new_width + j] += fixed * rhs[k * new_width + j]; 
     } 
    } 
} 

가장 안쪽에있는 두 행렬에 대한 액세스는 연속적이며 하나는 고정되어 있습니다. 좋은 컴파일러가 자동으로이 작업을 자동으로 수행하지만 실제로 데모 용으로 선택했습니다.

언어를 지정하지 않았지만 C++의 경우 고급 컴파일러는 일부 구성에서 부적절한 루프 순서를 인식하고 순서를 변경합니다.