Runtime Configurable Approximate Computing System for Simulated Annealing Algorithm

In this paper, we propose a runtime configurable approximate computing (RCAC) system for simulated annealing (SA) algorithm. The RCAC system integrates a configurable approximate hardware to calculate the cost function and a lightweight quality estimator, which provides valuable insights into the SA algorithm's effectiveness by estimating the acceptance rate of each iteration. By utilizing the acceptance rate, the system dynamically configures the operational mode of the approximate hardware, making a good trade-off between solution quality and computational efficiency. Experimental results demonstrate a 7.6% runtime improvement compared to traditional RCAC methods on SA algorithms with a quality loss of less than 2% in final solutions.