Deepmind’s AlphaDev discovers sorting algorithms that can revolutionize the foundations of computing

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 AlphaZero has taken 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 an article published today in the scientific journal Nature, DeepMind says that AlphaDev’s recently discovered algorithm achieves a 70% efficiency increase in sorting short sequences of items and about 1.7% for sequences exceeding the 250,000 elements, 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 that produced a new set of strategies for playing the old game of Go, AlphaDev’s unique algorithmic breakthroughs can hopefully inspire new perspectives and strategies for optimizing core computer algorithms and making them faster.

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 about 2% to 70%, are called trillions of times every day around the world, Mankowitz said. These algorithms can provide resource savings to developers and companies that call these functions into their systems and applications. We believe these algorithms will inspire researchers and practitioners to develop new 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 specific order. These serve as the foundation of computer science education.

Likewise, hashing finds widespread application in data storage and retrieval, such as 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.

Finely 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.

DeepMinds 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 thus 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 by a single instruction when applied to an assembly program.

Deepmind’s unique approach to discovering faster algorithms

DeepMinds 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.

The DeepMinds 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.

Whenever a developer or application needs to sort these types of data, our sorting algorithms can be called upon, 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 less resources.

Furthermore, AlphaDev’s capabilities surpass the realm of sorting algorithms. DeepMind has explored the potential of systems to generalize its approach and improve other essential computer algorithms, including hashing. Applying the AlphaDevs methodology to the hashing algorithm in the 9 to 16 byte range resulted in a 30% speed improvement.

Therefore, we optimized hashing correctness (minimizing collisions) and speed (latency), Mankowitz explained.

The hashing algorithm is now available in the Abseil open source library.

What will happen to 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 give researchers and practitioners a different perspective on how algorithms can be built, Mankowitz said.