Fast FPGA Accelerator of Graph Cut Algorithm with Out-of-order Parallel Execution in Folding Grid Architecture

Graph cut is a popular approach to solving optimization tasks related to Min-cut/Max-flow problems. However, existing FPGA accelerators of graph cut have difficulty in handling large grid graphs and achieving real-time performance. To address the issue, we propose a novel folding grid architecture that maps an actual one-layered large 2-dimension grid graph into a virtual multi-layered small 2-dimension grid graph. The new architecture not only enables the virtual multi-layered grid graph to execute on a small-size processor array but also adds the potential to concurrently execute grid graph nodes in different layers. In addition, we also propose a novel out-of-order parallel execution technique to fully utilize the architecture parallelism potential. Compared to the state-of-the-art, experimental results show that our design can solve the graph cut problem for grid graphs of 1920 × 1080 nodes in real-time (above 60fps) and achieve a 5.4× improvement in execution time with similar FPGA resources.