DeepMind launches a shocking sorting algorithm, and the C++ library is busy updating!

Click to participate in the 51CTO website content questionnaire

Compiled | Wang Ruiping, Yan Zheng

AlphaGo has another "little brother" joining!

Google DeepMind "rolled" the Alpha series into sorting algorithms and launched AlphaDev.

It is like a "development secret method". By using reinforcement learning AI to discover sorting algorithms and hashing algorithms, it forcibly speeds up algorithms designed by human programmers by about 70% and 30% respectively.

Once the research results were released, they instantly ignited the software circle! Suddenly, the running speed of millions of software around the world soared, directly surpassing the achievements of scientists and engineers for decades, and the LLVM standard C library that had not been updated in ten years was updated.

(Source: Nature)

This is also a disruptive technology launched after the merger of Google’s two AI departments. The paper was published in Nature under the title "Faster sorting algorithms discovered using deep reinforcement learning". The first author of the paper is Daniel Mankowitz, a computer scientist at DeepMind.

1. Evolution: The origin of the sorting algorithm

Sorting is a method of organizing many items in a specific order, for example, three letters in alphabetical order, from largest to smallest Sequence five numbers or sort a database containing millions of records.

The ordering method can be traced back to the second to third centuries and is still evolving. Initially, scholars manually sorted the thousands of books on the shelves of the Library of Alexandria into alphabetical order.

After the Industrial Revolution, self-sorting machines—tabulating machines that stored information on punched cards—were invented to collect the results of the 1890 U.S. Census.

In the 1950s, commercial computers began to rise, and sorting algorithms were immediately produced. Enter some unsorted numbers into a sorting algorithm and it will produce a sorted sequence of numbers.

Currently, many different sorting techniques and algorithms are still being used in code bases everywhere to process massive amounts of data.​​

#After decades of research and development, the efficiency of these sorting algorithms has continued to improve, and they have been recognized by computer scientists and programmers. However, significant challenges remain for its further improvement.

2. The highlight: How to use AlphaDev to generate a new sorting algorithm?

The researchers originally used AlphaDev to generate new algorithms with the goal of completing a given task efficiently.

AlphaDev builds a completely new algorithm and is not developed based on previous algorithms, so it can be regarded as original. In the process, it applies an intermediate language of assembly code. AlphaDev makes it easier to create efficient algorithms because the language is closer to computer binary instructions.

Specifically, AlphaDev generates an instruction each time, and then tests whether its output is correct. It also sets requirements in the model to generate the shortest algorithm.

When asked to redesign the sorting algorithm, AlphaDev randomly generated a new sorting algorithm that was 70% faster than the existing algorithm and could sort five data at the same time. It was also 1.7% faster than the best algorithm when sorting 250,000 data.

This innovation will have a huge impact on global algorithms, as sorting algorithms are widely used in a variety of common software. DeepMind has open-sourced them and integrated them into the Libc standard library.

According to DeepMind researchers: “Due to the large number of instruction combinations, the seemingly simple research process is extremely difficult.”

3. Origin: Finding the best algorithm while playing games

Furthermore, AlphaDev is a more advanced model designed based on the structure of AlphaZero. AlphaZero was previously DeepMind’s reinforcement learning model, which defeated world champions in Go, chess and other chess games.

Through this experiment, the new model AlphaDev exerts its unique advantages in moving from playing games to solving scientific problems, and from experimental simulations to real-world applications.

The researchers simulated sorting as a single-player "assembly game" to train AlphaDev to discover new algorithms. During each game turn, AlphaDev observes the generated algorithm and the information contained in the CPU, and then selects an instruction to add to the algorithm to make each move.

The paper mentions that assembly games are very difficult because AlphaDev must be able to efficiently search through a large number of possible instruction combinations to obtain an algorithm that can be sorted.

The number of instruction combinations is similar to the number of particles in the universe or the number of possible combinations of moves in chess (10120 games) and Go (10700 games). Each wrong move will invalidate the entire algorithm.

The model then outputs an algorithm and compares it to the expected output, rewarding the agent based on the algorithm's correctness and latency.

When building an algorithm, each time an instruction is input, AlphaDev checks for correctness by comparing the output algorithm with the expected results (for a sorting algorithm, this means that after inputting unordered numbers, it can output correctly sorted numbers).

