Claude заменил 4,9 МБ таблиц эмулятора PSP на 10,5 КБ

Claude Opus 5.5 примерно за час восстановил, как векторный блок VFPU в Sony PSP считает синус, log2, обратную величину и ещё пять функций. Теперь эмулятор PPSSPP вместо 4,9 МБ таблиц поправок обойдётся 10,5 КБ коэффициентов, и в будущих версиях точную эмуляцию этих функций включат по умолчанию. Как рассказали 24 сентября в блоге PPSSPP, новый код повторяет приставку бит в бит на каждом из 2^32 входов и работает быстрее старого: на синусе время упало с 14,6 до 5,9 нс.

VFPU устроен как сопроцессор MIPS: поток инструкций у него общий с основным CPU, а конвейер свой. Как и в современных GPU, в нём есть блок специальных функций: vrcp, vrsq, vsqrt, vexp2, vsin, vcos, vasin и vlog2, плюс vrot, который выдаёт синус и косинус разом для матриц поворота. Что эти инструкции возвращают, известно давно. Все они дают приближения, и ни одна не выдаёт корректно округлённого результата по IEEE. А вот как эти приближения получаются, не знал никто. Давний контрибьютор проекта fp64 добился точности в лоб: снял с настоящей PSP полные таблицы результатов и положил их поверх простого базового приближения в виде поправок на каждые 64 входа и списков исключений. В эмулятор это ушло файлами .dat примерно на 4,9 МБ и стоило части производительности.

Разработчика PPSSPP подтолкнула работа skmp, который с помощью трёх моделей разобрал FPU процессора SH-4 в Sega Dreamcast. Технический разбор в посте написал сам Claude, а люди его лишь слегка отредактировали. Вот замеры из поста, старая реализация на таблицах против новой:

• rcp: 4,2 → 3,6 нс
• rsqrt: 5,4 → 3,6 нс
• exp2: 6,3 → 3,9 нс
• log2: 7,1 → 5,1 нс
• sin: 14,6 → 5,9 нс
• asin: 6,0 → 3,6 нс

Для vrot общее приведение аргумента ускоряет пару синус-косинус примерно на 10%.

Эталон и полный перебор

Внутрь чипа никто не заглядывал. Claude опирался на код fp64 как на оракул (эталон, который на любой вход отвечает так же, как железо): он совпадает с приставкой везде и прогоняется за секунду на ноутбуке. Перед этим новый аппаратный тест pspautotests cpu/vfpu/exact прогнал на настоящей PSP особые значения и проходы по экспонентам. Тест сошёлся с оракулом, а заодно нашёл несколько расхождений в других CPU-бэкендах эмулятора. Проверка любой гипотезы на всех 2^32 входах занимает всего 30 секунд, так что неверные идеи отсеивались за минуты, и на этой связке держится весь час работы.

Очевидный ход не сработал. Кусочная квадратичная подгонка давала около 93% точных ответов при любом размере кусков и любой степени полинома. Хенрик подсказал, что функции могут собираться из скалярных произведений vdot: на Dreamcast блок FIPR, считающий скалярное произведение, как раз переиспользовался для приближения функций. Но и один vdot с коэффициентами во float застрял на 92%. Лучший вещественный полином промахивался примерно на один ulp (единицу младшего разряда результата), и это указывало на что-то дискретное, чего метод наименьших квадратов не увидит в принципе. Тогда Claude сменил вопрос: вместо «насколько близко можно подойти» он спрашивал, существуют ли вообще коэффициенты, которые воспроизводят каждый выход точно. Каждый выход при такой постановке превращается в интервал допустимых значений для неизвестных, а пересекать интервалы дёшево.

Один квадратор на все функции

Структуру удалось прочитать прямо из данных. Внутри каждых 64 подряд идущих входов выход лежит строго на прямой, а общий наклон делят 1 024 таких отрезка, но никогда не 2 048. Выходит, старшие 7 бит мантиссы выбирают один из 128 сегментов, и наклон в сегменте равен производной в его центре. Так выглядит учебный аппаратный квадратичный интерполятор: маленькая таблица по старшим битам и арифметика над остальными. После вычитания гладкой части остаётся пила высотой в один ulp, одинаковая у всех функций. Из неё следовало, что квадратичный член округляется вниз до целых ulp отдельно от линейного и от суммы.

Как именно он округляется, долго не получалось. Усечённые и разбитые квадраторы, округление с фазой, четверть и половина ulp упирались в одну стену: 99,65% верных выходов, а остальные отставали на шаг там, где квадратичный член оказывался в пределах примерно 0,015 ulp от целого. Помогло совпадение в выводе одного из проходов: у сегментов rcp с 115 по 120 лучший квадратичный коэффициент сошёлся до четвёртого знака, 143,9636. Одинаковые десятичные означали одинаковые целые данные. Более того, целочисленные последовательности совпадали байт в байт между функциями: 32-й сегмент exp2 повторяет 116-й сегмент rcp. Значит, квадратор один на всех, и его выход зависит только от коэффициента и смещения внутри сегмента.

Дальше квадратор уже измеряли, а не угадывали. По 109 разным значениям коэффициента в данных Claude решил его выход напрямую и выяснил, что t² округляется вверх до кратного 256. С этим правилом сошлись все 512 сегментов rcp, rsqrt, sqrt и exp2, и с первого прогона код совпал с fp64 на всех 2^32 входах, если не считать одного бага в обвязке.

Два случая потребовали своих поправок. Синус не ложился ни при каком размере сегментов, пока не выяснилось, что железо индексирует четверть волны с другого конца и фактически считает синус как косинус дополнительного угла. log2 для входов от 1 до 4 сошёлся сразу, а для остальных оказалось, что схема урезает коэффициенты под точность выхода. При отрицательных экспонентах квадратичный член пропадает целиком, поэтому этот путь и выглядел как простая линейная интерполяция.

Что известно о самом чипе

Найденная схема описана в литературе по аппаратному вычислению функций: это минимаксный квадратичный интерполятор Пиньейро, Обермана, Мюллера и Бругеры и мультифункциональный интерполятор NVIDIA (Оберман и Сиу, 2005), который покрывает почти тот же набор функций. В VFPU на каждую функцию приходится ПЗУ на 128 записей, квадратор видит только старшие 10 бит смещения, а разрядность коэффициентов подрезана под нужную точность. Зачем так делать, объясняет, например, статья на MDPI о таких интерполяторах: укороченные коэффициенты уменьшают таблицы, а усечённые умножители и квадраторы сокращают площадь, задержку и потребление.

Одного по выходам не скажешь: делит ли финальный сумматор схему с vdot, как на Dreamcast. Раздельно усечённые произведения с такой версией совместимы, но и только.

Часть тупиков Claude устроил себе сам. Один перебор шагал по коэффициенту так грубо, что не мог попасть в верное значение, одна выборка вычитала константу дважды, а из-за особенности zsh один проход по параметрам молча не проверял ничего. Отсюда последний из выводов в разборе Claude: «Подозревайте собственные инструменты. Несколько "невозможных" результатов оказались багами в моём поисковом коде».