hardware processing, this approach significantly enhances the overall efficiency of SpMV operations.

To implement Segin, we apply minimal changes to a targeted SpMV accelerator to select effective computations (non-zero values) and skip non-effective ones in each computation round. Additionally, the architecture tracks the results of each workload using a simple tagging mechanism. These optimization lead to more efficient utilization of computational resources. Additionally, since we can parallelize the computation of two or more matrices in a single round, throughput, defined as the number of SpMV completed per unit of time, is increased, too. In this work, we demonstrate the overlapping of two matrices, and the results indicate that throughput has increased by 1.92× compared to conventional output stationary systolic arrays.

To improve resource underutilization caused by sparsity in SpMV, our key insight is to leverage workload sparsity to enable processing multiple SpMV kernels concurrently in hardware rather than sequentially. By overlapping multiple workloads into a combined workload, which we call fine-grained multi-tenancy, the zeros of one workload are likely covered by the non-zeros of another, resulting in a denser workload. Mapping this denser workload to hardware reduces cycles spent processing zero elements, improving hardware utilization. Moreover, processing two SpMV kernels simultaneously allows completion in the same number of cycles as a single kernel in conventional hardware, boosting throughput.

Combining two or more matrices produces two scenarios: (1) nonoverlapping indices, where zero elements in one matrix are covered by non-zero elements in another, creating an ideal combined matrix; and (2) overlapping non-zero elements, where some indices are shared by multiple matrices. Our approach, Segin, handles both scenarios effectively. By adding a small hardware addition into the computation unit of the systolic array, we show how Segin efficiently resolves overlapping cases. The fine-grained multi-tenancy approach, can enable the processing of two or more SpMV kernels in parallel. Increasing the number of workloads brings both opportunities and challenges. In this work, we focus on processing a pair of workloads simultaneously.

Fig. 1 shows a high-level overview of Segin, with steps on both the host and hardware sides. On the host side (Fig. 1(a)), workloads are grouped into pairs of matrices. These matrices, stored in CSR format, are converted into hierarchical bitmap matrices and sent to the search unit. On the hardware side (Fig. 1(b)), the search engine scans the matrix rows to find pairs with minimal overlaps, saving them in the pair buffer to be processed by the processing elements (PEs). Once all pairs are found, the main computation begins by the PEs and the overlap handler, which deals with rare overlaps. While one set of matrices is being processed, the host sends the next group to the search unit, starting the search phase simultaneously. After computations, results from the overlap handler and PEs are merged by the merge unit, producing two vectors corresponding to the SpMV kernel of each input matrix. This process forms a pipeline with four stages: loading matrices, searching, computation, and merging results. The last three stages are collectively the computation stage.

Bitmap compression techniques for sparse matrix representation efficiently store and manage matrices with many zero elements by leveraging sparsity patterns, thereby reducing memory and storage requirements. A bitmap, which is a 1-bit array, indicates the positions of non-zero elements and is paired with a list of these values. More efficient and flexible methods, such as hierarchical bitmaps where each bit represents a chunk of non-zero values, have been explored in the hardware and software design of prior sparse accelerators [6]. In our work, Segin utilizes hierarchical bitmapping with a granularity of chunk_size, enabling quick searches and supporting multi-tenancy. Choosing an appropriate chunk_size impacts the search engine's efficiency, particularly in achieving a 100% non-overlap ratio between rows. A larger chunk_size aggregates multiple elements, potentially reducing non-overlap opportunities as it combines zero and non-zero values into a single 1-bit representation. For instance, a chunk_size of two would represent a chunk with three zero elements and one nonzero element as one, limiting the ability to exploit zero values for nonoverlap. The chunk_size also affects the search engine's latency, as a smaller bitmap matrix reduces the search window. Based on our analysis (detailed in Section V), a chunk_size of 32 strikes the optimal balance between latency reduction and maximizing the non-overlap ratio.

To find the best match for each row across matrices within a group, Segin's search algorithm operates on bitmap representations of the matrices and begins by dividing them into rows. An initial buffer is created, containing all rows from both matrices. The process starts with the first row, performing an AND operation between this row and each subsequent row in the buffer. For every '1' resulting from the AND operation, a num_overlaps counter is incremented. Once all elements of the row are processed, num_overlaps is compared to min_overlaps, which tracks the fewest overlaps encountered so far. If num_overlaps is smaller, min_overlaps is updated, and the current row is recorded as the best match. The best matching pair, consisting of their matrix numbers and row indices, is added to the final_result buffer. The matched rows are then removed from the initial buffer. The algorithm repeats this process until all rows are paired.

