Where Has HPC’s Math Gone?

By Gary Johnson

August 19, 2013

When we think about progress in HPC, most of us use hardware speed, as reported in listings like the Top500, as our yardstick.  But, is that the whole story – or even its most important component?  HPC hardware and the attendant systems software and tools suites are certainly necessary for progress.  But to harness HPC for practical problem solving, we also need the right math, as expressed in our solvers and applications algorithms.  Hardware is tangible and visible while math is seen through the mind’s eye – and is easily overlooked.  Lately, there hasn’t been much public discussion of HPC’s math.  Where has it gone?  Has it matured to the point of invisibility – or is it still a vibrant and dynamic part of HPC?  Let’s take a look.

“Unglamorous but Critical”

From the early days of HPC, math was clearly seen as a vital element.  In December of 1982, the Report of the Panel on Large Scale Computing in Science and Engineering, also known as the Lax Report, was published. One of its recommendations called for (emphasis mine):

Increased research in computational mathematics, software, and algorithms necessary to the effective and efficient use of supercomputer systems

Twenty years later, in July of 2003, the Department of Energy (DOE)’s Office of Science published: A Science-Based Case for Large-Scale Simulation, also known as the SCaLeS Report (Volume 1, Volume 2).  Among other things, it reiterated the critical role of solvers in HPC (emphasis mine):

Like the engine hidden beneath the hood of a car, the solver is an unglamorous but critical component of a scientific code, upon which the function of the whole critically depends. As an engine needs to be properly matched to avoid overheating and failure when the vehicle’s performance requirements are pushed, so a solver appropriate to the simulation at hand is required as the computational burden gets heavier with new physics or as the distance across the data structures increases with enhanced resolution.

Solvers & Speedup

When improvements in HPC hardware performance are discussed, mention is often made of Moore’s Law and the desire to keep pace with it.  Perhaps less well known is the observation that algorithm speedups have historically matched hardware speedups due to Moore’s Law.  For example, consider this excerpt from the SCaLeS Report:

The choice of appropriate mathematical tools can make or break a simulation code. For example, over a four-decade period of our brief simulation era, algorithms alone have brought a speed increase of a factor of more than a million to computing the electrostatic potential induced by a charge distribution, typical of a computational kernel found in a wide variety of problems in the sciences. The improvement resulting from this algorithmic speedup is comparable to that resulting from the hardware speedup due to Moore’s Law over the same length of time (see Figure 13).

Figure 13.

Top: A table of the scaling of memory and processing requirements for the solution of the electrostatic potential equation on a uniform cubic grid of n × n × n cells.

Bottom: The relative gains of some solution algorithms for this problem and Moore’s Law for improvement of processing rates over the same period (illustrated for the case where n = 64).

Algorithms yield a factor comparable to that of the hardware, and the gains typically can be combined (that is, multiplied together). The algorithmic gains become more important than the hardware gains for larger problems. If adaptivity is exploited in the discretization, algorithms may do better still, though combining all of the gains becomes more subtle in this case.

Time to Solution

So, if hardware gains and algorithmic gains could be “multiplied together,” what would that imply?  If we are currently targeting a 1,000 fold increase in hardware speed over the present decade and if algorithmic gains keep pace, then in ten years we’ll have improved our problem solving capability by a factor of 1,000,000.  Thus we’d be able to solve today’s problems in one millionth of their current solution time or use today’s time to solution to tackle problems a million times harder.  Sounds pretty impressive.  Is the necessary math on track to make this happen? 

Obviously, things aren’t as simplistic as I’ve made them out to be.  To get the multiplicative effect, algorithms and hardware architectures should be independent of one another.  But in real HPC life, algorithms and hardware architectures interact.  Fast algorithms are usually “complicated” and complicated algorithms are best implemented on “simple” uncomplicated architectures.  Historically, when new, more complicated, hardware architectures are introduced we revert to simpler and slower solvers.  Consequently, the optimistic estimates of improvement in time to solution may not materialize.  In fact, time to solution could go up.  This effect can go largely unnoticed by the general community because simpler solvers can require lots of mathematical operations and faster architectures spit out more operations per second.  Thus in this situation, applications codes can run “fast” but produce solutions slowly.

As we move toward extreme scale HPC hardware, the interaction of algorithms and hardware architectures is becoming more important than ever.  Last year, DOE’s Office of Advanced Scientific Computing Research (ASCR) published a Report on the Workshop on Extreme-Scale Solvers: Transition to Future Architectures.  In it, the following observation is made (emphasis mine):

The needs of extreme-scale science are expected to drive a hundredfold increase in computational capabilities by mid-decade and a factor of 1,000 increase within ten years. These 100 PF (and larger) supercomputers will change the way scientific discoveries are made; moreover, the technology developed for those systems will provide desktop performance on par with the fastest systems from just a few years ago. Since numerical solvers are at the heart of the codes that enable these discoveries, the development of efficient, robust, high-performance, portable solvers has a tremendous impact on harnessing these computers to achieve new science. But future architectures present major challenges to the research and development of such solvers. These architectural challenges include extreme parallelism, data placement and movement, resilience, and heterogeneity. 

