While Large Language Models (LLMs) are widely adopted, their massive parameter size constrains practical deployment. A common solution is clustering-based non-uniform quantization, which effectively compresses models to as low as 3 bits per weight while preserving high accuracy. However, instead of accelerating memory-bound LLM inference, the memory reduction paradoxically often causes a significant slowdown due to dequantization overhead and GPU underutilization. To address the issue, we propose Quantix, a framework designed to convert memory savings into inference speedups. Quantix applies two key optimizations: (1) a hardware-aligned bit shuffling scheme for efficient data access, and (2) a fused dequantization-multiplication pipeline that effectively maps workloads on both CUDA and Tensor Cores. Quantix enables high-throughput batched inference, delivering average kernel-level speedups of 4.82× over FP16 cuBLAS and end-to-end speedups of up to 11.46× over state-of-the-art quantization methods on NVIDIA L40 GPUs.

Sparse matrix multiplications are essential in scientific computing and machine learning applications. Recent researches offload sparse operations, such as sparse matrix-matrix multiplication (SpMM) and sampled dense-dense matrix multiplication (SDDMM), on Tensor Cores (TCs) for improved performance. However, their performance is often limited by the matrix's inherent sparsity and irregularity. In this paper, we find row reordering can potentially improve sparse operations on TCs, but existing reordering techniques exhibit limitations that hinder their effectiveness. To address the issues, we propose Groot, a graph-centric row reordering algorithm with tree. Groot aims to minimize row differences across the matrix, which is proved to be a NP-hard problem. To approximate the optimal solution, Groot firstly captures the local structure of the sparse matrix by constructing a k-nearest neighbor graph, where rows are represented as nodes. Then, it extracts a minimum spanning tree from the constructed graph for global structure optimization. Lastly, Groot traverses the extracted tree to obtain the final ordering. We evaluate Groot using real-world datasets in comparison with state-of-the-art reordering algorithms. Our results show that Groot significantly enhances the computational intensity of SpMM and SDDMM on TCs, delivering the average speedups of 1.8× and 2.0×, respectively. Furthermore, the performance gains extend broadly to sparse computations on CUDA cores and GNN systems.

Triangle counting is a fundamental graph algorithm used to identify the number of triangles within a graph. This algorithm can be reformulated into linear algebraic operations, including sparse matrix multiplication, intersection and reduction. Modern GPUs, equipped with Tensor Cores, offer massive parallelism that can significantly accelerate graph algorithms. However, leveraging Tensor Cores, originally designed for dense matrix multiplication, to handle sparse workloads for triangle counting presents non-trivial challenges. In this paper, we introduce ToT, which enhances the utilization of Tensor Cores and expands their functionalities for diverse sparse matrix operations. In experiments, ToT is evaluated against state-of-the-art methods. ToT outperform the second-fastest method with an 11.56× speedup in end-to-end execution. This work represents a pioneering exploration into utilizing Tensor Cores for accelerating graph algorithms.

Triangle counting is a fundamental graph algorithm used to identify the number of triangles within a graph. This algorithm can be reformulated into linear algebraic operations, including sparse matrix multiplication, intersection and reduction. Modern GPUs, equipped with Tensor Cores, offer massive parallelism that can significantly accelerate graph algorithms. However, leveraging Tensor Cores, originally designed for dense matrix multiplication, to handle sparse workloads for triangle counting presents non-trivial challenges. In this paper, we conduct an in-depth analysis of the state-of-the-art techniques that utilize Tensor Cores for matrix operations, identifying critical performance shortfalls. Based on these insights, we introduce ToT, which enhances the utilization of Tensor Cores and expands their functionalities for diverse sparse matrix operations. In experiments, ToT is evaluated against state-of-the-art methods. ToT outperforms the second-fastest method with a 3.81× speedup in end-to-end execution. Also, it achieves up to 17.00× memory savings. This work represents a pioneering exploration into utilizing Tensor Cores for accelerating the triangle counting algorithm.

Sparse matrix-vector multiplication ($SpMV$) is a fundamental operation in numerous scientific applications, particularly in the context of graph analytics. As graph-based computations become increasingly complex, there is a growing demand for the development of more efficient Sp MV. In this paper, we present a novel approach called Binn to enhance SpMV performance for scale-free graphs on modern multicore processors. Binn incorporates three key optimizations to accelerate SpMV. Firstly, it employs an adaptive cache blocking strategy, which partitions the adjacency matrix of a graph into 2D blocks of varying sizes. This promotes balanced workloads and cache efficiency. Secondly, Binn reorders the nonzero elements of the adjacency matrix, enabling regularized access patterns within each block. Lastly, Binn identifies and eliminates redundant message passing during the execution of SpMV, resulting in reduced memory costs. Through these optimizations, Binn aims to accelerate$SpMV$by facilitating efficient data movement across the memory-cache hierarchy and achieving workload balance among threads. Experimental evaluation on diverse graph datasets demonstrates the effectiveness of Binn, outperforming state-of-the-art Sp MV implementations and graph systems such as Intel's MKL by$3.78\times$and Galios by$1.47\times$.

Sparse matrix-vector multiplication (SpMV) plays a crucial role in various scientific and engineering tasks. Thus, extensive research efforts are devoted to enhancing its performance. In this work, we investigate the utilization of the tensor cores — hardware originally designed for dense matrix multiplications — for SpMV. By reverse engineering the architecture of tensor cores, we gain important insights into their internal register layout and develop a technique for direct access to these registers. Building on these findings, we propose Spaden, a method for accelerating SpMV using tensor cores. Spaden comprises two main components: (1) a bitmap-based format that achieves compression for the sparse matrix while preserving its rectangular shape, and (2) a pairing kernel, facilitating efficient execution of SpMV on tensor cores by enabling precise register-level control. Performance evaluation are conducted on Nvidia V100 and L40 GPUs. Compared with state-of-the-art approaches, Spaden demonstrates substantial speed advantage and memory efficiency, achieving, for example, a 1.63 × speedup and 2.83 × memory saving over cuSPARSE CSR on Nvidia L40.

