구글 딥마인드가 심층강화 학습을 응용해 다양한 컴퓨팅 알고리즘을 개선하는 AI인 알파데브(AlphaDev)를 발표했다. 동시에 알파데브를 이용해 정렬 알고리즘을 가속화할 수 있다는 논문이 학술지 네이처에 게재됐다.
정렬 알고리즘은 어색한 상태 데이터를 순서대로 정렬해주는 알고리즘이다. 검색 결과와 SNS 게시 순위를 비롯해 일반 앱 모든 부분에서 활용되고 있으며 전 세계에서 매일 몇 조회 실행되고 있다. 중요하고 기본적인 알고리즘으로 인해 전 세계 연구자에 의해 수십 년간 개선되고 있으며 이미 더 이상 없을 만큼 효율적인 구현이 되어 있다.
하지만 인간에 의한 개선 활동은 주로 C++ 코드 레벨에서 이뤄지고 있다. C++로 작성된 코드는 실제로 코드가 실행되기 전 어셈블리언어로 컴파일된 다음 어셈블러로 기계어로 변환하는 절차를 밟는다. 딥마인드 연구팀은 이 어셈블리언어 레벨이라면 C++ 코드에서 찾을 수 없는 개선점이 발견된다고 생각했다.
알파데브는 알파제로를 기반으로 한 AI로 정렬을 1인용 조립 게임으로 간주해 학습하는 것으로 알고리즘 개선을 실시할 수 있도록 했다. 알파데브는 각 턴에서 CPU에 저장된 정보와 생성된 알고리즘을 확인하고 새롭게 알고리즘에 명령을 추가했다. 알고리즘 구축이 완료되면 이 알고리즘을 실행해 테스트와 담합을 실시해 정답인지 어떤지와 정답까지 시간을 점수로 산출하고 있다. 올바른 대답을 낼 수 있는 빠른 프로그램을 발견할 수 있다면 승리를 하게 된다.
이 방법을 이용하는 것으로 알파데브는 오픈소스 컴파일러 기반 LLVM으로 이용되고 있는 표준 라이브러리 libc++ 구현을 고속화할 수 있었다고 한다. 3~5 요소 정렬로 최대 70% 고속화하고 있으며 25만 요소가 넘는 대규모 정렬에서도 1.7% 고속화할 수 있었다고 한다.
또 기존이라면 4요소용 처리, 3요소용 처리, 2요소용 처리로 나누던 걸 3요소 이상 경우에서 일단 3요소용 처리를 실시하고 만일 4요소였다면 나중에 단순한 처리를 덧붙이는 수법으로 처리 속도를 크게 개선했다.
알파데브가 개발한 정렬 알고리즘은 LLVM libc++에 도입되어 이미 개발자 수백만 명이 이용하고 있다. 알파데브는 정렬 알고리즘 뿐 아니라 해시함수 가속화에도 성공하고 있다. 해시함수가 가장 이용되는 데이터 구조용 처리에 주력한 결과 9∼16바이트 입력에 있어 30% 고속으로 해시를 계산하는 게 가능하게 됐다고 한다. 이 개선된 해시함수는 라이브러리(Abseil)에 도입됐다고 한다. 관련 내용은 이곳에서 확인할 수 있다.