Solver Dominance

The extreme-scale solver report goes on to address the issue of solver dominance:

Increasing the efficiency of numerical solvers will significantly improve the ability of computational scientists to make scientific discoveries, because such solvers account for so much of the computation underlying scientific applications. 

This figure, taken from the extreme-scale solver report, shows that for a typical application as processor count and problem size increase, the time spent in the application’s solver (blue), relative to the time spent in the rest of the application’s code (pink), grows and soon dominates the total execution time.

What’s to be done about this – especially as we anticipate the move to exascale architectures? 

ExaMath

In an attempt to find some answers, ASCR has formed an Exascale Mathematics Working Group (EMWG) “for the purpose of identifying mathematics and algorithms research opportunities that will enable scientific applications to harness the potential of exascale computing.”

At ASCR’s request, the EMWG has organized a DOE Workshop on Applied Mathematics Research for Exascale Computing (ExaMath13).  ExaMath13 is taking place on 21-22 August and encompasses 40 presentations, selected on the basis of two-page position papers submitted to the EMWG a few months ago.  About 2/3s of the presenters are from the DOE Labs with the rest coming from universities.  The seventy five submitted position papers from which the 40 presentations were selected may be found at the EMWG website.  They make interesting reading and reinforce one’s optimism about the applied math community’s commitment to meeting the challenges posed by exascale architectures.

As the ExaMath problem is complex, it’s not surprising that most of the position papers deal with intricate mathematics.  However, a few also address the bigger picture.  To mention just one of those, Ulrich Ruede’s paper, entitled: New Mathematics for Exascale Computational Science?, summarizes the challenges faced by the applied math community particularly well:

I believe that the advent of exascale forces mathematics to address the performance abyss that widens increasingly between existing math theory and the practical use of HPC systems. Tweaking codes is not enough – we must turn back and analyze where we have not yet thought deeply enough, developing a new interdisciplinary algorithm and performance engineering methodology. Beyond this, exascale opens fascinating new opportunities in fundamental research that go far beyond just increasing the mesh resolution.

So, it looks like HPC’s math is back in the foreground.  There are lots of bright folks in the applied math community.  Let’s see what they come up with to address the difficulties posed by ExaMath.

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!

Google Launches Site to Share its NYC-based Algorithm Research

August 22, 2017

Much of Google’s algorithm development occurs in groups scattered throughout New York City. Yesterday, Google launched a single website - NYC Algorithms and Optimization Team page - to provide a deeper view into all of Read more…

By John Russell

Dell Strikes Reseller Deal with Atos; Supplants SGI

August 22, 2017

Dell EMC and Atos announced a reseller deal today in which Dell will offer Atos’ high-end 8- and 16-socket Bullion servers. Some move from Dell had been expected following Hewlett Packard Enterprise’s purchase of SGI Read more…

By John Russell

Glimpses of Today’s Total Solar Eclipse

August 21, 2017

Here are a few arresting images posted by NASA of today’s total solar eclipse. Such astronomical events have always captured our imagination and it’s not hard to understand why such occurrences were often greeted wit Read more…

By John Russell

HPE Extreme Performance Solutions

Leveraging Deep Learning for Fraud Detection

Advancements in computing technologies and the expanding use of e-commerce platforms have dramatically increased the risk of fraud for financial services companies and their customers. Read more…

Tech Giants Outline Battle Plans for Future HPC Market

August 21, 2017

Four companies engaged in a cage fight for leadership in the emerging HPC market of the 2020s are, despite deep differences in some areas, in violent agreement on at least one thing: the power consumption and latency pen Read more…

By Doug Black

Tech Giants Outline Battle Plans for Future HPC Market

August 21, 2017

Four companies engaged in a cage fight for leadership in the emerging HPC market of the 2020s are, despite deep differences in some areas, in violent agreement Read more…

By Doug Black

Microsoft Bolsters Azure With Cloud HPC Deal

August 15, 2017

Microsoft has acquired cloud computing software vendor Cycle Computing in a move designed to bring orchestration tools along with high-end computing access capabilities to the cloud. Terms of the acquisition were not disclosed. Read more…

By George Leopold

HPE Ships Supercomputer to Space Station, Final Destination Mars

August 14, 2017

With a manned mission to Mars on the horizon, the demand for space-based supercomputing is at hand. Today HPE and NASA sent the first off-the-shelf HPC system i Read more…

By Tiffany Trader

AMD EPYC Video Takes Aim at Intel’s Broadwell

August 14, 2017

Let the benchmarking begin. Last week, AMD posted a YouTube video in which one of its EPYC-based systems outperformed a ‘comparable’ Intel Broadwell-based s Read more…

By John Russell

Deep Learning Thrives in Cancer Moonshot

August 8, 2017

The U.S. War on Cancer, certainly a worthy cause, is a collection of programs stretching back more than 40 years and abiding under many banners. The latest is t Read more…

By John Russell

IBM Raises the Bar for Distributed Deep Learning

August 8, 2017

