32bit_me 16 сен 2019 в 06:05

Posit-арифметика: победа над floating point на его собственном поле. Часть 2

12 мин

8.3K

Open source*Анализ и проектирование систем*Математика*Ненормальное программирование*Программирование*

Перевод

Автор оригинала: John L. Gustafson, Isaac Yonemoto

Часть 1

4. Количественное сравнение числовых систем

4.1. Определение десятичной точности

Точность обратна ошибке. Если у нас есть пара чисел x и y (ненулевых и одного знака), расстояние между ними в порядках величин составляет $\mid log_{10}( x / y )\mid$ десятичных порядков, это та же самая мера, которая определяет динамический диапазон между самым маленьким и самым большим представимым положительным числом x и y. Идеальным распределением десяти чисел между 1 и 10 в вещественной системе счисления было бы не равномерное распределение чисел по порядку от 1 до 10, а экспоненциальное: $1, 10^{1/10}, 10^{2/10},..., 10^{9/10}, 10$ . Это шкала децибел, долгое время используемая инженерами для выражения отношений, например, 10 децибел — это десятикратное отношение. 30db означает коэффициент $inline$ . Отношение 1db — это коэффициент около 1,26, если вы знаете значение с точностью 1db, вы имеете точность 1 десятичный знак. Если вы знаете величину с точностью 0,1 db, это означает 2 знака точности, и т.п. Формула десятичной точности — $log_{10}(1/\mid log_{10}(x/y)\mid)=-log_{10}(\mid log_{10}(x/y)\mid )$ , где x и y — либо корректные значения, вычисленные с использованием систем округления, таких, какие используются в форматах float и posit, либо верхние и нижние границы, если используются строгие системы, использующие интервалы, или значения valid.

4.2. Определение множеств сравнения чисел float и posit

Мы можем создать масштабные модели чисел float и posit длиной по 8 бит каждое. Преимущество данного подхода в том, что 256 значений, это достаточно маленькое множество, чтобы мы могли проверить его полностью, и сравнить все $inline$ вхождений в таблицах для операций сложения, вычитания, умножения и деления. Вещественные числа с точностью 1/4 имеют один знаковый бит, четыре бита экспоненты и три бита дробной части, и придерживаются всех правил стандарта IEEE 754. Наименьшее положительное число (денормализованное) равно 1/1024, наибольшее положительное равно 240, динамический диапазон ассиметричен и равен 5,1 десятичных порядков.14 битовых комбинаций представляют NaN.

Сравнимое 8-битное posit использует es=1, имеет диапазон положительных чисел от 1/4096 до 4096, симметричный динамический диапазон 7,2 десятичных порядков. Значений NaN нет. Мы можем построить графики десятичной точности положительных чисел в обоих наборах, как показано на рис. 7. Отметим, что значения, представленные числами posit, имеют на два десятичных порядка больший динамический диапазон, чем числа float, и точность такую же или больше для всех значений, кроме тех, где числа float близки к переполнению или антипереполнению. Зазубренность графиков для обоих систем представляет собой логарифмическую аппроксимацию кусочно-линейной функции. У чисел float точность снижается только слева, на участке, близком к антиперепонению, справа функция обрывается, т.к. дальше идут значения NaN. Числа posit имеют более симметрично уменьшающуюся по краям функцию точности.

Рис. 7. Сравнение десятичной точности чисел float и posit

4.3. Сравнение операций одного аргумента

4.3.1. Обратное значение

Для каждого возможного входного значения x функции 1/x, результат может точно соответствовать другому значению в данном множестве, или может быть округлён, в этом случае мы можем измерить десятичную ошибку, используя формулу из раздела 4.1, для чисел float, результат может привести к переполнению или NaN. См. рис. 8.

Рис. 8. Количественное сравнение чисел float и posit при вычислении обратного значения

Кривые на правом графике показывают величину ошибки при вычислении обратного значения, при этом числа float могут давать в результате NaN. Числа posit превосходят float в большом числе случаев, и это превосходство сохраняется во всём диапазоне. Вычисление обратного значения денормализованных чисел float приводит к переполнению, что приводит к бесконечному значению ошибки, и, конечно, аргумент NaN даёт обратное значение NaN. Числа posit замкнуты относительно вычисления обратного значения.

4.3.2. Квадратный корень