The model rewards AlphaDev for its correct ordering of numbers and its efficiency. In the end AlphaDev won the competition by discovering a more accurate and faster program.

4. Algorithm innovation: swap move and copy move instruction sequences

AlphaDev not only generates a faster algorithm, but also innovates two instruction sequences.

Specifically, the sorting algorithm it generates includes two new instruction sequences: swap move and copy move, and one instruction will be saved each time it is used. The researchers call it "AlphaDev's swap move and copy move."

This novel approach is reminiscent of AlphaGo's "Move 37" - a "counter-intuitive" chess play that shocked onlookers and created a chess legend Hand failure.

By swapping the move and copy move instruction sequences, AlphaDev skips a step, completing the goal in a way that looks like a mistake but is actually a shortcut. This means that AlphaDev has the ability to discover initial solutions and try to improve computer science algorithms.

5. Test: Promote and improve hashing algorithms

After researchers discovered a faster sorting algorithm, they tried to apply it to another computer science algorithm-the hashing algorithm. promotion and improvement.

Hashing algorithm is a basic algorithm in computing and is used to retrieve, store and compress data. Just like librarians use a classification system to locate a certain book, hashing algorithms help users know what they are looking for and where to find it.

These algorithms are able to take the data for a specific key (for example, the username "Jane Doe") and hash it - converting the raw data into a unique string (for example, 1234ghty).

The computer uses this hash to quickly retrieve data related to the key, rather than searching through all the data.

Researchers 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 the 9-16 byte range of the hash function, AlphaDev produced an algorithm that was 30% faster.

Earlier this year, the new hashing algorithm generated by AlphaDev was released into the open source Abseil library, making it available to millions of developers around the world. It is now estimated to be used by tens of thousands every day. billion times.

6. Gathering momentum: taking the first step in developing AGI

By optimizing the "sorting and hashing algorithm", AlphaDev has demonstrated the ability to generate different practical new algorithms.

This is also AlphaDev’s first step towards developing general artificial intelligence (AGI) tools. Similar AI tools can also help optimize the entire computing ecosystem and solve other problems that benefit society.

Although the optimization algorithm in the low-level assembly instruction space is very powerful, it also has limitations. Currently, the team is studying AlphaDev's ability to optimize algorithms in high-level languages ​​(such as C), which will be more beneficial to developers.

In short, it is hoped that these new discoveries will inspire developers to create new technologies and methods, further optimize basic algorithms, and create a stronger and more sustainable computing ecosystem.

7. Open source: Milestone breakthrough in AI optimization code

Previously, sorting algorithms were used trillions of times every day. With the growth of computing needs, people have higher and higher performance requirements for algorithms. Although human engineers have discovered different sorting algorithms, after decades of optimization, it is difficult to make breakthroughs and cannot meet the growing demand.

Now, AlphaDev has discovered a faster sorting algorithm for sorting data.

The new ranking algorithm can be used to rank online search results and social posts, as well as to process data on computers and mobile phones.

It is worth celebrating that the new sorting algorithm has been open sourced in the main C library. It is currently used by millions of developers and companies around the world for cloud computing, online shopping, supply chain management, and more.

In short, using artificial intelligence tools to optimize algorithms will completely change traditional programming methods. This is the first time in more than ten years that the sorting library has been changed, and the first time that algorithms designed by reinforcement learning models have been added to the sorting library. Therefore, it has become a milestone breakthrough in using artificial intelligence to optimize code.

8. Users: Maybe it’s just a gimmick

Users have mixed opinions about the research results, with most of the voices praising on Twitter:

Learn the basics Sequencing tasks is one of the skills programmers master early on, and this skill increases speed by 70%. It’s exciting to see leveraging AI to deliver significant acceleration in the algorithms and libraries we all rely on."

"Soon, ordinary people will be able to become advanced programmers."

" Interesting method, start optimizing from the assembly level!

However, some programmers think this is just a gimmick, and DeepMind exaggerates the function of the algorithm.

First of all, from the perspective of efficiency, It only counts the delay of the algorithm, rather than actually changing the time complexity.

Moreover, it does not really change the sorting, which is common in various other code libraries.

Reference Information:

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

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

3.https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools

4 .https://twitter.com/demishassabis

The above is the detailed content of DeepMind launches a shocking sorting algorithm, and the C++ library is busy updating!. For more information, please follow other related articles on the PHP Chinese website!