ALTO: Adaptive Linearized Storage of Sparse Tensors - Helal, Ahmed E; Laukemann, Jan; Checconi, Fabio; Tithi, Jesmin Jahan; Ranadive, Teresa; Petrini, Fabrizio; Choi, Jeewhan (ICS '21: 2021 International Conference on Supercomputing, 2021)
The analysis of high-dimensional sparse data is becoming increasingly popular in many important domains. However, real-world sparse tensors are challenging to process due to their irregular shapes and data distributions. We propose the Adaptive Linearized Tensor Order (ALTO) format, a novel mode-agnostic (general) representation that keeps neighboring nonzero elements in the multi-dimensional space close to each other in memory. To generate the indexing metadata, ALTO uses an adaptive bit encoding scheme that trades off index computations for lower memory usage and more effective use of memory bandwidth. Moreover, by decoupling its sparse representation from the irregular spatial distribution of nonzero elements, ALTO eliminates the workload imbalance and greatly reduces the synchronization overhead of tensor computations. As a result, the parallel performance of ALTO-based tensor operations becomes a function of their inherent data reuse. On a gamut of tensor datasets, ALTO outperforms an oracle that selects the best state-of-the-art format for each dataset, when used in key tensor decomposition operations. Specifically, ALTO achieves a geometric mean speedup of 8x over the best mode-agnostic (coordinate and hierarchical coordinate) formats, while delivering a geometric mean compression ratio of 4.x relative to the best mode-specific (compressed sparse fiber) formats.<br
Keywords: Sparse tensors; tensor decomposition; MTTKRP; multi-core CPU

Automated instruction stream throughput prediction for intel and AMD microarchitectures - Laukemann, Jan; Hammer, Julian; Hofmann, Johannes; Hager, Georg; Wellein, Gerhard (Proceedings of PMBS 2018: Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems, Held in conjunction with SC 2018: The International Conference for High Performance Computing, Networking, Storage and Analysis, 2019)
An accurate prediction of scheduling and execution of instruction streams is a necessary prerequisite for predicting the in-core performance behavior of throughput-bound loop kernels on out-of-order processor architectures. Such predictions are an indispensable component of analytical performance models, such as the Roofline and the Execution-Cache-Memory (ECM) model, and allow a deep understanding of the performance-relevant interactions between hardware architecture and loop code. We present the Open Source Architecture Code Analyzer (OSACA), a static analysis tool for predicting the execution time of sequential loops comprising x86 instructions under the assumption of an infinite first-level cache and perfect out-of-order scheduling. We show the process of building a machine model from available documentation and semi-automatic benchmarking, and carry it out for the latest Intel Skylake and AMD Zen micro-architectures. To validate the constructed models, we apply them to several assembly kernels and compare runtime predictions with actual measurements. Finally we give an outlook on how the method may be generalized to new architectures.
Created from Fastlane, Scopus look-up
Keywords: architecture analysis; benchmarking; performance engineering; performance modeling; static analysis

Automatic Throughput and Critical Path Analysis of x86 and ARM Assembly Kernels - Laukemann, Jan; Hammer, Julian; Hager, Georg; Wellein, Gerhard (10th IEEE/ACM Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems, PMBS 2019, 2019)
Keywords: benchmarking; architecture analysis; performance modeling; performance engineering; static analysis

CloverLeaf on Intel Multi-Core CPUs: A Case Study in Write-Allocate Evasion - Laukemann, Jan; Gruber, Thomas; Hager, Georg; Oryspayev, Dossay; Wellein, Gerhard (2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2024)
In this paper we analyze the MPI-only version of the CloverLeaf code from the SPEChpc 2021 benchmark suite on recent Intel Xeon "Ice Lake" and "Sapphire Rapids" server CPUs. We observe peculiar breakdowns in performance when the number of processes is prime. Investigating this effect, we create first-principles data traffic models for each of the stencil-like hotspot loops. With application measurements and microbenchmarks to study memory data traffic behavior, we can connect the breakdowns to SpecI2M, a new write-allocate evasion feature in current Intel CPUs. For serial and full-node cases we are able to predict the memory data volume analytically with an error of a few percent. We find that if the number of processes is prime, SpecI2M fails to work properly, which we can attribute to short inner loops emerging from the one-dimensional domain decomposition in this case. We can also rule out other possible causes of the prime number effect, such as breaking layer conditions, MPI communication overhead, and load imbalance.<br
CRIS-Team Scopus Importer:2024-07-26
Keywords: Sapphire Rapids; SPEChpc 2021; Ice Lake; non-temporal stores; SpecI2M; write allocate; CloverLeaf

Core-Level Performance Engineering with the Open-Source Architecture Code Analyzer (OSACA) and the Compiler Explorer - Laukemann, Jan; Hager, Georg (ICPE 2023 - Companion of the 2023 ACM/SPEC International Conference on Performance Engineering, 2023)
While many developers put a lot of effort into optimizing large-scale parallelism, they often neglect the importance of an efficient serial code. Even worse, slow serial code tends to scale very well, hiding the fact that resources are wasted because no definite hardware performance limit ("bottleneck") is exhausted. This tutorial conveys the required knowledge to develop a thorough understanding of the interactions between software and hardware on the level of a single CPU core and the lowest memory hierarchy level (the L1 cache). We introduce general out-of-order core architectures and their typical performance bottlenecks using modern x86-64 (Intel Ice Lake) and ARM (Fujitsu A64FX) processors as examples. We then go into detail about x86 and AArch64 assembly code, specifically including vectorization (SIMD), pipeline utilization, critical paths, and loop-carried dependencies. We also demonstrate performance analysis and performance engineering using the Open-Source Architecture Code Analyzer (OSACA) in combination with a dedicated instance of the well-known Compiler Explorer. Various hands-on exercises allow attendees to make their own experiments and measurements and identify in-core performance bottlenecks. Furthermore, we show real-life use cases to emphasize how profitable in-core performance engineering can be.
CRIS-Team Scopus Importer:2023-05-26
Keywords: in-core; performance engineering; performance modeling

Dynamic Tensor Linearization and Time Slicing for Efficient Factorization of Infinite Data Streams - Soh, Yongseok; Helal, Ahmed E.; Checconi, Fabio; Laukemann, Jan; Tithi, Jesmin Jahan; Ranadive, Teresa; Petrini, Fabrizio; Choi, Jee W. (2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2023)
Streaming tensor factorization is an effective tool for unsupervised analysis of time-evolving sparse data, which emerge in many critical domains such as cybersecurity and trend analysis. In contrast to traditional tensors, time-evolving tensors demonstrate extreme sparsity and sparsity variation over time, resulting in irregular memory access and inefficient use of parallel computing resources. Additionally, due to the prohibitive cost of dynamically generating compressed sparse tensor formats, the state-of-the-art approaches process streaming tensors in a raw form that fails to capture data locality and suffers from high synchronization cost. To address these challenges, we propose a new dynamic tensor linearization framework that quickly encodes streaming multi-dimensional data on-the-fly in a compact representation, which has substantially lower memory usage and higher data reuse and parallelism than the original raw data. This is achieved by using a spatial sketching algorithm that keeps all incoming nonzero elements but remaps them into a tensor sketch with considerably reduced multi-dimensional image space. Moreover, we present a dynamic time slicing mechanism that uses variable-width time slices (instead of the traditional fixed-width) to balance the frequency of factor updates and the utilization of computing resources. We demonstrate the efficacy of our framework by accelerating two high-performance streaming tensor algorithms, namely, CP-stream and spCP-stream, and significantly improve their performance for a range of real-world streaming tensors. On a modern 56-core CPU, our framework achieves 10.3 − 11× and 6.4 − 7.2× geometric-mean speedup for the CP-stream and spCP-stream algorithms, respectively.<br

Efficient, out-of-memory sparse MTTKRP on massively parallel architectures - Nguyen, Andy; Helal, Ahmed E.; Checconi, Fabio; Laukemann, Jan; Tithi, Jesmin Jahan; Soh, Yongseok; Ranadive, Teresa; Petrini, Fabrizio; Choi, Jee W. (Proceedings of the International Conference on Supercomputing, 2022)
Tensor decomposition (TD) is an important method for extracting latent information from high-dimensional (multi-modal) sparse data. This study presents a novel framework for accelerating fundamental TD operations on massively parallel GPU architectures. In contrast to prior work, the proposed Blocked Linearized Coordinate (BLCO) format enables efficient out-of-memory computation of tensor algorithms using a unified implementation that works on a single tensor copy. Our adaptive blocking and linearization strategies not only meet the resource constraints of GPU devices, but also accelerate data indexing, eliminate control-flow and memory-access irregularities, and reduce kernel launching overhead. To address the substantial synchronization cost on GPUs, we introduce an opportunistic conflict resolution algorithm, in which threads collaborate instead of contending on memory access to discover and resolve their conflicting updates on-the-fly, without keeping any auxiliary information or storing non-zero elements in specific mode orientations. As a result, our framework delivers superior in-memory performance compared to prior state-of-the-art, and is the only framework capable of processing out-of-memory tensors. On the latest Intel and NVIDIA GPUs, BLCO achieves 2.12-2.6X geometric-mean speedup (with up to 33.35X speedup) over the state-of-the-art mixed-mode compressed sparse fiber (MM-CSF) on a range of real-world sparse tensors.
Created from Fastlane, Scopus look-up
Keywords: GPU; MTTKRP; Parallel performance; Sparse formats; Sparse tensors; Tensor decomposition

Execution-Cache-Memory modeling and performance tuning of sparse matrix-vector multiplication and Lattice quantum chromodynamics on A64FX - Alappat, Christie; Meyer, Nils; Laukemann, Jan; Gruber, Thomas; Hager, Georg; Wellein, Gerhard; Wettig, Tilo (Concurrency and Computation-Practice & Experience, 2021)
Keywords: A64FX; ECM model; Lattice quantum chromodynamics; sparse matrix-vector multiplication

MD-Bench: A performance-focused prototyping harness for state-of-the-art short-range molecular dynamics algorithms - Ravedutti Lucio Machado, Rafael; Eitzinger, Jan; Laukemann, Jan; Hager, Georg; Köstler, Harald; Wellein, Gerhard (Future Generation Computer Systems-The International Journal of Grid Computing Theory Methods and Applications, 2023)
Molecular dynamics (MD) simulations provide considerable benefits for the investigation and experimentation of systems at atomic level. Their usage is widespread into several research fields, but their system size and timescale are crucially limited by the available computing power. Performance engineering of MD kernels is therefore critical to understand their bottlenecks and investigate possible improvements. For that reason, we developed MD-Bench, a performance-focused prototyping harness for short-range MD kernels that implements state-of-the-art algorithms from multiple production applications such as LAMMPS and GROMACS. The MD-Bench source code is simple, understandable, and extensible, and therefore well suited for benchmarking, teaching, and researching MD algorithms. In this paper we introduce MD-Bench, describe its design, structure, and implemented algorithms. Finally, we show five use-cases of MD-Bench and describe how these are useful to gain a deeper understanding of the performance of MD kernels.<br

MD-Bench: A performance-focused prototyping harness for state-of-the-art short-range molecular dynamics algorithms - Ravedutti Lucio Machado, Rafael; Eitzinger, Jan; Laukemann, Jan; Hager, Georg; Köstler, Harald; Wellein, Gerhard (Future Generation Computer Systems-The International Journal of Grid Computing Theory Methods and Applications, 2023)
Molecular dynamics (MD) simulations provide considerable benefits for the investigation and experimentation of systems at atomic level. Their usage is widespread into several research fields, but their system size and timescale are crucially limited by the available computing power. Performance engineering of MD kernels is therefore critical to understand their bottlenecks and investigate possible improvements. For that reason, we developed MD-Bench, a performance-focused prototyping harness for short-range MD kernels that implements state-of-the-art algorithms from multiple production applications such as LAMMPS and GROMACS. The MD-Bench source code is simple, understandable, and extensible, and therefore well suited for benchmarking, teaching, and researching MD algorithms. In this paper we introduce MD-Bench, describe its design, structure, and implemented algorithms. Finally, we show five use-cases of MD-Bench and describe how these are useful to gain a deeper understanding of the performance of MD kernels.<br

Microarchitectural comparison and in-core modeling of state-of-the-art CPUs: Grace, Sapphire Rapids, and Genoa - Laukemann, Jan; Hager, Georg; Wellein, Gerhard (SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2024)
With Nvidia’s release of the Grace Superchip, all three big semiconductor companies in HPC (AMD, Intel, Nvidia) are currently competing in the race for the best CPU. In this work we analyze the performance of these state-of-the-art CPUs and create an accurate in-core performance model for their microarchitectures Zen 4, Golden Cove, and Neoverse V2, extending the Open Source Architecture Code Analyzer (OSACA) tool and comparing it with LLVM-MCA. Starting from the peculiarities and up- and downsides of a single core, we extend our comparison by a variety of microbenchmarks and the capabilities of a full node. The "write-allocate (WA) evasion" feature, which can automatically reduce the memory traffic caused by write misses, receives special attention; we show that the Grace Superchip has a next-to-optimal implementation of WA evasion, and that the only way to avoid write allocates on Zen 4 is the explicit use of non-temporal store
Keywords: Semiconductor device modeling; Analytical models; Solid modeling; Microarchitecture; Codes; Accuracy; Runtime; Data models; Servers; Standards

Performance Modeling of Streaming Kernels and Sparse Matrix-Vector Multiplication on A64FX - Alappat, Christie; Laukemann, Jan; Gruber, Thomas; Hager, Georg; Wellein, Gerhard; Meyer, Nils; Wettig, Tilo (Proceedings of PMBS 2020: Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems, 2020)
The A64FX CPU powers the current #1 supercomputer on the Top500 list. Although it is a traditional cache-based multicore processor, its peak performance and memory bandwidth rival accelerator devices. Generating efficient code for such a new architecture requires a good understanding of its performance features. Using these features, we construct the Execution-Cache-Memory (ECM) performance model for the A64FX processor in the FX700 supercomputer and validate it using streaming loops. We also identify architectural peculiarities and derive optimization hints. Applying the ECM model to sparse matrix-vector multiplication (SpMV), we motivate why the CRS matrix storage format is inappropriate and how the SELL-C-σ format with suitable code optimizations can achieve bandwidth saturation for SpMV.
CRIS-Team Scopus Importer:2021-04-19
Keywords: A64FX; ECM model; sparse matrix-vector multiplication