FPGA implementation of a stochastic neural network for monotonic pseudo-Boolean optimization.

Area of Science:

• Computational Neuroscience
• Computer Engineering
• Optimization Algorithms

Background:

• NP-hard problems are computationally challenging.
• Existing heuristic methods often struggle with large-scale problems.
• Neural network models offer a promising approach to optimization.

Purpose of the Study:

• To propose and develop a novel neural stochastic model for solving constrained NP-hard problems.
• To implement this model on a Field-Programmable Gate Array (FPGA) for enhanced computational speed.
• To evaluate the performance and speed of the FPGA implementation against software solutions.

Main Methods:

• Utilized pseudo-Boolean functions to define constraints and cost functions (neural network energy).
• Developed a hardware architecture on an FPGA exploiting parallelism for neuron updates and constraint checking.
• Tested the neural system on random and benchmark graphs.

Main Results:

• The FPGA implementation achieved significantly faster computation compared to software implementations.
• The model demonstrated good performance on various NP-hard problems, particularly those with quadratic pseudo-Boolean penalty functions.
• Parallel processing in the hardware architecture contributed to high computational speed.

Conclusions:

• The proposed FPGA implementation of the neural stochastic model is effective for solving constrained NP-hard problems.
• Hardware acceleration via FPGAs offers a substantial speed advantage over software for this class of problems.
• The model's architecture is suitable for a wide range of NP-hard problems solvable with quadratic pseudo-Boolean penalty functions.