Google Deepmind's AlphaDev is designed to find better computer algorithms. In a test run, the AI system found sorting algorithms that were up to 70 % more efficient.
Google Deepmind has developed several influential AI models, including AlphaZero and MuZero. These algorithms are used by Google to better manage data centres and compress video. Perhaps the most influential to date is AlphaFold, an algorithm used by researchers around the world to aid protein research and development.
Now Google Deepmind has unveiled AlphaDev, an AI system that uses reinforcement learning to find new computer algorithms.
AlphaDev improves algorithms executed trillions of times a day
"Digital society is driving increasing demand for computation, and energy use. For the last five decades, we relied on improvements in hardware to keep pace. But as microchips approach their physical limits, it’s critical to improve the code that runs on them to make computing more powerful and sustainable", Google Deepmind explains its research. " This is especially important for the algorithms that make up the code running trillions of times a day."
With AlphaDev, the company has now discovered a new, faster sorting algorithm that outperforms algorithms developed by humans over decades. The algorithms, which are open source, underpin everything from classifying online search results to social messaging and computing on computers and smartphones.
The new algorithms led to improvements in the libc++ LLVM sorting library, which is now up to 70 percent faster for shorter sequences and about 1.7 percent faster for sequences with more than 250,000 elements. AlphaDev also discovered a faster algorithm for hashing, a fundamental process for storing and retrieving data. The new hashing algorithm improves the efficiency of data centre hashing functions in the 9 to 16-byte range by 30 percent.
AlphaDev is AlphaZero for assembly instructions
AlphaDev is based on AlphaZero, but instead of playing Go, Chess or Shogi, AlphaDev plays with the computer's assembly instructions. Assembly instructions are low-level instructions that a computer's CPU can understand and execute. To discover new algorithms, the team turned sorting into a singleplayer "assembly game". With each move, AlphaDev observes the algorithm it has created, and the information contained in the CPU. With each move, the system adds a new instruction to the algorithm.
According to Google Deepmind, the assembly game is incredibly difficult because it requires AlphaDev to efficiently sift through a huge number of possible instruction combinations to find a better algorithm.
As society becomes more digital, it’s critical to improve the code powering the world's computing.
Today in @Nature, we present AlphaDev, an AI system using reinforcement learning to discover enhanced computer science algorithms.
How does it work? 🧵 https://t.co/2ukGaPey5w pic.twitter.com/dSedrv7eik
— Google DeepMind (@DeepMind) June 7, 2023
As AlphaDev constructs the algorithm, it checks that the algorithm is correct by comparing the output of the algorithm with the expected results. For sorting algorithms, this means inputting unordered numbers and outputting correctly sorted numbers. AlphaDev is rewarded during training for sorting the numbers correctly and for the speed and efficiency with which it does so. The ultimate goal is to find a correct and faster program.
Once AlphaDev found such algorithms, the team reverse-engineered them and translated them into C++.
AlphaDev to play with C++ code in the future
Optimization in low-level assembler instructions was very efficient but reached its limits as the size of the algorithm increased. The team is currently investigating the ability of AlphaDev to optimize algorithms directly in languages such as C++.
"We see AlphaDev as a step towards developing general-purpose AI tools that could help optimise the entire computing ecosystem and solve other problems that will benefit society."
For more information, see the AlphaDev blog post.
