1. Overall Architecture

Fig. 2 illustrates the architecture of the baseline SpMV accelerator. It consists of a data distributor that reads matrix and vector data from off-chip DRAM, multiple PE lines that independently perform multiply-accumulate (MAC) operations, and an output updater that collects partial sums (PSUM) into a dedicated buffer. Each PE line contains a matrix buffer, a two-bank vector buffer, and two parallel MAC units, and the number of PE lines scales proportionally with the available off-chip memory bandwidth (e.g., 2, 4, and 8 PE lines for 64, 128, and 256 B/cycle interfaces, respectively).

2. Offline Pre-processing

The accelerator relies on an offline pre-processing stage to transform the input sparse matrix into a format that maximizes hardware utilization during online execution. The pre-processing consists of two steps: matrix partitioning and matrix rearrangement.

In the matrix partitioning step, the input matrix is divided into blocks whose dimensions are constrained by the on-chip vector buffer and PSUM buffer sizes. Each block is then assigned to the PE lines based on its column range. In the baseline design, this assignment follows a column-equal partitioning scheme: the column range of each block is divided equally among the available PE lines, so that each PE line is responsible for a contiguous and equally sized column range, as shown in Fig. 3.

In the matrix rearrangement step, the nonzero elements within each PE line's assigned portion are rearranged to avoid RAW dependencies and bank conflicts. The algorithm prioritizes vector element reuse between the two MAC units to maximize PE utilization, ensuring that each pair accesses different banks in the multi-bank vector buffer.

Fig. 2. Overall architecture of the baseline SpMV accelerator.

Fig. 3. Column-equal PE line partitioning and matrix rearrangement example.

3. Bandwidth Utilization Formulation

The performance of the accelerator is evaluated using bandwidth utilization (BU), defined as the ratio of computational throughput to off-chip memory bandwidth (GB/s) ^{[4, 10]}. Since each nonzero element undergoes two floating-point operations, an SpMV task with $NNZ$ nonzero elements yields $2 \times NNZ$ floating-point operations. The BU is calculated as

where $Bandwidth$ is the off-chip memory bandwidth in bytes per cycle and $C_{total}$ is the total execution cycle count. The accelerator processes each SpMV task in three phases–vector loading, block execution, and output storing–so the total execution cycle count is decomposed as

where $C_{ldv}$, $C_{exe}$, and $C_{sty}$ represent the cycles consumed for loading vector elements, processing all matrix blocks, and storing output results, respectively. $C_{PIPE}$ accounts for pipeline latency. In the vector loading phase, $N_v$ vector elements of $B_v$ bytes each are transferred from off-chip memory

In the block execution phase, each block is processed in parallel across PE lines, and the block completes when the slowest PE line finishes. Therefore $C_{exe}$ is modeled as the sum of the critical paths across all blocks

where $N_{block}$ is the total number of matrix blocks, $P$ is the total number of PE lines, and $C_{i,j}$ denotes the execution cycles of the $j$-th PE line in the $i$-th block. In the output storing phase, the results for $Block_{height}$ output rows are written back

Ideally, when the workload is perfectly balanced, the accelerator minimizes the $C_{exe}$ term in the equation, thereby achieving the theoretical maximum BU. For example, given a 64 B/cycle interface and 4 MAC units, the minimum execution cycle is $C_{total} = NNZ/4$, yielding a maximum BU of 0.125 FLOP/Byte. However, any load imbalance among PE lines causes the slowest PE line to increase the maximum execution cycle disproportionately, directly inflating $C_{exe}$ and degrading the BU. This architectural vulnerability motivates the in-depth PE line imbalance analysis and the proposed optimization detailed in the following section.

1. PE Line Imbalance under Column-equal Partitioning

To quantify the impact of PE line load imbalance on BU, we define a weighted PE line imbalance metric. Since the architecture operates on a synchronized block-level execution model, the difference between the maximum and minimum workload among PE lines directly translates to the hardware idle time experienced by the faster PE lines. For each matrix block $i$, the per-block imbalance ratio $IR_i$ is formulated as

where $NNZ_{i,j}$ denotes the number of nonzero elements assigned to PE line $j$ in block $i$. For an empty block ($NNZ_i = 0$), $IR_i$ is defined as 0. An $IR_i$ of 0.0 indicates a perfectly balanced workload. To evaluate the overall imbalance of the entire matrix, these per-block ratios are aggregated into a weighted average, giving higher weight to blocks with larger nonzero counts since they dominate the total execution time

where $NNZ_i$ is the total number of nonzero elements in block $i$.

As shown in Fig. 4, evaluating 29 SuiteSparse benchmark matrices ^[11] (detailed in Section IV-1) under column-equal partitioning reveals a clear negative correlation: as imbalance increases, BU decreases consistently. This confirms that PE line load imbalance is a primary source of BU degradation. Notably, most matrices exhibit more than 20% BU degradation from the theoretical maximum, indicating that this is not a marginal issue but a widespread problem across diverse matrix structures. Moreover, this imbalance worsens as the hardware scales. For the same matrix, the 8 PE line configuration generally exhibits higher imbalance and lower BU than the 2 PE line configuration. Architecturally, this occurs because increasing the PE line count narrows the column ranges assigned to each PE line, making the system highly susceptible to localized nonzero concentration. These observations collectively motivate the need for a workload-aware partitioning strategy that can maintain high BU across all PE line configurations.

