Integer Point Enumeration in Multi-Dimensional Geometric Objects with FPGA Acceleration

Abstract

This paper presents a hardware based approach to accelerate the process of integer point enumeration within multidimensional geometric objects using FPGA technology. We introduce a customized FPGA design based on the established integer point enumeration in fundamental parallelepiped algorithm. Through experimentation, we evaluate the performance of this FPGA-accelerated design in comparison to C and traditional Python implementations across a set of 12 test instances. Our experiments reveal a significant computational speedup for the C implementation, ranging from 83% to 100%, compared to the Python implementation. FPGA implementation can speed up the C version about 10x up to dimension 9. But beyond that, the I/O operations due to the lack of memory, make FPGA slower than C although the computation times are still better. © 2024 Elsevier B.V., All rights reserved.