Georg Hager's Blog

Random thoughts on High Performance Computing

Content

SIAM Parallel Processing 24 (PP24) Minisymposium on “Advancements in Sparse Linear Algebra: Hardware-Aware Algorithms and Optimization Techniques”

Together with Christie Alappat and Gerhard Wellein, I am organizing a two-part minisymposium at SIAM Parallel Processing 2024 in Baltimore, MD (full conference program available), on March 7, 2024. It is titled “Advancements in Sparse Linear Algebra: Hardware-Aware Algorithms and Optimization Techniques.” This is the abstract:

Over the last decade, the landscape of computer architecture has undergone tremendous transformations. At the same time, the field of sparse linear algebra (LA) has experienced a resurgence in interest, witnessing the emergence of novel algorithms and the revival of traditional ones. The irregular access patterns inherent in sparse LA often pose significant challenges for efficient execution on highly parallel modern computing devices. This minisymposium delves into diverse algorithmic and programming techniques that address these challenges. We will explore various methods for enhancing the computational intensity and node-level performance of sparse algorithms, along with approaches to improve their scalability. The topics covered encompass mixed precision computation, batched solvers, methods for reducing or hiding communication, cache blocking, and the efficient utilization of parallel paradigms. Naturally, the implementation of some of these techniques is not straightforward and may necessitate algorithmic reformulation. The discussions will shed light on this aspect while also examining their applications, benefits, and limitations. The primary objective is to present an overview of cutting-edge sparse LA techniques that effectively leverage hardware capabilities.

Here’s an overview of the agenda:

Part 1 – MS43 (March 7, 11:00 am – 1:00 pm EST)

11:00-11:25 Accelerating Sparse Solvers with Cache-Optimized Matrix Power Kernels abstract
Christie Louis Alappat, Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany

11:30-11:55 Efficient Schwarz Preconditioning Techniques on Current Hardware Using FROSch abstract
Alexander Heinlein
, Delft University of Technology, Netherlands; Sivasankaran Rajamanickam and Ichitaro Yamazaki, Sandia National Laboratories, U.S.

12:00-12:25 Sparse Algorithms for Large-Scale Bayesian Inference Problems abstract
Lisa Gaedke-Merzhäuser
and Olaf Schenk, Università della Svizzera italiana, Switzerland

12:30-12:55 Communication-Reduced Sparse-Dense Matrix Multiplication with Adaptive Parallelization abstract
Hua Huang
and Edmond Chow, Georgia Institute of Technology, U.S.

Part 2 – MS54 (March 7, 3:45 pm – 5:45 pm EST)

3:45-4:10 Residual Inverse Formulation of the Feast Eigenvalue Algorithm Using Mixed-Precision and Inexact System Solves abstract
Ivan Williams
and Eric Polizzi, University of Massachusetts, Amherst, U.S.

4:15-4:40 How Mixed Precision Can Accelerate Sparse Solvers abstract
Hartwig Anzt
, University of Tennessee, U.S.; Terry Cojean, Pratik Nayak, Thomas Gruetzmacher, Yu-Hsiang Mike Tsai, Marcel Koch, Tobias Ribizel, Fritz Goebel, and Gregor Olenik, Karlsruhe Institute of Technology, Germany

4:45-5:10 Algebraic Programming for High Performance Auto-Parallelised Solvers abstract
Albert Jan N. Yzelman
, Denis Jelovina, Aristeidis Mastoras, Alberto Scolari, and Daniele Giuseppe Spampinato, Huawei Technologies Switzerland AG, Switzerland

5:15-5:40 Pipelined Sparse Solvers: Can More Reliable Computations Help Us to Converge Faster? abstract
Roman Iakymchuk
, Umeå University and Uppsala University, Sweden

 

Node-Level Performance Engineering tutorial to be featured again at SC23

SC23 LogoOur popular “Node-Level Performance Engineering” full-day tutorial has been accepted again (now the twelfth time in a row!) for presentation at SC23, the International Conference for High Performance Computing, Networking, Storage and Analysis. Together with Thomas Gruber and Gerhard Wellein I will teach the basics of node-level computer architecture, the LIKWID performance tools suite, analytic performance modeling (via the Roofline model), and model-guided optimization. Find the details in the official SC23 agenda.

