Details

Работа посвящена проблеме низкой эффективности программной реализации алгоритмов комбинаторной оптимизации на RISC-V-процессорах. Основное препятствие – квадратичный рост матрицы взаимодействия модели Изинга, который при использовании чисел с плавающей точкой двойной точности приводит к высокому уровню кэш-промахов. Предложен подход к квантованию матрицы, реализующий три класса методов округления: простое, стохастическое и восемь схем диффузионного округления. Разработан программный прототип для Lichee Pi 4A, интегрирующий квантование с алгоритмом имитации отжига, адаптированным для целочисленных типов данных. Эксперименты проведены на трёх NP-трудных задачах: коммивояжёра, о рюкзаке и максимального разреза. Исследовано влияние методов округления и разрядности (2–16 бит) на качество решений. Показано, что эффективность квантования зависит от структуры задачи: для максимального разреза диффузионное округление улучшает качество на 10%, для рюкзака стохастическое требует не менее 8 бит, для коммивояжёра диффузионное эффективно только на 2 битах. Оценка производительности на Lichee Pi 4A показала, что переход с матрицы двойной точности на 8-битную целочисленную матрицу сокращает время выполнения в 3,6–4,7 раза и снижает долю кэш-промахов с 2,64% до 0,13–0,25%. Наилучшая производительность достигается с матрицей int8 и аккумулятором int32.

This work addresses the 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, which, when using double-precision floating-point representation, leads to a high cache miss rate. An approach to matrix quantization is proposed, implementing three classes of rounding methods: simple rounding, stochastic rounding, and eight error diffusion rounding schemes. A software prototype for the Lichee Pi 4A platform is developed, 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. The influence of rounding methods and bit widths (2–16 bits) on solution quality is studied. The results show that quantization efficiency depends on the problem structure: for the max-cut problem, diffusion rounding improves solution quality by 10%; for the knapsack problem, stochastic rounding requires at least 8 bits; for the traveling salesman problem, diffusion rounding is effective only at 2 bits. Performance evaluation on the Lichee Pi 4A shows that switching from a double-precision matrix to an 8-bit integer matrix reduces execution time by a factor of 3.6–4.7 and decreases the L1d cache miss rate from 2.64% to 0.13–0.25%. The best performance is achieved with an int8 matrix and an int32 accumulator.