Google DeepMind breaks the ten-year algorithm seal, and AlphaDev makes a stunning debut, subverting the human algorithm landscape!

Today, the "Alpha" family adds a new member: AlphaDev.

The foundation of the entire computing ecosystem may be subverted by new algorithms created by AI!

It didn’t take long for Google Brain and DeepMind to combine to bring such a stunning work.

AlphaDev can not only speed up sorting algorithms by 70%, but can even be as much as 3 times faster than humans on some algorithms.

For the first time in over a decade, the C sorting library has changed. AI optimizes the world's code and reaches a new milestone.

Currently, the latest research has been published in Nature.

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

Through reinforcement learning, AlphaDev discovered more efficient algorithms that directly surpassed decades of careful polishing by scientists and engineers.

The new algorithm is now part of two standard C coding libraries and is used trillions of times every day by programmers around the world.

Some netizens said that it is finally here, we are now entering unknown territory: artificial intelligence is building artificial intelligence!

Reinforcement learning breaks the ten-year algorithm bottleneck

Like predecessors such as AlphaZero and AlphaFold, AlphaDev also directly initiated changes in a field.

DeepMind computer scientist and first author of the paper Daniel Mankowitz said, "We didn't believe it at first."

"To be honest, we didn't expect it. Get better results: This is a very short program, and these types of programs have been studied for decades."

Currently, GPT-4, Bard, etc. The parameters of large models increase exponentially, and the demand for resources such as computing power continues to grow. Over the past 50 years, humans have continued to rely on chip improvements to keep up.

But as microchips approach physical limits, it’s critical to improve the code to make computing more powerful and sustained. This is especially true for algorithms that run trillions of code runs every day.

Today, Google DeepMind introduced AlphaDev, the “upstart” of the Alpha family, for the first time in a paper published in Nature.

AlphaDev discovers a faster sorting algorithm that billions of people unknowingly use every day these algorithms.

They are the basis for everything from online search results, to social posts, to how computers and phones process data. These algorithms are executed trillions of times every day.

Using AI to generate better algorithms will change the way we program computers and impact every aspect of our digital society.

According to data in the Nature paper, the algorithm created by AlphaZero can sort data three times faster than humans.

Today, Google DeepMind also open sourced the latest sorting algorithm in the main C library, making it available to everyone.

Open source address: https://reviews.llvm.org/D118029

What is sorting?

Sort is a method of organizing multiple items in a specific order.

Like arranging three letters alphabetically, arranging five numbers from largest to smallest, or sorting a database containing millions of records.

Sorting methods have evolved throughout human history. The earliest examples date back to the second and third centuries, when scholars manually arranged thousands of books in alphabetical order on the shelves of the Library of Alexandria.

After the Industrial Revolution, we invented machines that could help with classification—the tabulating machine, which stored information on punched cards, was used to collect the results of the 1890 U.S. Census.

With the rise of commercial computers in the 1950s, the earliest computer science sorting algorithms appeared.

Today, many different sorting techniques and algorithms are used in code bases around the world to organize large amounts of data online.

Sorting algorithm, that is, inputting a series of unsorted numbers and then outputting the sorted numbers

These algorithms have become the cornerstone of computer science.

Today’s algorithms require computer scientists and programmers to invest decades of research and development.

This is because the existing algorithm is so efficient that every step forward is a major challenge.

This degree of difficulty is like finding a new way to save electricity energy, or finding a more efficient mathematical method.

Looking for new algorithms

The innovative significance of AlphaDev is that it does not improve existing algorithms, but discovers faster algorithms completely from scratch.

Moreover, it actually started in a place that most humans did not think of - computer assembly instructions.

Assembly instructions are used to create binary code. Although developers use high-level languages ​​such as C when writing code, in order for the computer to understand, these high-level languages ​​must be translated into "low-level" assembly instructions.