Get the gist of it in our flashy promo video:

PERMAVOST Workshop submission deadline approaching

PERMAVOST 2023, the 3rd Workshop on Performance EngineeRing, Modelling, Analysis, and VisualizatiOn STrategy, is calling for papers. The workshop will be held in conjunction with ACM HPDC 2023 in Orlando, FL.

Modern software engineering is getting increasingly complicated. Effective monitoring and analysis of High-Performance Computing (HPC) applications and infrastructure is critical for ongoing improvement, design, and maintenance. The development and maintenance of these applications expand beyond the realm of computer science to encompass a diverse range of experts in mathematics, science, and other engineering disciplines. Many developers from these disciplines rely increasingly on the tools created by computer scientists to analyze and optimize their code. Thus, there is a pressing need for a forum to bring together a diverse group of experts between these different communities to share their experiences, collaborate on solving challenges, and work towards advancing the field of HPC performance analysis and optimization.

  • Submission deadline: April 1, 2023, 11:59 pm Anywhere on Earth (AoE)
  • Notification; April 20, 2023
  • Camera ready deadline: May 12, 2023
  • Workshop: June 20, 2023

Continue reading

New tutorial on “Core-Level Performance Engineering” accepted for ICPE 2023

ICPE 2023 LogoOur brand-new tutorial “Core-Level Performance Engineering” has been accepted as a full-day tutorial at ICPE 2023, the 14th ACM/SPEC International Conference on Performance Engineering. This tutorial concentrates on the in-core aspects of performance modeling and analysis on CPUs. We use Matt Godbolt’s Compiler Explorer and our Open-Source Architecture Code Analyzer (OSACA), which is now integrated with the Compiler Explorer, to teach the basics of code execution including pipelining, superscalarity, SIMD, intra-iteration and loop-carried dependencies, and more. Intel/AMD x86 and ARM Neon/SVE assembly code is introduced, and participants can get their hands dirty exploring the depths of machine code execution using only a web browser! Lead OSACA developer Jan Laukemann did most of the work for this exciting new event. Find the details at: https://icpe2023.spec.org/tutorials/tutorial3/.

All slides and some of the exercises are available at: http://tiny.cc/CLPE.

ISC 2022 has started

ISC High Performance 2022 is finally here! After two years of online ISC, people can finally get together and talk face to face (albeit with one or two layers of mask tissue in between). The first “full conference” day (Sunday is traditionally reserved for tutorials) marks some notable events this year.

After a warm welcome and introduction by ISC22 Program Chair Keren Bergman,  Rev Lebaredian (NVIDIA) and Michele Melchiorre (BMW) gave an enthralling keynote about how digital twins are used in industry and how they may become the one thing that you never knew about but desperately need. A digital twin is like a computational model of reality – be it a manufacturing plant, a building, or even a whole city. Such twins are used a lot in design phases, but they are rarely kept up to date over the whole life cycle of the structures they describe. With the advent of powerful AI methods, this may change as AI could close the gap between model and reality. Rev even went so far as to speculate that, given enough computing power, one could use the twin to move back and forth in time for improved insight, forecasting, or decision making.

An emotional moment (well, for a technical event at least) came with the special session for celebrating the life and work of Jack Dongarra, recipient of the 2021 ACM Turing Award. Horst Simon, Tony Hey, David E. Keyes, and Satoshi Matsuoka recalled Jack’s many achievements, the most prominent of which are the BLAS and LAPACK libraries (and their more current descendants), the initial seedling of the MPI standard, sustainable and scalable HPC benchmarks, and numerous contributions to mixed-precision linear algebra methods.

Next came Erich Strohmaier with his long-awaited presentation of the June 2022 Top500 list, in which he analyzed current trends in supercomputing using the historical data that is now available since 1993. One surprising fact about the current list is that there was never such a low turnaround – only 39 systems fell out of the list, and the entry threshold of just above 1.6 Pflop/s hasn’t even changed. On the positive side, Fritz and Alex, the new NHR@FAU systems, are officially on it: Fritz is at #323, despite some network hardware still missing, and Alex is at #184 although the more than 300 NVIDIA A40 GPUs could not even be used for running LINPACK. In addition, Alex struck #16 in the Green500, in which energy efficiency in Gflop/W determines the ranking. With that, Alex is the most energy-efficient system in Germany.

