Хабрахабр

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

Часть 2

В этой публикации я предлагаю вашему вниманию перевод статьи Джона Густафсона (автора Posit) и Айзека Йонемото, посвящённой формату Posit.
Так как статья имеет большой объём, я разделил её на две части. От переводчика: Тема формата Posit уже была на хабре здесь, но без существенных технических подробностей. Список ссылок находится в конце второй части.

В отличие от ранней формы — арифметики универсальных чисел (unum), стандарт posit не требует использования интервальной арифметики или операндов переменного размера, и, как и float, числа posit округляются, если результат не может быть представлен точно. Новый тип данных, называемый posit, разработан в качестве прямой замены чисел с плавающей точкой стандарта IEEE Standard 754. Числа posit не переполняются ни в сторону бесконечности, ни до нуля, и «нечисла» (Not aNumber, NaN) — это действия, а не битовые комбинации. Они имеют неоспоримые преимущества над форматом float, включая больший динамический диапазон, большую точность, побитовое совпадение результатов вычислений на разных системах, более простое аппаратное обеспечение и более простую поддержку исключений. Он потребляет меньшую мощность, и занимает меньшую площадь кремния, таким образом, чип может выполнять существенно больше операций над числами posit в секунду, чем FLOPS, при тех же аппаратных ресурсах. Блок обработки posit имеет меньшую сложность, чем FPU стандарта IEEE. Числа posit с низкой точностью являются лучшим решением для «приблизительных вычислений» в тех случаях, когда допустима низкая точность вычислений. GPU и процессоры глубокого обучения, в частности, могут выполнять больше операций на ватт потребляемой мощности, что позволит повысить качество их работы.
Были проведены всесторонние тесты, сравнивающие posit и float по точности вычислений для различной точности posit. Другими словами, posit выигрывает у float в его собственной игре. Числа posit с высокой точностью обеспечивают более высокую точность, чем float того же размера, в некоторых случаях, 32-битный posit может безопасно заменить 64-битный float.

Основы: Числа Unums: Type I и Type II

Арифметический фреймворк unum (универсальные числа, universal number) имеет несколько форм представления чисел. Исходной формой являются «Type I», надмножество IEEE 754; она использует «ubit» в конце дробной части для индикации того, что вещественное число является точным или находится в интервале между соседними вещественными числами. Несмотря на то, что Unum, как и float, имеет знак, экспоненту и дробную часть, длины экспоненты и дробной части варьируются автоматически, от одного бита до некоторого значения, определяемого пользователем. Unum Type I является компактным способом представить интервальную арифметику но переменная длина требует дополнительных усилий. Этот тип может повторять поведение float, путём использования специальной функции округления.

Ключевой идеей здесь является то, что знаковые целые числа в дополнительном коде элегантно отображаются на проективные вещественные числа, с тем же самым свойством перехода от положительных чисел к отрицательным, и с тем же самым порядком на числовой оси. Форма универсальных чисел “Type II” [4] не совместима с IEEE float, и представляет собой чистую, математически строгую концепцию, основанную на проективных вещественных числах. И это даёт возможность сделать арифметику очень, очень быстрой».
Структура 5-битного unum показана на рис. Цитируя Уильяма Каана (William Kahan) [5]:
«Они экономят пространство памяти, так как манипулируют не числами, а указателями на значения. Если каждый unum имеет n бит, то «u-решётка» заполняет верхний правый квадрант круга упорядоченным множеством из $2^-1$ вещественных чисел $x_i$ (не обязательно рациональными). 1. Нижняя половина круга содержит числа, обратные числам верхней половины, отражённые от горизонтальной оси, что делает операции умножения и деления такими же симметричными, как сложение и вычитание. В верхнем левом квадранте расположены отрицательные $x_i$, отражённые относительно вертикальной оси. Как и в случае Type I, числа unum типа Type II заканчиваются на 1 (ubit), представляя открытый интервал между соседними точными точками, для которых unum заканчивается на 0.

1.
Рис. Линия проективных вещественных чисел, отображаемая на целые числа в дополнительном коде длиной 4 бита.

