Квантование матриц модели Изинга для комбинаторной оптимизации на RISC-V с использованием Lichee Pi 4A
Квантование матриц модели Изинга для комбинаторной оптимизации на RISC-V с использованием Lichee Pi 4A
Аннотация
В работе рассматривается проблема низкой эффективности программной реализации алгоритмов комбинаторной оптимизации на RISC-V процессорах. Основное препятствие – квадратичный рост матрицы взаимодействия модели Изинга, который при использовании чисел с плавающей точкой двойной точности приводит к высокому уровню кэш-промахов и падению производительности. Цель исследования – повышение эффективности решения комбинаторных задач на RISC-V платформе за счёт уменьшения разрядности матрицы с использованием методов квантования. Предложенный подход реализует три класса методов округления: простое, стохастическое и восемь схем диффузионного округления. Новизна работы заключается в систематическом сравнении этих методов на трёх классических NP-трудных задачах, а также в анализе их эффективности в зависимости от структуры задачи и доступной разрядности данных. Разработан программный прототип для платы 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. Результаты позволяют решать задачи комбинаторной оптимизации большего размера на RISC-V системах с ограниченными ресурсами.
Ключевые слова
Издание
Труды Института системного программирования РАН, том 38, вып. 4, часть 2, 2026, стр. 143-160.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).
DOI: 10.15514/ISPRAS-2026-38(4)-23
Для цитирования
Полный текст статьи в формате pdf (на английском)
Вернуться к содержанию тома