Segin's fine-grained multi-tenancy method is adaptable across various architectures, such as adder trees, systolic arrays, or scalar processing elements. Depending on the baseline architecture, computational units can be modified to handle multiple SpMV kernels concurrently without compromising functionality. In this paper, we target a one dimentional systolic array. Fig. 2 illustrates the details of the Segin computation stage, covering modifications to the PEs, the overhead handler (OH), and the merge unit as explained below.

Segin uses an output-stationary systolic array, where the vector operand streams left to right and multiplies with matrix rows streaming from the top, computing the SpMV kernel. To support multitenancy, each PE processes two inputs from the same or different matrices, using a "find_non_zero_one" module to identify nonzero elements for multiplication. The module also tags outputs with matrix IDs (mat_id) and row indices (row_ind) for partial sum updates. Overlapping workloads trigger the "activate_OH" flag, connecting the PE to the OH module.

2) Overlap Handler (OH): addresses rare cases where two nonzero values overlap in a PE, operating parallel to the main systolic array to avoid latency. It buffers inputs (mat_id, row_index, vector, and matrix values) and computes results when the "activate_OH" flag is triggered. To minimize memory overhead, a small, fixed-size buffer (OH_size) is used, with a search phase to update or add elements as needed.

3) Merge Unit: combines outputs from the OH and systolic array.

It matches tags to accumulate results or appends unmatched elements from the OH. This ensures the results efficiently integrate contributions from both components.

Simulation Infrastructure: We model Segin and a conventional output stationary one-dimensional systolic array (CSA) baseline using a cycle-level simulator that incorporates unit latencies from Xilinx Alveo U55 C FPGA, operating at a 100 MHz clock frequency. We use the HBM on the Alveo U55 C FPGA, offering 460 GB/s memory bandwidth. Additionally, to evaluate Segin's area and power, we implement its PEs and the baseline in RTL using Verilog, synthesizing them with Synopsys Design Compiler in the NANGATE 45 nm library. We compare Segin's PE underutilization, throughput, area, power, and latency against the CSA and GPU implementations to assess performance and resource efficiency. For GPU comparisons, we analyze resource underutilization on an NVIDIA GTX 1650 Super using CUDA driver version 11.6 and the Nvidia Nsight toolkit. SpMV performance is evaluated with the cuSparse library using Nvidia's sample code.

Datasets and Hardware Configurations: For evaluations, we use the SuiteSparse matrix collection and synthetic matrices with sparsity levels ranging from 0.1 to 0.98, ensuring diverse structural properties and a wide spectrum of sparsity. We also include some machine learning workloads that originate from the query projection matrices of LLaMA-2 7B, specifically layers 0 to 7. These workloads are pruned to a given sparsity (30%, 50%, and 70% in this paper) using Wanda's pruning algorithm [11] with no constraints on the sparsity pattern. Segin processes these datasets in 4k × 4k chunks, with the NNZ column indicating the number of non-zero elements in each chunk. The performance of Segin is influenced by the following parameters:

#PEs: defines the systolic array size, which is set to 4 K. OH_size: determines the size of the buffer in OH, which depends on the number of overlapping elements we have in each timestep. Fig. 3 illustrates the distribution of OH_size needed for our datasets, which indicates that the largest buffer required to store data from PEsincluding vector value, matrix value, matrix_id, and row_index-is 32. Therefore, we set our OH_size to 32 to ensure sufficient capacity and provide a safety margin.

Chunk_size: Specifies the size of the hierarchical bitmap matrix (bitmap_size = mat_size/chunk_size). A chunk_size of 32 balances search engine latency and the non-overlap ratio.

Throughput: We define throughput as the number of SpMV kernels completed in one clock cycle. Since in Segin we overlap the computations of two SpMV kernels, we achieve 1.92× improvement in throughput compared to processing the two SpMV kernels sequentially in a CSA. This improvement is consistent across different pairs because, in a systolic array, the number of cycles required to process an SpMV kernel is fixed and independent of the workload characteristics.

Latency: Fig. 4 shows the latency of two stages of the overall pipeline in Segin for different datasets. As is evident in this figure, the computation stage latency in Segin is similar to the loading stage.

However, there are cases, such as the pair of (pf2177 -sp-0.96), where the latency of the compute stage is slightly more than the load stage. Overall, while taking advantage of Segin, we can still utilize HBM bandwidth, but the computation stage might need to stall in the cases where we have denser matrices in the group. In real-world applications with matrices of varying sparsity, the pipeline achieves better balance. Sparse pairs may cause idle load stages, while dense matrices make memory loading a bottleneck, stalling computation. Mixing diverse workloads balances the pipeline, with occasional stalls in either stage.

