Reconfigurable Low-latency Memory System for Sparse Matricized Tensor Times Khatri-Rao Product on FPGA

Sasindu Wijeratne, Rajgopal Kannan, Viktor K. Prasanna

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.

Overall FPGA system architecture showing the flow from PEs through LMBs to 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}$.

Speedup comparison of the proposed hybrid system against cache-only and DMA-only baselines across different configurations.

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

Abstract

Tensor decomposition has become an essential tool in many applications in various domains, including machine learning. Sparse Matricized Tensor Times Khatri-Rao Product (MTTKRP) is one of the most computationally expensive kernels in tensor computations. Despite having significant computational parallelism, MTTKRP is a challenging kernel to optimize due to its irregular memory access characteristics. This paper focuses on a multi-faceted memory system, which explores the spatial and temporal locality of the data structures of MTTKRP. Further, users can reconfigure our design depending on the behavior of the compute units used in the FPGA accelerator. Our system efficiently accesses all the MTTKRP data structures while reducing the total memory access time, using a distributed cache and Direct Memory Access (DMA) subsystem. Moreover, our work improves the memory access time by 3.5× compared with commercial memory controller IPs. Also, our system shows 2× and 1.26× speedups compared with cache-only and DMA-only memory systems, respectively.
BibTeX
@inproceedings{wijeratne2021reconfigurable,
  author = {Sasindu Wijeratne and Rajgopal Kannan and Viktor K. Prasanna},
  title = {{Reconfigurable Low-latency Memory System for Sparse Matricized Tensor Times Khatri-Rao Product on FPGA}},
  booktitle = {HPEC},
  year = {2021},
  url = {https://openreview.net/forum?id=uyavfUMoTG},
}
Figure