AI rewrites the sorting algorithm, 70% faster: DeepMind AlphaDev innovates the computing foundation, calling trillions of library updates every day

"By swapping and copy-moving, AlphaDev skips a step, connecting items in a way that seems wrong, but is actually a shortcut." This unprecedented and counterintuitive thought cannot help but It reminds me of the spring of 2016.

Seven years ago, AlphaGo defeated the human world champion at Go, and now AI has taught us another lesson in programming.

Early this morning, two sentences from Google DeepMind CEO Hassabis detonated the computer field: "AlphaDev has discovered a new and faster sorting algorithm, and we have open sourced it into the main C library for developers to use. This is just the beginning of AI's progress in improving code efficiency."

This time , Google DeepMind's new reinforcement learning system AlphaDev discovered a hash algorithm that is faster than ever before, which is a basic algorithm in the field of computer science. The results of AI have now been incorporated into the LLVM standard C library Abseil and open source.

How important is this result? "We estimate that the sorting and hashing algorithms it discovered are called trillions of times every day around the world," said Daniel J. Mankowitz, one of AlphaDev's lead authors and a research scientist at Google DeepMind.

AI seems to speed up the world from an algorithmic level.

These algorithms improve the LLVM libc sorting library. For shorter sequences, the sorting library is 70% faster. For sequences of more than 250,000 elements, the speed is also 70%. It can be increased by about 1.7%. Google DeepMind says this is the first change to this part of the sequencing library in more than a decade. It seems that now AI can not only help people write code, but also help us write better code.

In the latest blog, the authors of the new system introduced AlphaDev in detail.

New algorithms will change the foundation of computing

Digital societies drive growing demands for computing and energy. Over the past fifty years, the digital age has relied on improvements in hardware to keep up with demand. But as microchips approach their physical limits, improving the code that runs on them becomes critical. This is especially important for algorithms contained in code that are run trillions of times every day.

This research by Google DeepMind was born out of this. The related paper has been published in "Nature". AlphaDev is an AI system that uses reinforcement learning to discover algorithms, even beyond The result of decades of work by scientists and engineers.

Paper address: https://www.nature.com/articles /s41586-023-06004-9

Overall, AlphaDev discovered a faster sorting algorithm. Although billions of people use these algorithms every day, no one realizes that there is room for optimization. Sorting algorithms are used in a wide range of applications, from online search results, social post sorting, to various data processing on computers and mobile phones, all of which are inseparable from sorting algorithms. Using AI to generate better algorithms will change the way humans program computers and will have a significant impact on an increasingly digital society.

By open-sourcing the new sorting algorithm in a major C library, millions of developers and companies around the world can now leverage artificial intelligence in industries as diverse as cloud computing, online shopping, and supply chain management. Use it in smart applications. This is the first change to the ranking library in more than a decade, and the first time algorithms designed with reinforcement learning have been added to the library. Consider this an important milestone in using artificial intelligence to progressively optimize the world's code.

About sorting

The sorting algorithm is a method of arranging certain tasks in a specific order. For example, sort three letters alphabetically, arrange five numbers from largest to smallest, or sort a database of millions of records.

This algorithm has been around for a long time and has evolved well. One of the earliest examples of ordering dates back to the 2nd and 3rd centuries AD, when scholars alphabetized thousands of books by hand on the shelves of the Library of Alexandria. With the advent of the Industrial Revolution came machines that could help people sort, with tabulating machines storing information using punched cards that were used to collect the results of the U.S. 1890 census.

With the rise of commercial computers in the 1950s, the earliest computer science algorithms for sorting began to develop. Today, there are many different sorting techniques and algorithms used in code bases around the world to process massive amounts of online data.

Input a series of unsorted numbers into the algorithm and output sorted numbers.

After decades of research by computer scientists and programmers, the current sorting algorithm is already so efficient that it is difficult to achieve further improvements. This is somewhat similar to Trying to find a new way to save power or be more efficient with mathematics, and these algorithms are the cornerstone of computer science.

Explore new algorithms: assembly instructions

AlphaDev explores faster algorithms from scratch instead of based on existing algorithms. In addition, AlphaDev can also be used Looking for an area that most people don't get involved in: computer assembly instructions.

Assembly instructions can be used to create binary code that the computer executes. Developers write code in a high-level language such as C, but must translate it into "low-level" assembly instructions that the computer understands.

Google DeepMind believes there is much room for improvement at this level that may be difficult to detect in higher-level programming languages. At this level, computers are more flexible in their storage and operations, which means there are more potential possibilities for improvements that could have a greater impact on speed and energy use.

Code is usually written in a high-level programming language such as C. The compiler then converts this into low-level CPU instructions, called assembly instructions. The assembler converts assembly instructions into executable machine code so that the computer can run.

Figure A: Example of C algorithm that can sort up to two elements ; Figure B: Corresponding assembly representation.

Using AlphaGo’s method to find the best algorithm

AlphaDev is based on a previous achievement of Google DeepMind: defeating games such as Go, chess and chess The world champion reinforcement learning model AlphaZero. And AlphaDev shows how this model transfers from games to scientific challenges, and from simulations to real-world applications.