The computation stage consists of a search unit, PEs, and merge units. Using Vitis HLS, we evaluate the search engine's latency, which is influenced by the chunk_size parameter. A larger chunk_size reduces the bitmap matrix size, search window, and loop size, lowering latency. Fig. 5 shows how varying the chunk size from 16 to 512 affects computation latency. We fix the chunk_size to 32. Experiments show the search unit's latency dominates the computation stage but does not hinder full utilization of HBM bandwidth.

In Segin, loading from memory occurs through an HBM with a bandwidth of 460 GB/s. For each pair of workloads, we need to send the bitmap matrix (4k × 4k) and the actual 32-bit floating point values for sparse matrices ( N N Z × 32 bits). By utilizing parallel pseudo channels of HBM to transmit this data, we calculate the load stage latency based on the maximum amount of data sent in parallel. This includes two bitmap matrices of size 4k × 4k bits and two values for two sparse matrices, each with a size of 32 × NNZ. The larger of these determines the load stage latency.

Resource Underutilization: Segin can be applied to two scenarios. First the general scenario in which the search algorithm finds the best row pairings, whether from the same matrix or different matrices based on the minimal overlap, we refer to this scenarios as the multi-tenancy approach. Second, a more specific scenario, in which the search algorithm finds the best row pairings from the same matrix, we call this scenario the multi-threading approach. Fig. 6 illustrates the comparison of resource underutilization among a CSA, Segin, and GPU for the first scenario, multi-tenancy. The x-axis in this figure shows the names of workload pairs, with each pair consisting of a SuiteSparse matrix paired with a synthetic matrix by the grouping stage at the host, shown in Fig. 1. The sparsity level for each synthetic matrix is indicated in the pair label; for example, "sp-0.6" means that 60% sparsity. As Fig. 6 shows, TABLE I AREA AND POWER OF PES IN SEGIN AND CSA

workloads. Additionally, non-blocking simultaneous multithreading (NB-SMT) [8], [9] has been proposed to increase hardware utilization in deep learning accelerators. The SySMT framework applies NB-SMT to output-stationary systolic arrays (OS-SA), dynamically sharing resources among multiple execution flows. By temporarily reducing computation precision, SySMT maximizes hardware occupancy for deep learning workloads with minimal accuracy. Finally, while recent studies have explored executing multiple workloads on single hardware acceleratorsprimarily through scheduling or partitioning for multi-DNN scenarios [2], [12], [13] their techniques are coarse-grained, which sets them apart from Segin.

This paper proposed Segin, a fine-grained multi-tenancy approach that reveals the benefits of overlapping sparse workloads through a hierarchical bitmap mechanism. The key insights underscored how strategic pairing of sparse matrices can lead to more efficient resource utilization, which can inspire novel directions for optimizing computation in SpMV.

Segin significantly reduces resource underutilization compared to CSA. Additionally, in many cases, Segin's PE underutilization is lower than that of the GPU. On average, resource underutilization is improved by 14% compared to CSA and 6% compared to the GPU. This improvement results from pairing two sparse matrices with different levels of sparsity. For instance, Segin can improve resource underutilization of a pair of a matrix with a sparsity level of lower than 0.2 and SuiteSparse matrices up to 42%. However, if the random grouping process on the host side results in matrices with similar levels of sparsity in the same group, such as (t520 -sp-0.98), the improvement of Segin over CSA is not significant, and the GPU can utilize its resources more efficiently. Therefore, to leverage the benefits of Segin, we need a set of matrices on the host side with diverse sparsity. The results for the second scenario, multi-threading, shown in the Fig. 7, demonstrate its effectiveness in optimizing resource utilization across targeted LLaMA-2 7B layers. Our experiments, conducted across different sparsity levels (from 30% to 70%, indicate that Segin can achieve up to a 3 × improvement in resource utilization.

Area and Power: Table I lists the area and power of a single PE in Segin and CSA, suggesting both the area and power of Segin have increased by factors of approximately 1.1× and 1.4×, respectively. Therefore, we can conclude that the modifications to the PEs for Segin result in negligible power and area overhead. Also, implementing the Segin search unit in hardware results in an area of approximately 10.65× that of a single Segin PE, which translates to an overall area of about 0.24% of a total 4K-sized systolic array.