In the past half century, the integrated circuit industry has developed rapidly under the guidance of Moore's Law, and the efficiency of algorithms has maintained a large-span improvement. In 2018, the world's fastest computer, IBM Summit, was nearly 30 trillion times faster than the world's first electronic computer ENIAC in 1945.

However, as Moore's Law is approaching the physical limit, the cost of chip development and production has risen sharply, and there is limited room to rely on computing power to improve computing performance in the future. It may become increasingly difficult to meet the needs of massive computing by improving the performance of computer hardware. The future solution lies in improving the efficiency of algorithms.

This new MIT paper summarizes how quickly algorithmic efficiency has improved over the past 80 years.

When it comes to algorithms, it is a bit like the parent of a computer. It will tell the computer how to understand information, and the computer can in turn get useful things from the algorithm.

The more efficient an algorithm is, the less work the computer has to do. For all the technological advances in computer hardware, and the longevity of the much-debated Moore's Law, the performance of computer hardware is only one aspect of the problem.

On the other hand, the problem lies outside the hardware: the efficiency of the algorithm. If the efficiency of the algorithm is improved, the computing power required for the same computing task will be reduced.

While algorithmic efficiency issues may be less of a concern, have you ever noticed that your frequently used search engine is suddenly a tenth faster, while moving through large datasets feels like wading through mud?

These are all related to algorithmic efficiency.

Recently, scientists at MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) asked: How fast are algorithmic efficiencies improving?

Much of the existing data on this question is narrative, and a large part of it is case studies for specific algorithms, and the results of these studies are generalized.

Facing the lack of empirical research data, the research team mainly used data from 57 textbooks and more than 1110 research papers to trace the history of algorithm efficiency improvement.

Some of these papers directly show how efficient the new algorithm is in their conclusions, while others require the author to reconstruct it using "pseudocode" (a simple description of the basic details of the algorithm).

In total, the researchers looked at 113 "algorithm lines," or collections of algorithms that solve the same problem that is the most important in computer science textbooks. They review the history of each algorithm family, tracking each time a new algorithm is proposed for a problem, paying special attention to more efficient algorithms.

Fig. 1 Algorithm discovery and improvement. (a) Number of new algorithmic families discovered per decade. (b) The proportion of known algorithmic families has increased every decade. (c) Classification of the asymptotic time complexity of the algorithm family when first discovered. (d) The average annual probability of switching from an algorithm of one time complexity to another time complexity (reflecting the average level of complexity increase of the algorithm system). The time complexity of ">n3" in (c) and (d) means more than polynomial level, but less than exponential level.

The earliest algorithm department can be traced back to the 1940s. Each algorithm department has an average of 8 algorithms, and the efficiency is gradually improved in chronological order. To share this discovery, the team also created the "Algorithm Wiki" page (Algorithm-Wiki.org).

The researchers charted how quickly the efficiency of these families of algorithms improved, focusing on the most-analyzed characteristics of the algorithms—those that tend to determine how quickly a problem can be solved (in computing parlance, “worst-case time the complexity").

Fig. 2 Relative efficiency gains of the algorithm family, calculated using asymptotic time complexity changes. The reference line is the SPECInt baseline performance. (a) Historical improvements for the four algorithm families compared to the first algorithm in the series (n = 1 million). (b) The sensitivity of the algorithm improvement to the input size (n) of the "Nearest Neighbor Search" family of algorithms. In order to facilitate the comparison of the improvement effect of the algorithm over time, in Figure (b), the algorithm system and the initial time period of the hardware benchmark are aligned.

The results show a wide range of variables, but also uncover important information about the efficiency gains of transformative algorithms in computer science. Right now:

1. For large-scale computing problems, the benefits brought about by the efficiency improvement of 43% of the algorithm systems are no less than the benefits brought by Moore's Law.

2. In 14% of the problems, the benefit of improving algorithm efficiency far exceeds the benefit of improving hardware performance.

3. For big data problems, the benefits of improving algorithm efficiency are particularly large. Therefore, in recent years, this effect has become more and more obvious compared with Moore's Law.

The biggest change occurs when the algorithm system transitions from exponential to polynomial complexity.

The so-called exponential complexity algorithm is like a person guessing the password of a combination lock. The task is easy if there is only one digit on the combination disk. If the dial is 4 digits like a bicycle lock, it is estimated that it is difficult for someone to steal your bicycle, but you can still try one by one. If the dial is 50 digits, it is almost impossible to crack, and too many steps are required.

Figure 3. The annual average speed distribution of 110 algorithm systems based on the calculation of asymptotic time complexity, where the problem size is: (a) n = 1000, (b) n = 1 million, (c) n = 1 billion. The hardware performance improvement line represents the average annual growth rate of SPECInt benchmark performance from 1978 to 2017

This kind of problem is also a problem faced by computers. As the scale of the problem becomes larger and larger, it will soon exceed the processing capacity of the computer. This problem cannot be solved by Moore's Law alone.

The solution lies in finding algorithms of polynomial complexity.

image description

Figure 4 Evaluation of the importance of leading constants in algorithm performance improvement

The findings suggest that, historically, the gains from improved algorithmic efficiency have been substantial. However, there is a difference in frequency between the two. The improvement brought about by Moore's Law is smooth and slow, while the improvement of algorithm efficiency is a stepwise leap forward, but it occurs less frequently.

Corresponding author Neil Thompson said:

This is the first paper in the industry to illustrate the speed at which algorithmic efficiency improves. Through our analysis, we can get how many tasks can be completed with the same computing power after the algorithm is improved.

As problems grow in size, say to billions or trillions of data points, the gains in algorithmic efficiency outweigh the gains in hardware performance, and by far, much more.

Reference link:

Reference link:

https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9540991

Editor: Sue, Interstellar Vision