The abundance of sparse matrix formats, vendor libraries, and heterogeneous hardware architectures creates a complex optimization landscape in which performance depends on the interplay among data representation, software implementation, and hardware capabilities. To address this complexity, we present Situla, a comprehensive characterization of sparse-dense and sparse-sparse matrix multiplication across Intel Xeon CPUs, NVIDIA H100 GPUs, and many-core ARM Neoverse processors. Our systematic evaluation of CSR, CSC, BSR, and COO formats demonstrates that hardware superiority is not absolute but is instead contingent on software efficiency and matrix structure. Notably, a custom OpenMP implementation on ARM CPUs can outperform vendor-optimized libraries and achieve GPU-level performance for a significant subset of workloads. By analyzing latency, throughput, and power efficiency across diverse matrices from the SuiteSparse collection, Situla challenges conventional assumptions regarding accelerator dominance and highlights critical trade-offs between format selection, platform choice, and energy consumption. Situla’s findings can serve as a blueprint for developing sparsity-aware runtime systems capable of intelligent, dynamic workload scheduling in largescale heterogeneous environments.

While sparsity, a feature of data in many applications, provides optimization opportunities such as reducing unnecessary computations, data transfers, and storage, it causes several challenges, too. For instance, even in state-of-the-art sparse accelerators, sparsity can result in load imbalance; a performance bottleneck. To solve such challenges, our key insight is that if while reading/streaming compressed sparse matrices we can quickly anticipate the locations of the non-zero values in a sparse matrix, we can leverage this knowledge to accelerate processing sparse matrices. To enable this, we propose Pipirima, a lightweight prediction-based sparse accelerator. Inspired by traditional branch predictors, Pipirima uses resource-friendly simple counters to predict the patterns of non-zero values in the sparse matrices. We evaluate Pipirima based on sparse matrix vector multiplication (SpMV) and sparse matrix-dense matrix multiplication (SpMM) kernels on CSR compressed matrices derived from both scientific computing and transformer models. On average, our experiments show $6 \times$ and $4 \times$ speed up over Tensaurus for SpMM and SpMV, respectively on SuiteSparse workload. Pipirima also shows $40 \times$ speed up over ExTensor for SpMM. We achieve $8.3 \times$, $48.2 \times$ over Tensaurus and Extensor in lesser sparse transformer workloads. Piprima consumes $5.621 \mathrm{~mm}^{2}$ area and 544.93 mW power using 45 nm technology with predictor related components as the least expensive ones.

Evaluation of modern sparse accelerators is essential for enhancing their performance and guiding future research. However, modern fine-grained assessments of individual optimizations within these accelerators remain challenging and often lead to inconsistencies between proposals. To address this issue, we introduce La Superba, an optimization-granular analysis of prior studies using a self-comparison technique. La Superba expands existing approaches for analyzing constituent parts of sparse accelerators and introduces a set of categorizations for these optimizations. Our method involves isolating each optimization by systematically removing it from the accelerator and comparing the modified accelerator to its original configuration. This technique is applied to optimizations within three state-of-the-art sparse matrix multiplication accelerators, identifying and examining their individual impacts as well as categorizing them to uncover broader patterns in the performance benefits they offer. Through targeted case studies, we demonstrate the performance effects of some of our chosen optimizations, providing deeper insights into their contributions than those detailed in the original studies. We conclude the paper by discussing overarching patterns in optimization structures, utilizing our categorization as a foundation. By establishing a structured framework for evaluation, this work not only clarifies the contributions of specific optimizations but also provides a valuable tool for future designers and researchers to systematically assess and innovate within the sparse accelerator design space.

We demonstrate that unstructured sparsity significantly improves KV cache compression for LLMs, enabling sparsity levels up to 70\% without compromising accuracy or requiring fine-tuning. We conduct a systematic exploration of pruning strategies and find per-token magnitude-based pruning as highly effective for both Key and Value caches under unstructured sparsity, surpassing prior structured pruning schemes. The Key cache benefits from prominent outlier elements, while the Value cache surprisingly benefits from a simple magnitude-based pruning despite its uniform distribution. KV cache size is the major bottleneck in decode performance due to high memory overhead for large context lengths. To address this, we use a bitmap-based sparse format and a custom attention kernel capable of compressing and directly computing over compressed caches pruned to arbitrary sparsity patterns, significantly accelerating memory-bound operations in decode computations and thereby compensating for the overhead of runtime pruning and compression. Our custom attention kernel coupled with the bitmap-based format delivers substantial compression of KV cache up to 45\% of dense inference and thereby enables longer context lengths and increased tokens/sec throughput of up to 2.23$\times$ compared to dense inference. Our pruning mechanism and sparse attention kernel is available at https://github.com/dhjoo98/mustafar.

