Shulou(Shulou.com)11/24 Report--

A new member of the "Alpha" family, AlphaDev! Google brain DeepMind after the first effort, the new AI system will speed up the sorting algorithm 70% of the first change in the sorting library in a decade. Is the time coming for AI to create AI?

Today, a new member of the "Alpha" family is added: 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 bring such a masterpiece.

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

The C++ ranking library has changed for the first time in more than a decade. AI optimizes the world's code and reaches a new milestone.

At present, the latest research has been published on Nature.

Https://www.nature.com/ articles / s41586,023-06004-9 through reinforcement learning, AlphaDev has found a more effective algorithm, directly beyond the careful polishing of scientists and engineers for decades.

Today, the new algorithm has become part of two standard C++ coding libraries and is used by programmers around the world trillions of times a day.

Some netizens said, finally, we are now stepping into unknown territory: artificial intelligence is building artificial intelligence!

Reinforcement learning breaks the bottleneck of ten-year algorithm, like AlphaZero, AlphaFold and other predecessors, AlphaDev has also directly brought about a change in the field.

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

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

At present, the parameters of large models such as GPT-4 and Bard are growing exponentially, and the demand for computing power and other resources is increasing. Over the past 50 years, humans have been relying on chip improvements to keep pace.

But as the microchip approaches the physical limit, it is crucial to improve the code to make computing more powerful and more sustainable. In particular, the more important it is for algorithms that run trillions of code a day.

Today, in a paper published by Nature, Google DeepMind introduces the "upstart" AlphaDev of the Alpha family for the first time.

AlphaDev has discovered a faster sorting algorithm that billions of people use unwittingly every day.

They are the foundation of everything from online search results and social posts to the way computers and mobile data are processed. These algorithms are executed trillions of times a day.

Using AI to generate better algorithms will change the way we program computers and affect all aspects of our digital society.

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

Today, Google DeepMind also opens up the latest sorting algorithm in the main C++ library, which is available to everyone.

Open source address: https://reviews.llvm.org/ D118029 what is sorting? Sorting is a way to organize multiple projects in a specific order.

For example, arrange three letters in alphabetical order, five numbers from large to small, or sort a database containing millions of records.

The method of ranking has been evolving in human history. The earliest examples can be traced back to the second and third centuries, when scholars placed thousands of books in alphabetical order on the shelves of the Library of Alexandria.

After the Industrial Revolution, we invented machines that could help classify-tabulars that store information on punch cards to collect the results of the 1890 American census.

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

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

Sorting algorithms, that is, entering a series of unsorted numbers and then outputting sorted numbers, have become the cornerstone of computer science.

Today, our algorithms require decades of research and development by computer scientists and programmers.

This is because the existing algorithms are so efficient that every step of improvement is a major challenge.

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

The innovation of finding a new algorithm, AlphaDev, is that it does not improve existing algorithms, but finds faster algorithms completely from scratch.

Moreover, it went so far as to start in a place that most human beings did not think of-- computer assembly instructions.

Assembly instructions are used to create binaries. Although developers write code in high-level languages such as C++, these high-level languages must be translated into "low-level" assembly instructions in order for computers to understand them.

We typically write code in a high-level programming language such as C++, and then use a compiler to convert it into low-level CPU instructions, that is, assembly instructions. The assembler then converts assembly instructions into executable machine code Google DeepMind researchers believe that there is a lot of room for improvement at this lower level that may be difficult to find in higher-level programming languages.

At this lower level, computers are more flexible in storage and operation, so any more potential improvements will have a huge impact on speed and energy.

Figure A: a C++ algorithm that sorts at most two elements

Figure B: the corresponding assembly for the code

AlphaDev: the assembly version of AlphaZero is well known for its reinforcement learning model, which repeatedly beats world champions in games such as go, chess and general chess.

And our protagonist, AlphaDev, is based on AlphaZero.

AlphaDev works in a similar way to the previous AlphaZero, which combines computer reasoning and intuition to choose each step in a board game.

However, AlphaDev does not choose what to do next, but which instructions to add.

To train AlphaDev to discover new algorithms, DeepMind turns the sorting problem into an assembly game (Assembly Game).

In each round, AlphaDev needs to observe the algorithm it generates and the information contained in the central processing unit (CPU) and move it by adding an instruction to the algorithm.

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

Among them, the "possible instruction combination" can even be directly compared to the number of particles in the universe, or the possible combination of moves in chess (10 ^ 120 games) and go (10 ^ 700 games).

Furthermore, any wrong move may invalidate the entire algorithm.

Finally, DeepMind rewards AlphaDev for its ability to sort numbers correctly and the speed and efficiency of sorting, while AlphaDev needs to win the game by finding the right and faster program.

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

