DeepMind가 심층 강화 학습을 이용해 알고리즘을 개선하는 AI 「AlphaDev」를 발표

 
AlphaGo를 개발한 것으로 유명한 Google DeepMind가 심층 강화 학습을 응용해 다양한 컴퓨팅 알고리즘을 개선하는 AI 「AlphaDev」를 발표했습니다. 또한, 이 AlphaDev를 이용하여 정렬 알고리즘을 가속화할 수 있었다는 논문이 Nature에 게재되어 있습니다.

AlphaDev discovers faster sorting algorithms

AlphaDev discovers faster sorting algorithms

Faster sorting algorithms discovered using deep reinforcement learning | Nature
https://doi.org/10.1038/s41586-023-06004-9


정렬 알고리즘은 랜덤 상태의 데이터를 순서대로 정렬하는 알고리즘입니다. 검색결과 및 SNS 게시 순위를 비롯해 일반적인 앱의 모든 부분에서 활용되고 있으며, 전 세계로 따지면 매일 몇 조 번씩 실행되고 있습니다. 이는 매우 중요하고 기본적인 알고리즘으로 인해 전 세계 연구자들에 의해 수십 년 동안 개선되고 있으며, 이미 더 이상 고칠 곳이 없을 정도로 효율적으로 구현되어 있습니다.

그러나, 인간에 의한 개선 활동은 주로 C++의 코드 레벨에서 행해지고 있습니다. C++로 작성된 코드는 실제 코드가 실행되기 전에 어셈블리 언어로 컴파일된 다음 어셈블러를 통해 기계어로 변환하는 절차를 밟습니다. DeepMind의 연구팀은 이 「어셈블리 언어」 레벨이라면 C++의 코드에서는 찾을 수 없는 개선점을 발견할 수 있을지도 모른다고 생각했습니다.

AlphaDev는 AlphaZero를 베이스로 한 AI로, 정렬을 1인용의 「조립 게임」으로 간주해 트레이닝하는 것으로 알고리즘의 개선을 실시할 수 있도록 했습니다.

「조립 게임」의 구성은 아래와 같습니다. AlphaDev는 각 턴에서 CPU에 저장된 정보와 생성된 알고리즘을 확인하고 새롭게 알고리즘에 명령을 추가합니다. 알고리즘의 구축이 완료되면, 그 알고리즘의 실행해 정답을 맞힐 수 있었는지와 정답까지의 시간으로 스코어를 산출하고 있습니다. 결국, 정답을 더 빠르게 낼 수 있는 프로그램이 승리하는 것입니다.
이 수법을 이용하는 것으로, AlphaDev는 오픈 소스 컴파일러 기반 「LLVM」으로 이용되고 있는 표준 라이브러리 「libc++」의 정렬 구현을 고속화할 수 있었습니다. 3 ~ 5요소의 정렬에서 최대 70% 고속화하고 있으며, 25만 요소를 넘는 대규모 정렬에서도 약 1.7% 고속화가 가능했다고 합니다.

3 요소의 정렬을 예로 들어보면 AlphaDev는 이전 처리에서 2개의 입력의 대소가 사전에 고정되어 있는 경우를 놓치지 않고 명령수를 1개 줄일 수 있었다고 합니다.

또한, 기존이라면 아래 그림의 왼쪽과 같이 요소수에 따라 "4요소용 처리", "3요소용 처리", "2요소용 처리"라고 나누고 있던 것을 아래 그림 오른쪽과 같이 3 요소 이상의 경우에 있어서 일단 3요소용의 소트 처리를 실시하고, 만약 4요소였던 경우는 나중에 단순 처리를 덧붙인다고 하는 수법으로 크게 처리 속도를 개선했습니다.

AlphaDev가 개발한 정렬 알고리즘은 LLVM libc++ 에 도입되어, 이미 수백만 명의 개발자들에게 이용되고 있습니다.

AlphaDev는 정렬 알고리즘뿐만 아니라 해시 함수의 가속화에도 성공하고 있습니다. 해시 함수가 가장 이용되고 있는 데이터 구조 처리에 주력한 결과, 9~16 바이트의 입력에 있어서 30% 빠르게 해시를 계산하는 것이 가능했다고 합니다. 이 개선된 해시 함수는 Abseil 라이브러리에 도입되었다고 합니다.