np.sort는 이제부터 15배 빨라집니다. 인텔, 최대 17배 빠른 AVX-512 정렬, 새로운 알고리즘을 갖춘 x86-simd-sort 2.0 출시

np.sort는 이제부터 15배 빨라집니다.

(Numpy==1.25.0을 설치하고 AVX-512를 지원하는 프로세서를 사용한다면요.)

고성능 정렬 알고리즘과 AVX-512 프로젝트에 대해 관심이 있으신 분들께서 관심을 가질만한 새로운 소식이 있습니다.

2023년 6월 23일, AVX-512 정렬 프로젝트 Repository에서 공개된 문서

 

AVX-512 정렬 라이브러리

지난 3월, 인텔 소프트웨어 엔지니어들은 10~17배 빠른 정렬 속도를 제공하는 초고속 AVX-512 정렬 라이브러리를 발표했는데요. 이 라이브러리는 Numpy에 의해 처음 채택되기도 했습니다. 그리고 최근인 2023년 6월 23일, 더 많은 AVX-512 기능과 추가 정렬 알고리즘이 추가된 x86-simd-sort 2.0이 출시되었습니다.

 

 

x86-simd-sort 첫 번째 stable version인 v1.0은 SIMD 기반 16/32/64비트 데이터 유형의 정렬을 C++ 헤더 파일의 라이브러리로 지원하는 형태로 지난 3월에 릴리스되었는데요. 이후 별다른 소식을 전달하지 못하다가 최근 2.0 버전을 발표하였습니다.

 

AVX-512 특징

고성능 정렬에 관심이 있고 AVX-512의 성능 잠재력을 지속적으로 극대화하는 데 관심이 있는 분들은 이번 x86-simd-sort 2.0 버전의 공개에 대해 주목해볼만 할 것 같습니다. 관련 내용이 해당 프로젝트의 Github에 공개되었는데요. x86-simd-sort 2.0의 릴리스 하이라이트는 다음과 같습니다.

 

• 32비트 및 64비트 데이터 유형에 대해 O(1) 공간을 사용하는 AVX-512 기반 argsort 알고리즘, 이는 배열을 정렬할 수 있는 인덱스를 반환하며 std::sort를 사용하는 스칼라 솔루션과 비교했을 때 최대 6배 빠릅니다. (현재 최신 버전의 numpy 1.25.0 version 이상에서 사용할 수 있다고 하네요.)
• 16비트, 32비트 및 64비트 데이터 유형에 대한 AVX-512 기반 quick select 알고리즘. 이는 std::nthelement와 동일하지만 훨씬 더 빠른 성능을 발휘합니다. 성능은 K/N 비율에 따라 달라집니다(여기서 K는 배열이 분할되는 요소의 인덱스이고 N은 배열 크기입니다). K 값이 작을수록 64비트 데이터의 경우 최대 6배, 32비트 데이터의 경우 최대 15배, 16비트 데이터의 경우 최대 7배 더 빠릅니다. K가 커질수록 성능은 더 좋아집니다
• 16비트, 32비트 및 64비트 데이터 유형에 대한 AVX-512 기반 partial sort 알고리즘. std::partial_sort와 동일하며 성능은 K/N(여기서 K는 부분 정렬된 배열의 크기, N은 배열 크기)의 비율에 따라 달라지고, 이 값이 클수록 훨씬 더 빠른 성능을 발휘하는 경향이 있습니다. 작은 부분 배열 정렬의 경우 약 1.05배, 약간 큰 부분 배열의 경우 최대 20배 더 빠릅니다.
• AVX-512 기반 key-value 정렬. 이 정렬은 key-value 배열 쌍을 정렬하며 현재 64비트 데이터 유형에 대해서만 지원됩니다. 이 버전은 오픈 소스 분산 관계형 데이터베이스인 Oceanbase에 기여되었습니다.
• AVX-512 FP16 ISA를 사용한 _Float16 데이터 유형에 대한 AVX-512 정렬. Numpy에서 float16 데이터 유형을 에뮬레이트하는 AVX-512 기반의 정렬보다 거의 3배가 빠릅니다.

 

 

아직 인텔의 최신 클라이언트 프로세서에서는 AVX-512를 찾을 수 없지만 AMD Zen4나 Xeon Scalable 서버를 사용하시는 분들께는 흥미로운 소식일 것 같습니다.

 

 

Linus Torvalds

한편 리눅스의 창시자인 리누스 토발즈 (Linus Torvalds)가 과거에 "AVX-512가 고통스럽게 죽길 바란다."라고 발언했던 적이 있는데요. 관련 기사도 함께 보시면 좋을 것 같습니다.