딥마인드의 AlphaDev, 새로운 정렬 알고리즘을 발견하다

1. 서문

 

AlphaDev가 강화학습을 통해 설계된 더 빠른 정렬 알고리즘을 발견했다.

 

기본 C++ 라이브러리에서 10년만에 정렬 라이브러리에 대한 최초의 변경이며, 오픈소스화하여 전 세계 수백만명의

 

개발자와 기업이 클라우드 컴퓨팅 및 온라인 쇼핑에서 공급망 관리에 이르기까지 산업 전반의 AI 어플리케이션에서 이 알고리즘을 사용하고 있다

 

현대 정렬 알고리즘은 컴퓨터 과학자와 프로그래머가 개발하는데 수십년의 연구가 필요했다.

 

그것들은 매우 효율적이며, 이제는 전기를 절약하는 새로운 방법이나

 

보다 효율적인 수학적 접근 방식을 찾는 것과 유사하게 추가 개선을 하는 것이 주요 과제이다.

 

 

 

2. 어셈블리 언어에 해답이 있다

 

AlphaDev는 기존 알고리즘을 개선하지 않고, 처음부터 다시 시작하여 더 빠른 알고리즘을 발견했다.

 

대부분의 인간이 찾지 못하는 부분인 컴퓨터의 assembly instruction을 찾기 시작했다.

 

어셈블리 명령은 컴퓨터가 실행할 이진 코드를 만드는데 사용된다.

 

개발자는 고급 언어라고 하는 C++같은 코딩 언어로 작성하지만, 컴퓨터가 이해할 수 있도록 "저수준" 어셈블리 언어로 변환해야한다.

 

더 높은 수준의 코딩 언어에서 발견하기 어려운 많은 개선 사항이 이 낮은 수준의 어셈블리 언어에 존재한다고 믿었다.

 

컴퓨터 스토리지 및 운영은 이 수준에서 더 유연하며, 이는 속도와 에너지 사용에 더 큰 영향을 미칠 수 있는 잠재적인 개선 사항이 훨씬 더 많다는 것을 의미한다.

 

 

코드는 위와 같이 일반적으로, C++와 같은 고급 프로그래밍 언어로 작성된다.

 

그런 다음 컴파일러를 사용하여 어셈블리 명령이라고 하는 하위 수준 CPU 명령으로 변환된다.

 

그런 다음 어셈블러는 어셈블리 명령을 컴퓨터에서 실행할 수 있는 실행 가능한 기계어 코드로 변환한다.

 

 

 

 

배열에서 2개의 원소를 정렬하는 C++ 알고리즘이 왼쪽에 제시되어있고, 이를 어셈블리 언어로 표현하면 오른쪽과 같다.

 

 

3. 게임으로 최고의 알고리즘을 찾다

 

AlphaDev는 바둑, 체스, 일본 장기와 같은 게임에서 세계 챔피언을 이긴 강화학습 모델인 AlphaZero를 기반으로 한다.

 

AlphaDev를 통해 이 모델이 게임에서 과학적 과제로, 시뮬레이션에서 실제 어플리케이션으로 어떻게 전환될 수 있는지 보여준다.

 

AlphaDev가 새로운 알고리즘을 발견하도록 훈련시키기 위해 우리는 정렬을 싱글 플레이어의 "assembly game"으로 변환했다.

 

매 턴마다 AlphaDev는 생성한 알고리즘과 CPU에 포함된 정보를 관찰한다.

 

그런 다음 알고리즘에 추가할 명령을 선택한다.

 

어셈블리 게임은 AlphaDev가 정렬할 수 있고, 현재 최고의 알고리즘보다 빠른 알고리즘을 찾기 위해

 

엄청난 수의 가능한 명령 조합을 효율적으로 검색해야하므로, 매우 어렵다.

 

가능한 명령 조합의 수는 우주의 입자 수 또는 체스 게임($10^{120}$)에서 가능한 움직임 조합의 수, 바둑의 수($10^{700}$)와 유사하다

 

AlphaDev의 한번의 잘못된 선택이 전체 알고리즘을 무효로 할 수 있다.

 

 

그림 A는 AlphaDev의 assembly game이다. 현재 생성된 알고리즘의 상태인 $S_{t}$를 입력으로 받고,

 

다음 행동을 선택하여 게임을 시작한다.

 

