impact
Published June 7, 2023 Author
Daniel J. Mankowitz and Andrea Michi
New algorithms transform the foundation of computing
Digital society has increased the demand for computing and energy use. For the past 50 years, we’ve relied on hardware improvements to keep pace. But as microchips approach their physical limits, it is important to improve the code running on them to make computing more powerful and sustainable. This is especially important for algorithms that make up code that executes trillions of times a day.
A paper published today in Nature describes AlphaDev, an artificial intelligence (AI) system that uses reinforcement learning to discover enhanced computer science algorithms beyond what scientists and engineers have spent decades honing. Introducing.
AlphaDev has discovered 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 the rankings of online search results and social posts to the way data is processed on computers and mobile phones. Using AI to generate better algorithms will transform the way computers are programmed and impact every aspect of our increasingly digital society.
By open sourcing new sorting algorithms in our main C++ library, millions of developers and businesses around the world can build AI applications in a variety of industries, from cloud computing and online shopping to supply chain management. I am using this algorithm. This is the first change to this part of the sorting library in more than a decade, and the first time that algorithms designed through reinforcement learning have been added to the library. We see this as an important stepping stone to using AI to optimize our algorithms one step at a time.
What is sorting?
Sorting is a way to organize a large number of items in a specific order. Examples include alphabetizing three letters, ordering five numbers from largest to smallest, and ordering a database of millions of records.
This method has evolved throughout history. One of the earliest examples dates back to the 2nd and 3rd centuries, 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 classification. Tally machines stored information on punch cards that were 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 some of the earliest computer science algorithms for sorting. There are currently a variety of sorting techniques and algorithms used in codebases around the world to organize large amounts of data online.
Diagram of how the sorting algorithm works. An unsorted set of numbers is input to the algorithm, and a sorted number is output.
Modern algorithms took decades of research by computer scientists and programmers to develop. They are so efficient that making further improvements is a big challenge, similar to trying to find new ways to save power or more efficient mathematical approaches. These algorithms are also the foundation of computer science and are taught in introductory computer science classes at universities.
Exploring new algorithms
Rather than improving on existing algorithms, AlphaDev discovered faster algorithms by starting from scratch and began looking where most humans don’t look: computer assembly instructions.
Assembly instructions are used to create the 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 that many improvements exist at this lower level that are difficult to discover in higher-level coding languages. At this level, computer storage and operation are more flexible. This means there is potential for significant improvements that can have a significant impact on speed and energy usage.
Code is typically written in a high-level programming language such as C++. This is translated using a compiler into low-level CPU instructions called assembly instructions. The assembler then converts the assembly instructions into executable machine code that the computer can run.
Figure A: Example of a C++ algorithm that sorts up to two elements.
Figure B: Corresponding assembly representation of the code.
Find the best algorithm in your game
AlphaDev is based on AlphaZero, a reinforcement learning model that has defeated world champions in games such as Go, Chess, and Shogi. Using AlphaDev, we demonstrate how this model can move from games to scientific tasks, and from simulations to real-world applications.
To train AlphaDev to discover new algorithms, we transformed sorting into a single-player “building game.” At each turn, AlphaDev observes the generated algorithms and the information contained in the central processing unit (CPU). Then select the instructions you want to add to the algorithm and run your hand.
Assembly games are incredibly difficult because AlphaDev must efficiently search through a huge number of instruction combinations to find an algorithm that is reorderable and faster than the currently optimal algorithm. . The number of possible combinations of instructions is similar to the number of particles in the universe, or the number of possible combinations of moves in a game of Chess (10120 games) or Go (10700 games). And just one wrong move can invalidate the entire algorithm.
Figure A: Assembly game. Player AlphaDev plays a hand by taking the state of the system st as input and selecting assembly instructions to add to the algorithm generated so far.
Figure B: Compensation calculation. After each move, the generated algorithm is fed a test input sequence. 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 the case of sorting. Agents receive rewards based on the algorithm’s accuracy and latency.
Once the algorithm is built, one instruction at a time, AlphaDev checks whether the algorithm is correct by comparing the output of the algorithm with the expected result. For sorting algorithms, this means that unordered numbers are input and correctly ordered numbers are output. AlphaDev is rewarded both for sorting numbers correctly and for doing so quickly and efficiently. AlphaDev wins the game by discovering accurate and fast programs.
Discovering faster sorting algorithms
AlphaDev has discovered a new sorting algorithm that improves the LLVM libc++ sorting library. This resulted in speedups of up to 70% for short sequences and around 1.7% for sequences over 250,000 elements.
We focused on improving the sorting algorithm for short sequences of 3 to 5 elements. These algorithms are the most widely used because they are often called many times as part of a larger sorting function. Improving these algorithms increases the overall speed of sorting any number of items.
To make the new sorting algorithm easier to use, we reverse engineered it and translated it into C++, one of the most common 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 around the world.
find a new approach
AlphaDev not only discovered a faster algorithm, but also a new approach. Its sorting algorithm includes 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 is reminiscent of AlphaGo’s “move 37,” a counterintuitive play that surprised onlookers and led to the legendary Go player’s defeat. Swap and copy moves cause AlphaDev to skip the step of connecting items. Although this looks like a mistake, it is actually a shortcut. This demonstrates AlphaDev’s ability to discover unique solutions and challenges the way we think about how to improve computer science algorithms.
Left: Original implementation using min(A,B,C).
Right: AlphaDev Swap Move – AlphaDev discovers that only min(A,B) is required.
Left: Original implementation with max (B, min (A, C, D)) used in the larger sorting algorithm to sort 8 elements.
Right: AlphaDev discovered that when using copy move, only max(B, min(A, C)) is needed.
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 basic computing algorithm used to retrieve, store, and compress data. Just as librarians use classification systems to find specific books, hashing algorithms help users know what they’re looking for and exactly where to find it. These algorithms take data for a specific key (e.g. username “Jane Doe”) and hash it. This process converts the raw data into a unique string (e.g. 1234ghfty). This hash is used by the computer to quickly retrieve data related to the key instead of searching through all the data.
We applied AlphaDev to one of the most commonly used algorithms for hashing data structures to discover faster algorithms. And when we applied this to the 9-16 byte range of hash functions, the algorithm AlphaDev discovered 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 around the world and now estimated to be used trillions of times a day. Masu.
Optimize the world’s code one algorithm at a time
AlphaDev demonstrated its ability to generalize and discover new algorithms with real-world impact by optimizing and releasing improved sorting and hashing algorithms for use by developers around the world. We see AlphaDev as a step toward developing general-purpose AI tools that can help optimize the entire computing ecosystem and solve other problems that benefit society.
Optimization in the area of low-level assembly instructions is very powerful, but limits it as the algorithm grows. We are currently exploring the ability of AlphaDev to directly optimize algorithms in high-level languages such as C++, which would be more convenient for developers.
AlphaDev’s discoveries, such as swap and copy movements, show that not only can algorithms be improved, but new solutions can also be found. We hope that these discoveries will inspire researchers and developers alike to further optimize fundamental algorithms and create techniques and approaches that can build stronger, more sustainable computing ecosystems. I am.
Learn more about optimizing your compute ecosystem.
Acknowledgment
We thank Juanita Bawagan, Arielle Bier, Gabriella Pearl, Duncan Smith, Katie McAtackney, Kathryn Seager, Max Barnett, Ross West, Dominic Barlow, Hollie Dobson, and Domhnall Malone for text and illustration assistance. This work was supported by Daniel J. Mankovitz, Andrea Michi, Anton Zernoff, Marco Gelmi, Marco Cervi, Cosmin Padural, Edouard Roulin, Shariq Iqbal, Jean-Baptiste Respiau, Alex Ahern, Thomas Coppe, and Kevin. Millikin, Stephen Gaffney, Sophie Elster, Jackson Brossia, Chris Gamble, Kieran Millan, Robert Tan, Minjae Huang, Tyran Kamgil, Mohammadamine Barekatin, Yujia Lee, Amol Mandan, Thomas Huber. Julian Schlitwieser, Demis Hassabis, Pushmeet Kohli, Martin Riedmiller, Oriol Vinyals, David Silver. We would like to thank Mikita Sazanovich and Danila Kutenin for their contributions to the hashing algorithm.
