Оптимизация сложных вычислений под малый объём памяти

22 минуты назад

Согласно закону Мура, плотность размещения транзисторов на кристалле удваивается каждые два года. Непрерывный рост производительности центральных, графических и нейронных процессоров (CPU, GPU, TPU, NPU) на протяжении десятилетий вплотную подвел человечество к реализации амбициозных концепций моделирования мозга и создания Сверхразума.

Искусственный интеллект демонстрирует стремительную динамику, превосходя человеческие когнитивные способности в различных бенчмарках (за нулевую отметку принят человеческий уровень, а за -100 — начальный этап разработки моделей), источник: Kiela et al. (2023)

Если на заре компьютерной эры вычислительные машины занимали огромные залы, то сегодня мощные «суперкомпьютеры» стали повседневным аксессуаром в каждом кармане. Тем не менее, теоретики информатики продолжают искать ответ на фундаментальный вопрос: какой минимальный объем памяти необходим для решения конкретной задачи? Этот аспект составляет ядро понятия вычислительной сложности.

Вычислительная сложность в Computer Science определяет совокупность ресурсов, требуемых для исполнения алгоритма. Исследованием этих закономерностей занимается специализированная дисциплина — теория сложности вычислений.

Функционирование любого алгоритма сопряжено с потреблением двух типов ресурсов: временных (циклы CPU, ) и пространственных (оперативная память, ). Таким образом, мы анализируем временную и пространственную сложность программного решения.

Эти показатели обычно описываются с помощью математической нотации «O» большое. Примерами могут служить , $O(n\log n)$ , $O(n^{\alpha })$ или $O(2^{n})$ , где параметр n отражает масштаб входных данных.

Стратегии оптимизации алгоритмов для преодоления NP-сложности

Но как именно соотносятся время и память? Существует ли полная взаимозаменяемость между задачами из класса полиномиального пространства и полиномиального времени ?

Этот дискурс становится особенно острым в эпоху деградации качества интернета и софта. Разработчики все чаще жертвуют эффективностью ради скорости написания кода, считая такой компромисс оправданным: аппаратные ресурсы дешевы, а интеллектуальные — дороги. Это привело к тотальному «раздуванию» программного обеспечения, которое становится все более медлительным на фоне примитивизации интерфейсов и общего снижения цифровой грамотности.

Со времен классического труда Джона Хопкрофта «О соотношении времени и пространства» (1977) научное сообщество придерживалось интуитивной гипотезы: при усложнении задачи требования к памяти растут пропорционально числу операций.

Однако недавние исследования перевернули это представление. Выяснилось, что для выполнения вычислений длительностью t шагов требуется не линейный объем памяти, а величина порядка $\sqrt{t}$ .

P ≠ PSPACE

В теории сложности класс объединяет проблемы, которые могут быть решены при ограниченном (полиномиальном) потреблении памяти (например, или ). Экспоненциальный рост затрат () выводит задачу за пределы этого класса. Аналогично, класс описывает алгоритмы с полиномиальным временем выполнения.

Ученые полвека пытались понять, насколько глубоко пересекаются эти множества. Каковы теоретические лимиты «сжатия» вычислений в пространство памяти и как именно масштабируется потребление ресурсов? До недавнего времени удалось доказать возможность решения лишь узкого спектра задач в объеме $t / \log t$ бит. Считалось, что эта линейная зависимость универсальна: стократное усложнение требует стократного объема памяти.

Но эта логика оказалась ошибочной.

Прорывное открытие

На симпозиуме ACM в Праге была представлена фундаментальная работа Райана Уильямса из MIT. Он математически обосновал, что любая задача, требующая времени , реализуема всего в $\sqrt{t}$ бит памяти. Это означает, что для алгоритма, ставшего сложнее в 100 раз, достаточно увеличить память всего в 10 раз. Для индустрии это стало подлинной сенсацией.

«Данный результат опровергает устоявшуюся интуицию, — отметил Уильямс в интервью Quanta Magazine. — Поначалу я даже усомнился в корректности собственного доказательства, настолько неожиданным был вывод».

В основе его метода лежит редукция — трансформация исходной проблемы в эквивалентную математическую форму, позволяющую предельно эффективно переиспользовать пространство. Любую операцию можно упаковать в компактный контейнер объемом в квадратный корень от исходного набора бит.

«Это поразительный шаг вперед, — констатирует Махди Черагчи из Мичиганского университета. — Ранее существование таких алгоритмов в столь малом объеме памяти считалось невозможным».

Архитектура доказательства

Разделение P и PSPACE подразумевает доказательство того, что в линейном пространстве существуют задачи, которые невозможно выполнить за время для любого фиксированного $k\geq1$ . Работа Уильямса демонстрирует, что существуют проблемы, разрешимые в пространстве , но требующие времени более $n^2/{\log^c}n$ .

Это первый случай полиномиального разделения ресурсов в рамках классической многоленточной машины Тьюринга. Достигается это путем сверхэффективной симуляции временных процессов в сжатом пространстве.

Автор формулирует теорему, согласно которой для любой функции $t(n) \geq n$ справедливо соотношение:

$TIME[t(n)] ⊆ SPACE[\sqrt{t(n) \log t(n)}]$

Для обоснования используется инновационная структура «дерева вычислений» (Tree Evaluation) и модернизированный алгоритм:

Операции машины Тьюринга сегментируются на блоки по b шагов.
Формируется дерево, где каждый узел отражает состояние блока ленты, зависящее от предыдущих состояний (дочерних узлов).
Применяется алгоритм Кука–Мерца (2012), позволяющий вычислить корень дерева при экстремально низких затратах памяти:

$O(d⋅b+h \log⁡(d⋅b))$

Грамотный подбор параметров позволяет свести итоговое потребление памяти к $O(\sqrt{t \log t})$ .

Как иронично замечали авторы «Programming Perl»: «Недостаток памяти решается покупкой планок, но если у вас закончилось время — это катастрофа».

За свои исследования в области нижних границ сложности Райан Уильямс был удостоен премии Гёделя 2024 года. Посмотреть его выступление на церемонии в Таллине можно здесь:

Прежде чем перейти к просмотру YouTubeconsent.youtube.com

Культура эффективного кода

Этот научный прорыв меняет наши взгляды на архитектуру вычислений. Истинным барьером оказывается не физический объем носителя, а филигранная точность управления им.

Подобный подход всегда был характерен для выдающихся инженеров. Например, Фабрис Беллар и его проект MicroQuickJS — JS-движок для эмбеддед-систем, требующий всего 10 КБ ОЗУ. Библиотека на C занимает лишь 100 КБ, обеспечивая при этом быстродействие, сопоставимое с полноценными аналогами.