DeepMind announces AI `` AlphaDev '' that improves algorithms using deep reinforcement learning, and has already succeeded in speeding up sort algorithms and hash functions
Google DeepMind, which is famous as the developer of AlphaGo, has announced AI `` AlphaDev '' that applies deep reinforcement learning to improve various computing algorithms. At the same time, a paper has been published in Nature that speeds up sorting algorithms using AlphaDev.
AlphaDev discovers faster sorting algorithms
Faster sorting algorithms discovered using deep reinforcement learning |
https://doi.org/10.1038/s41586-023-06004-9
A sorting algorithm is an algorithm that rearranges data in an orderly manner. It's used in every part of a typical app, from ranking search results to social media posts, and is run trillions of times every day around the world. Because it is such an important underlying algorithm, it has been continuously improved over the decades by researchers all over the world, and it was already the most efficient implementation ever.
However, human improvement activities are mostly done at the C++ code level. Code written in C++ is compiled to assembly language before the code is actually executed, and then converted to machine language by an assembler. DeepMind's research team thought that at this 'assembly language' level, improvements that could not be found from C ++ code could be found.
AlphaDev is an AI based on AlphaZero, and he said that he was able to improve the algorithm by training sorting as a 'assembly game' for one person. AlphaZero is explained in the following article.
The image diagram of 'assembly game' is as follows. At each turn, AlphaDev checks the information stored in the CPU and the generated algorithms and adds new instructions to the algorithms. When the construction of the algorithm is completed, the algorithm is executed, the test is performed, the answer is checked, and the score is calculated based on whether the answer was correct and the time until the correct answer. If you can find a fast program that can give the correct answer, you win.
By using this method, AlphaDev was able to speed up the sorting implementation of the standard library `` libc ++ '' used in the open source compiler platform `` LLVM ''. It is said that sorting of 3 to 5 elements is up to 70% faster, and even large-scale sorting exceeding 250,000 elements can be speeded up by about 1.7%.
Taking the sorting of three elements as an example, AlphaDev was able to reduce the number of instructions by one without overlooking that the size of the two inputs may have been fixed in advance in the previous process.
Also, in the past, depending on the number of elements, as shown on the left of the figure below, it was divided into 'processing for 4 elements', 'processing for 3 elements', and 'processing for 2 elements'. In the case of more than 3 elements, sorting is performed once for 3 elements, and if there are 4 elements, simple processing is added later to greatly improve the processing speed.
Sorting algorithms developed by AlphaDev have been implemented in LLVM libc++ and are already being used by millions of developers.
AlphaDev has succeeded not only in sorting algorithms but also in speeding up hash functions. As a result of focusing on processing for the data structure where the hash function is most used, it became possible to calculate the hash 30% faster with an input of 9 to 16 bytes. This improved hash function is said to have been introduced in the Abseil library .
Related Posts:
in Software, Posted by log1d_ts