행동을 선택한다는 의미는 지금까지 생성된 정렬 알고리즘에 추가할 어셈블리 명령을 선택한다는 의미다.

 

MOV<Register0, Memory1>이라는 명령 $a_{t}$를 선택하여 알고리즘에 추가한다는 의미를 그림으로 나타냈다.

 

 

그림 B는 알고리즘의 보상을 계산하는 그림이다.

 

모든 test sequence를 현재 생성된 알고리즘에 입력받아, 출력인 output을 생성하고, 예상 출력과 비교한다

 

이때, agent는 알고리즘의 정확도와 latency(지연시간)에 따라 보상 reward를 받는다

 

----------------------------------------------------------------------------------------------------------------------------------------------------

 

알고리즘이 한 번에 하나의 명령어로 빌드되면, AlphaDev는 알고리즘의 출력을 예상 결과와 비교하여 올바른지 확인한다.

 

정렬 알고리즘의 경우 정렬되지 않은 숫자가 들어가고, 올바르게 정렬된 숫자가 나온다는 의미이다.

 

우리는 숫자를 올바르게 정렬하고 얼마나 빠르고 효율적으로 정렬하는지에 대해 AlphaDev에 보상한다.

 

결과적으로 AlphaDev는 정확하고 빠른 프로그램을 발견하여 이 게임에서 승리하게 된다.

 

 

4. 결과

 

AlphaDev는 짧은 sequence의 경우 최대 70%까지 더 빠르게 LLVM libc++ 정렬 라이브러리를 개선시켰고,

 

250000개의 요소를 초과하는 sequence의 경우 1.7% 더 빠르게 개선시켰다.

 

우리는 3~5개의 요소를 가지는 짧은 sequence의 정렬 알고리즘을 개선하는데 집중했다.

 

이 알고리즘은 가장 자주 사용되는데, 더 큰 정렬 함수의 일부로 많이 호출되기 때문이다.

 

이 알고리즘을 개선하는 것이 임의의 개수의 요소를 정렬하는데 전반적인 속도를 올리는데 기여할 수 있다.

 

이렇게 발견한 정렬 알고리즘을 사람들이 더 유용하게 사용할 수 있도록 reverse-engineering하고, 가장 인기 있는 언어중 하나인 C++로 변환하였다.

 

현재 전 세계 수백만 명의 개발자와 회사에서 사용하는 LLVM libc++ 표준 정렬 라이브러리에서 사용할 수 있다.

 

 

5. AlphaDev가 정렬을 위한 새로운 접근법을 발견하다

 

AlphaDev는 더 빠른 알고리즘 뿐만 아니라, 새로운 접근 방식도 발견하였다.

 

그러한 접근 방식은 매번 적용될 단일 명령을 가지고 있는 새로운 명령들의 연속을 포함한다.

 

하루에도 수조번이나 사용되는 이러한 알고리즘에 큰 영향을 미칠 수 있다.

 

우리는 이를 "AlphaDev swap and copy moves"라고 부른다.

 

이러한 새로운 접근법은 전설적인 바둑 선수 이세돌의 패배로 이어진 직관적이지 않은 플레이인 AlphaGo의 37수를 연상시킨다.

 

swap 및 copy를 통해 AlphaDev는 실수처럼 보이지만 실제로는 지름길인 방식으로 항목을 연결하는 단계를 건너뛴다.

 

이것은 독창적인 솔루션을 발견하는 AlphaDev의 능력을 보여주고 컴퓨터 과학 알고리즘을 개선하는 방법에 대해 생각하는 방식에 도전한다

 

------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

AlphaDev swap

 

 

$B \leq C$가 보장된 <A,B,C>에 대해 원래 최적화된 구현은 b의 수도코드와 같은데, 

 

AlphaDev는 그림 c의 수도코드를 찾아냈다.

 

정렬하면 min(A,B,C), max(min(A,C),B), max(A,C)와 같이 하면 된다는데,

 

min(A,B,C)대신에 min(A,B)만 하면 된다는 것을 발견하고, 이렇게 함으로써, 원래 구현보다 한줄의 명령(P=min(A,C))을 덜 처리한다

 

AlphaDev copy

 

또한 $D \geq min(A,C)$를만족하는 <A,B,C,D>에 대해서도 f의 수도코드를 발견했다 

 

원래 Q = max(B,min(A,C,D))를 사용한 왼쪽 e의 수도코드와 같이 구현한 최적화된 코드는 8개 요소를 정렬하는데 사용된다.

 