Функция квадратного корня не приводит к переполнению или антипереполнению. Для отрицательных аргументов, и для NaN результат будет NaN. Вспомним, что у нас «масштабная модель» чисел float и posit, преимущества posit возрастают с увеличением точности данных. Для 64-битных float и posit, ошибка posit будет составлять около 1/30 ошибки float, вместо 1/2.

4.3.3. Квадрат

Другая распространённая унарная операция — это $inline$ . Переполнения и антипереполнения обычное дело при возведении float в квадрат. Почти для половины float возведение в квадрат не приводит к осмысленному результату, тогда как возведение числа posit в квадрат всегда даёт в результате число posit (квадрат беззнаковой бесконечности есть беззнаковая бесконечность).

Рис. 9. Количественное сравнение чисел float и posit при вычислении $\sqrt x$

Рис. 10. Количественное сравнение чисел float и posit при вычислении $inline$

4.3.4. Логарифм по основанию 2

Мы также провели сравнение для покрытия функции логарифма по основанию 2, то есть процент случаев, при которых $inline$ может быть точно представлен, и если он не может быть точно представлен, сколько десятичных знаков мы теряем. Числа float имеют в этом случае единственное преимущество: с их помощью можно представить $inline$ как $-\infty$ и $log_2(\infty)$ как $\infty$ , но это более чем компенсируется большим словарём целых степеней двойки для чисел posit.

Рис. 11. Количественное сравнение чисел float и posit при вычислении $inline$

График похож на аналогичный для квадратного корня, примерно половина случаев даёт NaN в обоих случаях, но числа posit имеют вдвое меньшую потерю десятичной точности. Если вы можете вычислить $inline$ , нужно только умножить результат на масштабирующий коэффициент, чтобы получить $inline$ или $log_{10}(x)$ или логарифм с любым другим основанием.

4.3.5. Экспонента, $inline$

Аналогично, если вы можете вычислять $inline$ , вы можете легко с помощю масштабирующего коэффициента получить $inline$ или $inline$ и т.п. Числа posit имеют одно исключение, $inline$ равно NaN, когда аргумент равен $\pm\infty$ .

Рис. 12. Количественное сравнение чисел float и posit при вычислении $inline$

Максимальные десятичные потери для чисел posit могут показаться большими, так как $2^{maxpos}$ будут округлены обратно до maxpos. В этом примере, только небольшое количество ошибок так же велико, как $log_{10}(24096)\approx1233$ десятичных порядков. Решайте, что лучше: потерять свыше тысячи десятичны порядков, или потерять бесконечное количество десятичных порядков? Если вы можете не использовать настолько бльшие числа, числа posit по-прежнему выигрывают, потому что ошибки при маленьких значениях намного лучше. Во всех случаях, когда вы потеряете большое количество десятичных порядков при использовании чисел posit, входной аргумент лежит далеко за пределами того, что числа float могут даже выразить. Графики показывают, насколько числа posit более стабильны в терминах динамического диапазона, в котором результат имеет смысл, и имеют превосходство в точности в пределах этого диапазона.

Для обычных унарных операций $1/x, \sqrt x, x^2, log_2(x)$ и $inline$ , числа posit всецело и неизменно более точны, чем числа float с тем же числом бит, и выдают осмысленный результат в широком динамическом диапазоне. Мы сейчас обратим наше внимание на четыре элементарных арифметических действия, имеющие два аргумента: сложение, вычитание, умножение и деление.

4.4. Сравнение операций двух аргументов

Мы можем использовать масштабную модель числовой системы для изучения арифметических операций двух аргументов, таких, как сложение, вычитание, умножение и деление. Для того, чтобы визуализировать 65536 результатов, мы делаем «график покрытия» 256*256, который наглядно показывает, какая доля результатов точна, неточна, вызывает переполнение, антипереполнение или NaN.

4.4.1. Сложение и вычитание