Sparse matrix-vector multiplication (SpMV) plays a vital role in various scientific and engineering fields, from scientific computing to machine learning. Traditional general-purpose processors often fall short of their peak performance with sparse data, leading to the development of domain-specific architectures to enhance SpMV. Yet, these specialized approaches, whether tailored explicitly for SpMV or adapted from matrix-matrix multiplication accelerators, still face challenges in fully utilizing hardware resources as a result of sparsity. To tackle this problem, we introduce GUST, a hardware/software co-design, the key insight of which lies in separating multipliers and adders in the hardware, thereby enabling resource sharing across multiple rows and columns, leading to efficient hardware utilization and ameliorating negative performance impacts from sparsity. Resource sharing, however, can lead to collisions, a problem we address through a specially devised edge-coloring scheduling algorithm. Our comparisons with various prior domain specific architectures using real-world datasets shows the effectiveness of GUST, with an average hardware utilization of 33.67%. We further evaluate GUST by comparing SpMV execution time and energy consumption of length-256 and -87 GUST with length-256 1-dimensional systolic array (1D), achieving an average speedup of 411× and 108×, and energy efficiency improvement of 137× and 148×, respectively. To asses the implementation aspect, we compare resource consumption of GUST with 1D as a baseline through FPGA synthesis. Length-256 GUST uses the same number of arithmetic units as length-256 1D, while length-87 GUST uses considerably less. We also compare GUST with Serpens, a state-of-the-art FPGA-based SpMV accelerator, with GUST achieving lower execution time on seven out of nine matrices and lower energy consumption on four.

Although modern supercomputers are capable of delivering Exaflops now, they do not always achieve their peak performance. For instance, even today's high-end supercom-puters achieve only less than 5% of their peak FLOPS when running HPCG, a benchmark designed to represent real-world scientific computing programs. To improve the efficiency of the key kernels in scientific computing, such as those used in solving partial differential equations, computer architects have begun to expand the applications of domain-specific architectures (DSAs) to scientific computing. However, DSAs that often have a fixed design are not likely to be practical solutions, as one specialized solution cannot fit all the diverse scientific computing workloads, making them less effective. The challenges of hardware inef-ficiency in today's supercomputers and the ineffectiveness of DSAs are further exacerbated by sparsity, a key characteristic of scientific computing workloads. While prior studies have proposed DSA solutions for sparse computations, they too are static and not adaptable to variations in the patterns and levels of sparsity across different scientific workloads. To address these challenges and target not only the diversity of computations in such workloads but also variations in sparsity, we propose Acamar11Acamar /’ rckomarr/ is a binary star system in the constellation of Eridanus., a dynamically reconfigurable accelerator. Acamar is adaptable to various solvers across different workloads and dynamically optimizes the trade-off between resource utilization and latency for sparse computations. The adaptable design also enables selecting a solver that guarantees convergence. We evaluate Acamar based on its Vitis HLS implementation on Xilinx Alveo u55c. Our experiments show a resource utilization and latency improvement up to 3.5 x and 6 x as well as improved performance efficiency and achieved throughput over a static design and Nvidia GTX 1650 Super.

The remarkable progress in artificial intelligence (AI) has ushered in a new era characterized by models with billions of parameters, enabling extraordinary capabilities across diverse domains. However, these achievements come at a significant cost in terms of memory and energy consumption. The growing demand for computational resources raises grand challenges for the sustainable development of energy-efficient AI systems. This paper delves into the paradigm of memory-based computing as a promising avenue to address these challenges. By capitalizing on the inherent characteristics of memory and its efficient utilization, memory-based computing offers a novel approach to enhance AI performance while reducing the associated energy costs. Our paper systematically analyzes the multifaceted aspects of this paradigm, highlighting its potential benefits and outlining the challenges it poses. Through an exploration of various methodologies, architectures, and algorithms, we elucidate the intricate interplay between memory utilization, computational efficiency, and AI model complexity. Furthermore, we review the evolving area of hardware and software solutions for memory-based computing, underscoring their implications for achieving energy-efficient AI systems. As AI continues its rapid evolution, identifying the key challenges and insights presented in this paper serve as a foundational guide for researchers striving to navigate the complex field of memory-based computing and its pivotal role in shaping the future of energy-efficient AI.

Matrix inversion is an essential and challenging operation in several application domains, such as scientific computing, social networks, and recommendation systems. Since matrix inversion is a memory-bound task, it has the potential of being implemented near memory to efficiently use high memory bandwidth. However, data-dependency patterns in the common matrix-inversion algorithms limit memory bandwidth utilization. To minimize the negative impact of such dependencies on performance, we propose matrix inversion acceleration (Maia), a near-memory FPGA-based implementation of matrix inversion that converts the mathematical dependencies to gate-level dependencies thus reduces the critical-path latency. We implement and evaluate Maia on a high-end Xilinx Ultrascale+ xcu280 FPGA connected to a high-bandwidth memory (HBM2), targeting the data-center Alveo U280 boards. Maia performs matrix inversion 4 x faster than a baseline FPGA implementation without the proposed techniques for resolving dependencies.

With fully autonomous flight capabilities coupled with user-specific applications, drones, in particular quadcopter drones, are becoming prevalent solutions in myriad commercial and research contexts. However, autonomous drones must operate within constraints and design considerations that are quite different from any other compute-based agent. At any given time, a drone must arbitrate among its limited compute, energy, and electromechanical resources. Despite huge technological advances in this area, each of these problems has been approached in isolation and drone systems design-space tradeoffs are largely unknown. To address this knowledge gap, we formalize the fundamental drone subsystems and find how computations impact this design space. We present a design-space exploration of autonomous drone systems and quantify how we can provide productive solutions. As an example, we study widely used simultaneous localization and mapping (SLAM) on various platforms and demonstrate that optimizing SLAM on FPGA is more fruitful for the drones. Finally, to address the lack of publicly available experimental drones, we release our open-source drone that is customizable across the hardware-software stack.

Memory-bound sparse gathering, caused by irregular random memory accesses, has become an obstacle in several on-demand applications such as embedding lookup in recommendation systems. To reduce the amount of data movement, and thereby better utilize memory bandwidth, previous studies have proposed near-data processing (NDP) solutions. The issue of prior work, however, is that they either minimize data movement effectively at the cost of limited memory parallelism or try to improve memory parallelism (up to a certain degree) but cannot successfully decrease data movement, as prior proposals rely on spatial locality (an optimistic assumption) to utilize NDP. More importantly, neither approach proposes a solution for gathering data from random memory addresses; rather they just offload operations to NDP. We propose an effective solution for sparse gathering, an efficient near-memory intelligent reduction (Fafnir) tree, the leaves of which are all the ranks in a memory system, and the nodes gradually apply reduction operations while data is gathered from any rank. By using such an overall tree, Fafnir does not rely on spatial locality; therefore, it minimizes data movement by performing entire operations at NDP and fully benefits from parallel memory accesses in parallel processing at NDP. Further, Fafnir offers other advantages such as using fewer connections (because of the tree topology), eliminating redundant memory accesses without using costly and less effective caching mechanisms, and being applicable to other domains of sparse problems such as scientific computing and graph analytics. To evaluate Fafnir, we implement it on an XCVU9P Xilinx FPGA and in 7 nm ASAP ASIC. Fafnir looks up the embedding tables up to 21.3× more quickly than the state-of-the-art NDP proposal. Furthermore, the generic architecture of Fafnir allows running classic sparse problems using the same 1.2 mm2hardware up to 4.6× more quickly than the state of the art.

Scientific computations with a wide range of applications in domains such as developing vaccines, forecasting the weather, predicting natural disasters, simulating aerodynamics of spacecraft, and exploring oil resources, create the main workloads of supercomputers. The key integration of such scientific computations is modeling physical phenomena that are done with the aid of partial differential equations (PDEs). Solving PDEs on supercomputers, even with those equipped with GPUs, consumes a large amount of power and yet is not as fast as desired. The main reason behind such slow processing is data dependency. The key challenge is that software techniques cannot resolve these dependencies, therefore, such applications cannot benefit from the parallelism provided by processors such as GPUs. Our key insight to address this challenge is that although we cannot resolve the dependencies, we can reduce their negative impacts by using hardware/software co-optimization. To this end, we propose breaking down the data-dependent operations into two groups of operations: a majority of parallelizable and the minority of data-dependent operations. We execute these two groups in the desired order: first, we put together all parallelizable operations and execute them all, subsequently; then, we switch to execute the small data-dependent part. As long as the data-dependent part is small, we can accelerate them by using fast hardware mechanisms. Besides, our proposed hardware mechanisms guarantee quickly switching between the two groups of operations. To follow the same order of execution, dictated by our software mechanism, and implemented in hardware, we also propose a new low-overhead compression format - sparsity is another attribute of PDEs that require compression. Furthermore, the core generic architecture of our proposed hardware allows the execution of other applications including sparse matrix-vector multiplication (SpMV) and graph algorithms. The key feature of the proposed hardware is partial reconfigurability, which on one hand, facilitates the execution of data-dependent computations, and on the other hand, allows executing broad application without changing the entire configuration. Our evaluations show that compared to GPUs, we achieve an average speedup of 15.6x for scientific computations while consuming 14x less energy.

