Will Approximation Drive Post-Moore’s Law HPC Gains?

By Oliver Peckham

July 26, 2021

“Hardware-based improvements are going to get more and more difficult,” said Neil Thompson, an innovation scholar at MIT’s Computer Science and Artificial Intelligence Lab (CSAIL). “I think that’s something that this crowd will probably, actually, be already familiar with.” Thompson, speaking at Supercomputing Frontiers Europe 2021, likely wasn’t wrong: the proximate death of Moore’s law has been a hot topic in the HPC community for a long time. But Thompson wasn’t just there to sound the death knell – he was there to discuss the future of computing, which, in his terms, was an approximate one.

Replacing Moore’s law

Thompson opened with a graph of computing power utilized by the National Oceanic and Atmospheric Administration (NOAA) over time. “Since the 1950s, there has been about a one trillion-fold increase in the amount of computing power being used in these models,” he said. But there was a problem: tracking a weather forecasting metric called mean absolute error (“When you make a prediction, how far off are you on that prediction?”), Thompson pointed out that “you actually need exponentially more computing power to get that [improved] performance.” Without those exponential gains in computing power, the steady gains in accuracy would slow, as well.

Enter, of course, Moore’s law, and the flattening of CPU clock frequencies in the mid-2000s. “But then we have this division, right?” Thompson said. “We start getting into multicore chips, and we’re starting to get computing power in that very specific way, which is not as useful unless you have that amount of parallelism.” Separating out parallelism, he explained, progress had dramatically slowed. “This might worry us if we want to, say, improve weather prediction at the same speed going forward,” he said.

So in 2020, Thompson and others wrote a paper examining ways to improve performance over time in a post-Moore’s law world. The authors landed on three main categories of promise: software-level improvements; algorithmic improvements; and new hardware architectures.

This third category, Thompson said, is experiencing the biggest moment right now, with GPUs and FPGAs exploding in the HPC scene and ever more tailor-made chips emerging. Just five years ago, only four percent of advanced computing users used specialized chips; now, Thompson said, it was 11 percent, and in five more years, it would be 17 percent. But over time, he cautioned, gains from specialized hardware would encounter similar problems to those currently faced by traditional hardware, leaving researchers looking for yet more avenues to improve performance.

Zooming out, Thompson asked the audience to consider performance improvements in terms of a simple equation: tasks ÷ computation × computation ÷ time. Thompson said the latter term of this equation – computations per unit time – represented hardware; the former – tasks per unit computation – represented algorithms.

Image courtesy of Neil Thompson.

“The question, of course, is: how big are the benefits that we can get from algorithms?”

Algorithmic progress

Thompson referenced a report from a White House advisory council, which read, in part: “In many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.”

That report, Thompson cautioned, was citing a “pretty limited” study on linear solvers – and that wasn’t enough proof for him. So along with one of his students, Yash Sherry, Thompson went through 57 textbooks covering different areas of computer science across the decades – everything from operating systems and numerical analysis to statistics and cryptography. Through this work, which Thompson called “the first large census of important algorithms,” they identified around 100 algorithm “families” supported by around 1,100 research papers. This, he said, allowed them to graph those algorithms in terms of performance over time.

Thompson showed a few of those graphs as an example. Singling out one, he pointed out the enormous strides that algorithm improvements alone were able to achieve. “For this problem overall, there has been an enormous gain – in fact, a trillion-fold improvement in performance,” he said. “Now, compare that within the gray line here – that’s the hardware performance from spec.” The gray line, of course, was dwarfed.

Relative performance over time from the 1940s to present (with apologies for the pixelation). The colorful lines represent various algorithms, while the gray line represents hardware improvement. Image courtesy of Neil Thompson.

That isn’t always the case, though. Some of the other algorithms progressed about on par with Moore’s law; others had almost no improvement over time. On average, Thompson said, “if your problem size is small [around n=1000], the gains are not that big – about six percent per year.” Bump it up a few orders of magnitude, though, and the gains were more like 15 percent per year; a few more, 28 percent.