하지만 AlphaDev는 max(B,min(A,C))만 사용해도 된다는 것을 발견하여 한줄의 명령(mov P T)를 덜 처리하게 된다

 

sequence의 크기관계가 고정된 경우에 성립하는것 같기는 한디 이게 대단한건가..?

 

--------------------------------------------------------------------------------------------------------------------------------------------------------

 

논문에서는 다음과 같이 "AlphaDev가 발견한 근본적으로 다른 알고리즘"이라고 제시했는데,

 

길이 2,3,4인 배열에 대한 정렬 알고리즘을 플로우 차트로 나타냈다

 

 

 

그림 a는 받은 배열의 길이가 길이 4, 길이 3, 길이 2에 따라 각각의 정렬 알고리즘을 수행한 기존의 인간이 최적화한 알고리즘인데

 

그림 b는 똑같이 길이 2,3,4인 배열을 받는데, 길이가 2라면 2요소에 대한 정렬 알고리즘을 수행하고,

 

2보다 작다면 그대로 return하고, 2보다 크다면 길이 3의 정렬 알고리즘을 수행하는데, 

 

길이가 2보다 큰 경우, 먼저 첫 3개 원소에 대한 3요소 정렬 알고리즘을 수행하고, 길이가 3인지 4인지 검사한다

 

길이가 3이라면 그대로 return하지만, 길이가 4라면, "현재 첫 3요소가 정렬된 상태에서 4요소를 정렬하는 알고리즘"을 수행해서 속도를 상당히 개선했다고 한다

 

이거는 진짜 대단하긴하네 이게 강화학습인가..?

 

--------------------------------------------------------------------------------------------------------------------------------------------------------

 

6. AlphaDev가 hashing을 개선할 수 있는가

 

해싱은 데이터를 검색, 저장 및 압축하는데 사용되는 컴퓨팅 기본 알고리즘이다.

 

분류 시스템을 사용하여 특정 책을 바로 찾는 사서와 마찬가지로,

 

해싱 알고리즘은 사용자가 찾고 있는 내용과 책을 찾을 수 있는 정확한 위치를 알 수 있도록 도와준다.

 

이런 알고리즘은 특정 키(예: 이름 "Jane Doe")에 대한 데이터를 가져와 해시하고, 원시 데이터가 고유한 문자열(예: "1234ghfty")로 변환되는 프로세스이다.

 

이러한 해시 방식은 컴퓨터에서 모든 데이터를 검색하는 대신, 키와 관련된 데이터를 빠르게 검색하는데 사용한다.

 

더 빠른 알고리즘을 발견하기 위해 데이터 구조에서 해싱에 가장 일반적으로 사용되는 알고리즘 중 하나에 AlphaDev를 적용했다.

 

그리고 해싱 함수의 9~16바이트범위에 적용할때, AlphaDev가 발견한 알고리즘은 30%더 빨랐다.

 

이러한 알고리즘도 오픈소스 Abseil 라이브러리에 출시하여 현재 하루에 수조번 사용되고 있는 것으로 추정된다.

 

7. 결론

 

AlphaDev는 전 세계 개발자들이 사용하는 개선된 정렬 및 해싱 알고리즘을 최적화하고 출시하여, 

 

실제 세계에 영향을 미치는 새로운 알고리즘을 일반화하고 발견할 수 있는 능력을 입증했다.

 

낮은 수준의 어셈블리 명령어 공간에서 최적화하는 것은 매우 강력하지만, 알고리즘이 성장하면서 한계가 있으며,

 

현재 개발자에게 더 유용한 C++와 같은 고급 언어에서 직접적으로 알고리즘을 최적화하는 AlphaDev의 가능성을 탐색하고 있다.

 

swap, copy같은 AlphaDev의 새로운 발견은 알고리즘을 개선할 수 있을 뿐만 아니라 새로운 솔루션을 찾을 수 있음을 보여준다.

 

이러한 발견으로 연구자와 개발자 모두가 기본 알고리즘을 최적화하여 보다 강력하고 지속 가능한 컴퓨팅 세계를 만들 수 있는 기술과 접근 방식을 만들 수 있기를 바란다

 

AlphaDev, 더 빠른 정렬 알고리즘 발견 (deepmind.com)

AlphaDev discovers faster sorting algorithms

 

Faster sorting algorithms discovered using deep reinforcement learning | Nature