Так как $inline$ прекрасно работает как для float, так и для posit, нет необходимости изучать вычитание отдельно. Для операции сложения, мы вычисляем точное значение $inline$ , и сравниваем его с суммой, возвращённой в каждой из числовых систем. Может случиться, что результат неточный, тогда он должен быть округлён до ближайшего конечного ненулевого числа, может произойти переполнение или антипереполнение, или неопределённость вида $\infty-\infty$ , которая даёт в результате NaN. Каждый из этих случаев отмечен цветом, и мы можем охватить всю таблицу сложения одним взглядом. В случае округления результатов, цвет изменяется от чёрного (точное значение) до фиолетового (точное значение для posit и float). Рис. 13 показывает, на что похож график покрытия для чисел float и unum. Как и с унарными операциями, но имея гораздо больше точек, мы можем сделать выводы о способности каждой числовой системы давать осмысленные и точные ответы:

Рис. 13. Полный график покрытия для сложения чисел float и posit

Рис. 14. Количественное сравнение чисел float и posit для сложения

С первого взгляда становится очевидно, что числа posit имеет существенно больше точек на графике сложения, в которых результат точный. Широкая чёрная диагональная полоса на графике покрытия для float гораздо шире, чем она будет для большей точности, потому что она представляет зону денормализованных чисел, в которой числа float отстоят друг от друга на равных промежутках, подобно числам с фиксированной точкой, такие числа составляют большую долю от общего числа только в случае 8-битных чисел.

4.4.2. Умножение

Мы используем похожий подход для сравнения того, насколько хорошо числа float и posit умножаются. В отличие от сложения, умножение может вызвать антипереполнение чисел float. «Постепенное антипереполнение», зона, которую вы можете видеть в центре на рис.15. слева. (имеется в виду денормализованные числа. прим. перев.) Без этой зоны, голубая зона антипереполнения имела бы форму ромба. График умножения для чисел posit менее разноцветный, что лучше. Только два пиксела подсвечены как NaN, близко к месту, гда находится нулевая метка осей (пикселы крайний слева в центре по вертикали, и внизу в центре по горизонтали. прим. перев.) Там находятся результаты умножения $\pm\infty\cdot 0=NaN$ . Числа float имеют больше случаев, при которых произведение оказывается точным, но ужасной ценой. Как показано на рис.15, почти 1/4 всех произведений float приводит либо к переполнению, либо к антипереполнению, и эта доля не снижается при увеличении точности float.

Рис 15. Полный график покрытия для умножения чисел float и posit

Наихудший случай округления для чисел posit наступает при $maxpos \times maxpos$ , которое округляется снова до maxpos. Для таких случаев (очень редких) погрешность составлят 3,6 десятичных порядка. Как показываетграфик на рис. 16, числа posit существенно лучше, чем float, минимизируют ошибку умножения.

Рис. 16. Количественное сравнение чисел float и posit для умножения

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

4.5. Сравнения чисел float и posit для оценки выражений

4.5.1. Тест “32-битный бюджет точности”

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

$X=\left(\dfrac{27/10-e}{\pi-(\sqrt 2+\sqrt 3)}\right)^{67/16}=302.8827196\dotsb$

Правило состоит в том, что мы начинаем с наилучшего представления чисел $\pi$ и $inline$ , возможного в каждой из числовых систем, и представлений всех указанных целых чисел, и видим, сколько десятичных цифр совпадают с истинным значением X после выполнения девяти операций в выражении. Мы будем выделять неверные цифры оранжевым цветом.

Несмотря на то, что 32-битные числа IEEE float имеют десятичную точность, которая колеблется в диапазоне от 7.3 до 7.6 десятичных порядков, накопление ошибок округления при вычислении X даёт ответ 302.912⋯, имеющий всего три верные цифры. Это одна из причин того, что пользователи испытывают необходимость в использовании 64-битных float везде, так как даже простые выражения подвержены риску потери точности так сильно, что результат может оказаться бесполезен.

32-битные числа posit имеют переменную десятичную точность, которая колеблется между 8.2 и 8.5 десятичных порядков для чисел с абсолютным значением около 1. При вычислении X, они дают нам ответ 302.88231⋯, имеющий вдвое больше значащих цифр. Также не забываем, что 32-битные числа posit имеют динамический диапазон более 144 десятичных разрядов, а 32-битные float имеют гораздо меньший динамический диапазон 83 разряда. Следовательно, дополнительная точность результата достигается не за счёт сужения динамического диапазона.

4.5.2. Тест с четырёхкратной точностью: задача Голдберга о тонком треугольнике

