GN⁺: 처음부터 설계하는 SIMD 알고리즘

SIMD 알고리즘 설계

• SIMD 최적화에 대한 설명: SIMD는 단일 명령어 다중 데이터를 의미하며, 회로 설계자처럼 생각하는 것이 필요함.
• SIMD는 성능과 HPC(고성능 컴퓨팅)에서 자주 언급되지만 초보자에게 친숙한 주제는 아님.
• 대부분의 프로그래밍 언어에서 SIMD 프로그래밍 API는 사용하기 어려움.
• SIMD 알고리즘은 절차적 프로그래밍 사고방식으로는 이해하기 어려우며 함수형 프로그래밍이 도움이 됨.
• 본문은 Rust의 std::simd 라이브러리를 사용하여 base64 코덱을 구현한 vb64에 대한 것임.

물리적 한계

• 컴퓨터는 실제 세계에 존재하며 물리 법칙에 구속됨.
• 초기 컴퓨팅 시대에는 새 컴퓨터를 구입함으로써 성능을 향상시킬 수 있었음.
• 덴나드 스케일링 효과가 붕괴되어, 더 작은 트랜지스터는 더 많은 전력 소모를 의미함.
• 코어 수를 늘리는 것이 새로운 트렌드가 됨. 멀티스레딩을 통해 CPU 성능을 향상시킬 수 있으나 동기화 오버헤드가 발생함.

절차적 코드의 느림

• 현대 컴퓨터 코어는 코드를 줄 단위로 실행하지 않음.
• 명령어 수준 병렬성을 통해 데이터 의존성이 없는 경우 동시에 여러 연산을 수행함.
• 컴파일러가 데이터 위험을 해결할 수 있을 때 병렬성이 증가함.
• 분기와 메모리 작업은 스톨을 발생시키며, 이는 코드를 느리게 만듦.

SIMD와 레인

• SIMD와 벡터는 종종 동의어로 사용됨.
• SIMD 명령어는 고정 크기의 숫자 배열인 벡터를 기본 단위로 사용함.
• 벡터의 각 요소를 레인이라고 하며, SIMD 벡터는 일반적으로 작은 크기임.

실제 벡터에 대한 연산

• SIMD 벡터는 일반 레지스터보다 복잡한 연산을 제공함.
• 벡터 레지스터는 비트 연산, 레인별 산술 연산, 레인별 비교, 셔플 등 다양한 연산을 지원함.
• 셔플은 SIMD 프로그래밍에서 데이터를 적절한 위치로 이동시키는 데 중요함.

내장 함수와 명령 선택

• SIMD 코드 작성 시 사용 가능한 연산은 아키텍처에 따라 다름.
• 컴파일러는 사용자가 요청한 연산을 어떤 명령어로 선택할지 결정하는 명령 선택 문제를 해결함.
• 포터블 SIMD 코드 작성은 복잡하지만, 런타임 기능 감지를 통해 다양한 프로세서에서 최적의 코드를 생성할 수 있음.

SIMD로 파싱

• SIMD를 사용하여 텍스트 파싱이 가능하며, 매우 빠를 수 있음.
• base64 디코딩을 SIMD로 구현하는 것을 예로 들 수 있음.
• 모든 분기를 제거하는 것이 SIMD 버전을 만드는 과정의 핵심임.

GN⁺의 의견

이 글에서 가장 중요한 것은 SIMD 프로그래밍이 기존의 절차적 프로그래밍 방식과 다르게 데이터를 병렬로 처리하여 성능을 향상시킬 수 있다는 점입니다. SIMD는 고성능 컴퓨팅 분야에서 매우 중요하며, 특히 Rust와 같은 현대 프로그래밍 언어에서 SIMD를 효과적으로 사용하는 방법을 이해하는 것은 소프트웨어 엔지니어에게 매우 흥미로운 주제가 될 수 있습니다. SIMD를 통해 복잡한 알고리즘을 최적화하고, 실제 하드웨어의 한계를 극복하는 방법을 배울 수 있기 때문입니다.

[neo]

Hacker News 의견

• 포터블 SIMD 사용 사례를 볼 수 있는 훌륭한 기사. Zen 3 시스템에서 벤치마크를 재현해보니 동일한 속도 향상을 확인함. M1 mbp에서는 입력 길이 110바이트에서 최대 2배까지 성능 향상이 점진적으로 증가함. x86_64보다는 이득이 적지만 목표를 달성했다고 볼 수 있음. 그러나 Rust가 SIMD 및 포인터 관련 작업, 성능 엔지니어링 전반에 걸쳐 다소 불편한 점이 있음을 확인함.
• 때로는 C++로 최선을 다해 프로그래밍하려고 해도, SIMD를 사용한 버전이 10배 이상 빠른 성능을 보여주는 경우가 놀랍다. 코드의 이식성은 떨어지지만, 컴파일러가 자동 벡터화를 더 잘 해줬으면 하는 바람이 있음. 어노테이션을 통해 특정 연산의 순서를 재배열할 수 있도록 언어에 지원이 추가되었으면 좋겠음.
• 컴파일러가 특정 popcount 구현을 단일 명령어로 최적화하지 못했지만, 다른 구현에 대해서는 가능한 경우가 있음을 지적함.
• _mm256_cvtps_epu32는 AVX2의 명령어가 아니라 AVX-512의 명령어이며, AVX1에서는 정수가 부호 있는 형태로 존재하고 해당 명령어는 _mm256_cvtps_epi32임.
• 오른쪽에 있는 작은 미니맵이 매우 마음에 듦.
• ISPC는 C++나 Rust에 SIMD를 추가하는 것보다 낫다고 평가함. 또한, 동적 디스패칭을 지원하는데, 이는 직접 구현하기 까다로운 기능임.
• fastbase64와 비교했을 때 어떤가에 대한 질문과 함께, 포터블 SIMD 라이브러리에 대한 글쓴이의 낙관적인 태도를 공유하고 싶다는 의견을 제시함.
• 훌륭한 글로, 스스로 결코 이만큼 똑똑해질 수 없을 것 같다는 인상을 남김.
• 벡터화되지 않은 popcnt 구현의 첫 번째 예제가 "솔직히 말해서 우스꽝스러운 코드"를 생성한다고 언급되었지만, 네이티브 타겟 CPU에서 릴리스 모드로 컴파일하면 함수가 꽤 괜찮게 벡터화되는 것으로 보임.
• Rust Simd에 대한 상당히 좋은 시도. 생성된 코드를 검사했을 때 가장 놀라운 특이점은 무엇이었는지에 대한 질문을 제기함.