Extended-variable probabilistic computing with probabilistic d-dimensional bits

Ising machines can solve combinatorial optimization problems by representing them as energy minimization problems. A common implementation is the probabilistic Ising machine (PIM), which uses probabilistic (p-) bits to represent coupled binary spins. However, many real-world problems have complex data representations that do not map naturally into a binary encoding, leading to a significant increase in hardware resources and time-to-solution. Here, we describe a generalized spin model that supports an arbitrary number of spin dimensions, each with an arbitrary real component. We define the probabilistic d-dimensional bit (p-dit) as the base unit of a p-computing implementation of this model. We further describe two restricted forms of p-dits for specific classes of common problems and implement them experimentally on an application-specific integrated circuit (ASIC): (A) isotropic p-dits, which simplify the implementation of categorical variables resulting in ~34x performance improvement compared to a p-bit implementation on an example 3-partition problem. (B) Probabilistic integers (p-ints), which simplify the representation of numeric values and provide ~5x improvement compared to a p-bit implementation of an example integer linear programming (ILP) problem. Additionally, we report a field-programmable gate array (FPGA) p-int-based integer quadratic programming (IQP) solver which shows ~64x faster time-to-solution compared to the best of a series of state-of-the-art software solvers. The generalized formulation of probabilistic variables presented here provides a path to solving large-scale optimization problems on various hardware platforms including digital CMOS.

Methods
ASIC design

The ASIC PIM was defined using RTL Verilog code which was processed by the OpenLane RTL to GDSII pipeline, using the Skywater 130 nm open-source process design kit (PDK). The PIM was manufactured using the Efabless multi-project wafer (MPW) service, which also provided the design for a co-integrated small CPU based on a VexRiscv minimal+debug configuration [61]. An oscillator running at 10 MHz was used as the ASIC’s clock for all experiments shown.

Experimental code

All non-trivial problems and their Ising representations were created using self-made Python 3 code. All simulated data were gathered using self-made C++ code. Self-made C code executed on the RISC-V CPU was used to run all experimental trials. Communication with the RISC-V CPU, to upload trial code and to record results, was done using the UART protocol over a USB cable.

IQP Comparison

Solvers used for the IQP comparison were bundled with GAMS 49.3.0 [62] and accessed using GAMS Studio 1.20.2. To the best of our knowledge, all local, standalone (not utilizing other solvers included in GAMS as subsolvers) non-convex MIQCP solvers that were included in an academic license have been considered. For each trial, the solvers were instructed to use 4 threads, and to have a timeout of 10 minutes, with all other parameters kept at their default values, including the seed. For CPLEX, ‘OptimalityTarget’ was set to ‘3’ to allow it to process a non-convex problem. The solution time for each solver was extracted from the produced logfiles, where it is reported differently for each solver. CPLEX and MOSEK reported solution time to the nearest hundredth of the second, while ALPHAECP and XPRESS reported solution time to the nearest second. Total execution time was not considered. All solvers finished execution on their own apart from XPRESS which was halted after the timeout period. This comparison was conducted on a Ryzen 7 4700U which has a frequency of 2.0 GHz and a Turbo Clock of 4.1 GHz. Memory utilization was not a limiting factor for any solver.

FPGA design

All FPGA demonstrations were conducted using a Terasic Cyclone IV Altera DE2-115. A 50 MHz oscillator included on the FPGA was used as the driving clock. The design was defined by RTL SystemVerilog code compiled by Quartus Prime Version 23.1std.0 Build 991. One push-button was used to reset the pseudo-random number generator to an initial seed. The other independently reset the state of the PIM. The pseudo-random number generator is based on the state update procedure of the 32-bit PCG pseudo-random number generator [63]. It has a period of 233 states, corresponding to ~86 seconds. For each set of initial, randomly generated seeds, 5 trials were conducted. Readout of the iteration in which the true solution was found was done through LEDs.