Normally, we use high-level programming languages ​​​​such as C to write codes, and then the compiler translates them into low-level CPU instructions, also It's assembly instructions. The assembler then converts the assembly instructions into executable machine code

Researchers at Google DeepMind believe that there is a lot of room for improvement at this lower level, and These improvements may be difficult to find in higher-level programming languages.

At this lower level, the computer is more flexible in both storage and operations, so a few more potential improvements could have a huge impact on speed and energy.

Figure A: A C algorithm for sorting at most two elements

Figure B: Assembly corresponding to the code

AlphaDev: Assembly version of AlphaZero

As we all know, DeepMind’s reinforcement learning model is used in Go, International He has repeatedly defeated world champions in games such as chess and shogi.

And our protagonist this time - AlphaDev, is based on AlphaZero.

AlphaDev works similarly to its predecessor, AlphaZero, which combined computer reasoning and intuition to choose each move in the board game.

However, AlphaDev does not choose how to move next, but chooses which instructions to add.

In order to train AlphaDev to discover new algorithms, DeepMind transformed 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 make a move by adding an instruction to the algorithm.

And this assembly game is very difficult because AlphaDev must efficiently search a large number of possible instruction combinations to find an algorithm that can be sorted and faster than the current best algorithm.

The "possible command combinations" can even be directly compared to the number of particles in the universe, or the possible combinations of chess (10^120 games) and Go (10^700 games). combination of moves.

Furthermore, any wrong move may invalidate the entire algorithm.

In the end, DeepMind rewards AlphaDev based on its ability to correctly sort numbers and how quickly and efficiently it completes the sorting, and AlphaDev needs to win the game by discovering a correct and faster program.

Figure A: Assembly game. Player AlphaDev takes the system state st as input and makes a move by selecting an assembly instruction to add to the already generated algorithm.

Figure B: Reward calculation. After each move, the resulting algorithm is tested and the agent is rewarded based on its correctness and response time.

Specifically, when conducting in-depth thinking (deliberation), AlphaZero will consider the next possible action at each decision point, as well as the next possible next step. sex. Like a tree diagram, work backwards step by step to figure out which actions are most likely to succeed.

But the problem is that if every possible branch of the situation is considered, the time required may be longer than the age of the universe. So researchers use something like intuition to narrow it down.

At each step, the program feeds the current state into a neural network (a complex, adjustable mathematical function) to find the most appropriate behavior. At the same time, during the training process, the neural network will continue to be updated based on the results. Sometimes the behavior with the highest rating is deliberately not selected for active exploration.

There are four actions that AlphaDev can take, including comparing different values, moving a value to another location, or jumping to a different part of the program.

After each step, try to sort a set of lists and get rewarded based on the number of values ​​in the correctly sorted list.

So on, so on, until the entire list is sorted, or the program length limit is reached, and a new program starts from scratch.

C The running speed is increased by 70%

AlphaDev discovered a new sorting algorithm and brought significant improvements to the LLVM libc sorting library.

For shorter sequences, the speedup is 70%, while for sequences over 250,000 elements, the speedup is only about 1.7%.

Researchers focus on improving sequence sorting algorithms with shorter 3-5 elements.

These algorithms are among the most widely used because they are often called multiple times as part of a larger sorting function.

Improvements in these algorithms can improve overall speed for sorting any number of items.

In order to make the new sorting algorithm available to everyone, the researchers also reverse-engineered it and translated it into C, a coding language most commonly used by "programmers".

Currently, these algorithms are now available in the LLVM libc standard sorting library.

Hash function efficiency improved by 30%

After discovering a faster sorting algorithm, DeepMind tested whether AlphaDev could generalize and improve different Computer science algorithm - Hash.

Hashing is a fundamental algorithm in computing and is used to retrieve, store, and compress data. Just like librarians use a classification system to find specific books, hashing algorithms help users know what they are looking for and exactly where.