Figure B: award calculation. After each move, the generated algorithm is tested, and the agent is rewarded according to the correctness and response time of the algorithm.

Specifically, when thinking deeply (deliberation), AlphaZero ponders the possible next step at each decision point, as well as the possibility of the next step. Just like a tree diagram, push back step by step to figure out which actions are most likely to succeed.

But the problem is that if every possible branch is taken into account, it may take longer than the age of the universe. So the researchers used something like intuition to narrow it down.

At each step, the program inputs the current state into the neural network (a complex and adjustable mathematical function) to find the most appropriate behavior. At the same time, in the process of training, the neural network will be constantly updated according to the results. Sometimes they deliberately do not choose the behavior with the highest score to explore actively.

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

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

So, until the entire list is arranged, or the length limit of the program is reached, and a new program is started from scratch.

C++ runs faster and 70%AlphaDev discovers a new sorting algorithm, which brings a significant improvement to the LLVM libc++ sorting library.

For shorter sequences, the speed is increased by 70%, while for sequences with more than 250000 elements, the speed is only increased by about 1.7%.

The researchers focused on improving the sequence sorting algorithm with 3-5 short elements.

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

Improving these algorithms can improve the overall speed for the sorting of any number of items.

To make the new sorting algorithm available to everyone, the researchers reverse-engineered it and translated it into C++, one of the most commonly used coding languages for programmers.

Currently, these algorithms can now be found in the LLVM libc++ standard sorting library.

After discovering faster sorting algorithms, DeepMind tested whether AlphaDev could generalize and improve a different computer science algorithm, the hash (Hash).

Hash is a basic algorithm in computing, which is used to retrieve, store and compress data. Just as 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 raw data into a unique string (such as 1234ghfty). The computer then uses this hash value to quickly retrieve key-related data instead of searching all the data.

The results show that when applied to the range of 9 to 16 bytes of the hash function, the algorithm found by AlphaDev is 30 per cent faster than the traditional algorithm.

Now, DeepMind has also released the new hashing algorithm to 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, have discovered not only faster algorithms, but also new methods.

Its sorting algorithm contains a new sequence of instructions, and one instruction is saved each time it is applied. This could have a huge impact because these algorithms are used trillions of times a day.

The researchers call them "AlphaDev swap move" and "AlphaDev copy move".

The latest approach is reminiscent of AlphaGo's shocking "step 37".

In the 2016 man-machine war, AlphaGo played a counterintuitive move, a simple shoulder stroke, to beat legendary go player Lee se-dol.

With both strategies, AlphaDev skips one step to connect the project in a way that looks wrong but is actually a shortcut.

This shows that AlphaDev has the ability to find original solutions and challenges the way we think about how to improve computer science algorithms.

The following illustration shows the original sort3 implementation with min (A, B, C), using AlphaDev Swap Move,AlphaDev to discover that you only need min (A, B).

For example, the original implementation sorts eight elements using the larger sorting algorithm in max (B, min (A, C, D)).

AlphaDev finds that only max (B, min (A, C)) is needed to use its "swap and copy moves".

Optimize code around the world, one algorithm at a time by optimizing and introducing improved sorting and hashing algorithms used by developers around the world, 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 help optimize the entire computing ecosystem and solve other socially beneficial problems.

However, the researchers also admit that at present, AlphaDev has a very strong ability to optimize assembly instructions at low levels, but it also has limitations with the development of algorithms.

To make it more available to 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 the algorithm, 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.

Netizens commented that Jim Fan, a scientist at Nvidia, made an in-depth summary of AlphaDev:

Sorting algorithm is the basis of all key software. DeepMind's AlphaDev increases the sorting speed of small sequences (3-5 items) by 70%. Main points:

-the main RL algorithm is based on the AlphaZero that initially played go Go, Chess & Shogi. The same idea applies to search programs!

-instead of optimizing the C code, the researchers optimized the assembly code. This is a deliberate choice to go to a low level to squeeze the save of each instruction.

The assembler code is then reverse-engineered as Cellular codes and opened in LLVM.

-even if the characterization network uses Transformer, it is not a basic model. The whole process is only applicable to sorting, and other tasks, such as hashing, must be retrained.

Another important milestone has been achieved in algorithm discovery using ML!

AlphaDev is a game-changing artificial intelligence of DeepMind, which innovates the core computer science algorithms. It is reinventing the sorting method, which can increase the speed of short sequences by 70%. Even the discovery speed of hash algorithms has been improved by 30%. Reinforcement learning is reshaping the pattern of algorithms!

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

Reference:

Https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

This article comes from the official account of Wechat: Xin Zhiyuan (ID:AI_era)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.