Если нужно n бит точности, то таблица (в наихудшем случае) будет иметь $2^{2n}$ значений для функции двух аргументов, но с учётом симметрий и других трюков таблица может быть уменьшена до более приемлемого размера. Числа unum типа Type II имеют много идеальных математических свойств, но большинство операций с ними производится с помощью look-up таблиц. Числа unum типа Type II также плохо поддаются операциям слияния. Размер таблицы ограничивает масштаб этого ультрабыстрого формата размером 20 бит или меньше, для технологий сегодняшнего дня. Эти недостатки послужили мотивацией для поиска формата, который сохраняет многие свойства чисел unum Type II, но является более «дружественным» к аппаратному обеспечению, и может быть вычислен логическими схемами, похожими на существующие FPU.

2. Числа Posit и Valid

Есть два противоположных подхода к вычислениям в вещественных числах:

  • Нестрогий, но дешёвый, и приемлемый для большого количества практических применений
  • Математически строгий, даже ценой больших затрат времени и памяти

Первое утверждение относится к вещественной арифметике, в которой ошибка округления достаточно мала, второе утверждение относится к интервальной арифметике. Числа unum типов I и II также могут рассматриваться в подобном ключе, и это одна из причин, по которой они являются «универсальными числами». Однако, если мы всегда собираемся использовать некоторую функцию для округления после каждой операции, то мы лучше не будем использовать последний бит как значащий бит дробной части и не как ubit. Число unum такого типа мы будем называть числом posit.

Цитата из «New Oxford American Dictionary», 3-я редакция:

posit (сущ): заявление, которое делается исходя из предположения, что оно окажется правдой.

Это позволяет нам заполнить u-сетку так, что конечные числа останутся похожими на float, и будут иметь форму $m\cdot2^k$, где k и m целые. С целью упрощения аппаратной реализации числа unum Type II ослабляют одно из правил: точные обратные величины существуют только для 0, $\pm \infty$ и степеней двойки. Открытых интервалов нет.

Они предназначены для использования в тех приложениях, где важно строго определять, в каком интервале находится число, например, при отладке численных алгоритмов. Valid — это пара чисел posit равного размера, каждое из которых заканчивается на ubit. Однако они не являются темой данной публикации. Значения Valid являются более мощными, чем обычная интервальная арифметика и менее склонными к быстрому расширению чрезмерно пессимистических границ интервалов [2, 4].

показана структура n-битного представления posit с битами экспоненты. На рис 2.

Обобщённый формат posit format для конечных ненулевых значений
Рис 2.

Для отрицательных чисел, находим дополнение 2 перед декодированием режима, экспоненты и дробной части. Бит знака содержит 0 для положительных чисел, 1 для отрицательных. Для понимания битов режима, рассмотрим бинарные строки, показанные в таблице 1, в которых k означает длину ведущей последовательности, а x в битовой стоке означает безразличное состояние.

Run-length meaning k of the regime bits Table 1.

Бинарные строки начинаются с определённого количества нулей или единиц, идущих подряд, за которыми идёт противоположный бит, или достигается конец строки. Мы называем длину ведущей последовательности режимом числа. Пусть m — количество одинаковых бит в последовательности, если эти биты равны нулю, то k = -m, если 1, то k = m-1. Биты режима выделены янтарным цветом, противоположный бит выделен коричневым. Режим означает масштабирующий фактор, равный $useed^k$, где $useed=2^{2^{es}}$. Большинство процессоров могут найти первую единицу в слове или первый ноль в слове аппаратно, то есть декодирующая логика уже доступна. Таблица 2 показывает пример значений useed.

useed как функция es Таблица 2.

Она не сдвинута, как это сдклано во float-ах, она представляет масштабирование на $2^e$. Следующие биты (выделенные синим на рисунке) — это экспонента e, относящаяся к беззнаковому целому. Это компактный способ изменения точности, числа, близкие к 1 по абсолютной величине, имеют большую точность, чем очень большие или очень маленькие числа, которые гораздо реже встречаются в вычислениях. Может быть до es битов экспоненты, в зависимости от того, сколько бит осталось справа от битов режима.

Денормализованных чисел со скрытым 0 нет, в отличие от float. Если остались биты после битов режима и экспоненты, они представляют дробную часть, f, так же, как дробная часть 1.f в формате float, но скрытый бит всегда равен 1.

