Quick News Bit

DeepMind achieves giant leap in sorting speed

0
DeepMind achieves giant leap in sorting speed
Fundamentally different algorithms discovered by AlphaDev. a, A flow diagram of the variable sort 4 (VarSort4) human benchmark algorithm. In this algorithm, a sequence of unsorted numbers are input into the algorithm. If the sequence length is four, three or two numbers, then the corresponding sort 4, sort 3 or sort 2 sorting network is called that sorts the resulting sequence. The result is then returned and output by the function. b, The VarSort4 algorithm discovered by AlphaDev. This algorithm also receives sequences of length four, three or two numbers as input. In this case, if the length is two, then it calls the sort 2 sorting network and returns. If the length is three then it calls sort 3 to sort the first three numbers and returns. If, however, the length is greater than three, then it calls sort 3, followed by a simplified sort 4 routine that sorts the remaining unsorted number. It is this part of the routine that results in significant latency savings. Credit: Nature (2023). DOI: 10.1038/s41586-023-06004-9

Sorting, or data structuring, has been a core principle of computing operations since the first computers were developed.

The ordering and processing of numbers were demonstrated by the Babylonians around 2500 BC. The Egyptians followed suit around 1550 BC and the Greek mathematician Euclid around 300 BC devised a formula to quickly find the greatest common divisor of two integers.

In the mid-1800s, ordering was a primary objective of mathematician Augusta Ada King, the daughter of poet Lord Byron. She created the first algorithm, intended for use on what was then a theoretical machine imagined by her mentor, mathematician Charles Babbage (known as the father of computers). For that achievement, she earned the title “first computer programmer.”

In 1951, another woman, Frances Elizabeth Holberton, designed the first generative programming system, a rudimentary sort/merge procedure for the U.S. Army. She also helped program ballistics trajectories during World War II.

Actually, according to computer design and cryptology expert Frank Rubin, sorting can be traced to life forms even before humans evolved—some 65 million years before. Dinosaurs, he said, performed simple sorting. They classified all living things into two categories: “food” and “not food.”

The pace of computing algorithm development quickened from midway in the 20th century to the present. We now have computers capable of a quintillion calculations a second.

The Babylonians—maybe even the dinosaurs—would be quite impressed.

Also impressive is a breakthrough announced June 7 by the team at Google’s DeepMind in an online blog.

The team devised an approach to crunching numbers that is up to 70% faster than current methods. The algorithms have been in use for a year as they have been added to the C++ library. The open-source algorithms are now being used by millions of developers and companies globally, according to DeepMind.

The AI project, called AlphaDev, is “an artificial intelligence system that uses reinforcement learning to discover enhanced computer science algorithms—surpassing those honed by scientists and engineers over decades,” DeepMind reported on its blog. The paper is also published in the journal Nature.

AlphaDev builds upon the success of its predecessor, AlphaZero, which mastered strategies behind Go and chess.

AlphaDev training in sorting was conducted using what researchers referred to as a “single player assembly [language] game.”

Sort algorithms were built one instruction at a time, as AlphaDev continuously explored options to find one that worked better than the last one. The process involves tapping into neural networks to compare and move values, all to attain the most accurate results in the shortest amount of time.

“Moore’s Law is coming to an end, where chips are approaching their fundamental physical limits,” said DeepMind scientist Daniel Mankowitz. “We need to find new and innovative ways of optimizing computing.”

The research focused on short lists of up to five characters. Researchers said algorithms for three to five characters are the most frequently used by programmers. Such algorithms are used “trillions of times a day,” the DeepMind blog stated.

For longer sorting sequences, up to 250,000 elements, there was marginal speed improvement over current methods.

The next step for AlphaDev is to study optimization in higher-level languages such as C++ that should uncover greater speed improvement and be more useful for developers.

More information:
Daniel J. Mankowitz et al, Faster sorting algorithms discovered using deep reinforcement learning, Nature (2023). DOI: 10.1038/s41586-023-06004-9

DeepMind blog: AlphaDev discovers faster sorting algorithms

© 2023 Science X Network

Citation:
DeepMind achieves giant leap in sorting speed (2023, June 12)
retrieved 12 June 2023
from https://techxplore.com/news/2023-06-deepmind-giant.html

This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no
part may be reproduced without the written permission. The content is provided for information purposes only.

For all the latest Technology News Click Here 

 For the latest news and updates, follow us on Google News

Read original article here

Denial of responsibility! NewsBit.us is an automatic aggregator around the global media. All the content are available free on Internet. We have just arranged it in one platform for educational purpose only. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials on our website, please contact us by email – [email protected]. The content will be deleted within 24 hours.

Leave a comment