AI는 정렬 알고리즘을 70% 더 빠르게 다시 작성합니다. DeepMind AlphaDev는 매일 수조 건의 라이브러리 업데이트를 호출하여 컴퓨팅 기반을 혁신합니다.

"교체 및 복사 이동을 통해 AlphaDev는 한 단계를 건너뛰고 잘못된 것처럼 보이지만 실제로는 지름길입니다." 이 전례 없고 반직관적인 아이디어는 사람들에게 2016년 봄을 상기시키지 않을 수 없습니다.

7년 전 AlphaGo는 바둑에서 인간 세계 챔피언을 이겼고 이제 AI는 우리에게 프로그래밍에 대한 또 다른 교훈을 가르쳐주었습니다.

오늘 아침 일찍, Google DeepMind CEO Hassabis의 두 문장이 컴퓨터 분야를 충격에 빠뜨렸습니다. "AlphaDev는 새롭고 더 빠른 정렬 알고리즘을 발견했으며 우리는 개발자가 사용할 수 있도록 이를 기본 C++ 라이브러리에 오픈 소스로 제공했습니다. 이것은 단지 코드 효율성 향상을 위한 AI 발전의 시작 이번에 Google DeepMind의 새로운 강화 학습 시스템인 AlphaDev는 이전보다 더 빠른 해싱 알고리즘을 발견했으며, AI의 결과가 이제 LLVM 표준 C++에 통합되었습니다. 라이브러리 Abseil 및 오픈 소스.

이 결과가 얼마나 중요합니까? AlphaDev의 주요 저자 중 한 명이자 Google DeepMind의 연구 과학자인 Daniel J. Mankowitz는 "우리가 발견한 정렬 및 해싱 알고리즘은 전 세계적으로 매일 수조 번 호출되는 것으로 추정됩니다."라고 말했습니다. 알고리즘 수준에서 세상의 속도를 높이세요.

이러한 알고리즘은 LLVM libc++ 정렬 라이브러리를 개선하여 더 짧은 시퀀스의 경우 70% 더 빠르고 요소가 250,000개가 넘는 시퀀스의 경우 약 1.7% 더 빠릅니다. Google DeepMind는 이것이 시퀀싱 라이브러리의 이 부분에 대한 첫 번째 변경이라고 말합니다. 이제 AI는 사람들이 코드를 작성하는 데 도움을 줄 뿐만 아니라 더 나은 코드를 작성하는 데도 도움이 되는 것 같습니다.

최신 블로그에서 새로운 시스템의 저자들이 AlphaDev를 자세히 소개했습니다.

새로운 알고리즘은 컴퓨팅의 기반을 바꿀 것입니다.

디지털 사회는 컴퓨팅과 에너지에 대한 수요 증가를 주도합니다. 지난 50년 동안 디지털 시대는 수요를 따라가기 위해 하드웨어의 개선에 의존해 왔습니다. 그러나 마이크로칩이 물리적 한계에 가까워짐에 따라 마이크로칩에서 실행되는 코드를 개선하는 것이 중요해졌습니다. 이는 매일 수조 번 실행되는 코드에 포함된 알고리즘에 특히 중요합니다.

Google DeepMind의 이번 연구는 "Nature"에 관련 논문이 게재되었습니다. AlphaDev는 강화 학습을 사용하여 과학자와 엔지니어가 수십 년 동안 연마한 것보다 더 뛰어난 알고리즘을 발견하는 AI 시스템입니다. 결과.

논문 주소: https://www.nature.com/articles/s41586-023-06004-9

일반적으로 AlphaDev는 더 빠른 정렬 알고리즘을 발견했습니다. 매일 수십억 명의 사람들이 이러한 알고리즘을 사용하지만 개선의 여지가 있다는 것을 깨닫는 사람은 아무도 없습니다. 정렬 알고리즘은 온라인 검색 결과, 소셜 게시물 정렬, 컴퓨터 및 휴대폰에서의 다양한 데이터 처리에 이르기까지 광범위한 응용 분야에 사용되며 모두 정렬 알고리즘과 분리될 수 없습니다. AI를 사용하여 더 나은 알고리즘을 생성하면 인간이 컴퓨터를 프로그래밍하는 방식이 바뀌고 점점 더 디지털화되는 사회에 큰 영향을 미칠 것입니다.