IBM is announcing today an enhancement to its PowerAI software platform aimed at facilitating the practical scaling of AI models on today’s fastest GPUs. Scal Read more…

By Tiffany Trader

IBM Storage Breakthrough Paves Way for 330TB Tape Cartridges

August 3, 2017

IBM announced yesterday a new record for magnetic tape storage that it says will keep tape storage density on a Moore's law-like path far into the next decade. Read more…

By Tiffany Trader

AMD Stuffs a Petaflops of Machine Intelligence into 20-Node Rack

August 1, 2017

With its Radeon “Vega” Instinct datacenter GPUs and EPYC “Naples” server chips entering the market this summer, AMD has positioned itself for a two-head Read more…

By Tiffany Trader

How ‘Knights Mill’ Gets Its Deep Learning Flops

June 22, 2017

Intel, the subject of much speculation regarding the delayed, rewritten or potentially canceled “Aurora” contract (the Argonne Lab part of the CORAL “ Read more…

By Tiffany Trader

Nvidia’s Mammoth Volta GPU Aims High for AI, HPC

May 10, 2017

At Nvidia's GPU Technology Conference (GTC17) in San Jose, Calif., this morning, CEO Jensen Huang announced the company's much-anticipated Volta architecture a Read more…

By Tiffany Trader

Reinders: “AVX-512 May Be a Hidden Gem” in Intel Xeon Scalable Processors

June 29, 2017

Imagine if we could use vector processing on something other than just floating point problems.  Today, GPUs and CPUs work tirelessly to accelerate algorithms Read more…

By James Reinders

Russian Researchers Claim First Quantum-Safe Blockchain

May 25, 2017

The Russian Quantum Center today announced it has overcome the threat of quantum cryptography by creating the first quantum-safe blockchain, securing cryptocurrencies like Bitcoin, along with classified government communications and other sensitive digital transfers. Read more…

By Doug Black

Quantum Bits: D-Wave and VW; Google Quantum Lab; IBM Expands Access

March 21, 2017

For a technology that’s usually characterized as far off and in a distant galaxy, quantum computing has been steadily picking up steam. Just how close real-wo Read more…

By John Russell

Nvidia Responds to Google TPU Benchmarking

April 10, 2017

Nvidia highlights strengths of its newest GPU silicon in response to Google's report on the performance and energy advantages of its custom tensor processor. Read more…

By Tiffany Trader

Groq This: New AI Chips to Give GPUs a Run for Deep Learning Money

April 24, 2017

CPUs and GPUs, move over. Thanks to recent revelations surrounding Google’s new Tensor Processing Unit (TPU), the computing world appears to be on the cusp of Read more…

By Alex Woodie

HPC Compiler Company PathScale Seeks Life Raft

March 23, 2017

HPCwire has learned that HPC compiler company PathScale has fallen on difficult times and is asking the community for help or actively seeking a buyer for its a Read more…

By Tiffany Trader

Leading Solution Providers

Trump Budget Targets NIH, DOE, and EPA; No Mention of NSF

March 16, 2017

President Trump’s proposed U.S. fiscal 2018 budget issued today sharply cuts science spending while bolstering military spending as he promised during the cam Read more…

By John Russell

Google Debuts TPU v2 and will Add to Google Cloud

May 25, 2017

Not long after stirring attention in the deep learning/AI community by revealing the details of its Tensor Processing Unit (TPU), Google last week announced the Read more…

By John Russell

CPU-based Visualization Positions for Exascale Supercomputing

March 16, 2017

In this contributed perspective piece, Intel’s Jim Jeffers makes the case that CPU-based visualization is now widely adopted and as such is no longer a contrarian view, but is rather an exascale requirement. Read more…

By Jim Jeffers, Principal Engineer and Engineering Leader, Intel

Six Exascale PathForward Vendors Selected; DoE Providing $258M

June 15, 2017

The much-anticipated PathForward awards for hardware R&D in support of the Exascale Computing Project were announced today with six vendors selected – AMD Read more…

By John Russell

Top500 Results: Latest List Trends and What’s in Store

June 19, 2017

Greetings from Frankfurt and the 2017 International Supercomputing Conference where the latest Top500 list has just been revealed. Although there were no major Read more…

By Tiffany Trader

IBM Clears Path to 5nm with Silicon Nanosheets

June 5, 2017

Two years since announcing the industry’s first 7nm node test chip, IBM and its research alliance partners GlobalFoundries and Samsung have developed a proces Read more…

By Tiffany Trader

Messina Update: The US Path to Exascale in 16 Slides

April 26, 2017

Paul Messina, director of the U.S. Exascale Computing Project, provided a wide-ranging review of ECP’s evolving plans last week at the HPC User Forum. Read more…

By John Russell

Graphcore Readies Launch of 16nm Colossus-IPU Chip

July 20, 2017

A second $30 million funding round for U.K. AI chip developer Graphcore sets up the company to go to market with its “intelligent processing unit” (IPU) in Read more…

By Tiffany Trader

  • arrow
  • Click Here for More Headlines
  • arrow
Share This