Research Project: SparCity: An Optimization and Co-design Framework for Sparse Computation
Loading...
Contributors
Funders
ID
EC.00144
Authors
Erten, Didem Unat
Faculty Member
Publications
Mixed and multi-precision SpMV for GPUs with row-wise precision selection
(IEEE Computer Society, 2022) Erten, Didem Unat; Koşar, Fahrican; Tezcan, Erhan; Torun, Tuğba; Kaya, Kamer; Department of Computer Engineering; Yes; College of Engineering
Sparse Matrix-Vector Multiplication (SpMV) is one of the key memory-bound kernels commonly used in industrial and scientific applications. To improve its data movement and benefit from higher compute rates, there are several efforts to utilize mixed precision on SpMV. Most of the prior-art focus on performing the entire SpMV in single-precision within a bigger context of an iterative solver (e.g., CG, GMRES). In this work, we are interested in a more fine-grained mixed-precision SpMV, where the level of precision is decided for each element in the matrix to be used in a single operation. We extend an existing entry-wise precision based approach by deciding precisions per row, motivated by the granularity of parallelism on a GPU where groups of threads process rows in CSR-based matrices. We propose mixed-precision CSR storage methods with row permutations and describe their greater efficiency and load-balancing compared to the existing method. We also consider a multi-precision case where single and double precision copies of the matrix are stored priorly and further extend our mixed-precision SpMV approach to comply with it. As such, we leverage a mixed-precision SpMV to obtain a multi-precision Jacobi method which is faster than yet almost as accurate as double-precision Jacobi implementation, and further evaluate a multi-precision Cardiac modeling algorithm. We demonstrate the effectiveness of the proposed SpMV methods on an extensive dataset of real-valued large sparse matrices from the SuiteSparse Matrix Collection using an NVIDIA V100 GPU.
A sparse tensor generator with efficient feature extraction
(Frontiers Media Sa, 2025) Torun, Tuğba; Taweel, Ameer; Erten, Didem Unat; Department of Computer Engineering; ParCoreLab (Parallel and Multicore Computing Laboratory); Yes; College of Engineering; Laboratory; Taweel, Ameer
Sparse tensor operations are increasingly important in diverse applications such as social networks, deep learning, diagnosis, crime, and review analysis. However, a major obstacle in sparse tensor research is the lack of large-scale sparse tensor datasets. Another challenge lies in analyzing sparse tensor features, which are essential not only for understanding the nonzero pattern but also for selecting the most suitable storage format, decomposition algorithm, and reordering methods. However, due to the large size of real-world tensors, even extracting these features can be computationally expensive without careful optimization. To address these limitations, we have developed a smart sparse tensor generator that replicates key characteristics of real sparse tensors. Additionally, we propose efficient methods for extracting a comprehensive set of sparse tensor features. The effectiveness of our generator is validated through the quality of extracted features and the performance of decomposition on the generated tensors. Both the sparse tensor feature extractor and the tensor generator are open source with all the artifacts available at https://github.com/sparcityeu/FeaTensor and https://github.com/sparcityeu/GenTensor, respectively.
Bringing order to sparsity: a sparse matrix reordering study on multicore CPUs
(Association for Computing Machinery, Inc, 2023) Düzakın, Emre; Erten, Didem Unat; Torun, Tuğba; Trotter, James D.; Ekmekçibaşı, Sinan; Langguth, Johannes; Ilic, Aleksandar; Department of Computer Engineering; Graduate School of Sciences and Engineering; Yes; College of Engineering; GRADUATE SCHOOL OF SCIENCES AND ENGINEERING
Many real-world computations involve sparse data structures in the form of sparse matrices. A common strategy for optimizing sparse matrix operations is to reorder a matrix to improve data locality. However, it's not always clear whether reordering will provide benefits over the unordered matrix, as its effectiveness depends on several factors, such as structural features of the matrix, the reordering algorithm and the hardware that is used. This paper aims to establish the relationship between matrix reordering algorithms and the performance of sparse matrix operations. We thoroughly evaluate six different matrix reordering algorithms on 490 matrices across eight multicore architectures, focusing on the commonly used sparse matrix-vector multiplication (SpMV) kernel. We find that reordering based on graph partitioning provides better SpMV performance than the alternatives for a large majority of matrices, and that the resulting performance is explained through a combination of data locality and load balancing concerns. © 2023 Owner/Author(s).
Precise event sampling-based data locality tools for AMD multicore architectures
(Wiley, 2023) Sasongko, Muhammad Aditya; Erten, Didem Unat; Chabbi, Milind; Kelly, Paul H.; Department of Computer Engineering; Yes; College of Engineering
We propose ComDetective+, an inter-thread communication analyzer, and ReuseTracker+, a reuse distance analyzer, that leverage the hardware features in AMD processors to support low-overhead profiling. Both tools employ the instruction-based sampling (IBS) facility and debug registers in AMD processors to detect inter-thread communication and data reuse. Different from prior arts, ComDetective+ differentiates the communication into true and false sharing, and ReuseTracker+ measures reuse distance in private and shared caches by also considering cache line invalidation with low overhead. Both tools can attribute the communications and reuses to source code lines. To our knowledge these tools are two of the few profiling tools designed specifically for AMD x86 architectures using IBS. Our tools are timely and relevant considering the rise in numbers of AMD processor based data centers and HPC systems. We perform experiments to evaluate the accuracy and overheads of the proposed tools on an AMD machine with two-socket EPYC 7352 processors. ComDetective+ exhibits high accuracy while introducing 5.14xruntime and 1.4x memory overheads. ReuseTracker+ also displays high accuracy, which is 95%, with 11.76x runtime and 1.46x memory overheads. These overheads are much lower than the overheads of existing simulators and code instrumentation-based tools. Lastly, we demonstrate the usage of the tools by having COMDETECTIVE+ and REUSETRACKER+ facilitate the code refactoring of two data mining benchmarks to improve their performance by up to 29%.