주요 C++ 라이브러리에 새로운 정렬 알고리즘을 오픈 소스화함으로써 전 세계 수백만 명의 개발자와 기업이 이제 클라우드 컴퓨팅, 온라인 쇼핑, 공급망 관리 등 다양한 산업 분야의 AI 애플리케이션에서 이를 사용할 수 있습니다. . 이는 10여년 만에 순위 라이브러리에 대한 첫 번째 변경 사항이며, 강화 학습으로 설계된 알고리즘이 라이브러리에 추가된 것은 처음입니다. 이는 인공 지능을 사용하여 전 세계의 코드를 점진적으로 최적화하는 데 있어 중요한 이정표라고 생각하세요.

정렬 정보

정렬 알고리즘은 특정 작업을 특정 순서로 정렬하는 방법입니다. 예를 들어, 세 글자를 알파벳순으로 정렬하거나, 다섯 개의 숫자를 가장 큰 것부터 가장 작은 것 순으로 정렬하거나, 수백만 개의 레코드로 구성된 데이터베이스를 정렬할 수 있습니다.

이 알고리즘은 오랫동안 사용되어 왔으며 잘 발전했습니다. 주문의 최초 사례 중 하나는 학자들이 알렉산드리아 도서관 서가에 있는 수천 권의 책을 손으로 알파벳순으로 정리한 서기 2~3세기로 거슬러 올라갑니다. 산업 혁명의 도래와 함께 사람들이 분류하는 데 도움을 줄 수 있는 기계가 등장했습니다. 표 작성 기계는 1890년 미국 인구 조사 결과를 수집하는 데 사용된 천공 카드를 사용하여 정보를 저장했습니다.

1950년대 상업용 컴퓨터가 등장하면서 정렬 알고리즘을 위한 최초의 컴퓨터 과학 알고리즘이 개발되기 시작했습니다. 오늘날 엄청난 양의 온라인 데이터를 처리하기 위해 전 세계의 코드 기반에서 사용되는 다양한 정렬 기술과 알고리즘이 있습니다.

알고리즘에 정렬되지 않은 일련의 숫자를 입력하고 정렬된 숫자를 출력합니다.

컴퓨터 과학자와 프로그래머가 수십 년간 연구한 결과, 현재의 정렬 알고리즘은 이미 너무 효율적이어서 추가 개선을 이루기가 어렵습니다. 이는 전력을 절약하거나 더 효율적인 수학을 위한 새로운 방법을 찾으려는 것과 다소 유사합니다. 이러한 알고리즘은 컴퓨터 과학의 초석이기도 합니다.

새로운 알고리즘 탐색: 조립 지침

AlphaDev는 기존 알고리즘을 기반으로 하는 대신 처음부터 더 빠른 알고리즘을 탐색하는 데에도 사용할 수 있습니다: 컴퓨터 조립 지침.

어셈블리 명령어를 사용하여 컴퓨터가 실행하는 바이너리 코드를 만들 수 있습니다. 개발자는 C++와 같은 고급 언어로 코드를 작성하지만 이를 컴퓨터가 이해할 수 있는 "저급" 어셈블리 명령으로 변환해야 합니다.

Google DeepMind는 이 수준에서 더 높은 수준의 프로그래밍 언어에서는 발견하기 어려울 수 있는 개선의 여지가 많다고 믿습니다. 이 수준에서는 컴퓨터의 저장 및 작동이 더 유연해집니다. 즉, 속도와 에너지 사용에 더 큰 영향을 줄 수 있는 개선 가능성이 더 많다는 의미입니다.

코드는 일반적으로 C++와 같은 고급 프로그래밍 언어로 작성됩니다. 그런 다음 컴파일러는 이를 어셈블리 명령어라고 하는 하위 수준 CPU 명령어로 변환합니다. 어셈블러는 컴퓨터가 실행할 수 있도록 어셈블리 명령을 실행 가능한 기계어 코드로 변환합니다.

그림 A: 최대 두 개의 요소를 정렬하는 C++ 알고리즘의 예 그림 B: 해당 어셈블리 표현.

AlphaGo의 방법을 사용하여 최고의 알고리즘 찾기

AlphaDev는 바둑, 체스, 체스 등의 게임에서 세계 챔피언을 물리친 강화 학습 모델인 Google DeepMind: AlphaZero의 이전 결과를 기반으로 합니다. 그리고 AlphaDev는 이 모델이 게임에서 과학적 과제로, 시뮬레이션에서 실제 응용 프로그램으로 어떻게 전환되는지 보여줍니다.