Fig. 4. Weighted PE line imbalance ratio versus bandwidth utilization for 29 benchmark matrices under column-equal partitioning with 2, 4, and 8 PE line configurations.

2. Nonzero-aware PE Line Partitioning

To address this imbalance, we propose a nonzero-aware PE line partitioning strategy that sets partition boundaries based on the cumulative nonzero distribution within each block. The procedure constructs a column-wise nonzero histogram, computes its cumulative sum, and places the partition boundary at the column where the cumulative count reaches $NNZ_i/P$, ensuring that each PE line receives approximately the same number of nonzero elements. The boundary is then aligned to the memory access granularity of 8 elements to avoid misaligned vector accesses, and monotonicity is enforced to prevent degenerate partitions. Finally, each PE line's assigned column range is checked against the vector buffer limit (VBL), and boundaries are clamped if necessary to satisfy the constraint.

Fig. 5 illustrates the difference between column-equal and nonzero-aware partitioning for a representative matrix block. Column-equal partitioning yields an imbalance ratio of 0.91 (23 vs. 2 nonzero elements), whereas nonzero-aware partitioning reduces it to 0.08 (12 vs. 13). The proposed strategy modifies only the block partitioning step within the offline pre-processing stage, requiring no changes to the hardware architecture.

Fig. 5. Comparison of column-equal and nonzero-aware partitioning: NNZ distribution, PE line assignment, and execution timeline.

1. Experimental Setup

The proposed strategy is evaluated using a cycle-accurate simulator modeling the accelerator, configured with a total buffer size of 512KB. All computations use FP64 values and INT32 indices in COO format. We evaluate three configurations with 2, 4, and 8 PE lines to examine the bandwidth scalability. Table 1 lists the 29 benchmark matrices from the SuiteSparse collection ^[11] used in the evaluation, covering diverse application domains and sparsity patterns.

2. BU Improvement

Fig. 6 presents the BU before and after applying the proposed nonzero-aware partitioning for (a) 2, (b) 4, (c) 8 PE line configurations. The average BU improves by 17.2% with 2 PE lines, 65.4% with 4 PE lines, and 113.7% with 8 PE lines. The improvement scales with PE line count because the baseline column-equal partitioning produces increasingly severe imbalance as the column range per PE line shrinks, amplifying the benefit of nonzero-aware partitioning. Notably, no matrix exhibits BU degradation under the proposed strategy in any configuration.

Fig. 6. BU comparison before and after applying nonzero-aware partitioning for (a) 2, (b) 4, and (c) 8 PE line configurations.

3. Relationship between Imbalance Reduction and BU Improvement

Fig. 7 plots the imbalance reduction (defined as $Imbalance_{before} - Imbalance_{after}$) against BU improvement for each matrix across all three PE line configurations. A positive correlation is observed: matrices with larger imbalance reduction achieve greater BU gains, and the trend steepens with more PE lines.

Notable outliers deviate from the general trend for distinct structural reasons. For TSOPF_RS_b2383 with 8 PE lines, the baseline imbalance ratio reaches 0.9997 and the baseline BU is only 0.024, so even a moderate imbalance reduction yields a BU gain exceeding 300%, due to the low baseline. In contrast, com-Youtube exhibits a large imbalance reduction (0.69) but only a 43% BU gain with 8 PE lines, because its large dimension (1.1M $\times$ 1.1M) and extreme sparsity ($\sim$5.3 nonzeros per row) produce many blocks with few nonzeros each. Since each block loads vector elements up to the vector buffer capacity regardless of its nonzero count, $C_{ldv}$ dominates the total execution time and limits the BU impact of reducing $C_{exe}$. For mip1, the weighted PE line imbalance remains high (0.695) even after nonzero-aware partitioning despite a baseline imbalance of 0.990, because its highly skewed nonzero distribution forces the partition boundaries to shift beyond the VBL. The algorithm clamps these boundaries to satisfy the hardware constraint, preventing further imbalance reduction.

Fig. 7. Relationship between imbalance reduction and BU improvement across 2, 4, and 8 PE line configurations.

4. Discussion

The BU improvement originates from reduced PE line idle time: balancing the nonzero count across PE lines decreases $C_{exe}$ while the vector loading cycles ($C_{ldv}$) remain nearly unchanged. The VBL constraint similarly limits improvement for eu-2005, whose large column dimension (862K) causes partition boundaries to be clamped at the VBL. These results suggest that further BU gains for VBL-constrained matrices would require either a larger on-chip vector buffer or a partitioning strategy that subdivides the column range into multiple passes per PE line.