Oh yes, and there’s a new #1: “Frontier” at Oak Ridge National Lab broke the Exaflop barrier. We have now officially entered the age of exascale, at least if we use the debatable LINPACK metric as the yardstick. Erich pointed out that Frontier now encompasses 25% of the total aggregated Top500 performance; grain-of-salty extrapolations indicate that this ratio may go up to 50% in 2030, but who knows which marvels await behind the closed doors of Nvidia, Intel, or AMD labs.

 

Gprofng is the next-generation GNU profiler

This week, Ruud van der Pas of OpenMP fame gave a talk in our NHR PerfLab seminar on gprofng, the next-generation GNU profiling tool. If you ever felt that gprof was sorely lacking features like threading support, sampling, and drilling down to source, gprofng comes to rescue. Now you can profile code without even recompiling it, which comes in handy (not only) if you don’t have the source. It has recently been accepted as part of the Linux binutils package and will inevitably find its way into standard Linux distros. If you don’t want to wait that long, clone the development repo with

git clone git://sourceware.org/git/binutils-gdb.git

and compile it yourself. Here’s the recording of Ruud’s talk, where he explains the basic functions of gprofng and also takes a peek at upcoming features like HTML output and hardware performance counter support:

SIAM Parallel Processing 2022 Minisymposium on “Advances in Performance Modeling of Parallel Code”

Together with Alexandru Calotoiu (ETH Zurich), I am organizing a two-part minisymposium at SIAM Parallel Processing 2022.  It is to take place on February 25, 2022, and it is titled “Advances in Performance Modeling of Parallel Code.” This is the abstract:

Performance modeling is an indispensable tool for the assessment, analysis, prediction, and optimization of parallel code in scientific computing and computational science. Modeling approaches can take a variety of forms, from purely analytic, first-principle models to curve fitting, machine learning, and AI-based solutions. The goals of modeling are just as diverse: Identification of bottlenecks or scaling problems, extrapolation, architectural exploration, and even the prediction of power dissipation and energy consumption can all be supported be modeling procedures. This minisymposium tries to provide an overview of the current state of the art in performance, or more generally, resource modeling of parallel code. The hardware focus will be very broad, from the node to the massively parallel level, including standard multicore systems, GPUs, and reconfigurable hardware. Contributions will cover fundamental research as well as tools development and case studies. After the minisymposium, the organizers plan to issue an open call for a journal special issue.

An impressive lineup of international speakers have been brought together:

Part 1 (February 25, 11:10 am – 12:50 pm PST)

11:10-11:30 Computational Waves in Parallel Programs and Their Impact on Performance Modeling

Ayesha Afzal, Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany; Georg Hager, Erlangen National High Performance Computing Center, Germany

11:35-11:55 The Price Performance of Performance Models

Alexandru Calotoiu, ETH Zurich, Switzerland; Alexander Geiss, Benedikt Naumann, Marcus Ritter, and Felix Wolf, Technische Universität Darmstadt, Germany

12:00-12:20 perf-taint: Extracting Clean Performance Models from Tainted Programs

Marcin Copik, ETH Zurich, Switzerland

12:25-12:45 Extra-P Meets Hatchet: Towards Modeling in Performance Analytics

Sergei Shudler, Lawrence Livermore National Laboratory, U.S.

Part 2 (February 25, 3:35 pm – 5:15 pm PST)

3:35-3:55 Performance Modeling of Graph Processing Workloads

Ana Lucia Varbanescu and Merijn Verstraaten, University of Amsterdam, Netherlands

4:00-4:20 Machine Learning–enabled Scalable Performance Prediction of Scientific Codes

Stephan Eidenbenz and Nandakishore Santhi, Los Alamos National Laboratory, U.S.

4:25-4:45 Automatic Application Performance Data Collection with Caliper and Adiak

David Boehme, Lawrence Livermore National Laboratory, U.S.

 

SIAM PP22 will be a hybrid conference, and many details are still to be sorted out. The full conference program can be viewed at: https://meetings.siam.org/program.cfm?CONFCODE=PP22. Stay tuned for news.

LIKWID 5.2.1 is out!

LIKWID stickersLIKWID 5.2.1 is out! This bugfix release addresses a lot of small and not-so-small issues:

  • Support for Intel Rocket Lake and AMD Zen3 variant (Family 19, Model 0x50)
  • Fix for perf_event multiplexing (important!)
  • Fix for a potential deadlock in MarkerAPI (thx @jenny-cheung)
  • Build and runtime fixes for Nvidia GPU backend, updates for CUDA test codes
  • likwid-bench “peakflops” kernel for ARMv8
  • Updates for AMD Zen1/2/3 event lists and groups
  • Support spaces in MarkerAPI region tags (thx @jrmadsen)
  • Use ‘online’ cpulist instead of ‘present’
  • Check PID if given through –perfpid
  • Intel Icelake: OFFCORE_RESPONSE events
  • likwid-mpirun: Set MPI type for SLURM automatically
  • likwid-mpirun: Fix skip mask for OpenMPI
  • Fix for triad_sve* benchmarks

You can download the new version from the FTP or GitHub.

Write-allocate evasion has finally arrived at Intel – or has it?

Intel’s Xeon Ice Lake CPU has finally caught up with AMD’s Rome in terms of full-chip peak performance and memory bandwidth. And, at long last, they have also fixed the Port 7 AGU problem I wrote about two years ago: Ice Lake now has two fully capable Store AGUs and an additional Store unit (although you can only do two stores concurrently if they go to the same cache line). There is one thing, however, that has appeared in recent years on ARM-based CPUs: automatic write-allocate elimination. We saw this for the first time on Cavium/Marvell’s ThunderX2 [1], although it was presumably present before on other ARM-based chips as well.

Basically what happens is that in situations where a write-allocate operation would be necessary, the hardware detects if the whole cache line is going to be overwritten. If it is, there’s no point in reading the cache line at all, and it can just be claimed in the cache right away. This saves 1/3 of the memory traffic on STREAM Copy, leading to a 50% performance gain if the saturated bandwidth doesn’t change. On the Fujitsu A64FX, this is not automatic but can be triggered by a special instruction, to the same effect [2]. Up to now, Intel followed a different path and supported nontemporal stores, which also avoid the write-allocate but in a different way: The cache line is stored “directly” to memory (actually through a write-combine buffer) so that it does not end up in the cache in the first place. Which strategy is better depends on the application: If the data is not needed soon, nontemporal stores may be better because the stored cache lines do not pollute the cache.

With Ice Lake, Intel provides for the first time a working mechanism for write-allocate evasion that’s similar to what the TX2 did. Intel calls it “SpecI2M,” and it’s described on slide 12 of a HotChips 2020 presentation:

SpecI2M optimization: Convert RFO to specI2M when memory subsystem is heavily loaded

  • Reduces mem bandwidth demand on streaming WLs that do full cache line writes (25% efficiency increase)

This is quite cryptic, and there’s a lot of speculation about what SpecI2M actually does, but it’s actually simple to figure out. likwid-bench is the perfect tool for that. The copy_avx512 kernel provided with it is as simple as it gets:

vmovapd    zmm1, [STR0 + GPR1 * 8]
vmovapd    zmm2, [STR0 + GPR1 * 8 + 64]
vmovapd    zmm3, [STR0 + GPR1 * 8 + 128]
vmovapd    zmm4, [STR0 + GPR1 * 8 + 192]
vmovapd    [STR1 + GPR1 * 8]     , zmm1
vmovapd    [STR1 + GPR1 * 8 + 64], zmm2
vmovapd    [STR1 + GPR1 * 8 + 128], zmm3
vmovapd    [STR1 + GPR1 * 8 + 192], zmm4

I’ve omitted the loop mechanics here (and don’t worry about the base/index registers; the likwid-bench code generator substitutes them with the real names). This is the version with normal stores (vmovapd). The copy_mem_avx512 kernel uses nontemporal stores (vmovntpd) instead.

