Hardware acceleration of simulated annealing for constraint satisfaction problems

Area of Science:

• Computational Optimization
• Materials Science
• Hardware Acceleration

Background:

• Simulated annealing (SA) is a metaheuristic algorithm for combinatorial optimization.
• SA uses stochastic search to escape local minima and find global optima.
• Spatial optimization problems, like drone placement, are computationally intensive.

Purpose of the Study:

• To present hardware acceleration of SA for spatial optimization in constrained environments.
• To target drone placement for maximized area coverage while avoiding no-fly zones.
• To utilize 2D materials for stochasticity and programmable logic in the SA process.

Main Methods:

• Developed a hardware accelerator for simulated annealing.
• Integrated a true random number generator (TRNG) based on 2D materials for stochasticity.
• Employed 2D logic circuits for system energy evaluation and solution acceptance with tunable thresholds.

Main Results:

• Achieved 1800-fold search acceleration compared to brute-force for drone placement.
• Hardware modules consume 43 nJ of energy per iteration.
• Demonstrated feasibility of 2D-material-based hardware for real-time optimization.

Conclusions:

• Hardware acceleration of SA using 2D materials is effective for constrained spatial optimization.
• The developed system offers significant speedup and energy efficiency.
• Highlights the potential of 2D-material-enabled hardware for real-time optimization tasks.