A key real-time task in autonomous systems is simultaneous localization and mapping (SLAM). Although prior work has proposed hardware accelerators to process SLAM in real time, they paid less attention to power consumption. To be more power-efficient, we propose Pisces, which co-optimizes power consumption and latency by exploiting sparsity, a key characteristic of SLAM missed in prior work. By orchestrating sparse data, Pisces aligns correlated data and enables deterministic, one-time, and parallel accesses to the on-chip memory. Therefore, Pisces (i) eliminates unnecessary memory accesses and (ii) enables pipelined and parallel processing. Our FPGA implementation shows that Pisces consumes 2.5× less power and executes SLAM 7.4× faster than the state of the art.

Sparse computations dominate a wide range of applications from scientific problems to graph analytics. The main characterization of sparse computations, indirect memory accesses, prevents them from effectively achieving high performance on general-purpose processors. Therefore, hardware accelerators have been proposed for sparse problems. For these accelerators, the storage format and the decompression mechanism is crucial but have seen less attention in prior work. To address this gap, we propose Ascella, an accelerator for sparse computations, which besides enabling a smooth stream of data and parallel computation, proposes a fast decompression mechanism. Our implementation on a ZYNQ FPGA shows that on average, Ascella executes sparse problems up to 5.1× as fast as prior work.

Matrix multiplication (MM) has several applications in fields such as statistics, physics, economics, and computer science. For instance, the main computation behind deep neural networks (DNNs) is a convolution that can be implemented as MM. The increasing demand for executing MM quickly has motivated several proposals to design specialized hardware for it. Among the proposals, systolic arrays [1] [2] [3] [4] [5] have seen significant interest mainly because of their unique interconnections that satisfies the unique requirement of data reuse in MM. Systolic arrays are networks of connected compute units that independently compute partial results as a function of the input and pass data within their structure.

Sparse problems that dominate a wide range of applications fail to effectively benefit from high memory bandwidth and concurrent computations in modern high-performance computer systems. Therefore, hardware accelerators have been proposed to capture a high degree of parallelism in sparse problems. However, the unexplored challenge for sparse problems is the limited opportunity for parallelism because of data dependencies, a common computation pattern in scientific sparse problems. Our key insight is to extract parallelism by mathematically transforming the computations into equivalent forms. The transformation breaks down the sparse kernels into a majority of independent parts and a minority of data-dependent ones and reorders these parts to gain performance. To implement the key insight, we propose a lightweight reconfigurable sparse-computation accelerator (Alrescha). To efficiently run the data-dependent and parallel parts and to enable fast switching between them, Alrescha makes two contributions. First, it implements a compute engine with a fixed compute unit for the parallel parts and a lightweight reconfigurable engine for the execution of the data-dependent parts. Second, Alrescha benefits from a locally-dense storage format, with the right order of non-zero values to yield the order of computations dictated by the transformation. The combination of the lightweight reconfigurable hardware and the storage format enables uninterrupted streaming from memory. Our simulation results show that compared to GPU, Alrescha achieves an average speedup of 15.6x for scientific sparse problems, and 8x for graph algorithms. Moreover, compared to GPU, Alrescha consumes 14x less energy.

The fundamental building block of many algorithms such as data analytics and neural networks is matrix multiplication. Besides its popularity, matrix multiplication is one of the rare algebraic computations that demand high data reuse rate. During the past decades, systolic arrays have been proposed as a low-cost solution for implementing high data reuse, and they have seen a resurgence of interest recently. Particularly, two categories of systolic arrays have been proposed, both of which are made of connected multiply-and-accumulate (MAC) units: non-stationary and stationary architectures. While in the nonstationary architecture both operands of the matrix multiplication flow through the MAC units, in the stationary architecture, only one of them flows. Regardless of their advantages, their common challenges are that they have high latency and are not scalable. In other words, latency increases linearly when the input size grows. Particularly, these are crucial challenges for applications of large matrix multiplication (e.g., deep neural networks (DNNs)) in the edge, in which latency must be optimized not throughput. To resolve this challenge, we propose multiplying matrices efficiently in a scalable systolic architecture (Meissa). Meissa is a novel stationary systolic array that, unlike prior work, separates multipliers from the adders rather than combining them in a unified array of MACs. Such an interconnection enables Meissa to sustain a sublinear growing rate in latency with scaling problem size. Our experimental results on a ZYNQ XC7Z020 FPGA show that Meissa executes the single-batch inference of DNNs 1.99× and 1.83× as fast as the prior non-stationary and stationary systolic arrays, respectively.

