ЧУЖОЙ ЗАПОЛНЕННЫЙ ДИСК УСКОРЯЕТ КОМПЬЮТЕРЫ

Одни задачи дёшевы по времени, но жадны до памяти, другие — наоборот. Для нескольких базовых задач теоретики доказали жёсткие пределы этого компромисса: с маленькой рабочей памятью быстро работать невозможно. Новая статья показывает, что эти пределы ломает странный ресурс — память, которая уже заполнена и должна быть возвращена в целости.

Одолженный жёсткий диск

Модель называется каталитическими вычислениями (catalytic computing); её ввели в 2014 году Бурман, Клив, Коуцки, Лофф и Спелман. Алгоритм получает крошечную чистую память, порядка log n бит для входа размера n, плюс огромную грязную память, уже заполненную произвольными данными, которые он не выбирал. Он может пользоваться обеими как угодно, но, когда он останавливается, каждый бит грязной памяти должен быть в точности таким, как был.

Авторы используют привычный образ: вы одалживаете у друга огромный жёсткий диск, полный драгоценных цифровых воспоминаний, чтобы провести вычисление. Терять друга вы не хотите, поэтому по окончании восстанавливаете каждый бит.

Изначально модель должна была доказать, что такая память бесполезна. Интуитивно, чтобы всё восстановить, нужно сохранить всю информацию, а значит, места никогда не освобождается. Удивительно, но оказалось наоборот: заполненная память позволяет решать задачи, которые никто не умеет решать с одной лишь чистой памятью. Но эти результаты касались объёма памяти, а алгоритмы были чрезвычайно медленными.

Быстрее доказуемо возможного

Адельмо Моррисон Ороско, Натан Шеффилд и Райан Уильямс (MIT) теперь обращаются к скорости. С логарифмической чистой памятью и полиномиальным объёмом одолженной памяти они предлагают алгоритмы, которые:

• сортируют список и вычисляют дискретное преобразование Фурье за время n^(1+o(1)), почти линейное;
• перемножают матрицы за время n^(ω+o(1)), так же быстро, как лучший известный метод с неограниченной памятью.

Без одолженного диска доказано, что произведение времени на память должно быть не меньше порядка n² для сортировки и преобразования Фурье и n³ для умножения матриц. Значит, эти каталитические алгоритмы достигают скоростей, недоступных ни одному обычному алгоритму с малой памятью. Авторы называют это первой безусловной демонстрацией того, что каталитические алгоритмы превосходят свои некаталитические аналоги.

Переключить, считать, отменить

Ключевой ингредиент — короткий комбинаторный трюк. Предположим, алгоритм может переключать участок одолженной памяти между неизвестным значением τ и τ + x, где x — интересующий его результат. В большой «вспомогательной» таблице, тоже одолженной, к тщательно выбранному набору ячеек прибавляется 1. Ячейка на позиции τ увеличивается на единицу тогда и только тогда, когда x принадлежит заданному множеству. Затем каждый шаг выполняется в обратном порядке, и диск становится прежним — за исключением того кусочка ответа, который был нужен.

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

Честное сравнение

Одно возражение: классические пределы предполагают, что ответ записывается один раз, слева направо, на отдельную выходную ленту, тогда как каталитические алгоритмы записывают ответ на одолженный диск. Статья отвечает и на это. Авторы показывают, что их алгоритмы могут записать ответ на выходную ленту за два прохода и что обычным алгоритмам два прохода помогают не больше, чем один. Значит, пределы по-прежнему применимы, и разделение сохраняется. Они также доказывают, что одного прохода недостаточно даже с одолженным диском: сортировка тогда упирается в тот же барьер n².

Длинный список выгодоприобретателей

Те же инструменты дают быстрые каталитические алгоритмы для умножения больших целых чисел и многочленов, подсчёта треугольников и поиска клик в сетях, обнаружения путей и циклов, а также поиска текстовых шаблонов с подстановочными символами. Их время работы совпадает, с точностью до небольших множителей, с лучшими известными алгоритмами, у которых памяти сколько угодно. В каждом случае одолженная память должна вернуться ровно такой, какой её дали взаймы.