Много лет назад я работал в отделе Xbox 360 компании Microsoft. Мы думали над выпуском новой консоли, и решили, что было бы здорово, если эта консоль сможет запускать игры с консоли предыдущего поколения.

Эмуляция — это всегда сложно, но она оказывается ещё труднее, если твоё корпоративное начальство постоянно меняет типы центральных процессоров. В первом Xbox (не путать с Xbox One) использовался ЦП x86. Во втором Xbox, то есть, простите, в Xbox 360 использовался процессор PowerPC. В третьем Xbox, то есть в Xbox One, использовался ЦП x86/x64. Подобные скачки между разными ISA не упрощали нам жизнь.

Я участвовал в работе команды, которая учила Xbox 360 эмулировать многие игры первого Xbox, то есть эмулировать x86 на PowerPC, и за эту работу получил титул «ниндзя эмуляции». Затем меня попросили изучить вопрос эмуляции ЦП PowerPC консоли Xbox 360 на ЦП x64. Заранее скажу, что удовлетворительного решения я не нашёл.


FMA != MMA


Одним из самых волновавших меня аспектов было умножение-сложение с однократным округлением (fused multiply add), или инструкции FMA. Эти инструкции получали на входе три параметра, перемножали два первых, а затем прибавляли третий. Fused означало, что округление не выполняется до конца операции. То есть умножение выполняется с полной точностью, после чего выполняется сложение, и только затем результат округляется до окончательного ответа.

Чтобы показать это на конкретном примере, давайте представим, что мы используем десятичные числа с плавающей запятой и двумя разрядами точности. Представим это вычисление, показанное в виде функции:

FMA(8.1e1, 2.9e1, 4.1e1), или 8.1e1 * 2.9e1 + 4.1e1, или 81 * 29 + 41

81*29 равно 2349 и после прибавления 41 мы получаем 2390. Округлив до двух разрядов, мы получаем 2400 или 2.4e3.

Если у нас нет FMA, то нам придётся сначала выполнять умножение, получить 2349, что округлится до двух разрядов точности и даст 2300 (2.3e3). Затем мы прибавляем 41 и получаем 2341, что снова будет округлено и мы получим окончательный результат 2300 (2.3e3), который менее точен, чем ответ FMA.

Примечание 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 бит).

Кажется, что эмуляция инструкций FMA, имеющих точность float, с помощью вычислений с точностью double должна быть простой (голос рассказчика: но это не так; работа с плавающей запятой никогда не бывает простой). Float имеет точность 24 бит, а double — точность 53 бита. Это значит, что если преобразовать входящие float в точность double (преобразование без потерь), то затем можно выполнять умножение без ошибок. То есть для хранения полностью точных результатов достаточно всего 48 бит точности, а у нас есть больше, то есть всё в порядке.

Затем нам нужно выполнить сложение. Достаточно всего лишь взять второе слагаемое в формате float, преобразовать его в double, а затем сложить его с результатом умножения. Так как в процессе умножения округления не происходит, и оно выполняется только после сложения, этого совершенно достаточно для эмуляции FMA. Наша логика идеальна. Можно объявлять о победе и возвращаться домой.

Победа была так близка…


Но это не работает. Или, по крайней мере, завершается неудачей для части входящих данных. Поразмыслите самостоятельно, почему так может произойти.

Звучит музыка удержания звонка…

Сбой возникает, потому что по определению FMA умножение и сложение выполняются с полной точностью, после чего результат округляется то точности float. Нам почти удалось этого добиться.

Умножение происходит без округления, а затем, после сложения, выполняется округление. Это похоже на то, что мы пытаемся сделать. Но округление после сложения выполняется с точностью double. После этого нам нужно сохранить результат с точностью float, из-за чего снова происходит округление.

Уф-ф-ф. Двойное округление.

Наглядно показать это будет сложновато, так что давайте вернёмся к нашим десятичным форматам с плавающей запятой, где точность single — это два десятичных разряда, а точность double — четыре разряда. И давайте представим, что мы вычисляем FMA(8.1e1, 2.9e1, 9.9e-1), или 81 * 29 + .99.

Совершенно точным ответом этого выражения будет 2349.99 или 2.34999e3. Округлив до точности single (два разряда), мы получим 2.3e3. Посмотрим, что пойдёт не так, когда мы попробуем эмулировать эти вычисления.

Когда мы выполняем умножение 81 и 29 с точностью double, то получаем 2349. Пока всё отлично.

Затем мы прибавляем .99 и получаем 2349.99. По-прежнему всё отлично.

Этот результат округляется до точности double и мы получаем 2350 (2.350e3). Ой-ёй.

Мы округляем это до точности single и по правилам IEEE округления до ближайшего чётного получаем 2400 (2.4e3). Это неверный ответ. Он имеет слегка бОльшую ошибку, чем правильно округлённый результат, возвращаемый инструкцией FMA.

Вы можете заявить, что проблема в правиле IEEE окружения до ближайшего чётного. Однако, какое бы правило округления вы ни выбрали, всегда будет случай, когда двойное округление возвращает результат, отличающийся от истинной FMA.

Чем же всё закончилось?


Полностью удовлетворяющего меня решения этой проблемы мне найти не удалось.

Я ушёл из команды Xbox задолго до выпуска Xbox One и с тех пор не уделял консоли особого внимания, поэтому не знаю, к какому решению они пришли. В современных ЦП x64 есть инструкции FMA, способные идеально эмулировать такие операции. Также можно каким-то образом использовать для эмуляции FMA математический сопроцессор x87 — я не помню, к какому выводу пришёл при изучении этого вопроса. А возможно, разработчики просто решили, что результаты достаточно близки и их можно использовать.

Комментарии (3)


  1. akhalat
    11.04.2019 17:07

    В современных ЦП x64 есть инструкции FMA, способные идеально эмулировать такие операции


    А смысл, если результат всё равно будет double и опять возникнет проблема двойного округления?
    Или " современных ЦП x64" есть инструкции FMA именно над float?

    А вообще в эмуляции всё ещё веселее. Например, в Playstation 2 плавающие числа реализованы не по IEEE, там при определенной операции (деление на 0 что ли, или 0/0) возникает другое число, а не то, что будет на компьютерных процах. И некоторые разрабы активно пользовались в играх подобных «хаком».


    1. Nagg
      11.04.2019 17:13
      +1

      Или " современных ЦП x64" есть инструкции FMA именно над float?

      И float и double есть в FMA.
      Сохранение точности, кстати, по сути нарушает IEEE754.


  1. netch80
    14.04.2019 19:56

    Двойное округление имеет меньше проблем, если первое округление делать особым образом — в двоичном случае это round to nearest, ties to odd (а не even, как по умолчанию). Ещё это называется «фоннеймановское округление».
    Реализовано, например, в IBM zSeries:

    > Round to prepare for shorter precision: For a BFP or HFP (то есть двоичная арифметика), permissible set, the candidate selected is the one whose voting digit has an odd value. For a DFP permissible set (десятичная арифметика), the candidate that is smaller in magnitude is selected, unless its voting digit has a value of either 0 or 5; in that case, the candidate that is greater in magnitude is selected.

    На x86 (любой разрядности), увы, такого не водится.