Figure 1: STREAM copy standard stores (blue, red) vs. nontemporal stores on Xeon Platinum 8358

Figure 2: Ratio of actual vs. reported memory bandwidth

I’ve run scaling tests with these kernels using a 2 GB working set on a Xeon Platinum 8358 (Ice Lake 32 cores, 2.6 GHz base frequency, SNC off, THP=always, numa_balancing=0):

$ likwid-bench -t copy_avx512 -W S0:2GB:${NUM_THREADS}:1:2

For standard stores, Figure 1 shows the reported bandwidth in blue and the actual bus bandwidth (measured with likwid-perfctr) in red. With a few cores, the actual bandwidth is exactly 50% larger than reported, as expected. This can be seen in Figure 2 where I plotted this ratio (basically red divided by blue in Fig. 1). However, the ratio gradually goes down as the number of cores goes up. It’s as if the write-allocate is avoided, but not based on the (sole) fact that full cache lines are overwritten but based on the actual bus utilization! At 29 cores and above, the ratio is finally down at 1.0, so the write-allocate is fully gone.

I don’t like that behavior.

Figure 3: Reported bandwidth of the copy_avx512 kernel on the 38-core Ice Lake at KIT (HoreKa)

What I do like is a nice saturation curve like the one we see for NT stores (gray in Fig. 1). Not everyone can use NT stores, though; they only exist in SIMD variants (not quite, but for practical purposes they do), and you have to convince the compiler to use them unless you want to employ intrinsics or assembly. I looked for a way to switch off or alter the behavior of SpecI2M in the machine’s BIOS, but to no avail. [Update 2022: There is an MSR bit which can switch SpecI2M off or on; however, Intel does not disclose it publicly so we can’t include it in an open-source tool. Duh!]

Even worse, there are machines on which SpecI2M acts even more weirdly. The HoreKa cluster at KIT has 38-core Ice Lake Xeon Platinum 8368 CPUs. Figure 3 shows the reported bandwidth of the copy_avx512 loop vs. cores.  Here, the write-allocate evasion mechanism seems to kick in only beyond 30 cores, when the memory bandwidth is already very close to saturation (and it has been this way at 20 cores already). This means that in order to get the full socket performance, I have to use (almost) all cores although I could get away with much fewer if only the SpecI2M were more aggressive. I wonder what speaks against letting it fire already from core 1. What harm could it do? And why can I not just turn it off?

To make sure that this is not just a property of the specific benchmark setup, here are some additional observations:

  • The working set has no influence on the behavior. 10 GB instead of 2 GB make no difference whatsoever.
  • It’s not specific to STREAM Copy but it shows with all streaming loops that have store misses (STREAM Triad, Schönauer Triad, etc.). Of course, the higher the load/store ratio, the smaller the effect.
  • Turbo mode was switched off in these experiments, but it makes no difference if it’s on (apart from the higher single-core bandwidth, obviously).
  • It’s not a specific quirk of likwid-bench; the same behavior can be observed with code that was compiled from a high-level language, such as Jan Eitzinger’s TheBandwidthBenchmark or the original McCalpin STREAM.

Although it makes teaching people about memory traffic harder, I still see SpecI2M as a step in the right direction. We certainly have to ask additional questions: At which cache level is the cache line claimed? Does the write-allocate evasion also work with more realistic code such as a stencil smoother? Great questions. Stay tuned.

 

[1] J. Hofmann, C. L. Alappat, G. Hager, D. Fey, and G. Wellein: Bridging the Architecture Gap: Abstracting Performance-Relevant Properties of Modern Server Processors. Supercomputing Frontiers and Innovations 7(2), 54-78, July 2020. Available with Open Access. DOI: 10.14529/jsfi200204.

[2] C. L. Alappat, N. Meyer, J. Laukemann, T. Gruber, G. Hager, G. Wellein, and T. Wettig: ECM modeling and performance tuning of SpMV and Lattice QCD on A64FX. Concurrency and Computation: Practice and Experience, e6512 (2021). Available with Open Access. DOI: 10.1002/cpe.6512.