These algorithms hash a specific key (such as the user name "Jane Doe"), that is, convert the original data into a unique string (such as 1234ghfty). The computer then uses this hash value to quickly retrieve the data associated with the key, rather than searching through all the data.

The results show that the algorithm discovered by AlphaDev is 30% faster than traditional algorithms when applied to the 9 to 16 byte range of the hash function.

Now, DeepMind has also released the new hashing algorithm into the open source Abseil library. It is understood that this algorithm is expected to be used trillions of times every day.

Two new strategies: “swap move” and “copy move”

AlphaDev not only discovered a faster algorithm; New methods.

Its sorting algorithm consists of a new sequence of instructions, one of which is saved each time it is applied. This could have a huge impact, as these algorithms are used trillions of times every day.

Researchers call it "AlphaDev swap move" and "AlphaDev copy move".

The latest method is reminiscent of AlphaGo’s shocking “Step 37”.

In the 2016 man-machine war, AlphaGo played a move that went against human intuition, a simple shoulder charge, and defeated the legendary Go player Lee Sedol.

With both strategies, AlphaDev skips a step and connects projects in a way that looks wrong but is actually a shortcut.

This demonstrates AlphaDev’s ability to discover original solutions and challenges the way we think about how to improve computer science algorithms.

As shown in the figure below, the original sort3 implementation has min(A, B, C). Using AlphaDev Swap Move, AlphaDev found that you only need min(A, B).

For another example, the original implementation uses the larger sorting algorithm in max(B, min(A,C, D)) to sort 8 elements Sort.

AlphaDev found that using its "swap and copy moves" only requires max(B, min(A, C)).

Optimizing the world’s code, one algorithm at a time

By optimizing and rolling out for use by developers around the world With improved sorting and hashing algorithms, AlphaDev has demonstrated its ability to generalize and discover world-class new algorithms.

Google DeepMind believes that AlphaDev is a step towards developing AGI tools that can help optimize the entire computing ecosystem and solve other problems that benefit society.

However, researchers also admit that AlphaDev is currently very capable of optimizing low-level assembly instructions, but there are also limitations as the algorithm develops.

In order to make it more usable for developers, AlphaDev's ability to optimize algorithms in high-level languages ​​(such as C) is being explored.

AlphaDev's new discoveries, such as "AlphaDev swap move" and "AlphaDev copy move", not only show that it can improve algorithms, but also find new solutions.

The researchers hope that these findings will inspire researchers and developers to create technologies and methods to further optimize the underlying algorithms to create a stronger and more sustainable computing ecosystem.

Hot comments from netizens

NVIDIA scientist Jim Fan made an in-depth summary of AlphaDev:

The sorting algorithm is the key to everything The basis of software. DeepMind's AlphaDev speeds up sorting of small sequences (3-5 items) by 70%. Key points:

- The main RL algorithm is based on AlphaZero, which originally played Go, Chess & Shogi. The same idea applies to search programs!

- The researchers did not optimize the C code, but the assembly code. This is a deliberate choice to go low-level and squeeze every instruction saved.

- The assembly code was then reverse-engineered into C and open sourced in LLVM.

- Even if the representation network uses Transformer, it is not a basic model. The entire process only works for sorting, and must be retrained for other tasks such as hashing.

Another major milestone achieved in algorithm discovery using ML!

AlphaDev is a game-changing artificial intelligence from DeepMind that innovates core computer science algorithms. It is reimagining sequencing methods to make short sequences 70% faster. Even the discovery speed of hashing algorithms is increased by 30%. Reinforcement learning is reshaping the algorithm landscape!

Some netizens said that while we are excited about language models, we should not forget the success stories of other deep learning algorithms: AlphaZero, AlphaFold , and now AlphaDev.

The above is the detailed content of Google DeepMind breaks the ten-year algorithm seal, and AlphaDev makes a stunning debut, subverting the human algorithm landscape!. For more information, please follow other related articles on the PHP Chinese website!