Есть классическая задача о «тонком треугольнике» [1]: найти площадь треугольника со сторонами a, b, c, когда две из сторон b и c всего на 3 единицы младшего разряда (Units in the Last Place, ULPs) длиннее, чем половина длинной стороны (рис. 17).

Рис. 17. Задача Голдберга о тонком треугольнике

Классическая формула для площади A использует промежуточную переменную s:

$s=\frac{a+b+c}2;A=\sqrt{s(s-a)(s-b)(s-c)}$

Опасность в этой формуле заключается в том, что s очень близко к значению a, и вычисление $inline$ увеличивает погрешность округления очень сильно. Попробуем 128-битные (с четырёхкратной точностью) числа IEEE float, для которых $a=7,b=c=7/2+3\times 2^{− 111}$ . (Если за единицу измерения принять световой год, то короткая сторона будет длиннее половины длинной стороны всего на 1/200 диаметра протона. Но это делает треугольник высотой с дверной проём у вершины.) Мы также вычисляем значение A, используя 128-битные числа posit (es=7). Ниже приведены результаты:

$\begin{matrix} \textrm{Верное значение:} & 3.14784204874900425235885265494550774498\dots \times 10^{−16} \\ \textrm{128-bit IEEE float:} & 3.\color{orange}{63481490842332134725920516158057682788}\dots \times 10^{− 16}\\ \textrm{128-bit posit:} & 3.147842048749004252358852654945507744\color{orange}{39} \dots \times 10^{−16} \end{matrix}$

Числа posit имеют до 1.8 десятичных цифр точности больше по сравнению с float четырёхкратной точности в широком динамическом диапазоне: от $2\times 10^{− 270}$ до $5 \times 10^{− 269}$ . Этого достаточно для предотвращения катастрофических последствий усиления погрешности в данном конкретном случае. Интересно также отметить, что ответ в формате posit будет более точным, чем в формате float, даже если мы в конце скорвертируем его в 16-битный posit.

4.5.3. Решение квадратного уравнения

Существует классический приём, предназначенный для того, чтобы избежать ошибки округления при вычислении корней $inline$ , $inline$ уравнения $inline$ , используя обычную формулу $r_1,r_2=(-b\pm \sqrt {b^2-4ac})/(2a)$ , когда b намного больше, чем a и c, что приводит к пропаданию цифр слева, так как $\sqrt {b^2-4ac}$ очень близко к b. Но вместо того, чтобы заставлять программистов запоминать мистические приёмы, возможно, лучше, чтобы posit сделал вычисление безопасным при использовании простой формулы из учебника. Положим $inline$ и сравним результат в формате 32-битного float и posit.

Таблица 5. Решение квадратного уравнения

Численно неустойчивый корень — $inline$ , но отметим, что 32-битный posit даёт 6 верных цифр вместо 4-х для float.

4.6. Сравнение систем floats и Posit для классического теста LINPACK

Основным методом оценки суперкомпьютеров долгое время было решение $n\times n$ системы линейных уравнений $\mathbf Ax=b$ . А именно, тест заполняет матрицу A псевдослучайными числами от 0 до 1, и вектор b суммами строк A. Это означает, что решением x будет вектор, состоящий из единиц. Тест вычисляет норму вычетов $\|\mathbf Ax-b\|$ для проверки правильности, хотя нет жёстко установленного количества цифр, которые должны быть верными в ответе. Для теста типична потеря нескольких цифр точности, и обычно используются 64-битные float (не обязательно IEEE). Изначально тест предусматривал n=100, но этот размер оказался слишком мал для самых быстрых суперкомпьютеров, поэтому n было увеличено до 300, затем до 1000, и, наконец (с подачи первого автора), тест стал масштабируемым, и выдаёт количество операций в секунду, исходя из того, что тест выполняет $\frac {2}{3}n^3+2n^2$ операций умножения и сложения.

Сравнивая posit и float, мы отметили небольшой недостаток теста: ответ в общем случае не является последовательностью единиц, из-за ошибок округления сумм в строках. Такая ошибка может быть устранена, если мы найдём, какием вхождения в A вносят в сумму 1 бит, лежащий за пределами возможной точности, и установим этот бит в 0. Это даст нам уверенность, что сумма строки A представима без округления, и что ответ x на самом деле является вектором, состоящим из единиц. Для исходного варианта задачи, с размером 100х100, 64-битные IEEE float дают ответ такого вида:

0.9999999999999633626401873698341660201549530029296875
1.0000000000000011102230246251565404236316680908203125
$\vdots$
1.000000000000022648549702353193424642086029052734375

Ни одно из 100 чисел не является верным; они близки к 1, но никогда не равны 1. С числами posit, мы можем сделать замечательную вещь. Использовав 32-битные числа posit и тот же самый алгоритм, вычислим вычет $r = \mathbf Ax − b$ , используя операцию слияния — скалярное произведение. Затем решим $\mathbf Ax'=r$ (используя уже обработанное $\mathbf A$ ) и используем $inline$ для коррекции: $x \leftarrow x-x'$ . Результатом является беспреценднтно точный для теста LINPACK ответ: $\{1, 1,...,1\}$ . Могут ли правила LINPACK запретить использовать новый 32-битный тип чисел, использование которого позволяет достичь совершенного результата с нулевой ошибкой, или продолжат настаивать на использовании 64-битного float, который этого не позволяет? Это решение будут принимать те, кто отвечает за этот тест. Тем же, кому нужно решение систем линейных уравнений для решения реальных задач, а не сравнение скорости суперкомпьютеров, posit предлагает ошеломляющие преимущества.

5. Заключение

Posit побеждает float в его собственной игре: с его помощью можно выполнять вычисления и уменьшать ошибки округления. Числа posit имеют большую точность, больший динамический диапазон и большее покрытие. Они могут использоваться для получения лучших результатов, чем float той же разрядности, или (что может быть ещё большим конкурентным преимуществом), тех же результатов при меньшей разрядности. Так как пропускная способность систем ограничена, использование операндов меньшего размера означает большую скорость и меньшую потребляемую мощность.
Так как они работают как float, а не как интервальная система, они могут рассматриваться как прямая замена float, как и было продемонстрировано здесь. Если алгоритм, использующий float, проходит тесты, и время и стабильность «достаточно хороши», то с posit он будет работать ещё лучше. Комбинированные операции (fused operations), доступные в posit, предоставляют мощное средство для предотвращения накопления ошибок округления, и в некоторых случаях позволяют безопасно использовать 32-битные числа posit вместо 64-битных float в приложениях, требующих высокую производительность. Это в общем случае повысит производительность приложения в 2-4 раза, и сокращает потребляемую мощность, экономит энергию и снижает стоимость хранения данных. Аппаратная поддержка posit даст нам эквивалент одного или двух шагов закона Мура, без необходимости уменьшать размер транзистора или повышать стоимость. В отличие от float, система posit даёт побитовую воспроизводимость результатов на разных системах, избавляя нас от главного недостатка стандарта IEEE 754. Числа posit проще и элегантнее, чем float, и позволяют сократить количество аппаратуры для их поддержки. Хотя числа float сейчас распространены повсеместно, числа posit вскоре могут сделать их устарешими.

Ссылки:

1. David Goldberg. What every computer scientist should know about floating-point arithmetic.
ACM Computing Surveys (CSUR), 23(1):5–48, 1991. DOI: doi:10.1145/103162.103163.
2. John L Gustafson. The End of Error: Unum Computing, volume 24. CRC Press, 2015.
3. John L Gustafson. Beyond Floating Point: Next Generation Computer Arithmetic. Stanford Seminar: https://www.youtube.com/watch?v=aP0Y1uAA-2Y, 2016. full transcription
available at http://www.johngustafson.net/pdfs/DebateTranscription.pdf.
4. John L Gustafson. A radical approach to computation with real numbers. Supercomputing
Frontiers and Innovations, 3(2):38–53, 2016. doi:http://dx.doi.org/10.14529/jsfi160203.
5. John L Gustafson. The Great Debate @ ARITH23. https://www.youtube.com/watch?v=
KEAKYDyUua4, 2016. full transcription available at http://www.johngustafson.net/pdfs/
DebateTranscription.pdf.
6. Ulrich W Kulisch and Willard L Miranker. A new approach to scientific computation, volume 7. Elsevier, 2014.
7. More Sites. IEEE standard for floating-point arithmetic. IEEE Computer Society, 2008.
DOI:10.1109/IEEESTD.2008.4610935.
8. Isaac Yonemoto. https://github.com/interplanetary-robot/SigmoidNumbers

Теги:

Хабы: