Join top executives in San Francisco July 11-12 to hear how leaders are integrating and optimizing AI investments for success. Learn more
Google’s artificial intelligence (AI) research lab DeepMind has achieved a remarkable feat in computing through its latest AI system, AlphaDev. This specialized version of AlfaZero took a significant step forward by discovering faster sorting and hashing algorithms, which are essential processes used trillions of times a day by developers around the world for sorting, storing, and retrieving data.
In a paper published Today in the scientific journal Nature, DeepMind says AlphaDev’s recently discovered algorithm achieves an efficiency increase of 70% for sorting short sequences of items and about 1.7% for sequences exceeding 250,000 items , compared to the algorithms in the C++ library. As a result, when a user submits a search query, AlphaDev’s algorithm facilitates faster sorting of results, leading to significant time and energy savings when deployed at scale.
In addition, the system also discovered a faster algorithm for hashing information, resulting in a 30% efficiency improvement when applied to hashing functions in the 9 to 16 byte range in data centers.
Revolutionize computing
Deepmind believes this remarkable achievement revolutionizes computing and promises to improve efficiency and effectiveness.
“AlphaDev discovered improved sorting algorithms, including new innovations like AlphaDev’s copy and swap moves,” Google DeepMind staff researcher Daniel Mankowitz told VentureBeat. “Similar to AlphaGo’s famous ‘move 37’ which produced a new set of strategies for playing the old game of Go, it is hoped that AlphaDev’s unique algorithmic discoveries will inspire new perspectives and strategies to optimize core computer algorithms and make them more fast.”
Mankowitz said this is a significant milestone for reinforcement learning as it provides further evidence of its ability to make new discoveries, especially in the domain of code optimization.
The company also announced plans to make the new algorithms available through the LLVM libc++ standard sorting library, with the goal of empowering millions of developers and businesses across multiple industries. Significantly, this update represents the first revision of this section of the sorting library in over a decade and the initial inclusion of an algorithm developed through reinforcement learning.
“We estimate that our open-source sorting algorithms, which produce speed improvements of approximately 2% to 70%, are called trillions of times every day around the world,” Mankowitz said. “These algorithms can provide resource savings to developers and enterprises that call these functions into their systems and applications. We believe these algorithms will inspire researchers and practitioners to develop novel approaches that will lead to further discovery of new and improved algorithms.”
Using reinforcement learning to improve traditional algorithm development
According to DeepMind, most computational algorithms have reached a stage where human experts have been unable to optimize them further, resulting in an increasing computational bottleneck.
The company emphasized the fact that the use of deep reinforcement learning improves development methods by generating precise and efficient algorithms. This is achieved by optimizing the effective latency measured at the CPU instruction level, conducting more efficient lookup, and accounting for fast and accurate programs in the space.
Sorting algorithms, in essence, facilitate the systematic arrangement of items in a specified order. These serve as the foundation of computer science education.
Likewise, hashing finds widespread application in data storage and retrieval, such as in a customer database. Hashing algorithms commonly use a key (username “Jane Doe”) to generate a unique hash corresponding to the data values desired for retrieval (“order number 164335-87”). Similar to a librarian using a filing system to readily locate a particular book, a hashing system allows the computer to possess prior knowledge of the desired information and its precise location.
Detailed overview
While developers primarily write code in intuitive high-level languages such as C++, translating these languages into low-level assembly instructions is imperative to understanding computers.
DeepMind researchers believe that there are many improvements at the lower level, which could be a challenge to unravel in higher-level programming languages. The assembly level offers flexibility in computer storage and operations, presenting the vast potential for improvements that can substantially affect speed and power efficiency.
To run an algorithm in C++, it is first compiled into low-level CPU instructions called assembly instructions, which manipulate data between memory and registers on the CPU.
“This provides a much more detailed overview of how the algorithm works and therefore makes it easier to find optimizations to improve the algorithm,” Mankowitz said. “By optimizing in assembly, we discovered AlphaDev’s copy and swap moves. These are sequences of assembly instructions that reduce the program size to a single instruction when applied to an assembly program.
Deepmind’s unique approach to discovering faster algorithms
DeepMind’s AlphaDev has taken an unconventional approach to discovering faster algorithms by venturing into the realm of computer assembly instructions, a domain rarely explored by humans.
To unlock new algorithms, AlphaDev drew inspiration from DeepMind’s popular reinforcement learning model, AlphaZero, which has scored victories against world champions in games like Go, chess, and shogi (Japanese chess).
To train AlphaDev to discover new algorithms, the research team reinvented sorting as a single-player “assembly game”. AlphaDev used reinforcement learning to observe and generate algorithms by incorporating information from the CPU.
The AI system proactively chose an instruction to incorporate into the algorithm at each stage, resulting in an extremely complex and challenging process given the vast number of potential instruction combinations.
Discovering a faster and more correct program
Since AlphaDev built the algorithm incrementally, it also validated the correctness of each move by comparing the algorithm’s output with the expected results. The ultimate goal of this approach was to discover a correct and faster program, thus achieving victory in the game.
DeepMind’s AI system has unearthed new sorting algorithms that have resulted in substantial improvements within the LLVM libc++ sorting library.
Research has mainly focused on improving sorting algorithms for shorter sequences, typically consisting of three to five elements. Since these algorithms are often incorporated into larger sort functions, improving their efficiency can improve overall speed when sorting any number of items.
To improve usability, DeepMind reverse engineered the discovered algorithms and converted them to C++.
Overcoming the realm of sorting algorithms
The improvements affect the sort3, sort4, and sort5 routines that sort numbers, specifically integers and floats, Mankowitz explained.
“Anytime a developer or an application needs to sort these types of data, our sorting algorithms can be called,” he said. “With speed improvements ranging from 2% to 70% depending on the number of items being sorted and these functions being called trillions of times every day, developers and users will be able to run their applications/use various services while consuming fewer resources.”
Furthermore, AlphaDev’s capabilities surpass the realm of sorting algorithms. DeepMind explored the system’s potential to generalize its approach and improve other essential computer algorithms, including hashing. Applying AlphaDev’s methodology to the hashing algorithm in the 9 to 16 byte range resulted in a 30% speed improvement.
“As such, we optimized for hashing ‘correctness’ (minimizing collisions) and speed (latency),” Mankowitz explained.
The hashing algorithm is now available in the open source library Abseil.
What’s next for Deepmind?
DeepMind claims that AlphaDev is a significant milestone in the progression towards building versatile AI tools that can optimize the entire computing ecosystem and address various societal challenges.
While optimizing low-level assembly instructions has proven immensely powerful, the company said it is actively exploring AlphaDev’s potential for optimizing algorithms directly in high-level languages like C++, which would be even more valuable to developers. .
“AlphaDev is optimizing a portion of the compute stack,” Mankowitz said. “This makes the underlying algorithms that run on the stack more efficient. We’re also looking to optimize other aspects of the stack.”
For example, scheduling resources more efficiently when running applications and services, optimizing the YouTube video compression pipeline, and optimizing the underlying hardware on which systems and applications run.
“We hope these algorithms will give researchers and practitioners a different perspective on how algorithms can be built,” said Mankowitz.
VentureBeat’s mission it is to be a digital city square for technical decision makers to gain insights into transformative business technology and transactions. Discover our Briefings.