Начнём с простого 3-битного posit, для ясности, на рис. Система, которую мы описали, это естественное следствие заполнения u-сетки. Итак, числа на рис. 3 показана только правая половина проективных вещественных чисел. подчиняются правилам Type II. 3. Для других значений posit на рис. Есть только два особых значения: 0 (все биты 0) и ±∞ ( единица, за которой следуют все нули), их битовая последовательность не следует позиционной нотации. Отметим, что все положительные значения на рис. 3., биты раскрашены, как было описано выше. 3 являются точными значениями useed в степени k, представленной битами режима.

3.
Рис. Положительные значения 3-битного posit

Когда добавляется 1, создаётся новое значение между двумя значениями posit на круге. Точность чисел Posit увеличивается по мере добавления бит, и значения остаются там, где они есть на круге, когда добавляется бит 0. Пусть maxpos будет наибольшим положительным значением, а minpos — наименьшим положительным значением на круге, определяемыми битовой строкой. Какое числовое значение мы должны им присвоить? 3., maxpos — это useed, а minpos — это 1/useed. На рис. Правила интерполяции следующие:

Между maxpos и ±∞, новое значение — это maxpos × useed; между 0 и minpos, новое значение — это minpos / useed (с новым битом режима)
Между существующими значениями $x=2^m$ и $y=2^n$, где m и n отличаются больше, чем на 1, новое значение будет их геометрическим средним, $\sqrt{x\cdot y}=2^{(m+n)/2}$ (с новым битом экспоненты).
В других случаях, новое значение расположено посередине между существующими x и y, то есть является арифметическим средним, $(x+y)/2$ (с новым битом дробной части)

4 показывает построение чисел posit от 2 до 5 бит с es=2, и, таким образом, useed=16. Как пример, рис.

4.
Рис. Построение Posit с двумя битами экспоненты, $es=2, useed=2^{2^{es}}=16$

4 добавить ещё один бит, чтобы получить 6-битные posit, к числам posit, представляющим диапазоны значений между 1/16 и 16, будет добавлен бит дробной части, а не бит экспоненты. Если на рис. Пусть k будет целым числом, представляющим биты режима, e — беззнаковым числом, представляющим биты экспоненты, если они присутствуют. Рассмотрим строку бит, представляющую число posit p как знаковое целое, в диапазоне от $-2^{n-1}$ до $2^{n-1}-1$. Тогда p представляет Если набор бит дробной части $\{f_1f_2...f_{f_s}\}$, возможно, пустой, то пусть f будет значением, представляющим число $1,f_1f_2...f_{f_s}$.

$x= \begin{cases} 0, & p=0,\\ \pm\infty, & p=-2^{n-1},\\ sign(p)\times useed^k \times 2^e \times f\,& \text{любое другое }p \end{cases}$

Биты режима и es выполняют ту же функцию, что и биты экспоненты в стандартном float, вместе они определяют масштабирующий коэффициент, равный степени двух, и каждый инкремент useed означает сдвиг $2^{es}$ бит. Число maxpos равно $useed^{n-2}$ и minpos равно $useed^{2-n}$. Пример декодирования числа posit показан на рис.5 (с «нестандартным» значением для es, для упрощения).

5.
Рис. Пример битовой строки posit и её математический смысл

Биты режима 0001 имеют последовательность из трёх нулей, что означает, что k=-3, следовательно, масштабирующий коэффициент, вносимый битами режима, равен $256^{-3}$. Бит знака 0 означает, что значение положительное. Наконец, биты дробной части 11011101 представляют число 221, то есть дробная часть равна 1+221/256. Биты экспоненты,101, представляют 5 как беззнаковое двоичное целое, и вносимый масштабирующий коэффициент равен $2^5$. 5. Выражение, записанное под битовым полем на рис. 55393\times10^{-6}$" data-tex="inline"/> приводит нас к результату <img src="https://habrastorage.org/getpro/habr/formulas/e1c/8b1/46a/e1c8b146a6d3492a61a01cede0f7e8bf.svg" alt="$477/134217728\approx3.

2.2. 8-битные posit и обучение нейронной сети

