FPGA Accelerated Parallel Sparse Matrix Factorization for Circuit Simulations

Wei Wu, Yi Shan, Xiaoming Chen, Yu Wang, Huazhong YangARC 2011 · DOI

TL;DR

This paper introduces a novel CPU+FPGA architecture to accelerate sparse matrix factorization, a critical bottleneck in circuit simulations. By offloading the computationally intensive numeric factorization to an FPGA and leveraging parallelism across multiple processing elements, they achieve significant speedups compared to traditional CPU-based solvers.

What Problem Does This Paper Address?

Modern integrated circuit simulations rely heavily on solving large systems of linear equations, often represented by sparse matrices. The process of solving these equations, particularly the LU factorization step, is computationally expensive and must be repeated many times within iterative simulation algorithms like Newton-Raphson. As circuit complexity grows, the size of these matrices can reach tens of thousands or even millions of dimensions, making traditional CPU-based solvers a significant performance bottleneck. Existing hardware acceleration approaches using FPGAs have often lacked scalability or were limited to specific matrix structures, necessitating a more general and efficient solution.

Methods

The authors propose a hybrid CPU+FPGA architecture that leverages the strengths of both platforms. The CPU handles the pre-processing and symbolic analysis of the sparse matrix, which is performed only once. The computationally demanding numeric factorization is then offloaded to an FPGA.

Their core innovation lies in adapting the Gilbert/Peierls (G/P) algorithm for parallel execution on an FPGA. The G/P algorithm is modified to extract symbolic analysis from the numeric factorization, allowing it to be performed on the CPU. The FPGA implementation then focuses on parallelizing the numeric factorization by processing multiple columns of the sparse matrix concurrently across several Processing Elements (PEs). To address memory bandwidth limitations inherent in shared memory architectures, they adopt a distributed shared memory approach where each PE has its own cache, connected via a switch-based network.

For scalability, they introduce a "section-based" G/P algorithm. Instead of processing entire columns at once, a column is divided into smaller sections, allowing for more efficient memory access and reducing the size of the Content Addressable Memory (CAM) required per PE.

Datasets

The authors evaluated their approach using a variety of circuit matrices from the University of Florida Sparse Matrix Collection. Specific matrices mentioned include rajat19, circuit1, circuit_2, add32, and meg4. No new benchmarks were introduced.

Key Insights and Ideas

  • Hybrid CPU+FPGA for Specialized Tasks: The paper demonstrates the effectiveness of a hybrid approach where computationally intensive, repetitive tasks (numeric factorization) are offloaded to hardware accelerators (FPGA), while setup and less parallelizable tasks (pre-processing, symbolic analysis) remain on the CPU.
  • Parallelizing G/P Algorithm on FPGA: Adapting and parallelizing the G/P algorithm, which is suitable for sparse matrices, for an FPGA architecture is a key contribution. This allows for significant speedups by exploiting fine-grained parallelism.
  • Distributed Shared Memory for Bandwidth: The shift from a single shared memory to a distributed shared memory with per-PE caches is crucial for overcoming memory bandwidth bottlenecks in parallel FPGA architectures.
  • Section-Based Processing for Scalability: Dividing matrix columns into sections is an effective strategy to improve scalability to larger matrix sizes by managing memory consumption and access patterns.

Key Results

The proposed CPU+FPGA architecture achieved a speedup of 0.5x to 5.36x compared to the CPU-based KLU solver on various circuit matrices. The geometric average acceleration was approximately 2.19x. The performance varied depending on the matrix characteristics, with some matrices showing higher acceleration than others.

Limitations and Future Work

The authors acknowledge that the switch-based interconnect in their parallelized architecture can become a bottleneck as the number of PEs increases, limiting scalability beyond a certain point. They suggest that a mesh network architecture could be a future solution for better scalability. Additionally, they propose future work to:

  • Reuse the PEs for front/back solvers.
  • Implement partial factorization to further reduce computational burden by only recomputing for modified entities in circuit simulations.
  • Explore ASIC implementations with 3D-stacked memory for even larger matrices.

Summary updated

BibTeX
@inproceedings{wu2011fpga,
  author = {Wei Wu and Yi Shan and Xiaoming Chen and Yu Wang and Huazhong Yang},
  title = {{FPGA Accelerated Parallel Sparse Matrix Factorization for Circuit Simulations}},
  booktitle = {ARC},
  year = {2011},
  doi = {10.1007/978-3-642-19475-7\_33},
}
Figure