AlphaDev가 새로운 알고리즘을 발견하도록 훈련시키기 위해 팀은 정렬을 싱글 플레이어 "조립 게임"으로 전환했습니다. 각 단계에서 AlphaDev는 자신이 생성한 알고리즘과 CPU에 포함된 정보를 관찰한 후 알고리즘에 추가할 명령어를 선택하여 다음 동작을 수행합니다.

조립 게임은 매우 어렵습니다. 왜냐하면 AlphaDev는 정렬할 수 있고 현재 최고의 알고리즘보다 더 빠른 알고리즘을 찾기 위해 가능한 많은 명령어 조합을 통해 효율적으로 검색해야 하기 때문입니다. 가능한 명령 조합 수는 우주의 입자 수 또는 체스(10^120 게임) 및 바둑(10^700 게임)의 가능한 동작 조합 수와 유사하며 한 번의 잘못된 동작으로 인해 게임이 중단될 수 있습니다. 전체 알고리즘.

사진 A: 조립 게임. 플레이어 AlphaDev는 시스템 st의 상태를 입력으로 받고 현재 생성된 알고리즘에 추가할 어셈블리 명령을 선택하여 체스를 플레이합니다. 그림 B: 보상 계산. 각 이동 후 결과 알고리즘에는 테스트 입력 시퀀스가 ​​제공됩니다. sort3의 경우 이는 세 요소 시퀀스의 모든 조합에 해당합니다. 그런 다음 알고리즘은 정렬 상황에 따라 정렬된 시퀀스의 예상 출력과 비교되는 출력을 생성합니다. 에이전트는 알고리즘 정확성과 지연 시간을 기준으로 보상을 받습니다.

한 번에 하나의 명령어씩 알고리즘을 구축할 때 AlphaDev는 알고리즘의 출력을 예상 결과와 비교하여 올바른지 확인합니다. 정렬 알고리즘의 경우 순서가 없는 숫자가 들어가고 올바르게 정렬된 숫자가 나온다는 의미입니다. 팀은 숫자를 정확하게 정렬한 것에 대해 AlphaDev에게 보상하고 정렬의 속도와 효율성을 제공하며 AlphaDev는 정확하고 빠른 프로그램을 발견하여 게임에서 승리합니다.

더 빠른 정렬 알고리즘을 발견했습니다.

AlphaDev는 LLVM libc++ 정렬 라이브러리를 개선한 새로운 정렬 알고리즘을 발견했습니다. 더 짧은 시퀀스의 경우 정렬 라이브러리가 70% 더 빠릅니다. 250,000개 이상의 요소 시퀀스의 경우, 속도는 약 1.7% 증가합니다.

그 중 Google DeepMind 팀은 3~5개 요소의 짧은 시퀀스 정렬 알고리즘을 개선하는 데 더 중점을 두고 있습니다. 이러한 알고리즘은 더 큰 정렬 기능의 일부로 여러 번 호출되는 경우가 많기 때문에 가장 널리 사용되며, 이러한 알고리즘을 개선하면 항목 수에 관계없이 전체 정렬 속도를 높일 수 있습니다.

새로운 정렬 알고리즘을 사람들에게 더욱 유용하게 만들기 위해 팀에서는 알고리즘을 역설계하고 개발자가 가장 많이 사용하는 프로그래밍 언어 중 하나인 C++로 번역했습니다.

현재 이러한 알고리즘은 LLVM libc++ 표준 정렬 라이브러리(https://reviews.llvm.org/D118029)에서 제공되며 전 세계 수백만 명의 개발자와 회사에서 사용됩니다.

"교환과 복사 행위", 신의 손이 다시 나타난다?

실제로 AlphaDev는 더 빠른 알고리즘뿐만 아니라 새로운 방법도 발견했습니다. 정렬 알고리즘은 적용될 때마다 명령을 저장하는 새로운 명령 시퀀스로 구성됩니다. 이러한 알고리즘은 매일 수조 번 사용되기 때문에 분명히 큰 영향을 미칩니다. 그들은 이것을 "AlphaDev 스왑 및 복사 작업"이라고 부릅니다.

이 참신한 접근 방식은 AlphaGo의 "37단계"를 연상시킵니다. 이는 구경꾼을 놀라게 하고 전설적인 바둑 선수 이세돌을 패배시키는 반직관적인 움직임입니다. 작업을 교환하고 복사함으로써 AlphaDev는 단계를 건너뛰고 실수처럼 보이지만 실제로는 지름길인 방식으로 항목을 연결합니다. 이는 독창적인 솔루션을 발견하고 컴퓨터 과학 알고리즘을 개선하는 방법에 대해 인간이 생각하는 방식에 도전하는 AlphaDev의 능력을 보여줍니다.

왼쪽: min(A,B,C) 원래 sort3 구현, 오른쪽: AlphaDev 스왑 이동 - AlphaDev는 min(A,B)만 필요하다는 것을 발견했습니다.

왼쪽: 8개 요소를 정렬하기 위한 대규모 정렬 알고리즘에서 max(B,min(A,C,D))를 사용한 원래 구현, 오른쪽: AlphaDev는 복사 작업을 사용할 때 max(B,min(A)만 발견했습니다. ,C))가 필요하다.

확장 능력 테스트: "정렬"에서 "해시"까지

더 빠른 정렬 알고리즘을 발견한 후 팀은 AlphaDev가 다른 컴퓨터 과학 알고리즘인 해싱을 일반화하고 개선할 수 있는지 테스트했습니다.

해시는 컴퓨팅에서 데이터를 검색, 저장 및 압축하는 데 사용되는 기본 알고리즘입니다. 특정 책을 찾기 위해 분류 시스템을 사용하는 사서와 마찬가지로 해싱 알고리즘은 사용자가 무엇을 찾고 있는지, 어디서 찾을 수 있는지 알 수 있도록 도와줍니다. 이러한 알고리즘은 특정 키(예: 사용자 이름 "Jane Doe")에 대한 데이터를 가져와 해시합니다. 즉, 원시 데이터를 고유한 문자열(예: 1234ghfty)로 변환하는 프로세스입니다. 컴퓨터는 모든 데이터를 검색하는 대신 이 해시를 사용하여 키와 관련된 데이터를 빠르게 검색합니다.

팀은 더 빠른 알고리즘을 발견하기 위해 데이터 구조에서 가장 일반적으로 사용되는 해싱 알고리즘 중 하나에 AlphaDev를 적용했습니다. 9~16바이트 범위의 해시 함수에 적용하면 AlphaDev는 알고리즘 속도가 30% 향상되는 것을 확인했습니다.

올해 AlphaDev의 새로운 해싱 알고리즘이 오픈 소스 Abseil 라이브러리에 출시되어 전 세계 수백만 명의 개발자가 사용할 수 있게 되었으며 현재는 하루에도 수조 번 정도 사용되고 있습니다.

오픈소스 주소: https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e

결론

구글 딥마인드는 ㅋㅋㅋ ​주변에서 사용 가능한 해시 알고리즘을 최적화하고 출시함으로써 개발자가 사용하는 AlphaDev는 실제 세계에 영향을 미치는 새로운 알고리즘을 일반화하고 발견하는 능력을 보여줍니다. AlphaDev는 전체 컴퓨팅 생태계를 최적화하고 사회의 이익을 위해 다른 문제를 해결하는 데 도움이 될 수 있는 범용 AI 도구를 개발하기 위한 한 단계로 볼 수 있습니다.

저수준 어셈블리 명령 공간에서의 최적화는 매우 강력하지만 AlphaDev는 알고리즘이 성장함에 따라 여전히 한계를 갖고 있으며 팀은 현재 C++와 같은 고급 언어에서 직접 알고리즘을 최적화하는 능력을 탐색하고 있습니다. 개발자에게 더 유용합니다.

교체 및 복사 작업과 같은 AlphaDev의 발견은 알고리즘을 개선할 수 있을 뿐만 아니라 새로운 솔루션을 찾을 수도 있음을 보여줍니다. 이러한 발견은 연구원과 개발자가 기본 알고리즘을 더욱 최적화하여 더욱 강력하고 지속 가능한 컴퓨팅 생태계를 만들 수 있는 기술과 방법을 개발하도록 영감을 줄 수 있습니다.

위 내용은 AI는 정렬 알고리즘을 70% 더 빠르게 다시 작성합니다. DeepMind AlphaDev는 매일 수조 건의 라이브러리 업데이트를 호출하여 컴퓨팅 기반을 혁신합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!