Kadir Akbudak
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Kadir Akbudak has a total of 44 co-authors. Here are the top co-authors by number of shared publications:
- David Keyes
King Abdullah University of Science and Technology
7 shared publications - Hatem Ltaief
King Abdullah University of Science and Technology (KAUST)
7 shared publications Cevdet Aykanat
Bilkent University, Ankara, Turkey
5 shared publications- Aleksandr Mikhalev
Skolkovo Institute of Science and Technology Moscow
2 shared publications - Cevdet Aykanat
Department of Computer Engineering, Bilkent University, Ankara, Turkey
2 shared publications Oguz Selvitopi
Bilkent University, Ankara, Turkey
2 shared publications
Latest Publications
- Open Access
- 26 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 44-54
Balancing Throughput and Energy: Power Provisioning Case Studies for CPU and GPU Workloads
- 26 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 44-54
Open AccessBalancing Throughput and Energy: Power Provisioning Case Studies for CPU and GPU Workloads
- 27 September 2024
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 39 (1) , 3-17
Evolution of the SLATE linear algebra library
SLATE (Software for Linear Algebra Targeting Exascale) is a distributed, dense linear algebra library targeting both CPU-only and GPU-accelerated systems, developed over the course of the Exascale Computing Project (ECP). While it began with several documents setting out its initial design, significant design changes occurred throughout its development. In some cases, these were anticipated: an early version used a simple consistency flag that was later replaced with a full-featured consistency protocol. In other cases, performance limitations and software and hardware changes prompted a redesign. Sequential communication tasks were parallelized; host-to-host MPI calls were replaced with GPU device-to-device MPI calls; more advanced algorithms such as Communication Avoiding LU and the Random Butterfly Transform (RBT) were introduced. Early choices that turned out to be cumbersome, error prone, or inflexible have been replaced with simpler, more intuitive, or more flexible designs. Applications have been a driving force, prompting a lighter weight queue class, nonuniform tile sizes, and more flexible MPI process grids. Of paramount importance has been building a portable library that works across several different GPU architectures – AMD, Intel, and NVIDIA – while keeping a clean and maintainable codebase. Here we explore the evolving design choices and their effects, both in terms of performance and software sustainability.
- 27 September 2024
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 39 (1) , 3-17
Evolution of the SLATE linear algebra library
SLATE (Software for Linear Algebra Targeting Exascale) is a distributed, dense linear algebra library targeting both CPU-only and GPU-accelerated systems, developed over the course of the Exascale Computing Project (ECP). While it began with several documents setting out its initial design, significant design changes occurred throughout its development. In some cases, these were anticipated: an early version used a simple consistency flag that was later replaced with a full-featured consistency protocol. In other cases, performance limitations and software and hardware changes prompted a redesign. Sequential communication tasks were parallelized; host-to-host MPI calls were replaced with GPU device-to-device MPI calls; more advanced algorithms such as Communication Avoiding LU and the Random Butterfly Transform (RBT) were introduced. Early choices that turned out to be cumbersome, error prone, or inflexible have been replaced with simpler, more intuitive, or more flexible designs. Applications have been a driving force, prompting a lighter weight queue class, nonuniform tile sizes, and more flexible MPI process grids. Of paramount importance has been building a portable library that works across several different GPU architectures – AMD, Intel, and NVIDIA – while keeping a clean and maintainable codebase. Here we explore the evolving design choices and their effects, both in terms of performance and software sustainability.
- Open Access
- 3 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-13
Leveraging the High Bandwidth of Last-Level Cache for HPC Seismic Imaging Applications
We solve the 3D acoustic wave equation using the finite-difference time-domain (FDTD) formulation in both first and second order. The FDTD approach is expressed as a stencil-based computational scheme with a long-range discretization, i.e., 8th order in space and 2nd order in time, which is routinely used in the oil and gas industry and environmental geophysics for high subsurface imaging fidelity purposes. Absorbing Boundary Conditions (ABCs) are employed to attenuate reflections from artificial boundaries. The high order discretization engenders extensive data movement across the memory subsystem and may consequently impact the kernel throughput due to the inherent memory-bound behavior of the stencil operator, especially on systems facing memory starvation. The first-order formulation of the 3D acoustic equation further exacerbates this phenomenon because it calculates both the pressure and velocity fields, which corresponds to 1.6X the memory footprint of the second-order formulation. To address this memory bottleneck, we design, implement, and deploy the multicore wavefront diamond tiling with temporal blocking (MWD-TB) to boost the performance of seismic wavefield modeling by exploiting spatial and temporal data reuse. MWD-TB leverages the large capacity of last-level cache (LLC) of modern x86 systems and extracts high bandwidth memory from the underlying architecture. We demonstrate the numerical accuracy of MWD-TB on the Salt3D model from the Society of Exploration Geophysicists (SEG). Our MWD-TB implementations for the first- and second-order FDTD formulations achieve speedups of up to 3.5X and 3X on a large grid size on AMD systems equipped with large LLC, respectively, compared to the traditional spatial blocking method alone.
- 3 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-13
Open AccessLeveraging the High Bandwidth of Last-Level Cache for HPC Seismic Imaging Applications
We solve the 3D acoustic wave equation using the finite-difference time-domain (FDTD) formulation in both first and second order. The FDTD approach is expressed as a stencil-based computational scheme with a long-range discretization, i.e., 8th order in space and 2nd order in time, which is routinely used in the oil and gas industry and environmental geophysics for high subsurface imaging fidelity purposes. Absorbing Boundary Conditions (ABCs) are employed to attenuate reflections from artificial boundaries. The high order discretization engenders extensive data movement across the memory subsystem and may consequently impact the kernel throughput due to the inherent memory-bound behavior of the stencil operator, especially on systems facing memory starvation. The first-order formulation of the 3D acoustic equation further exacerbates this phenomenon because it calculates both the pressure and velocity fields, which corresponds to 1.6X the memory footprint of the second-order formulation. To address this memory bottleneck, we design, implement, and deploy the multicore wavefront diamond tiling with temporal blocking (MWD-TB) to boost the performance of seismic wavefield modeling by exploiting spatial and temporal data reuse. MWD-TB leverages the large capacity of last-level cache (LLC) of modern x86 systems and extracts high bandwidth memory from the underlying architecture. We demonstrate the numerical accuracy of MWD-TB on the Salt3D model from the Society of Exploration Geophysicists (SEG). Our MWD-TB implementations for the first- and second-order FDTD formulations achieve speedups of up to 3.5X and 3X on a large grid size on AMD systems equipped with large LLC, respectively, compared to the traditional spatial blocking method alone.
- 20 November 2023
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 38 (3) , 210-224
Hypergraph-based locality-enhancing methods for graph operations in Big Data applications
The need for speeding up data analytics increases inevitably due to the need for extracting valuable information from social media, data generated by smart devices with sensors, patterns of people’s communications over the web, items viewed and bought by global-scale customers, cloud applications, etc., all of which take part in the “Big Data.” Such kind of interaction data is very well represented as sparse graphs to enable the graph analytics, which requires efficient underlying kernels. The breadth-first search (BFS)-based traversal is a commonly used kernel in graph algorithms such as the betweenness centrality algorithm for centrality analysis. In this work, we focus on parallel BFS operations and propose hypergraph-based combinatorial models that aim at reducing cache misses and hence exploiting data locality during the parallel BFS operations. Our models are based on finding new vertex visit orders so that locality in accessing the data associated with vertices is exploited. Experiments on graphs arising in a wide range of applications show that our proposed models achieve on average 9% performance improvement in the CPU-based Ligra data analytics framework.
- 20 November 2023
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 38 (3) , 210-224
Hypergraph-based locality-enhancing methods for graph operations in Big Data applications
The need for speeding up data analytics increases inevitably due to the need for extracting valuable information from social media, data generated by smart devices with sensors, patterns of people’s communications over the web, items viewed and bought by global-scale customers, cloud applications, etc., all of which take part in the “Big Data.” Such kind of interaction data is very well represented as sparse graphs to enable the graph analytics, which requires efficient underlying kernels. The breadth-first search (BFS)-based traversal is a commonly used kernel in graph algorithms such as the betweenness centrality algorithm for centrality analysis. In this work, we focus on parallel BFS operations and propose hypergraph-based combinatorial models that aim at reducing cache misses and hence exploiting data locality during the parallel BFS operations. Our models are based on finding new vertex visit orders so that locality in accessing the data associated with vertices is exploited. Experiments on graphs arising in a wide range of applications show that our proposed models achieve on average 9% performance improvement in the CPU-based Ligra data analytics framework.
- Open Access
- 22 May 2020
- Published by Springer Nature
- Vol. 12151, 209-229
Solving Acoustic Boundary Integral Equations Using High Performance Tile Low-Rank LU Factorization
We design and develop a new high performance implementation of a fast direct LU-based solver using low-rank approximations on massively parallel systems. The LU factorization is the most time-consuming step in solving systems of linear equations in the context of analyzing acoustic scattering from large 3D objects. The matrix equation is obtained by discretizing the boundary integral of the exterior Helmholtz problem using a higher-order Nyström scheme. The main idea is to exploit the inherent data sparsity of the matrix operator by performing local tile-centric approximations while still capturing the most significant information. In particular, the proposed LU-based solver leverages the Tile Low-Rank (TLR) data compression format as implemented in the Hierarchical Computations on Manycore Architectures () library to decrease the complexity of “classical” dense direct solvers from cubic to quadratic order. We taskify the underlying boundary integral kernels to expose fine-grained computations. We then employ the dynamic runtime system to orchestrate the scheduling of computational tasks on shared and distributed-memory systems. The resulting asynchronous execution permits to compensate for the load imbalance due to the heterogeneous ranks, while mitigating the overhead of data motion. We assess the robustness of our TLR LU-based solver and study the qualitative impact when using different numerical accuracies. The new TLR LU factorization outperforms the state-of-the-art dense factorizations by up to an order of magnitude on various parallel systems, for analysis of scattering from large-scale 3D synthetic and real geometries.
- 22 May 2020
- Published by Springer Nature
- Vol. 12151, 209-229
Open AccessSolving Acoustic Boundary Integral Equations Using High Performance Tile Low-Rank LU Factorization
We design and develop a new high performance implementation of a fast direct LU-based solver using low-rank approximations on massively parallel systems. The LU factorization is the most time-consuming step in solving systems of linear equations in the context of analyzing acoustic scattering from large 3D objects. The matrix equation is obtained by discretizing the boundary integral of the exterior Helmholtz problem using a higher-order Nyström scheme. The main idea is to exploit the inherent data sparsity of the matrix operator by performing local tile-centric approximations while still capturing the most significant information. In particular, the proposed LU-based solver leverages the Tile Low-Rank (TLR) data compression format as implemented in the Hierarchical Computations on Manycore Architectures () library to decrease the complexity of “classical” dense direct solvers from cubic to quadratic order. We taskify the underlying boundary integral kernels to expose fine-grained computations. We then employ the dynamic runtime system to orchestrate the scheduling of computational tasks on shared and distributed-memory systems. The resulting asynchronous execution permits to compensate for the load imbalance due to the heterogeneous ranks, while mitigating the overhead of data motion. We assess the robustness of our TLR LU-based solver and study the qualitative impact when using different numerical accuracies. The new TLR LU factorization outperforms the state-of-the-art dense factorizations by up to an order of magnitude on various parallel systems, for analysis of scattering from large-scale 3D synthetic and real geometries.
- 19 May 2020
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 34 (4) , 377-393
Asynchronous computations for solving the acoustic wave propagation equation
The aim of this study is to design and implement an asynchronous computational scheme for solving the acoustic wave propagation equation with absorbing boundary conditions (ABCs) in the context of seismic imaging applications. While the convolutional perfectly matched layer (CPML) is typically used for ABCs in the oil and gas industry, its formulation further stresses memory accesses and decreases the arithmetic intensity at the physical domain boundaries. The challenges with CPML are twofold: (1) the strong, inherent data dependencies imposed on the explicit time-stepping scheme render asynchronous time integration cumbersome and (2) the idle time is further exacerbated by the load imbalance introduced among processing units. In fact, the CPML formulation of the ABCs requires expensive synchronization points, which may hinder the parallel performance of the overall asynchronous time integration. In particular, when deployed in conjunction with the multicore-optimized wavefront diamond temporal blocking (MWD-TB) approach for the inner domain points, it results in a major performance slow down. To relax CPML’s synchrony and mitigate the resulting load imbalance, we embed CPML’s calculation into MWD-TB’s inner loop and carry on the time integration with fine-grained computations in an asynchronous, holistic way. This comes at the price of storing transient results to alleviate dependencies from critical data hazards while maintaining the numerical accuracy of the original scheme. Performance and scalability results on various x86 architectures demonstrate the superiority of MWD-TB with CPML support against the standard spatial blocking on various grid sizes. To our knowledge, this is the first practical study that highlights the consolidation of CPML ABCs with asynchronous temporal blocking stencil computations.
- 19 May 2020
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 34 (4) , 377-393
Asynchronous computations for solving the acoustic wave propagation equation
The aim of this study is to design and implement an asynchronous computational scheme for solving the acoustic wave propagation equation with absorbing boundary conditions (ABCs) in the context of seismic imaging applications. While the convolutional perfectly matched layer (CPML) is typically used for ABCs in the oil and gas industry, its formulation further stresses memory accesses and decreases the arithmetic intensity at the physical domain boundaries. The challenges with CPML are twofold: (1) the strong, inherent data dependencies imposed on the explicit time-stepping scheme render asynchronous time integration cumbersome and (2) the idle time is further exacerbated by the load imbalance introduced among processing units. In fact, the CPML formulation of the ABCs requires expensive synchronization points, which may hinder the parallel performance of the overall asynchronous time integration. In particular, when deployed in conjunction with the multicore-optimized wavefront diamond temporal blocking (MWD-TB) approach for the inner domain points, it results in a major performance slow down. To relax CPML’s synchrony and mitigate the resulting load imbalance, we embed CPML’s calculation into MWD-TB’s inner loop and carry on the time integration with fine-grained computations in an asynchronous, holistic way. This comes at the price of storing transient results to alleviate dependencies from critical data hazards while maintaining the numerical accuracy of the original scheme. Performance and scalability results on various x86 architectures demonstrate the superiority of MWD-TB with CPML support against the standard spatial blocking on various grid sizes. To our knowledge, this is the first practical study that highlights the consolidation of CPML ABCs with asynchronous temporal blocking stencil computations.
- 1 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 25-32
Performance Analysis of Tile Low-Rank Cholesky Factorization Using PaRSEC Instrumentation Tools
This paper highlights the necessary development of new instrumentation tools within the PaRSE task-based runtime system to leverage the performance of low-rank matrix computations. In particular, the tile low-rank (TLR) Cholesky factorization represents one of the most critical matrix operations toward solving challenging large-scale scientific applications. The challenge resides in the heterogeneous arithmetic intensity of the various computational kernels, which stresses PaRSE's dynamic engine when orchestrating the task executions at runtime. Such irregular workload imposes the deployment of new scheduling heuristics to privilege the critical path, while exposing task parallelism to maximize hardware occupancy. To measure the effectiveness of PaRSE's engine and its various scheduling strategies for tackling such workloads, it becomes paramount to implement adequate performance analysis and profiling tools tailored to fine-grained and heterogeneous task execution. This permits us not only to provide insights from PaRSE, but also to identify potential applications' performance bottlenecks. These instrumentation tools may actually foster synergism between applications and PaRSE developers for productivity as well as high-performance computing purposes. We demonstrate the benefits of these amenable tools, while assessing the performance of TLR Cholesky factorization from data distribution, communication-reducing and synchronization-reducing perspectives. This tool-assisted performance analysis results in three major contributions: a new hybrid data distribution, a new hierarchical TLR Cholesky algorithm, and a new performance model for tuning the tile size. The new TLR Cholesky factorization achieves an 8X performance speedup over existing implementations on massively parallel supercomputers, toward solving large-scale 3D climate and weather prediction applications.
- 1 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 25-32
Performance Analysis of Tile Low-Rank Cholesky Factorization Using PaRSEC Instrumentation Tools
This paper highlights the necessary development of new instrumentation tools within the PaRSE task-based runtime system to leverage the performance of low-rank matrix computations. In particular, the tile low-rank (TLR) Cholesky factorization represents one of the most critical matrix operations toward solving challenging large-scale scientific applications. The challenge resides in the heterogeneous arithmetic intensity of the various computational kernels, which stresses PaRSE's dynamic engine when orchestrating the task executions at runtime. Such irregular workload imposes the deployment of new scheduling heuristics to privilege the critical path, while exposing task parallelism to maximize hardware occupancy. To measure the effectiveness of PaRSE's engine and its various scheduling strategies for tackling such workloads, it becomes paramount to implement adequate performance analysis and profiling tools tailored to fine-grained and heterogeneous task execution. This permits us not only to provide insights from PaRSE, but also to identify potential applications' performance bottlenecks. These instrumentation tools may actually foster synergism between applications and PaRSE developers for productivity as well as high-performance computing purposes. We demonstrate the benefits of these amenable tools, while assessing the performance of TLR Cholesky factorization from data distribution, communication-reducing and synchronization-reducing perspectives. This tool-assisted performance analysis results in three major contributions: a new hybrid data distribution, a new hierarchical TLR Cholesky algorithm, and a new performance model for tuning the tile size. The new TLR Cholesky factorization achieves an 8X performance speedup over existing implementations on massively parallel supercomputers, toward solving large-scale 3D climate and weather prediction applications.
- 10 August 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 30 (2) , 445-458
Spatiotemporal Graph and Hypergraph Partitioning Models for Sparse Matrix-Vector Multiplication on Many-Core Architectures
There exist graph/hypergraph partitioning-based row/column reordering methods for encoding either spatial or temporal locality separately for sparse matrix-vector multiplication (SpMV) operations. Spatial and temporal hypergraph models in these methods are extended to encapsulate both spatial and temporal localities based on cut/uncut net categorization obtained from vertex partitioning. These extensions of spatial and temporal hypergraph models encode the spatial locality primarily and the temporal locality secondarily, and vice-versa, respectively. However, the literature lacks models that simultaneously encode both spatial and temporal localities utilizing only vertex partitioning for further improving the performance of SpMV on shared-memory architectures. In order to fill this gap, we propose a novel spatiotemporal hypergraph model that leads to a one-phase spatiotemporal reordering method which encodes both types of locality simultaneously. We also propose a framework for spatiotemporal methods which encodes both types of locality in two dependent phases and two separate phases. The validity of the proposed spatiotemporal models and methods are tested on a wide range of sparse matrices and the experiments are performed on both a 60-core Intel Xeon Phi processor and a Xeon processor. Results show the validity of the methods via almost doubling the Gflop/s performance through enhancing data locality in parallel SpMV operations.
- 10 August 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 30 (2) , 445-458
Spatiotemporal Graph and Hypergraph Partitioning Models for Sparse Matrix-Vector Multiplication on Many-Core Architectures
There exist graph/hypergraph partitioning-based row/column reordering methods for encoding either spatial or temporal locality separately for sparse matrix-vector multiplication (SpMV) operations. Spatial and temporal hypergraph models in these methods are extended to encapsulate both spatial and temporal localities based on cut/uncut net categorization obtained from vertex partitioning. These extensions of spatial and temporal hypergraph models encode the spatial locality primarily and the temporal locality secondarily, and vice-versa, respectively. However, the literature lacks models that simultaneously encode both spatial and temporal localities utilizing only vertex partitioning for further improving the performance of SpMV on shared-memory architectures. In order to fill this gap, we propose a novel spatiotemporal hypergraph model that leads to a one-phase spatiotemporal reordering method which encodes both types of locality simultaneously. We also propose a framework for spatiotemporal methods which encodes both types of locality in two dependent phases and two separate phases. The validity of the proposed spatiotemporal models and methods are tested on a wide range of sparse matrices and the experiments are performed on both a 60-core Intel Xeon Phi processor and a Xeon processor. Results show the validity of the methods via almost doubling the Gflop/s performance through enhancing data locality in parallel SpMV operations.
- 1 August 2018
- Published by Springer Nature
- p. 721-734
Exploiting Data Sparsity for Large-Scale Matrix Computations
- 1 August 2018
- Published by Springer Nature
- p. 721-734
Exploiting Data Sparsity for Large-Scale Matrix Computations
- Open Access
- 30 September 2017
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 4 (3) , 1-34
Partitioning Models for Scaling Parallel Sparse Matrix-Matrix Multiplication
We investigate outer-product--parallel, inner-product--parallel, and row-by-row-product--parallel formulations of sparse matrix-matrix multiplication (SpGEMM) on distributed memory architectures. For each of these three formulations, we propose a hypergraph model and a bipartite graph model for distributing SpGEMM computations based on one-dimensional (1D) partitioning of input matrices. We also propose a communication hypergraph model for each formulation for distributing communication operations. The computational graph and hypergraph models adopted in the first phase aim at minimizing the total message volume and balancing the computational loads of processors, whereas the communication hypergraph models adopted in the second phase aim at minimizing the total message count and balancing the message volume loads of processors. That is, the computational partitioning models reduce the bandwidth cost and the communication hypergraph models reduce the latency cost. Our extensive parallel experiments on up to 2048 processors for a wide range of realistic SpGEMM instances show that although the outer-product--parallel formulation scales better, the row-by-row-product--parallel formulation is more viable due to its significantly lower partitioning overhead and competitive scalability. For computational partitioning models, our experimental findings indicate that the proposed bipartite graph models are attractive alternatives to their hypergraph counterparts because of their lower partitioning overhead. Finally, we show that by reducing the latency cost besides the bandwidth cost through using the communication hypergraph models, the parallel SpGEMM time can be further improved up to 32%.
- 30 September 2017
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 4 (3) , 1-34
Open AccessPartitioning Models for Scaling Parallel Sparse Matrix-Matrix Multiplication
We investigate outer-product--parallel, inner-product--parallel, and row-by-row-product--parallel formulations of sparse matrix-matrix multiplication (SpGEMM) on distributed memory architectures. For each of these three formulations, we propose a hypergraph model and a bipartite graph model for distributing SpGEMM computations based on one-dimensional (1D) partitioning of input matrices. We also propose a communication hypergraph model for each formulation for distributing communication operations. The computational graph and hypergraph models adopted in the first phase aim at minimizing the total message volume and balancing the computational loads of processors, whereas the communication hypergraph models adopted in the second phase aim at minimizing the total message count and balancing the message volume loads of processors. That is, the computational partitioning models reduce the bandwidth cost and the communication hypergraph models reduce the latency cost. Our extensive parallel experiments on up to 2048 processors for a wide range of realistic SpGEMM instances show that although the outer-product--parallel formulation scales better, the row-by-row-product--parallel formulation is more viable due to its significantly lower partitioning overhead and competitive scalability. For computational partitioning models, our experimental findings indicate that the proposed bipartite graph models are attractive alternatives to their hypergraph counterparts because of their lower partitioning overhead. Finally, we show that by reducing the latency cost besides the bandwidth cost through using the communication hypergraph models, the parallel SpGEMM time can be further improved up to 32%.