These rates, Thompson said, compared favorably to the current state of Moore’s law. “In the 1990s, Moore’s law was improving very, very rapidly,” he said. “The gains were actually more than 52 percent per year. And so … gains from algorithms are not that high. But Moore’s law has slowed down a lot, right?” In fact, he showed that the current gains from Moore’s law were hovering around six percent — about the same as algorithmic improvements for small problem sizes.

Yearly improvement rate in algorithm performance by problem size. Image courtesy of Neil Thompson.

“Can we continue to get these gains in algorithms?” Thompson asked – or would performance improvements from algorithms, too, suffer the same fate as Moore’s law? By way of example, he presented a sequence alignment algorithm used to establish how many edits “apart” two texts were. The algorithm, Thompson said, had experienced steady improvement until about 2015, and now, “this algorithm is as good as we can mathematically make it.”

But, Thompson said, “what if we were willing to accept a little bit of error? What if we’re willing to get the answer wrong – but just a bit?”

The approximate future of computing

The way past these mathematical limits in algorithm optimization, Thompson explained, was through approximation. He brought back the graph of algorithm improvement over time, adding in approximate algorithms – one 100 percent off, one ten percent off. “If you are willing to accept a ten percent approximation to this problem,” he said, you could get enormous jumps, improving performance by a factor of 32. “We are in the process of analyzing this data right now, but I think what you can already see here is that these approximate algorithms are in fact giving us very very substantial gains.”

Thompson presented another graph, this time charting the balance of approximate versus exact improvements in algorithms over time. “In the 1940s,” he said, “almost all of the improvements that people are making are exact improvements – meaning they’re solving the exact problem. … But you can see that as we approach these later decades, and many of the exact algorithms are starting to become already completely solved in an optimal way … approximate algorithms are becoming more and more important as the way that we are advancing algorithms.”

Share of algorithm improvement by decade from the 1940s to the 2010s, divided into approximate (light blue) and exact (dark blue). Image courtesy of Neil Thompson.

“This gives me hope that, indeed, this approximate future of computing will still allow us to have very large gains coming from algorithms,” he concluded.

Subscribe to HPCwire's Weekly Update!

Be the most informed person in the room! Stay ahead of the tech trends with industy updates delivered to you every week!

White House Scientific Integrity Report Addresses AI and ML Ethics

January 26, 2022

Earlier this month, the White House Office of Science and Technology Policy (OSTP) Scientific Integrity Task Force released a report titled “Protecting the Integrity of Government Science.” While broad-based and over Read more…

IBM Quantum Debuts Classical Entanglement Forging to Expand Simulation Capabilities

January 26, 2022

IBM last week reported a new technique – entanglement forging – that uses both quantum and classical computing resources to double the size of select simulation problems that can be solved on current quantum computer Read more…

Lenovo Launches Its TruScale HPC as a Service Offering

January 26, 2022

Lenovo today announced TruScale High Performance Computing as a Service (HPCaaS), which it says will offer a “cloud-like experience” to HPC organizations of all sizes. The new HPC-as-a-Service is part of the TruScale Read more…

Ceremorphic Touts Its HPC/AI Silicon Technology as It Exits Stealth

January 25, 2022

In a market still filling with fledging silicon chips, Ceremorphic, Inc. has exited stealth and is telling the world about what it calls its patented new ThreadArch multi-thread processor technology that is intended to h Read more…

Quantum Watch: Neutral Atoms Draw Growing Attention as Promising Qubit Technology

January 25, 2022

Currently, there are many qubit technologies vying for sway in quantum computing. So far, superconducting (IBM, Google) and trapped ion (IonQ, Quantinuum) have dominated the conversation. Microsoft’s proposed topologic Read more…

AWS Solution Channel

Register for the AWS “Speeds n’ Feeds” event on Feb. 9th

Since the debut of the first ‘Beowulf’ cluster in 1994, HPC has been a race between technologists squeezing as much performance as possible from hardware, and scale economics driving mass-production prices to affordable levels. Read more…

Meta’s Massive New AI Supercomputer Will Be ‘World’s Fastest’

January 24, 2022

Fresh off its rebrand last October, Meta (née Facebook) is putting muscle behind its vision of a metaversal future with a massive new AI supercomputer called the AI Research SuperCluster (RSC). Meta says that RSC will b Read more…

Lenovo Launches Its TruScale HPC as a Service Offering

