Quantizing Ising model matrices for combinatorial optimization on RISC-V with Lichee Pi 4A

Quantizing Ising model matrices for combinatorial optimization on RISC-V with Lichee Pi 4A

Bratenkov A. M. (SPbPU, St. Petersburg, Russia)
Stepina N. O. (SPbPU, St. Petersburg, Russia)
Nikiforov I. V. (SPbPU, St. Petersburg, Russia)
Yusupova O. A. (SPbPU, St. Petersburg, Russia)

Abstract

This study addresses problem of low efficiency of software implementation of combinatorial optimization algorithms on RISC-V processors. The main obstacle is the quadratic growth of the Ising model interaction matrix. Using double-precision floating-point representation leads to high cache miss rates and degrades performance. The aim of the study is to improve efficiency of solving combinatorial problems on the RISC-V platform by reducing the bit width of the interaction matrix using quantization methods. The proposed approach implements three classes of rounding methods: simple rounding, stochastic rounding, and eight diffusion rounding schemes. A software prototype is developed for the Lichee Pi 4A board, integrating matrix quantization with simulated annealing adapted for integer data types. Experiments are conducted on three NP-hard problems: the traveling salesman problem, the knapsack problem, and the max-cut problem, with bit widths from 2 to 16 bits. The novelty lies in a systematic comparison of these methods on three classical NP-hard problems and in the analysis of their effectiveness depending on the problem structure and available bit width. The results show that quantization effectiveness depends on the problem structure. For the max-cut problem, diffusion rounding improves solution quality by 10% compared to the unrounded matrix. For the knapsack problem, diffusion methods offer no advantage over simple rounding, while stochastic rounding requires at least 8 bits. For the traveling salesman problem, diffusion rounding is beneficial only at 2 bits. Performance evaluation on Lichee Pi 4A shows that switching from double-precision to 8-bit integer matrices reduces execution time by a factor of 3.6–4.7 and decreases cache miss rates from 2.64% to 0.13–0.25%. The best performance is achieved with int8 matrix and int32 accumulator. The findings enable solving larger combinatorial problems on resource-constrained RISC-V platforms.

Keywords

RISC-V; Lichee Pi 4A; combinatorial optimization; Ising model; matrix quantization; error diffusion rounding; stochastic rounding; simulated annealing.

Edition

Proceedings of the Institute for System Programming, vol. 38, issue 4, part 2, 2026, pp. 143-160

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(4)-23

For citation

Bratenkov A. M., Stepina N. O., Nikiforov I. V., Yusupova O. A. Quantizing Ising model matrices for combinatorial optimization on RISC-V with Lichee Pi 4A. Proceedings of the Institute for System Programming, vol. 38, issue 4, part 2, 2026, pp. 143-160 DOI: 10.15514/ISPRAS-2026-38(4)-23.

Full text of the paper in pdf Back to the contents of the volume