To train AlphaDev to discover new algorithms, the team turned sorting into a single-player "assembly game." At each turn, AlphaDev observes the algorithm it produces and the information contained in the CPU, and then makes its next move by selecting an instruction to add to the algorithm.

Assembly games are very difficult because AlphaDev must search efficiently through a large number of possible instruction combinations to find an algorithm that can be sorted and faster than the current best algorithm. The number of possible combinations of instructions is similar to the number of particles in the universe, or the number of possible combinations of moves in chess (10^120 games) and Go (10^700 games), and one wrong move can bring down the entire algorithm.

Figure A: Assembly game. The player AlphaDev receives as input the state of system st and plays chess by selecting an assembly instruction to add to the currently generated algorithm. Figure B: Reward calculation. After each move, the resulting algorithm is fed a test input sequence—for sort3, this corresponds to all combinations of three element sequences. The algorithm then produces an output that is compared to the expected output of the sorted sequence given the sorting situation. Agents are rewarded based on algorithm correctness and latency.

#When building an algorithm, one instruction at a time, AlphaDev checks that the algorithm's output is correct by comparing it to the expected result. For a sorting algorithm, this means that unordered numbers go in and correctly sorted numbers come out. The team rewards AlphaDev for correctly sorting numbers as well as the speed and efficiency of the sorting, and AlphaDev then wins the game by discovering the correct, faster program.

It discovered faster sorting algorithms

AlphaDev discovered new sorting algorithms that resulted in improvements to the LLVM libc sorting library: The sequencing library is 70% faster for shorter sequences and about 1.7% faster for sequences over 250,000 elements.

# Among them, the Google DeepMind team is more focused on improving the short sequence sorting algorithm of three to five elements. These algorithms are among the most widely used because they are often called multiple times as part of a larger sorting function, and improving these algorithms can increase the overall speed of sorting any number of items.

#To make the new sorting algorithms more useful to people, the team reverse-engineered the algorithms and translated them into C, which is the most commonly used by developers. One of the popular programming languages.

Currently, these algorithms are provided in the LLVM libc standard sorting library (https://reviews.llvm.org/D118029) and are used by millions of people around the world Used by developers and companies.

"Exchange and copy actions", the hand of God reappears?

In fact, AlphaDev not only discovered faster algorithms, but also discovered new methods. Its sorting algorithm consists of a new sequence of instructions that saves an instruction every time it is applied - which obviously has a huge impact, since these algorithms are used trillions of times every day. They call these "AlphaDev swap and copy actions."

This novel method is reminiscent of AlphaGo's "Step 37" - at that time, this counter-intuitive method stunned onlookers and led to the legendary Lee Sedol The Go player was defeated. By swapping and copying actions, AlphaDev skips a step, connecting items in a way that looks like a mistake but is actually a shortcut. This demonstrates AlphaDev’s ability to uncover original solutions and challenge the way humans think about how to improve computer science algorithms.

Left picture: min (A,B,C) original sort3 implementation; right picture: AlphaDev Swapping moves - AlphaDev discovered that you only need min (A,B).

Left: Original implementation using max(B,min(A,C,D)) in a larger sorting algorithm for sorting eight elements; Right: AlphaDev discovery , when using its copy action, only max(B, min(A, C)) is required.

Scaling Ability Test: From "Sort" to "Hash"

After discovering a faster sorting algorithm, the team tested whether AlphaDev could generalize and improving a different computer science algorithm: hashing.

Hashing is a basic algorithm used in computing to retrieve, store, and compress data. Just like a librarian who uses a classification system to locate a particular book, hashing algorithms help users know what they are looking for and where to find it. These algorithms take data for a specific key (e.g. username “Jane Doe”) and hashes it – a process that converts the raw data into a unique string (e.g. 1234ghfty). The computer uses this hash to quickly retrieve data related to the key instead of searching through all the data.

The team applied AlphaDev to one of the most commonly used hashing algorithms in data structures in an attempt to discover a faster algorithm. When applied to hash functions in the 9-16 byte range, AlphaDev found a 30% improvement in algorithm speed.

This year, AlphaDev’s new hashing algorithm has been released into the open source Abseil library, making it available to millions of developers around the world. It is now used probably every day Used trillions of times.

Open source address: https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e

Conclusion

Google DeepMind By optimizing and launching improved sorting and hashing algorithms for use by developers around the world, AlphaDev demonstrates its ability to generalize and discover new algorithms with real-world impact. AlphaDev can be seen as a step toward developing general-purpose AI tools that can help optimize the entire computing ecosystem and solve other problems for the benefit of society.

Although it is very powerful to optimize in the low-level assembly instruction space, AlphaDev still has limitations as the algorithm grows, and the team is currently exploring its direct optimization in high-level languages ​​​​such as C. The ability to optimize algorithms, which is more useful for developers.

AlphaDev's discoveries, such as swap and copy actions, show not only that it can improve algorithms but also find new solutions. These findings may inspire researchers and developers to create technologies and methods that can further optimize underlying algorithms to create a more robust and sustainable computing ecosystem.

The above is the detailed content of AI rewrites the sorting algorithm, 70% faster: DeepMind AlphaDev innovates the computing foundation, calling trillions of library updates every day. For more information, please follow other related articles on the PHP Chinese website!