January 26, 2022

Lenovo today announced TruScale High Performance Computing as a Service (HPCaaS), which it says will offer a “cloud-like experience” to HPC organizations of Read more…

Ceremorphic Touts Its HPC/AI Silicon Technology as It Exits Stealth

January 25, 2022

In a market still filling with fledging silicon chips, Ceremorphic, Inc. has exited stealth and is telling the world about what it calls its patented new Thread Read more…

Quantum Watch: Neutral Atoms Draw Growing Attention as Promising Qubit Technology

January 25, 2022

Currently, there are many qubit technologies vying for sway in quantum computing. So far, superconducting (IBM, Google) and trapped ion (IonQ, Quantinuum) have Read more…

Meta’s Massive New AI Supercomputer Will Be ‘World’s Fastest’

January 24, 2022

Fresh off its rebrand last October, Meta (née Facebook) is putting muscle behind its vision of a metaversal future with a massive new AI supercomputer called t Read more…

IBM Watson Health Finally Sold by IBM After 11 Months of Rumors

January 21, 2022

IBM has sold its underachieving IBM Watson Health unit for an undisclosed price tag to a global investment firm after almost a year’s worth of rumors that sai Read more…

Supercomputer Analysis Shows the Atmospheric Reach of the Tonga Eruption

January 21, 2022

On Saturday, an enormous eruption on the volcanic islands of Hunga Tonga and Hunga Haʻapai shook the Pacific Ocean. The explosion, which could be heard six tho Read more…

NSB Issues US State of Science and Engineering 2022 Report

January 20, 2022

This week the National Science Board released its biannual U.S. State of Science and Engineering 2022 report, as required by the NSF Act. Broadly, the report presents a near-term view of S&E based mostly on 2019 data. To a large extent, this year’s edition echoes trends from the last few reports. The U.S. is still a world leader in R&D spending and S&E education... Read more…

Multiverse Targets ‘Quantum Computing for the Masses’

January 19, 2022

The race to deliver quantum computing solutions that shield users from the underlying complexity of quantum computing is heating up quickly. One example is Multiverse Computing, a European company, which today launched the second financial services product in its Singularity product group. The new offering, Fair Price, “delivers a higher accuracy in fair price calculations for financial... Read more…

IonQ Is First Quantum Startup to Go Public; Will It be First to Deliver Profits?

November 3, 2021

On October 1 of this year, IonQ became the first pure-play quantum computing start-up to go public. At this writing, the stock (NYSE: IONQ) was around $15 and its market capitalization was roughly $2.89 billion. Co-founder and chief scientist Chris Monroe says it was fun to have a few of the company’s roughly 100 employees travel to New York to ring the opening bell of the New York Stock... Read more…

US Closes in on Exascale: Frontier Installation Is Underway

September 29, 2021

At the Advanced Scientific Computing Advisory Committee (ASCAC) meeting, held by Zoom this week (Sept. 29-30), it was revealed that the Frontier supercomputer is currently being installed at Oak Ridge National Laboratory in Oak Ridge, Tenn. The staff at the Oak Ridge Leadership... Read more…

AMD Launches Milan-X CPU with 3D V-Cache and Multichip Instinct MI200 GPU

November 8, 2021

At a virtual event this morning, AMD CEO Lisa Su unveiled the company’s latest and much-anticipated server products: the new Milan-X CPU, which leverages AMD’s new 3D V-Cache technology; and its new Instinct MI200 GPU, which provides up to 220 compute units across two Infinity Fabric-connected dies, delivering an astounding 47.9 peak double-precision teraflops. “We're in a high-performance computing megacycle, driven by the growing need to deploy additional compute performance... Read more…

Intel Reorgs HPC Group, Creates Two ‘Super Compute’ Groups

October 15, 2021

Following on changes made in June that moved Intel’s HPC unit out of the Data Platform Group and into the newly created Accelerated Computing Systems and Graphics (AXG) business unit, led by Raja Koduri, Intel is making further updates to the HPC group and announcing... Read more…

Nvidia Buys HPC Cluster Management Company Bright Computing

January 10, 2022

