두 요소가있는 필드에서 피터슨과 모니 코의 Lanczos 알고리즘을 SIMD로 구현하는 경우

Question

(이 질문은 "소프트웨어 권장 사항 없음"규칙과 관련이있을 것입니다. 자신의 종이 F_2 Lanczos revisited, 피터슨과 Monico는 Z/2Z 이상 선형지도의 커널의 부분 공간을 찾기위한에는 Lanczos 알고리즘의 버전을 제공에서

. 내 논문의 읽기가 정확하다면 (그것이 맞는지 아닌지에 상관없이), 제시된 알고리즘은 사용 된 기계의 단어 크기에 반비례하는 많은 반복을 요구한다. 저자는 개념 증명 알고리즘을 64 비트 워드 크기로 구현했습니다.

(잠재적으로 중요한) 속도 향상을 위해 넓은 SIMD 단어를 사용하여 공개적으로 사용할 수있는 알고리즘 구현이 있습니까?

Answer 1

기존 구현은 소프트웨어 권장 사항입니다. 더 흥미로운 질문은 "이 알고리즘을 더 빠르게 실행하려면 SIMD를 사용할 수 있습니까?" 필자의 글을 보면, SIMD가 정확하게 묘사 한 것처럼 들린다. ("64 비트 머신 워드 x를 8 개의 서브 워드로 분할 할 것입니다. 각각은 ... 8 비트 워드입니다.") 그래서 만약 저자의 구현은 어딘가에서 공개적으로 사용 가능하며, 이미 사용하고 있기 때문에 대답은 "예"입니다. 이 알고리즘이 C/C++ 또는 그와 비슷한 것으로 작성된 경우 최적화 컴파일러는 수동으로 레지스터 분할 방법을 지정하지 않고도 (어셈블리를 통해 확인할 수 있음) SIMD로 벡터화하는 작업을 수행 할 가능성이 높습니다. 논리적으로 레지스터를 수동으로 분할하지 않고 고수준 언어로 구현하는 것이 바람직합니다. 컴파일러는 대상 시스템의 워드 크기에 맞게 최적화 할 수 있기 때문입니다.