Parallel Tempering-Inspired Distributed Binary Optimization with In-Memory Computing
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915224240521216 |
|---|---|
| author | Zhang, Xiangyi Böhm, Fabian Valiante, Elisabetta Noori, Moslem Van Vaerenbergh, Thomas Yang, Chan-Woo Pedretti, Giacomo Mohseni, Masoud Beausoleil, Raymond Rozada, Ignacio |
| author_facet | Zhang, Xiangyi Böhm, Fabian Valiante, Elisabetta Noori, Moslem Van Vaerenbergh, Thomas Yang, Chan-Woo Pedretti, Giacomo Mohseni, Masoud Beausoleil, Raymond Rozada, Ignacio |
| contents | 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 physics-inspired parallel tempering (PT) algorithm, enabling cross-replica communication to improve the performance of IMC solvers. This framework enables an IMC solver not only 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 (SAT) problem, using the WalkSAT heuristic as a proxy for existing IMC solvers. The resulting PT-inspired cooperative WalkSAT (PTIC-WalkSAT) algorithm outperforms the standard WalkSAT heuristic in terms of the iterations-to-solution in 84.0% of the tested problem instances and its naïve parallel variant (PA-WalkSAT) does so in 64.9% of the instances, and with a higher success rate in the majority of 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_09152 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parallel Tempering-Inspired Distributed Binary Optimization with In-Memory Computing Zhang, Xiangyi Böhm, Fabian Valiante, Elisabetta Noori, Moslem Van Vaerenbergh, Thomas Yang, Chan-Woo Pedretti, Giacomo Mohseni, Masoud Beausoleil, Raymond Rozada, Ignacio Emerging Technologies Hardware Architecture Optimization and Control 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 physics-inspired parallel tempering (PT) algorithm, enabling cross-replica communication to improve the performance of IMC solvers. This framework enables an IMC solver not only 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 (SAT) problem, using the WalkSAT heuristic as a proxy for existing IMC solvers. The resulting PT-inspired cooperative WalkSAT (PTIC-WalkSAT) algorithm outperforms the standard WalkSAT heuristic in terms of the iterations-to-solution in 84.0% of the tested problem instances and its naïve parallel variant (PA-WalkSAT) does so in 64.9% of the instances, and with a higher success rate in the majority of 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. |
| title | Parallel Tempering-Inspired Distributed Binary Optimization with In-Memory Computing |
| topic | Emerging Technologies Hardware Architecture Optimization and Control |
| url | https://arxiv.org/abs/2409.09152 |