Несмотря на то, что стандарт IEEE не определяет 8-битные float, числа posit разметом 8 бит с es=0 доказали свою полезность для некоторых целей, они очень полезны для построения нейросетей [3, 8]. В настоящее время для этих целей часто используются числа IEEE с половинной точностью (16-bit), но 8-битные числа posit потенциально могут обрабатываться в 2-4 раза быстрее. Важной функцией в нейросетях является сигмоида, имеющая асимптоту 0 при $x\to- \infty$ и 1 при $x\to \infty$. Общий вид сигмоидной функции $1/(1+e^{-x})$, и она является дорогой для вычислений, и легко может потребовать более сотни циклов процессора на вызов функции exp(x) из библиотеки, и из-за деления. С числами posit, можно просто инвертировать первый бит числа posit, представляющего x, сдвинуть число на 2 бита вправо, заполняя биты слева нулями, и результирующая функция posit, показанная на рис.6. фиолетовым цветом, близка к сигмоиде (показанной зелёным), и даже имеет тот же наклон при пересечении оси y.

6.
Рис. Быстрая сигмоидная функция с использованием posit-представления

2.3. Использование Useed для того, чтобы достичь и превзойти динамический диапазон float

Мы определяем динамический диапазон системы счисления как количество десятичных порядков от наименьшего до наибольшего положительного конечного значения, от minpos до maxpos. То есть, динамический диапазон определяется как $log_{10}(maxpos)−log_{10}(minpos)=log_{10}(maxpos/minpos)$. Для 8-битного posit c es=0, minpos равен 1/64 и maxpos равен 64, таким образом, динамический диапазон составляет 3,6 десятичных порядков. Числа posit, определённые с es=0, элегантны и просты, но их 16- и 32-битные версии имеют меньший динамический диапазон, чем IEEE float того же размера. Например, 32-битный IEEE float имеет динамический диапазон 83 декады, но 32-битный posit с es=0 будет иметь динамический диапазон только 18 декад.

Ниже приведена таблица значений es, которые позволяют числам posit превзойти динамический диапазон float для размеров 16- и 32-бит, и вплотную приблизиться к нему для размеров 64-, 128- и 256-бит.

Динамические диапазоны float и posit для равного числа бит Таблица 3.

Аналогично, динамический диапазон в 17 декад у 16-битных posit открывает им дорогу в приложения, в которых в настоящее время используются 32-битные float. Одной из причин выбрать es=3 для 32-битных posit является то, что в этом случае они могу служить простой заменой не только 32-битным float, но и 64-битным. Мы покажем, что posit может превосходить float как по динамическому диапазону, так и по точности при той же размере в битах.

2.4. Качественное сравнение форматов Float и Posit

В формате posit нет “NaN” (нечисел), вместо этого, вычисления прерываются, и обработчик прерывания должен либо сообщить об ошибке, либо каким-либо образом обработать ошибку и продолжить вычисления, но числа posit не допускают присваивание некоего значения, сигнализирующего о логической ошибке, чем, по определению, и является нечисло. Это существенно упрощает аппаратное обеспечение. Если программист видит необходимость в использовании значений NaN, это показывает, что программа пока не завершена, и в отладочном окружении должны использоваться числа valid для поиска и устранения подобных ошибок. Также, posit не имеет $+\infty$ и $-\infty$, как float, однако, числа valid поддерживают открытые интервалы $(maxpos, +\infty)$ и $(-\infty, -maxpos)$, которые дают возможность представить неограниченную величину любого знака, и необходимость в знаковой бесконечности будет означать лишь то, что вместо чисел posit нужно применять значения valid.

С числами posit, если a=b, то f(a)=f(b). Также в представлении posit нет «отрицательного нуля», отрицательный ноль, это ещё один логический недостаток, существующий в стандарте IEEE float. Следовательно, подразумевается, что $-\infty=+\infty$? Стандарт IEEE 754 говорит, что число, обратное к -0 равно $-\infty$, а число, обратное к +0, равно $+\infty$, но также говорит, что -0 равно +0.

