# Substream-Centric Maximum Matchings on FPGA

arXiv: https://arxiv.org/abs/2010.14684 · HTML: https://mlsanity.com/paper/2010.14684/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2020.

## Built on by (most cited first, 7 of 7)

- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [Motif Prediction with Graph Neural Networks](https://mlsanity.com/paper/2106.00761/) (2021)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra](https://mlsanity.com/paper/2103.03653/) (2021)
- [GraphSeek: Next-Generation Graph Analytics with LLMs](https://mlsanity.com/paper/2602.11052/) (2026)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)

## Abstract (arXiv)

Developing high-performance and energy-efficient algorithms for maximum matchings is becoming increasingly important in social network analysis, computational sciences, scheduling, and others. In this work, we propose the first maximum matching algorithm designed for FPGAs; it is energy-efficient and has provable guarantees on accuracy, performance, and storage utilization. To achieve this, we forego popular graph processing paradigms, such as vertex-centric programming, that often entail large communication costs. Instead, we propose a substream-centric approach, in which the input stream of data is divided into substreams processed independently to enable more parallelism while lowering communication costs. We base our work on the theory of streaming graph algorithms and analyze 14 models and 28 algorithms. We use this analysis to provide theoretical underpinning that matches the physical constraints of FPGA platforms. Our algorithm delivers high performance (more than 4x speedup over tuned parallel CPU variants), low memory, high accuracy, and effective usage of FPGA resources. The substream-centric approach could easily be extended to other algorithms to offer low-power and high-performance graph processing on FPGAs.