표준 행렬 곱셈 알고리즘의 효율성 향상?

Question

표준 매트릭스 곱셈 알고리즘의 효율성을 어떻게 향상시킬 수 있습니까? 이 방법에 관련된

주요 작업은 다음과 같습니다 C[i][j]+=A[i][p]*B[p][j]

알고리즘의 효율성을 개선하기 위해 무엇을 할 수 있는지

?

Answer 1

당신은 BLAS (기본 선형 대수 서브 루틴) 라이브러리를 사용하여 좀보고 할 수 있습니다

는 특히 인텔이 자신의 MKL here을 제공, AMD는이 자신의 ACML here과 (오픈 소스)도있다 고토 BLAS here.

(조밀 한) 행렬 - 행렬 곱셈 커널은 ?GEMM 호출이됩니다. 여기서 ?은 부동 소수점 유형을 나타냅니다. 예를 들어 DGEMM은 double 루틴을 호출합니다.

낮은 수준의 최적화로 무엇을하고 있는지 잘 알지 못하는 한이 라이브러리는 아마도 직접 코딩 할 수있는 것보다 우수한 성능을 제공 할 것입니다. 당신이 자신을이 코딩에서 이동을 할 경우

당신은 다음 고려할 수 있습니다 :

1. 사용 "벡터"지시. SSE, SSE2..4 명령어가 널리 지원되며, 일부 최신 버전 CPU은 AVX 명령어도 지원합니다.
2. 부동 소수점 연산과로드/저장 연산의 비율을 최대화하는 중첩 루프 언 롤링입니다.
3. 효과적인 캐시 사용을 보장하는 블록 별 알고리즘.
4. 멀티 스레딩. - K 고토 수준-3 BLAS의

   고성능 구현 :

이 참조하면 사물의 현재 상태의 아이디어를 줄 수 있습니다.

희망이 도움이됩니다.

Answer 2

이 정확한 질문을 다루는 Golub and Van Loan의 1 장을 읽는 것이 좋습니다.

Answer 3

1. 캐시 차단 - 제대로 사용하고 캐시에
2. 더 나은 알고리즘을 값을 재사용하고 있는지 만들기 - 행렬을 곱하려면 "별로 정의"방법은 최적이 아닌, Strassen's algorithm
3. 를 살펴 병렬화 - 컴퓨터가 하나 개 이상의 코어 및/또는 프로세서가있는 경우, 당신은 분할하고
4. SIMD를 정복 할 수 있습니다 - 현대 CPU 아키텍처에
5. GPGPU를 SSE 벡터 명령을 활용 - 현대의 GPU는 단지 이런 종류의 작업을 수행하도록 최적화되어 맡은 일. CUDA 및 OpenCL을 살펴보십시오.

이러한 방법을 사용한다고해서 성능이 향상되는 것은 아닙니다. 상당한 속도 향상을 위해 많은 튜닝이 필요합니다. 주제에 대한 저널 기사의 부족이 없도록 행렬을 빠르게 곱하는 방법을 알아내는 데 많은 돈이 소요됩니다.

Answer 4

여러 행렬 곱셈 - M1 x M2 x ... x Mn -과 관련하여 동적 프로그래밍을 기반으로하는 또 다른 최적화 기술이 있습니다. 이는 다른 볼 게임의 일종입니다. 이것은 두 개의 행렬을 곱하는 효율성을 향상시키는 데는 적용되지 않는다는 점에 유의하십시오. 그러나 3 개 이상의 행렬을 한 쌍으로 곱하면 더 높은 수준에서 최적화 할 수 있습니다. 그냥 정보를 완성하기 위해이 답변을 힙에 던질 것이라고 생각했습니다.

가

Answer 5

글쎄, 매트릭스의 크기에 따라 목록에있는 표준 알고리즘보다 약간 더 빠른 Strassen's Algorithm이 있습니다. 물론 even faster algorithms이 있지만 구현하기가 쉽지 않습니다.

표준 알고리즘은 O이다 (N은^3) 쉬트 라쎈의 ALGO은 O (N^2.8) 이고 카퍼 - Winograd은 O (N^2.3)