Computing with Invertible Logic: Combinatorial Optimization with Probabilistic Bits
Computing with Invertible Logic: Combinatorial Optimization with Probabilistic Bits
复制标题
可逆逻辑计算：概率位组合优化
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kerem Y Çamsarı
中科院分区：
文献类型：
--
作者：
Navid Anjum Aadit;Andrea Grimaldi;M. Carpentieri;L. Theogarajan;G. Finocchio;Kerem Y Çamsarı
求解组合优化问题的专用加速器正受到越来越多的关注。该方法中的一个竞争者是基于具有概率或p比特的概率计算。P比特是比特和Q比特之间的基本计算单位，介于逻辑0和1之间。改进的磁阻RAM技术使用数百万比特构建高度集成的概率计算机成为可能。对于基于p比特的中等规模加速器，使用现场可编程门阵列和专用集成电路的传统cmos工艺提供了一种具有竞争力的替代方案。在这里，我们介绍了一些最新的结果，使用p位，稀疏，模块化和可扩展的p-电路。给出了整数分解和布尔可满足性(SAT)等组合优化问题的结果，使用可逆逻辑的原理来生成硬件感知的图表示。可逆逻辑允许设计可以反向操作的布尔电路：例如，由基本逻辑门(AND、OR、NOT)构建的数字乘法器可以用来对整数进行因数分解。同样，SAT问题可以通过在硬件中构建相应的逻辑电路并反向运行来简单地解决。使用模拟退火法和并行回火等强大的概率算法，我们展示了可逆概率电路中互连的p比特如何解决计算困难的优化问题，如布尔SAT和高达25比特半素数(数千万)的整数因式分解，表现出与所有Ising机器的竞争性能。
Special purpose accelerators for solving combinato-rial optimization problems have been receiving increasing attention. One contender in this approach is based on probabilistic computing with probabilistic or p-bits. P-bits constitute the fundamental computational unit between bits and q-bits, fluc-tuating between logic 0 and 1. Modified magnetoresistive RAM technology opens up the possibility of building highly integrated probabilistic computers with millions of p-bits. For medium-scale p-bit based accelerators conventional CMOS technology using FPGAs and ASICs offer a competitive alternative. Here, we present some of the latest results using p-bits, in sparse, modular, and scalable p-circuits. Results are presented for combinatorial optimization problems such as integer factorization and Boolean satisfiability (SAT), using the principles of invertible logic for generating hardware-aware graph representations. Invertible logic allows the design of Boolean circuits that can be operated in reverse: for example, a digital multiplier built out of elemental logic gates (AND, OR, NOT), can be used to factor integers. Similarly, SAT problems can simply be solved by constructing the corresponding logical circuit in hardware and running it in re-verse. Using powerful probabilistic algorithms such as simulated annealing and parallel tempering, we show how interconnected p-bits in invertible probabilistic circuits can solve computationally hard optimization problems such as Boolean SAT and integer factorization up to 25-bit semiprimes (in the tens of millions) showing competitive performance amongst all Ising Machines.