.png){kind=icon}
.png){kind=icon}
Return
Parallel tempering-inspired distributed binary optimization with in-memory computing
.png){kind=icon}
PRE
AI
DOI：10.1103/PhysRevApplied.23.034031.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In-memory computing (IMC) has been shown to be a promising approach for solving binary optimization problems while significantly reducing energy and latency. Building on the advantages of parallel computation, we propose an IMC-compatible parallelism framework based on the physicsinspired parallel tempering (PT) algorithm, enabling cross-replica communication to improve the performance of IMC solvers. This framework not only enables an IMC solver to improve performance beyond what can be achieved through parallelization, but also affords greater flexibility for the search process with low hardware overhead. We justify that the framework can be applied to almost any IMC solver. We demonstrate the effectiveness of the framework for the Boolean satisfiability problem, using the WalkSAT heuristic as a proxy for existing IMC solvers. The resulting PT-inspired cooperative WalkSAT (PTICWalkSAT) algorithm outperforms the standard WalkSAT heuristic in terms of the iterations to solution in 84.0% of the tested problem instances, and its naive parallel variant does so in 64.9% of the instances, and with a higher success rate in most instances. An estimate of the energy overhead of the PTIC framework for two hardware accelerator architectures indicates that in both cases the overhead of running the PTIC framework would be less than 1% of the total energy required to run each accelerator.
Keywords:
VARIABLE NEIGHBORHOOD SEARCH
SAT