The performance of sparse problems suffers from lack of spatial locality and low memory bandwidth utilization. However, the distribution of non-zero values in the data structures of a class of sparse problems, such as matrix operations in neural networks, is modifiable so that it can be matched with an efficient underlying hardware, such as systolic arrays. Such modification helps addressing the challenges coupled with sparsity. To efficiently execute sparse neural network inference on systolic arrays, we propose a structured pruning algorithm that increases the spatial locality in neural network models, while maintaining the accuracy of inference.

Conventionally, systems have relied on technology scaling to provide smaller cells, which helps in increasing the capacity of on-chip and off-chip structures. Unfortunately, scaling technology to smaller nodes causes increased susceptibility to faults. We study the problem of efficiently tolerating transient failures using scalable Spin-Transfer Torque RAM (STTRAM) as an example. At smaller feature sizes, the energy required to flip a STTRAM cell reduces, which makes these cells more susceptible to random failures caused by thermal noise. Such failures can be tolerated by periodic scrubbing and provisioning each line with Error Correction Code (ECC). However, to tolerate the desired bit-error-rate, the cache needs ECC-6 (six bit error correction) per line, incurring impractical storage overheads. Ideally, we want to tolerate these faults without relying on multi-bit ECC. We propose SuDoku, a design that provisions each line with ECC-1 and a strong error detection code, and relies on a region-based RAID-4 to perform correction of multi-bit errors. Unfortunately, simply having such a RAID-4 based architecture is ineffective at tolerating a high-rate of transient faults and provides an MTTF in the order of only a few seconds. We describe a novel data resurrection scheme that can repair multiple faulty lines in a RAID-4 region to increase the MTTF to several hours. We propose an extension of SuDoku, which hashes a given line into two regions of RAID-4 to significantly enhance reliability and increase the MTTF to trillions of hours. Our evaluations show that SuDoku provides 874x higher reliability than ECC-6, incurs 30% less storage than ECC-6, and performs within 0.1% of an ideal fault-free baseline.

Deep neural networks (DNNs) have seen resurgent attraction to be implemented in edge applications. However, such implementations are not easy to achieve because execution of DNNs often require more resources than those provided by individual edge devices. On the other hand, relying on model-level distribution methods to implement a DNN on connected edge devices leads to costly communication overheads. To utilize available in-the-edge resources with less communication overhead, we propose using edge-tailored models comprised of nearly-independent narrow DNNs, the inference of which are accelerated using small cost-efficient RISC-based engines. We implement these engines on PYNQ boards as a platform that mimics the limited resources of edge devices. We create the narrow DNNs based on the available resources of PYNQ boards, and allocate each narrow DNN to one engine, implemented in an FPGA. We compare the communication overhead of our implantation against the state-of-the-art model-level distribution methods.

Three-dimensional (3D)-stacked memories, such as the Hybrid Memory Cube (HMC), provide a promising solution for overcoming the bandwidth wall between processors and memory by integrating memory and logic dies in a single stack. Such memories also utilize a network-on-chip (NoC) to connect their internal structural elements and to enable scalability. This novel usage of NoCs enables numerous benefits such as high bandwidth and memory-level parallelism and creates future possibilities for efficient processing-in-memory techniques. However, the implications of such NoC integration on the performance characteristics of 3D-stacked memories in terms of memory access latency and bandwidth have not been fully explored. This paper addresses this knowledge gap (i) by characterizing an HMC prototype using Micron's AC-510 accelerator board and by revealing its access latency and bandwidth behaviors; and (ii) by investigating the implications of such behaviors on system- and software-level designs. Compared to traditional DDR-based memories, our examinations reveal the performance impacts of NoCs for current and future 3D-stacked memories and demonstrate how the packet-based protocol, internal queuing characteristics, traffic conditions, and other unique features of the HMC affects the performance of applications.