Abstract
Sparse Matricized Tensor Times Khatri-Rao Product (MTTKRP) is a critical computational kernel in tensor decomposition, yet its performance on FPGAs is often limited by the "memory wall" caused by irregular access patterns. This paper presents a reconfigurable, low-latency memory system designed to optimize these patterns through a hybrid cache-and-DMA architecture. By utilizing a specialized Request Reductor to merge redundant memory traffic, the proposed system achieves up to a 3.5× speedup over standard commercial memory controllers while maintaining a small hardware footprint. Experimental results on a Xilinx Alveo U250 demonstrate the effectiveness of this approach for large-scale, extremely sparse tensors.
Introduction
In applications ranging from recommender systems to signal processing, Canonical Polyadic Decomposition (CPD) is a vital tool for analyzing multi-dimensional data. The primary bottleneck in CPD is the MTTKRP kernel. Real-world tensors are typically extremely sparse (often >99%), leading to irregular memory access patterns that traditional memory systems are ill-equipped to handle. Caches fail due to low spatial locality in scattered tensor elements, while Direct Memory Access (DMA) engines are inefficient for the small, frequent requests typical of sparse data. This research addresses these challenges by building a memory system that simultaneously handles streaming matrix fibers and scattered tensor elements without stalling compute units.
System Architecture
The proposed architecture is built around modular Local Memory Blocks (LMBs) that serve as intermediaries between Processing Elements (PEs) and external DRAM.
Key components of the LMB include:
- Hybrid Transfer Strategy: The system employs a non-blocking cache for tensor scalars (which exhibit some temporal locality) and a DMA engine for matrix fibers, which are accessed sequentially as bulk data.
- Request Reductor (RR): This unit features a Recent Request Status Holder (RRSH)—an XOR-based hash table that tracks and merges pending memory requests. This drastically reduces redundant traffic when multiple PEs target the same cache line.
- Reconfigurability: Users can tune the number of LMBs and cache parameters to balance throughput and routing complexity based on the specific FPGA fabric and data characteristics.
Performance Evaluation
The system was implemented on a Xilinx Alveo U250 and evaluated using large-scale synthetic 3D tensors with densities as low as $9.05 \times 10^{-13}$.
As shown in the results, the proposed hybrid architecture achieves a 3.5× speedup over standard commercial Xilinx memory controller IPs. It also provides a 2× improvement over cache-only systems and a 1.26× improvement over DMA-only systems. Despite these performance gains, the complete system remains resource-efficient, utilizing only ~3.6% of the FPGA's Look-Up Tables (LUTs) and ~8.5% of its UltraRAM (URAM).
Conclusion
This work demonstrates that a specialized, reconfigurable memory path can effectively overcome the memory wall for sparse tensor algebra on FPGAs. By combining the strengths of caching and DMA with intelligent request merging, the system provides high-throughput access for irregular workloads. Future research will explore extending this architecture to higher-order tensors and further optimizing the XOR hash table for increased PE counts.
Summary updated