Graphics chip powerhouse Nvidia today announced that it has acquired HPC cluster management company Bright Computing for an undisclosed sum. Unlike Nvidia’s bid to purchase semiconductor IP company Arm, which has been stymied by regulatory challenges, the Bright deal is a straightforward acquisition that aims to expand... Read more…

D-Wave Embraces Gate-Based Quantum Computing; Charts Path Forward

October 21, 2021

Earlier this month D-Wave Systems, the quantum computing pioneer that has long championed quantum annealing-based quantum computing (and sometimes taken heat fo Read more…

Killer Instinct: AMD’s Multi-Chip MI200 GPU Readies for a Major Global Debut

October 21, 2021

AMD’s next-generation supercomputer GPU is on its way – and by all appearances, it’s about to make a name for itself. The AMD Radeon Instinct MI200 GPU (a successor to the MI100) will, over the next year, begin to power three massive systems on three continents: the United States’ exascale Frontier system; the European Union’s pre-exascale LUMI system; and Australia’s petascale Setonix system. Read more…

Three Chinese Exascale Systems Detailed at SC21: Two Operational and One Delayed

November 24, 2021

Details about two previously rumored Chinese exascale systems came to light during last week’s SC21 proceedings. Asked about these systems during the Top500 media briefing on Monday, Nov. 15, list author and co-founder Jack Dongarra indicated he was aware of some very impressive results, but withheld comment when asked directly if he had... Read more…

Leading Solution Providers

Contributors

Lessons from LLVM: An SC21 Fireside Chat with Chris Lattner

December 27, 2021

Today, the LLVM compiler infrastructure world is essentially inescapable in HPC. But back in the 2000 timeframe, LLVM (low level virtual machine) was just getting its start as a new way of thinking about how to overcome shortcomings in the Java Virtual Machine. At the time, Chris Lattner was a graduate student of... Read more…

2021 Gordon Bell Prize Goes to Exascale-Powered Quantum Supremacy Challenge

November 18, 2021

Today at the hybrid virtual/in-person SC21 conference, the organizers announced the winners of the 2021 ACM Gordon Bell Prize: a team of Chinese researchers leveraging the new exascale Sunway system to simulate quantum circuits. The Gordon Bell Prize, which comes with an award of $10,000 courtesy of HPC pioneer Gordon Bell, is awarded annually... Read more…

Meta’s Massive New AI Supercomputer Will Be ‘World’s Fastest’

January 24, 2022

Fresh off its rebrand last October, Meta (née Facebook) is putting muscle behind its vision of a metaversal future with a massive new AI supercomputer called t Read more…

Nvidia Defends Arm Acquisition Deal: a ‘Once-in-a-Generation Opportunity’

January 13, 2022

GPU-maker Nvidia is continuing to try to keep its proposed acquisition of British chip IP vendor Arm Ltd. alive, despite continuing concerns from several governments around the world. In its latest action, Nvidia filed a 29-page response to the U.K. government to point out a list of potential benefits of the proposed $40 billion deal. Read more…

Julia Update: Adoption Keeps Climbing; Is It a Python Challenger?

January 13, 2021

The rapid adoption of Julia, the open source, high level programing language with roots at MIT, shows no sign of slowing according to data from Julialang.org. I Read more…

Top500: No Exascale, Fugaku Still Reigns, Polaris Debuts at #12

November 15, 2021

No exascale for you* -- at least, not within the High-Performance Linpack (HPL) territory of the latest Top500 list, issued today from the 33rd annual Supercomputing Conference (SC21), held in-person in St. Louis, Mo., and virtually, from Nov. 14–19. "We were hoping to have the first exascale system on this list but that didn’t happen," said Top500 co-author... Read more…

TACC Unveils Lonestar6 Supercomputer

November 1, 2021

The Texas Advanced Computing Center (TACC) is unveiling its latest supercomputer: Lonestar6, a three peak petaflops Dell system aimed at supporting researchers Read more…

10nm, 7nm, 5nm…. Should the Chip Nanometer Metric Be Replaced?

June 1, 2020

The biggest cool factor in server chips is the nanometer. AMD beating Intel to a CPU built on a 7nm process node* – with 5nm and 3nm on the way – has been i Read more…

  • arrow
  • Click Here for More Headlines
  • arrow
HPCwire