{"id":584,"date":"2023-06-07T15:52:33","date_gmt":"2023-06-07T15:52:33","guid":{"rendered":"https:\/\/todaysainews.com\/index.php\/2023\/06\/07\/alphadev-discovers-faster-sorting-algorithms\/"},"modified":"2025-04-27T07:33:22","modified_gmt":"2025-04-27T07:33:22","slug":"alphadev-discovers-faster-sorting-algorithms","status":"publish","type":"post","link":"https:\/\/todaysainews.com\/index.php\/2023\/06\/07\/alphadev-discovers-faster-sorting-algorithms\/","title":{"rendered":"AlphaDev discovers faster sorting algorithms"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n

New algorithms will transform the foundations of computing<\/h4>\n

Digital society is driving increasing demand for computation, and energy use. For the last five decades, we relied on improvements in hardware to keep pace. But as microchips approach their physical limits, it\u2019s critical to improve the code that runs on them to make computing more powerful and sustainable. This is especially important for the algorithms that make up the code running trillions of times a day.\u00a0<\/p>\n

In our paper published today in Nature<\/em><\/a>, we introduce AlphaDev, an artificial intelligence (AI) system that uses reinforcement learning to discover enhanced computer science algorithms \u2013 surpassing those honed by scientists and engineers over decades.\u00a0<\/p>\n

AlphaDev uncovered a faster algorithm for sorting, a method for ordering data. Billions of people use these algorithms everyday without realising it. They underpin everything from ranking online search results and social posts to how data is processed on computers and phones. Generating better algorithms using AI will transform how we program computers and impact all aspects of our increasingly digital society.\u00a0<\/p>\n

By open sourcing our new sorting algorithms in the main C++ library<\/a>, millions of developers and companies around the world now use it on AI applications across industries from cloud computing and online shopping to supply chain management. This is the 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 this library. We see this as an important stepping stone for using AI to optimise the world\u2019s code, one algorithm at a time.\u00a0<\/p>\n

What is sorting?<\/h4>\n

Sorting is a method of organising a number of items in a particular order. Examples include alphabetising three letters, arranging five numbers from biggest to smallest, or ordering a database of millions of records.\u00a0<\/p>\n

This method has evolved throughout history. One of the earliest examples dates back to the second and third century when scholars alphabetised thousands of books by hand on the shelves of the Great Library of Alexandria. Following the industrial revolution, came the invention of machines that could help with sorting \u2013 tabulation machines stored information on punch cards which were used to collect the 1890 census results in the United States.\u00a0<\/p>\n

And with the rise of commercial computers in the 1950s, we saw the development of the earliest computer science algorithms for sorting. Today, there are many different sorting techniques and algorithms which are used in codebases around the world to organise massive amounts of data online.\u00a0<\/p>\n

\n
\"\"\/<\/div>
Illustration of what a sorting algorithm does. A series of unsorted numbers is input into the algorithm and sorted numbers are output.<\/figcaption><\/figure>\n

Contemporary algorithms took computer scientists and programmers decades of research to develop. They\u2019re so efficient that making further improvements is a major challenge, akin to trying to find a new way to save electricity or a more efficient mathematical approach. These algorithms are also a cornerstone of computer science, taught in introductory computer science classes at universities.\u00a0<\/p>\n

Searching for new algorithms<\/h4>\n

AlphaDev uncovered faster algorithms by starting from scratch rather than refining existing algorithms, and began looking where most humans don\u2019t: the computer\u2019s assembly instructions.\u00a0<\/p>\n

Assembly instructions are used to create binary code for computers to put into action. While developers write in coding languages like C++, known as high-level languages, this must be translated into \u2018low-level\u2019 assembly instructions for computers to understand.\u00a0<\/p>\n

We believe many improvements exist at this lower level that may be difficult to discover in a higher-level coding language. Computer storage and operations are more flexible at this level, which means there are significantly more potential improvements that could have a larger impact on speed and energy usage. <\/p>\n

\n
\"\"\/<\/div>
Code is typically written in a high level programming language such as C++. This is then translated to low-level CPU instructions, called assembly instructions, using a compiler. An assembler then converts the assembly instructions to executable machine code that the computer can run.<\/figcaption><\/figure>\n
\n
\"\"\/<\/div>
Figure A:<\/strong> An example C++ algorithm that sorts up to two elements.
\u200dFigure B:<\/strong> The corresponding assembly representation of the code.<\/figcaption><\/figure>\n

Finding the best algorithms with a game<\/h4>\n

AlphaDev is based on AlphaZero<\/a>, our reinforcement learning model that defeated world champions in games like Go, chess and shogi. With AlphaDev, we show how this model can transfer from games to scientific challenges, and from simulations to real-world applications.<\/p>\n

To train AlphaDev to uncover new algorithms, we transformed sorting into a single player \u2018assembly game\u2019. At each turn, AlphaDev observes the algorithm it has generated and the information contained in the central processing unit (CPU). Then it plays a move by choosing an instruction to add to the algorithm..\u00a0<\/p>\n

The assembly game is incredibly hard because AlphaDev has to efficiently search through an enormous number of possible combinations of instructions to find an algorithm that can sort, and is faster than the current best one. 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 games of chess (10120<\/sup> games) and Go (10700<\/sup> games). And a single, wrong move can invalidate the entire algorithm.<\/p>\n

\n
\"\"\/<\/div>
Figure A: <\/strong>The assembly game. The player, AlphaDev, receives the state of the system st as input and plays a move at by selecting an assembly instruction to add to the algorithm that has been generated thus far.
\u200dFigure B: <\/strong>The reward computation. After each move, the generated algorithm is fed test input sequences – for sort3, this corresponds to all combinations of sequences of three elements. The algorithm then generates an output, which is compared to the expected output of sorted sequences for the case of sorting. The agent is rewarded based on the algorithm’s correctness and latency.<\/figcaption><\/figure>\n

As the algorithm is built, one instruction at a time, AlphaDev checks that it\u2019s correct by comparing the algorithm\u2019s output with the expected results. For sorting algorithms, this means unordered numbers go in and correctly sorted numbers come out. We reward AlphaDev for both sorting the numbers correctly and for how quickly and efficiently it does so. AlphaDev wins the game by discovering a correct, faster program.\u00a0<\/p>\n

Discovering faster sorting algorithms<\/h4>\n

AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements.\u00a0<\/p>\n

We focused on improving sorting algorithms for shorter sequences of three to five elements. These algorithms are among the most widely used because they are often called many times as a part of larger sorting functions. Improving these algorithms can lead to an overall speedup for sorting any number of items.<\/p>\n

To make the new sorting algorithm more usable for people, we reverse-engineered the algorithms and translated them into C++, one of the most popular coding languages that developers use. These algorithms are now available in the LLVM libc++ standard sorting library<\/a>, used by millions of developers and companies around the world.<\/p>\n

Finding novel approaches<\/h4>\n

AlphaDev not only found faster algorithms, but also uncovered novel approaches. Its sorting algorithms contain new sequences of instructions that save a single instruction each time they\u2019re applied. This can have a huge impact as these algorithms are used trillions of times a day.\u00a0<\/p>\n

We call these \u2018AlphaDev swap and copy moves\u2019. This novel approach is reminiscent of AlphaGo\u2019s \u2018move 37\u2019 \u2013 a counterintuitive play that stunned onlookers and led to the defeat of a legendary Go player. With the swap and copy move, AlphaDev skips over a step to connect items in a way that looks like a mistake but is actually a shortcut. This shows AlphaDev\u2019s ability to uncover original solutions and challenges the way we think about how to improve computer science algorithms.<\/p>\n

\n
\"\"\/<\/div>
Left: <\/strong>The original sort3 implementation with min(A,B,C).
\u200dRight:<\/strong> AlphaDev Swap Move – AlphaDev discovers that you only need min(A,B).<\/figcaption><\/figure>\n
\n
\"\"\/<\/div>
Left: <\/strong>The original implementation with max (B, min (A, C, D))used in a larger sorting algorithm for sorting eight elements.
\u200dRight:<\/strong> AlphaDev discovered that only max (B, min (A, C)) is needed when using its copy move.<\/figcaption><\/figure>\n

From sorting to hashing in data structures<\/h4>\n

After discovering faster sorting algorithms, we tested whether AlphaDev could generalise and improve a different computer science algorithm: hashing.\u00a0<\/p>\n

Hashing is a fundamental algorithm in computing used to retrieve, store, and compress data. Like a librarian who uses a classification system to locate a certain book, hashing algorithms help users know what they\u2019re looking for and exactly where to find it. These algorithms take data for a specific key (e.g. user name \u201cJane Doe\u201d) and hashes it \u2013 a process where raw data is turned into a unique string of characters (e.g 1234ghfty). This hash is used by the computer to retrieve the data related to the key quickly rather than searching all of the data.\u00a0<\/p>\n

We applied AlphaDev to one of the most commonly used algorithms for hashing in data structures to try and discover a faster algorithm. And when we applied it to the 9-16 bytes range of the hashing function, the algorithm that AlphaDev discovered was 30% faster.\u00a0<\/p>\n

This year, AlphaDev\u2019s new hashing algorithm was released into the open-source Abseil library<\/a>, available to millions of developers around the world, and we estimate that it\u2019s now being used trillions of times a day.\u00a0<\/p>\n

Optimising the world\u2019s code, one algorithm at a time<\/h4>\n

By optimising and launching improved sorting and hashing algorithms used by developers all around the world, AlphaDev has demonstrated its ability to generalise and discover new algorithms with real-world impact. We see AlphaDev as a step towards developing general-purpose AI tools that could help optimise the entire computing ecosystem and solve other problems that will benefit society.<\/p>\n

While optimising in the space of low-level assembly instructions is very powerful, there are limitations as the algorithm grows, and we are currently exploring AlphaDev\u2019s ability to optimise algorithms directly in high-level languages such as C++ which would be more useful for developers.<\/p>\n

AlphaDev\u2019s discoveries, such as the swap and copy moves, not only show that it can improve algorithms but also find new solutions. We hope these discoveries inspire researchers and developers alike to create techniques and approaches that can further optimise fundamental algorithms to create a more powerful and sustainable computing ecosystem.<\/p>\n

Learn more about optimising the computing ecosystem:<\/strong><\/p>\n<\/div>\n

[ad_2]
\n
Source link <\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

[ad_1] New algorithms will transform the foundations of computing Digital society is driving increasing demand for computation, and<\/p>\n","protected":false},"author":2,"featured_media":585,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[21],"tags":[],"class_list":["post-584","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-deepmind-ai"],"_links":{"self":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/584","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/comments?post=584"}],"version-history":[{"count":1,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/584\/revisions"}],"predecessor-version":[{"id":2780,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/posts\/584\/revisions\/2780"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/media\/585"}],"wp:attachment":[{"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/media?parent=584"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/categories?post=584"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/todaysainews.com\/index.php\/wp-json\/wp\/v2\/tags?post=584"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}