Link analysis is a fundamental task for graph analytics, as it enables the identification of important nodes and patterns in the graph. Link analysis algorithms typically require traversing the graph and accessing the links of each node. However, for graphs with a skewed degree distribution, the computing efficiency of link analysis is severely constrained due to irregular connectivity, which results in randomized memory accesses and high cache miss ratio.

Recent advances in computer architecture significantly enhance the computational capacity of multicore systems. It allows large-scale graphs to be processed inside a single machine. Nevertheless, the irregular processing pattern of graph-structured data constrains the hardware resources from being productively utilized. In this paper, we investigate the constraints in two aspects: workload imbalance and parallel inefficiency. When a graph analytics algorithm is multithreaded, the thread time is highly diversified, indicating an uneven work distribution. Also, the intensive thread contention lowers the computing capacity of CPU cores, thereby hindering the effective utilization of CPU resources. To address these challenges, we present a proactive graph caching strategy that unequally segments graph components into cache-able subsets of varying sizes, namely Syze. First, the computational loads of cache-sized subgraphs are estimated. Then, the demanding subgraphs are further subdivided until certain threshold is met. Moreover, during the propagation of updates, a fraction of vertex ID (i.e., several bits) are encoded to facilitate the communication between subgraphs. As a result, Syze is able to balance the workloads amongst the logical cores by shortening the longest thread execution time. Meanwhile, it alleviates thread contention and thus elevates the parallel efficiency of multicores. Compared with well-optimized Ligra, Gemini and GPOP, Syze achieves accelerations by up to$17.76\times$,$11.67\times$and$2.81\times$respectively. Additionally, the side effects of Syze are evaluated, including raised cache misses and memory accesses. They play a trivial role in deciding the overall performance, as their costs are far outweighed by the gains from the even distribution of workloads and the improved utilization of multicores.Author: Please confirm or add details for any funding or financial support for the research of this article. ?>

In a shared-memory multicore system, the intrinsic irregular data structure of graphs leads to poor cache utilization, and therefore deteriorates the performance of graph analytics. To address the problem, prior works have proposed a variety of lightweight reordering methods with focus on the optimization of cache locality. However, there is a compromise between cache locality and workload balance. Little insight has been devoted into the issue of workload imbalance for the underlying multicore system, which degrades the effectiveness of parallel graph processing. In this work, a measurement approach is proposed to quantify the imbalance incurred by the concentration of vertices. Inspired by it, we presentCache-aware Reorder (Corder), a lightweight reordering method exploiting the cache hierarchy of multicore systems. At the shared-memory level, Corder promotes even distribution of computation loads amongst multicores. At the private-cache level, Corder facilitates cache efficiency by applying further refinement to local vertex order. Comprehensive performance evaluation of Corder is conducted on various graph applications and datasets. Experimental results show that Corder yields speedup of up to$2.59\times$and on average$1.45\times$, which significantly outperforms existing lightweight reordering methods. To identify the root causes of performance boost delivered by Corder, multicore activities are investigated in terms of thread behavior, cache efficiency, and memory utilization. Statistical analysis demonstrates that the issue of imbalanced thread execution time dominates other factors in determining the overall graph processing time. Moreover, Corder achieves remarkable advantages in cross-platform scalability and reordering overhead.

PageRank, weighing the importance of vertices in a graph, serves as an fundamental algorithm for graph-structured tasks in a variety of domains. However, the processing capacity of multicore systems is oftentimes poorly utilized for large-scale PageRank due to the irregular memory accesses and poor cache efficiency. In this paper, we present HiPa, a novel hierarchical partitioning methodology to accelerate PageRank by utilizing the memory-cache architecture of the multicore system. For the shared memory, HiPa subdivides the graph based on the NUMA characteristics to reduce remote memory access while ensuring workload balance. For the private cache, HiPa further splits the graph into cache-able partitions to promote in-core computing and cache locality. Based on the partitioning strategy, systematical optimizations are proposed, such as thread management and new data layout. These effectively alleviate thread migration and thread contention, thus enhancing the scalability of HiPa. The integration of NUMA- and cache-aware parallelism allows HiPa to harness the potential of multicore systems. The performance of HiPa is evaluated by comparing with the the start-of-the-art graph frameworks and hand-optimized implementations. Over the best among them, HiPa achieves accelerations from 1.11 × to 1.45 × , and reductions in remote memory accesses from 1.87 × to 3.90 × . Moreover, we investigate the behaviors of HiPa on different processor micro-architectures to push its performance closer to hardware limit.

The intrinsic irregular data structure of graphs often causes poor cache utilization thus deteriorates the performance of graph analytics. Prior works have designed a variety of graph reordering methods to improve cache efficiency. However, little insight has been provided into the issue of workload imbalance for multicore systems. In this work, we identify that a major factor affecting the performance is the unevenly distributed computation load amongst cores. To cope with this problem, we propose cache-aware reordering (Corder), a lightweight reordering algorithm that facilitates workload balance as well as cache optimization. Comprehensive performance evaluation of Corder is conducted on various graph applications and datasets. We observe that Corder yields speedup of up to 2.59× (on average 1.47×) over original graphs.