New Algorithms Transform the Foundation of Computing
The digital world has increased the demand for computing and energy usage. For the past 50 years, we’ve relied on hardware improvements to keep pace. But as microchips approach their physical limits, it’s important to improve the code that runs on them to make computing more powerful and sustainable. This is especially important for algorithms that make up code that runs trillions of times a day.
In a paper published today, Natureintroduces AlphaDev, an artificial intelligence (AI) system that uses reinforcement learning to discover enhanced computer science algorithms. This goes beyond what has been honed over decades by scientists and engineers.
AlphaDev found a faster algorithm for sorting data, a way to sort data. Billions of people use these algorithms every day without realizing it. They underpin everything from ranking online search results and social posts to how data is processed on computers and mobile phones. Using AI to generate better algorithms will transform the way we program computers and impact every aspect of our increasingly digital society.
By open sourcing our new sorting algorithm in our main C++ library, millions of developers and companies around the world are working on AI applications in a variety of industries, from cloud computing and online shopping to supply chain management. uses this algorithm in This is his first change to this part of the sorting library in over a decade, and the first time an algorithm designed through reinforcement learning has been added to the library. We see this as an important stepping stone to using AI to optimize algorithms one by one.
What is sorting?
Sorting is a way of arranging a number of items in a particular order. Examples include ordering three letters alphabetically, ordering five numbers from largest to smallest, or ordering a database of millions of records.
This method has evolved throughout history. One of the earliest examples dates from the 2nd to his 3rd century, when scholars manually alphabetized the thousands of books on the shelves of the Great Library of Alexandria. Following the industrial revolution, machines were invented to help with sorting. A tallying machine stored information on punch cards used to collect the results of the 1890 Census in the United States.
And the rise of commercial computers in the 1950s saw the development of the earliest computer science algorithms for sorting. Currently, there are various sorting techniques and algorithms used by codebases around the world to organize large amounts of data online.
Modern algorithms have taken decades of research for computer scientists and programmers to develop. They are so efficient that making further improvements is a big challenge, akin to trying to find new ways to save power or more efficient mathematical approaches. These algorithms are also fundamental to computer science and are taught in introductory computer science classes at universities.
Exploring new algorithms
By starting from scratch rather than improving existing algorithms, AlphaDev found faster algorithms and began looking where most humans don’t look: computer assembly instructions.
Assembly instructions are used to create binary code for computers to operate. Developers write in coding languages such as C++, known as high-level languages, which must be translated into “low-level” assembly instructions for computers to understand.
We believe there are many improvements at this low level that are hard to find in high-level coding languages. At this level, computer storage and operations are more flexible. This means there is the potential for significant improvements that can have a significant impact on speed and energy usage.
.png)
Figure B: Corresponding assembly representation of the code.
Finding the Best Algorithms in Games
AlphaDev is based on AlphaZero, a reinforcement learning model that has beaten world champions in games such as Go, Chess, and Shogi. We use AlphaDev to show how this model can be transferred from games to scientific challenges and from simulations to real-world applications.
To train AlphaDev to discover new algorithms, we turned sorting into a single-player “construction game”. At each turn, AlphaDev observes the algorithms it generates and the information contained in the central processing unit (CPU). Then select the instructions you want to add to your algorithm and run your hand.
Assembly games are incredibly difficult because AlphaDev has to efficiently search through a huge number of instruction combinations to find an algorithm that can be permuted and is faster than the current best one. . The number of possible combinations of instructions is analogous to the number of particles in the universe, or the number of possible hand combinations in a game of chess (10).120 games) and Go (10700 game). And just one wrong move can invalidate the entire algorithm.
.png)
Figure B: Compensation calculation. After each move, a test input sequence is fed to the generated algorithm. For sort3 this corresponds to all combinations of sequences of three elements. The algorithm then produces an output that is compared to the expected output of the sorted sequence in case of sorting. Agents are rewarded based on algorithm accuracy and latency.
Once the algorithm is built, one instruction at a time, AlphaDev compares the output of the algorithm with the expected result to check if the algorithm is correct. For sorting algorithms, this means that unordered numbers are input and correctly sorted numbers are output. AlphaDev is rewarded both for sorting numbers correctly and for doing it quickly and efficiently. AlphaDev wins the game by finding programs that are accurate and fast.
Finding a Faster Sorting Algorithm
AlphaDev has discovered a new sorting algorithm that improves the LLVM libc++ sorting library. This gave ~70% speedup for short sequences and about 1.7% speedup for sequences over 250,000 elements.
We focused on improving the sorting algorithm for short sequences of 3-5 elements. These algorithms are the most widely used because they are often called many times as part of a large sorting function. Improving these algorithms will improve the overall speed of sorting any number of items.
To make the new sorting algorithm easier to use, we reverse-engineered it and converted it to C++, one of the most popular coding languages used by developers. These algorithms are now available in the LLVM libc++ standard sorting library and are used by millions of developers and companies worldwide.
find a novel approach
AlphaDev not only found a faster algorithm, but also a new approach. Its reordering algorithm contains a new instruction sequence that saves one instruction each time it is applied. These algorithms are used trillions of times a day, so this can have a big impact.
We call these “AlphaDev Swap and Copy Movements”. This novel approach stuns onlookers and is reminiscent of his AlphaGo “hand 37”, a counterintuitive play that led to the defeat of the legendary Go player. With swap and copy moves, AlphaDev skips the step of connecting items. This looks like a mistake, but it’s actually a shortcut. It demonstrates his AlphaDev’s ability to discover unique solutions and challenges our thinking about how computer science can improve his algorithms.
right: AlphaDev Swap Move – AlphaDev discovers that only min(A,B) is required.
right: AlphaDev found that only max(B, min(A, C)) is needed when using copy-move.
From sorting to hashing in data structures
After discovering a faster sorting algorithm, AlphaDev tested whether it could generalize and improve another computer science algorithm, hashing.
Hashing is a fundamental algorithm in computing used to retrieve, store, and compress data. Much like librarians use classification systems to find specific books, hashing algorithms help users know what they’re looking for and exactly where. These algorithms take data with a specific key (e.g. username “Jane Doe”) and hash it. This process converts the raw data into a unique string (eg 1234ghfty). This hash is used by the computer to quickly retrieve the data associated with the key instead of searching through all the data.
To find a faster algorithm, we applied AlphaDev to one of the most commonly used algorithms for hashing data structures. And applying this to the 9-16 byte range of the hash function, the algorithm AlphaDev found was 30% faster.
This year, AlphaDev’s new hashing algorithm was released into the open-source Abseil library, making it available to millions of developers worldwide and now estimated to be used trillions of times a day. increase.
Optimize the world’s code, one algorithm at a time
By optimizing and releasing improved sorting and hashing algorithms used by developers around the world, AlphaDev has demonstrated its ability to generalize and discover new algorithms with real-world impact. We see AlphaDev as a step towards developing general-purpose AI tools that help optimize the entire computing ecosystem and solve other problems that benefit society.
Optimizations in the area of low-level assembly instructions are very powerful, but limit themselves as algorithms grow. We are currently exploring AlphaDev’s ability to optimize algorithms directly in high-level languages such as C++, which is more convenient for developers.
AlphaDev’s findings, such as swap and copy behavior, show that not only can algorithms be improved, but new solutions can be found. We hope these findings will inspire researchers and developers alike to further optimize underlying algorithms and create techniques and approaches that can build a stronger and more sustainable computing ecosystem. I’m here.
Learn more about optimizing your computing ecosystem here.
