Fast FPGA Accelerator of Graph Cut Algorithm With Threshold Global Relabel and Inertial Push

Graph cut algorithms are popular in optimization tasks related to min-cut and max-flow problems. However, modern FPGA graph cut algorithm accelerators still need performance and memory resource utilization optimization. On the one hand, they suffer from redundant computations in the heuristic global relabel algorithm and slow convergence speeds during the pushing operation. On the other hand, they can only handle 8-bit 2-D grid graphs with limited size. To address the challenges, first, we propose a novel threshold global relabel algorithm that divides the graph into sleeping and active regions, significantly reducing redundant computations in the sleeping region. Second, we introduce an inertial push technique that imparts flow inertia to break flow barriers and accelerate the algorithm’s convergence. Third, to fully utilize the memory resource in FPGA, we propose an efficient memory layout that divides the memory into read-write and read-only regions. Compared to the state-of-the-art, our FPGA accelerator can efficiently handle 16-bit 2-D grid graphs with 2 million nodes and achieve up to a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2.49\times $ </tex-math></inline-formula> improvement in execution time with the same memory usage.