Много лет назад я работал в отделе Xbox 360 компании Microsoft. Мы думали над выпуском новой консоли, и решили, что было бы здорово, если эта консоль сможет запускать игры с консоли предыдущего поколения.
В первом Xbox (не путать с Xbox One) использовался ЦП x86. Эмуляция — это всегда сложно, но она оказывается ещё труднее, если твоё корпоративное начальство постоянно меняет типы центральных процессоров. В третьем Xbox, то есть в Xbox One, использовался ЦП x86/x64. Во втором Xbox, то есть, простите, в Xbox 360 использовался процессор PowerPC. Подобные скачки между разными ISA не упрощали нам жизнь.
Затем меня попросили изучить вопрос эмуляции ЦП PowerPC консоли Xbox 360 на ЦП x64. Я участвовал в работе команды, которая учила Xbox 360 эмулировать многие игры первого Xbox, то есть эмулировать x86 на PowerPC, и за эту работу получил титул «ниндзя эмуляции». Заранее скажу, что удовлетворительного решения я не нашёл.
FMA != MMA
Одним из самых волновавших меня аспектов было умножение-сложение с однократным округлением (fused multiply add), или инструкции FMA. Эти инструкции получали на входе три параметра, перемножали два первых, а затем прибавляли третий. Fused означало, что округление не выполняется до конца операции. То есть умножение выполняется с полной точностью, после чего выполняется сложение, и только затем результат округляется до окончательного ответа.
Представим это вычисление, показанное в виде функции: Чтобы показать это на конкретном примере, давайте представим, что мы используем десятичные числа с плавающей запятой и двумя разрядами точности.
1e1, 2.
FMA(8. 1e1), или 8. 9e1, 4. 9e1 + 4. 1e1 * 2. 1e1, или 81 * 29 + 41
81*29 равно 2349 и после прибавления 41 мы получаем 2390. Округлив до двух разрядов, мы получаем 2400 или 2.4e3.
3e3). Если у нас нет FMA, то нам придётся сначала выполнять умножение, получить 2349, что округлится до двух разрядов точности и даст 2300 (2. 3e3), который менее точен, чем ответ FMA. Затем мы прибавляем 41 и получаем 2341, что снова будет округлено и мы получим окончательный результат 2300 (2.
Примечание 1:
FMA(a,b, -a*b)вычисляет ошибку вa*b, что вообще-то круто.Примечание 2: Один из побочных эффектов примечания 1 заключается в том
x = a * b – a * bможет не вернуть ноль, если компьютер автоматически генерирует инструкции FMA.
Итак, очевидно, что FMA даёт более точные результаты, чем отдельные инструкции умножения и сложения. Мы не будем углубляться, но согласимся с тем, что если нам нужно перемножить два числа, а затем прибавить третье, то FMA будет более точной, чем её альтернативы. Кроме того, инструкции FMA часто имеют меньшую задержку, чем инструкция умножения с последующей инструкцией сложения. В ЦП Xbox 360 задежка и скорость обработки FMA была равна этим показателям у fmul или fadd, поэтому использование FMA вместо fmul с последующей зависимой fadd позволяло снизить задержку вдвое.
Эмуляция FMA
Компилятор Xbox 360 всегда генерировал инструкции FMA, как векторные, так и скалярные. Мы не были уверены, что выбранные нами процессоры x64 будут поддерживать эти инструкции, поэтому критически важно было эмулировать их быстро и точно. Необходимо было, чтобы наша эмуляция этих инструкций стала идеальной, потому что по предыдущему опыту эмуляции вычислений с плавающей запятой я знал, что «достаточно близкие» результаты приводили проваливанию персонажей сквозь пол, разлёту автомобилей за пределы мира, и так далее.
Так что же нужно для идеальной эмуляции инструкций FMA, если ЦП x64 не поддерживает их?
К счастью, подавляющее большинство вычислений с плавающей запятой в играх выполняется с точностью float (32 бита), и я с радостью мог использовать в эмуляции FMA инструкции с точностью double (64 бит).
Float имеет точность 24 бит, а double — точность 53 бита. Кажется, что эмуляция инструкций FMA, имеющих точность float, с помощью вычислений с точностью double должна быть простой (голос рассказчика: но это не так; работа с плавающей запятой никогда не бывает простой). То есть для хранения полностью точных результатов достаточно всего 48 бит точности, а у нас есть больше, то есть всё в порядке. Это значит, что если преобразовать входящие float в точность double (преобразование без потерь), то затем можно выполнять умножение без ошибок.
Достаточно всего лишь взять второе слагаемое в формате float, преобразовать его в double, а затем сложить его с результатом умножения. Затем нам нужно выполнить сложение. Наша логика идеальна. Так как в процессе умножения округления не происходит, и оно выполняется только после сложения, этого совершенно достаточно для эмуляции FMA. Можно объявлять о победе и возвращаться домой.
Победа была так близка…
Но это не работает. Или, по крайней мере, завершается неудачей для части входящих данных. Поразмыслите самостоятельно, почему так может произойти.
Звучит музыка удержания звонка…
Сбой возникает, потому что по определению FMA умножение и сложение выполняются с полной точностью, после чего результат округляется то точности float. Нам почти удалось этого добиться.
Это похоже на то, что мы пытаемся сделать. Умножение происходит без округления, а затем, после сложения, выполняется округление. После этого нам нужно сохранить результат с точностью float, из-за чего снова происходит округление. Но округление после сложения выполняется с точностью double.
Двойное округление. Уф-ф-ф.
И давайте представим, что мы вычисляем FMA(8. Наглядно показать это будет сложновато, так что давайте вернёмся к нашим десятичным форматам с плавающей запятой, где точность single — это два десятичных разряда, а точность double — четыре разряда. 9e1, 9. 1e1, 2. 99. 9e-1), или 81 * 29 + .
99 или 2. Совершенно точным ответом этого выражения будет 2349. Округлив до точности single (два разряда), мы получим .2. 34999e3. Посмотрим, что пойдёт не так, когда мы попробуем эмулировать эти вычисления. 3e3
Пока всё отлично. Когда мы выполняем умножение 81 и 29 с точностью double, то получаем 2349.
99 и получаем 2349. Затем мы прибавляем . По-прежнему всё отлично. 99.
350e3). Этот результат округляется до точности double и мы получаем 2350 (2. Ой-ёй.
4e3). Мы округляем это до точности single и по правилам IEEE округления до ближайшего чётного получаем 2400 (2. Он имеет слегка бОльшую ошибку, чем правильно округлённый результат, возвращаемый инструкцией FMA. Это неверный ответ.
Однако, какое бы правило округления вы ни выбрали, всегда будет случай, когда двойное округление возвращает результат, отличающийся от истинной FMA. Вы можете заявить, что проблема в правиле IEEE окружения до ближайшего чётного.
Чем же всё закончилось?
Полностью удовлетворяющего меня решения этой проблемы мне найти не удалось.
В современных ЦП x64 есть инструкции FMA, способные идеально эмулировать такие операции. Я ушёл из команды Xbox задолго до выпуска Xbox One и с тех пор не уделял консоли особого внимания, поэтому не знаю, к какому решению они пришли. А возможно, разработчики просто решили, что результаты достаточно близки и их можно использовать. Также можно каким-то образом использовать для эмуляции FMA математический сопроцессор x87 — я не помню, к какому выводу пришёл при изучении этого вопроса.