Если любое из (a, b) равно NaN, результат сравнения всегда отрицательный, даже если их битовое представление одинаковое. Числа float имеют сложный алгоритм сравнения a=b. В posix проверка равенства такая же, как у целых чисел: если биты равны, числа равны. Если битовое представление разное, то по-прежнему есть возможность, чтобы a было равно b, так как отрицательный ноль равен положительному нулю! Числа posit имеют такое же отношение (a < b), как и знаковые целые, как и со знаковыми целыми, вы должны следить, чтобы не произошло переполнение с изменением знака, но вам не нужны отдельные машинные инструкции для сравнения posit, если у вас есть инструкции для сравнения знаковых целых. Если любой бит отличается, они не равны.

Posit не использует антипереполнение, вместо этого, используется постепенное снижение точности, что обеспечивает функциональность антипереполнения и его симметричного случая, переполнения (в отличие от posit, стандарт float ассиметричен, и использует эти битовые паттерны для представления большого и бесполезного множества NaN-значений). В формате posit нет денормализованных чисел, то есть нет специальной комбинации бит, показывающей, что скрытый бит равен 0 вместо 1.

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

3. Побитовая совместимость и комбинированные операции

Одна из причин, по которой IEEE float не даёт идентичных результатов на различных системах является то, что для элементарный функций, таких, как $log(x)$ и $cos(x)$ по стандарту IEEE не требуется точности до последнего бита для любого возможного входа. Окружение posit должно корректно округлять все результаты поддерживаемых арифметических операций. (Некоторые программисты математических библиотек беспокоятся насчёт «дилемы составителя таблиц», которая заключается в том, что для некоторых значений может быть очень затратно определить их корректное округление, это может быть устранено путём использования интерполяционых таблиц вместо полиномиальных аппроксимаций.) Некорректное значение в последнем бите фунции $e^x$, например, может в итоге привести к тому, что компьютерная система скажет нам, что 2+2=5.

Арифметика posit запрещает такие скрытые трюки. Более фундаментальная причина того, что IEEE float не даёт повторяющихся результатов на разных системах, заключается в том, что стандарт разрешает использование завуалированных методов для избегания переполнения/антипереполнения, и для повышения точности операций, такие, как внутреннее сохранение дополнительного бита переноса для экспоненциальной и дробной части.

Это было противоречивое изменение, не одобренное многими членами комитета. Последняя (2008 год) версия стандарта IEEE 754 [7] включает в требования комбинированную операцию умножения-сложения. Комбинирование операций — это не то же самое, что арифметические операции с расширяемой точностью, которые могут увеличивать разрядность целых чисел до переполнения памяти компьютера. Комбинированные операции приводят к отсрочке операции округления до момента завершения последней операции в вычислении, включающем в себя более чем одну операцию, после выполнения всех операций, включая точные целочисленные операции.

Окружение posit требует обязательного присутствия следующих комбинированных операций:

Комбинированное умножение-сложение $(a\times b)+c$
Комбинированное сложение-умножение $(a+b)\times c$
Комбинированное умножение-умножение-вычитание $(a\times b)-(c\times d)$
Комбинированное суммирование $\sum a_i$
Комбинированное скалярное умножение $\sum a_i b_i$

Наименьшее по абсолютному значению ненулевое число, которое может быть получено с помощью скалярного умножения — это $minpos^2$. Отметим, что все операции из приведённого списка являются подмножеством комбинированного скалярного умножения [6] в терминах требований к аппаратному обеспечению процессора. Если мы хотим получить скалярное произведение векторов $\{maxpos, minpos\}$ и $\{maxpos, minpos\}$ как точную операцию в scratch-зоне, нам нужно целое, достаточно большое, чтобы хранить $maxpos^2/minpos^2$. Любое произведение, это целое число, умноженное на $minpos^2$. Таким образом, $maxpos^2/minpos^2=useed^{4n-8}$. Вспомним, что $maxpos=useed^{n-2}$ и $minpos=1/maxpos$. 4. С учётом битов переноса и округления вверх до степени двойки, получим рекомендованные значения, приведённые в табл.

Точные размеры аккумулятора для каждого размера posit Таблица 4.

Комбинированные операции могут выполняться программно или аппаратно, но должны быть доступны для выполнения в posit-среде. В некоторых случаях размер аккумулятора сопоставим с размером регистра, в других случаях, требуется scratch-зона, эквивалентная кэшу L1 или L2.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть