Sorting algorithms are a fundamental feature that computers around the world are constantly using, and while billions of people use them every day, no one realizes that there is room for optimization. Google DeepMind said: "It seems that now AI can not only help people write code, but also help us write better code." ”
On June 7, local time, Google DeepMind, which has just been merged, announced the launch of a new member of the Alpha family, AlphaDev, an artificial intelligence system that uses reinforcement learning to improve computer science algorithms, which has discovered a faster sorting algorithm, which is hailed as breaking the "seal" of algorithms for a decade and becoming an important milestone in optimizing code using artificial intelligence.
Google DeepMind CEO Demis Hassabis announced on the social platform: "AlphaDev has discovered a new and faster sorting algorithm that we have open-sourced into major C++ libraries for developers to use. This is just the beginning of AI's progress in improving code efficiency. ”
The new algorithm speeds up the sorting library by 70 percent for shorter sequences and about 1.7 percent faster for sequences with more than 250,000 data, surpassing decades of careful polishing by human scientists and engineers. From online search results and social posts to how computers and mobile phones process data, algorithms exist everywhere on the Internet and are executed trillions of times a day. Using AI to generate better algorithms will change the way we program computers and impact every aspect of our digital society.
The work has now been included and open sourced into the LLVM standard C++ library Abseil, the first time the C++ ordering library has been changed in more than a decade, and the first time an algorithm designed through reinforcement learning has been added to the library. The related research paper, entitled "Faster sorting algorithms discovered using deep reinforcement learning", has been published in the authoritative scientific journal Nature.
The new AI of the Alpha family breaks the code bottleneck, and the algorithm used by billions of people is 70% more efficient.
Find the optimal solution of the acceleration algorithm through the game
Sorting algorithms are a fundamental feature that computers around the world use constantly, and while billions of people use them every day, no one realizes that there is room for optimization. Google DeepMind said: "It seems that now AI can not only help people write code, but also help us write better code." ”
According to reports, AlphaDev is built on the AlphaZero reinforcement learning model, and its working method is similar to AlphaZero, which combines computer reasoning and intuition, and has repeatedly defeated world champions in games such as Go and chess. In board games, AlphaZero has the ability to choose each move, but AlphaDev can only choose to add instructions, not how to move next.
It is worth mentioning that DeepMind chose assembly language, which is now rare, which is the language in which code written in languages such as C++ is translated before running, and processed by computer chips. The advantage of assembly is that it allows the algorithm to be broken down into smaller steps, which is a good starting point if it is looking for a faster way.
To train AlphaDev to discover new algorithms, Google DeepMind turned the sorting problem into an "Assembly Game." In each round, AlphaDev needs to observe the algorithm it generates and the information contained in the central processing unit (CPU), and move by adding an instruction to the algorithm. And this assembly game is very difficult, because AlphaDev must effectively search through a large number of possible combinations of instructions to find an algorithm that can be sorted and faster than the best algorithm at the moment.
The number of "possible command combinations" that AlphaDev needs to operate on is comparable to the number of particles in the universe, or the number of possible combinations of moves in chess (10 to the power of 120) and Go (10 to the power of 700). Even harsher, any one wrong move can invalidate the entire algorithm. DeepMind's breakthrough lies in treating the problem of finding faster algorithms as a game, then letting its AI win the game, and finally rewarding AlphaDev based on its ability to sort numbers correctly and the speed and efficiency with which it completes the sorting, while AlphaDev needs to win the game by finding a correct and faster program. If AlphaDev's algorithm is both correct and faster than existing algorithms, it wins.
It may solve the problem of Moore's Law slowdown
The sorting algorithm improves the LLVM libc++ sorting library: 70% faster for shorter sequences and about 1.7% faster for sequences with more than 250,000 data.
Among them, the Google DeepMind team is more focused on improving the short sequence sorting algorithm of 3 to 5 elements. These algorithms are among the most widely used because they are often called multiple times as part of a larger sort function, and improving these algorithms can improve the overall speed of sorting any number of items.
In fact, AlphaDev has discovered not only faster algorithms, but also new methods. Its sequencing algorithms contain new sequences of instructions, saving one instruction each time they are applied – which obviously has a huge impact, as these algorithms use trillions of times a day. The researchers call these "AlphaDev swap and copy actions."
The novel approach is reminiscent of AlphaGo's "Step 37," a counterintuitive move that stunned onlookers and led to the defeat of the legendary Go player, Lee Sedol. By swapping and copying actions, AlphaDev skips a step and connects items in a way that looks like a bug but is actually a shortcut. This demonstrates AlphaDev's ability to unearth original solutions and challenge the way humans think about how to improve computer science algorithms.
"To be honest, we didn't expect better results: it's a very short procedure, and these types of procedures have been studied for decades." Daniel Mankowitz, a research scientist at Google DeepMind and lead author of the paper, said, "We initially thought it had made a mistake, or had a bug or something, but when we analyzed the program, we realized that AlphaDev had actually found something faster." ”
"Optimizing code for basic functions that are called trillions of times per day is expected to bring enough benefits to encourage people to try to execute more of these functions as one of the ways to solve the bottleneck of Moore's Law slowdown," Mankowitz said. ”
Mark Lee, a professor at the University of Birmingham in the United Kingdom, argues that AlphaDev is interesting and that even a 1.7% speed increase is useful, but it is not yet certain whether this method can compensate for the bottleneck of Moore's Law, because it cannot achieve the same benefits in more complex situations.
30% faster hashing algorithm
After discovering a faster sorting algorithm, the team tested whether AlphaDev could generalize and improve a different computer science algorithm: hashing.
Hashing is the basic algorithm used in computing to retrieve, store, and compress data. Just like librarians who use a classification system to locate a certain book, hashing algorithms can help users know what they're looking for and where to find it. These algorithms take data for a specific key (e.g. the username "Jane Doe") and hash it – a process that converts the raw data into a unique string (e.g. 1234ghfty). Computers use this hash to quickly retrieve data related to the key instead of searching for all the data. When the team applied AlphaDev to the 9-16 byte range of the hash function, the algorithm found by AlphaDev was 30 percent faster.
Currently, Google DeepMind is exploring AlphaDev's ability to directly optimize algorithms in high-level languages such as C++, which will be more useful for developers.
Google DeepMind wrote in its official blog: "By optimizing and rolling out improved sorting and hashing algorithms used by developers around the world, AlphaDev has demonstrated its ability to generalize and discover new algorithms with real-world impact." We see AlphaDev as a step in the development of general-purpose AI tools that can help optimize the entire computing ecosystem and solve other problems that benefit society. ”