Арифметика нового поколения: реализация числового формата Posit. Часть I

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

Группа исследователей-математиков во главе с Джоном Густафсоном и Айзеком Йонемото, пришли к выводу о том, что сложившиеся типы данных, широко применяемые в научных и промышленных вычислениях, не соответствуют тем требованиям, которые выдвигает огромный парк вычислительных машин. Джон Густафсон анализируя повсеместно используемые типы с плавающей точкой стандартаIEEE 754, пришел к выводу о наличии серьезных математических противоречий в форматах float и double. Также, он заметил еще и то, что данные типы не подходят для организации точных вычислений, особенно на аппаратных платформах, работающих с ограниченными ресурсами и пониженным энергопотреблением. Все это подтолкнуло Густафсона к разработке нового формата хранения значений с плавающей точкой, лишенного противоречий и более соответствующего темпам развития вычислительной техники. Данный формат был назван Posit, и именно о его реализации пойдет речь далее.

Что такое Posit?

Posit — это новый формат представления чисел с плавающей запятой, который обладает следующим рядом преимуществ по сравнению с уже существующими float и double:

одинаковое аппаратное представление одних и тех же чисел с плавающей запятой на разных аппаратных платформах;
больший динамический диапазон в представлении чисел;
высокая точность в вычислениях;
меньшая сложность в аппаратной реализации и меньшая площадь, занимаемая микросхемами для обработки нового формата;
меньшая потребляемая микросхемами мощность при обработке данных;
более простая система обработки исключений;
отсутствие переполнений в сторону нуля, плюс и минус бесконечности, «не число» (Not a Number, NaN);
отсутствиеденормализованных значений, а также некорректных с точки зрения математики понятий, таких как «положительный» и «отрицательный» ноль.

Кроме того, по заявлениям создателей, формат Posit при сопоставимой длине (в байтах) может полностью заменить существующие типы float и double.

Почему мы взялись за это?

Заманчивое обещание о «безопасной замене типов float и double» сподвигло нашу команду взяться за попытку реализации данного формата на языке программирования D, основываясь на той немногой информации, которую сумели найти в интернете. Из-за отсутствия строго и внятного описания базовой арифметики чисел Posit, нам пришлось обратиться к уже известным полным реализациям данного формата на других языках программирования. По этим причинам, за основу нашей собственной реализации Posit были выбраны две библиотеки Python под названиемSoftPosit (примеры и среда для испытаний) иPySigmoid (основа кода и элементарные операции). Также наша команда специально перед подготовкой этой статьи создала небольшой рецепт для описания побитовых операций над самыми разными типами, с которым настоятельно мы рекомендуемознакомиться перед дальнейшим прочтением.

Описание формата Posit

Формат Posit представляет собой n-битное целое число, которое служит для хранения в битовом виде числа с плавающей точкой. Целое n-битное число интерпретируется как битовое поле с определенными компонентами:

знаком числа (первый бит числа, 0 для положительных чисел и 1 для отрицательных);
режимом числа (битовое поле переменной длины);
экспонентой (битовое поле переменной длины);
дробной частью (битовое поле переменной длины).

Строго говоря, в этом формате обязательно наличие только знака и режима числа, а экспоненты и дробной части может и не быть. Сразу после бита знака идут, так называемые, биты режима числа (или просто режим), которые при декодировании Posit интерпретируются как некоторый масштабирующий фактор.

Режим числа — это строка из битов, первый бит которой имеет нулевое, либо единичное значение, она продолжается до тех пор, пока не попадется бит противоположной величины. Математики называют это ведущей последовательностью, а количество битов одной величины (с одинаковым значением) длиной этой последовательности. В случае формата Posit в режиме числа имеют значение два фактора: с бита какой величины начинается режим и количество этих одинаковых битов. Запомните этот факт, он потребуется далее для понимания процесса интерпретации отдельно взятого Posit.

Режим числа может распространяться на всё число, тогда для битов экспоненты и дробной части места не остается, а число с плавающей точкой отображается напрямую без экспоненты и дробной части. Стоит учитывать этот факт, поскольку он представляет один из ключевых моментов в реализации типа Posit, в дальнейшем описании мы будем предполагать, что алгоритм сам учитывает наличие или отсутствие всех компонентов после режима.

После битов режима следуют биты экспоненты, их может быть разное количество. В описании типов Posit применяются два стандартных обозначения, позволяющих конструировать разные виды Posit — это количество битов, отведенных на хранение самого Posit, и максимальное количество битов, занимаемых экспонентой числа. Обратите внимание, сам формат указывает на максимально возможное количество битов, в которых хранится экспонента, это значит, что даже в пределах одного и того же типа Posit для разных чисел экспонента может быть разной длины!

Если получилось так, что после битов экспоненты в целочисленном контейнере Posit еще осталось место, то оно понимается как биты дробной части.

Наш числовой тип Posit можно охарактеризовать двумя параметрами: размером всего Posit (обозначим его, как NBITS) и максимальным числом бит, выделенных под экспоненту (обозначим его как ES). И именно этот тип, который мы представим как шаблон Posit!(NBITS, ES) мы будем реализовывать далее, но перед этим просуммируем то, что мы знаем о Posit в виде такой диаграммы:

Необходимо прояснить темный момент об интерпретации Posit как числа с плавающей точкой. Как же интерпретировать то, что перед нами?

Начнем с бита знака: если он 0, то перед нами положительное число; если он равен 1, то отрицательное. Для отрицательных чисел, прежде чем выполнять дальнейшие операции нужно выполнить операцию дополнения до 2 (стандартная операция, идущая из такого понятия как дополнительный код, с описанием которого вы можете ознакомится здесь) и только после этого, переходить к последующим шагам. Следующее, на что мы обращаем внимание, это режим числа. Режим может начинаться с 0 или 1, а дальше следует цепочка одинаковых бит, которая заканчивается с появлением противоположного по величине бита. Пусть, количество одинаковых бит равно m, тогда мы введем некое число k, которое равно:

-m, если режим начинался с нулевого бита;
m-1, если режим начинался с единичного бита.

Режим, как упоминалось ранее, это масштабирующий фактор, который равен USEED ^^ k (где под USEED понимается величина равная 2 ^^ ( 2 ^^ ES)). То есть, сам по себе режим это некий коэффициент, который позволяет хранить точные значения для дробных величин степеней двойки (это вытекает из бинарной природы компьютеров).

Следующими идут биты экспоненты, и они также понимаются как масштабирующий фактор, равный 2 ^^ e, где e — это значение, представленное битами экспоненты (т.е. эти биты воспринимаются как самостоятельное число, в отрыве от остального битового поля Posit).

Если после экспоненты остались биты, то они воспринимаются как дробная часть вида 1.f, где f — это значение, представленное в битах дробной части. Поясним, допустим, что дробная часть занимает FS битов, а ее значение — это все та же f, тогда дробная часть (в десятичном виде) будет равна 1 + (f / (2 ^^ FS)). Стоит заметить, что в float/double почти такой же способ представления дробной части.

В общем случае, то что хранится в контейнере Posit интерпретируется по следующей формуле:

Под p мы понимаем строку бит (т.е. бинарную запись числа Posit), тогда sign(p) — это значение бита знака, k — целое число, представленное в битах режима, e — значение, представленное в битах экспоненты, f — число, представленное в битах дробной части.

В этой формуле заложена одна из особенностей формата: две величины, которые есть в формате Posit, не подчиняются общей схеме построения Posit. Эти две величины соответствуют нулю (все биты Posit равны 0), и «не действительное число» (Not a Real, NaR), т.е. то что обычно называется «плюс-минус бесконечность».

В качестве иллюстрации того, как это работает, рассмотрим пример Posit!(16, 3), т.е. 16-битный Posit с 3 битами экспоненты. В качестве числа, сохраненного в Posit будем рассматривать такую последовательность битов:

Бит знака равен 0, а это значит, что число перед нами положительное. Биты режима начинаются с бита со значением 0, и этих битов ровно 3 (бит со значением равным 1 является лишь сигналом конца режима, в сам режим он не входит), следовательно, число k равно -3. Биты экспоненты представляют собой число 101 в двоичном виде, или иначе говоря, 5 в десятичном. Поскольку, после битов экспоненты еще остались биты, то они представляют собой дробную часть, в которой в двоичном виде записано число 11011101 в двоичном виде или 221 в десятичном.

Теперь, осталось собрать все это вместе:

Некоторые пояснения: первый сомножитель равен 1, поскольку функция знака числа дает 1 в случае того, если число положительное (и -1, если отрицательное); второй сомножитель — это уже описанный нами подход с USEED, и в данном случае, USEED равен (2 ^^ (2 ^^ 3)), поскольку рассчитывается данный коэффициент из размера экспоненты (максимальный размер экспоненты равен 3), USEED после этого возводится в степень равную коэффициенту k, полученному из битов режима; третий сомножитель — это масштабирующий фактор степени двойки, который получается из простого возведения двух в степень, выраженную битами экспоненты; и, наконец, четвертый сомножитель — это выражение дробной части, которая получается делением значения в битах дробной части на двойку в степени размера дробной части (в битах) и прибавлением полученного результата к единице.

На этом, как мы считаем, информации о Posit достаточно (на самом минимальном уровне), и если вы хотите более подробно ознакомиться с темой, то в конце статьи мы оставили ссылки как на само описание Posit, так и на связанные с ним темы. Кроме того, вынуждены вас предупредить о том, что Posit — это формат только для хранения значений с плавающей точкой, а не формат вычислений. Сами вычисления с Posit выполняются с применением формата под названием Quire, но это уже выходит за рамки нашей статьи. Более того, наш порт реализации формата не является даже минимальной средой для Posit и служит лишь фундаментом для построения таковой. Дело в том, что минимальная среда для работы с Posit требует реализации и формата Quire с его операциями накопительного сложения-умножения (т.н. fused operations), и средств конверсии одного типа Posit в другой. Конверсия легко реализуема, и мы оставляем ее как дополнительное упражнение для искушенного читателя.

Прежде чем перейти к реализации специфического типа Posit, мы говорим вам о том, что не будем прояснять некоторые моменты, такие как работа базовой арифметики и битовые операции, а лишь опишем особенности и интересные участки довольного большого программного проекта, проделанного нами за 3 месяца работы.

Эта статья носит вводный характер в нашу реализацию, а саму реализацию мы опишем в следующих частях.

Источники

Что такое Posit?

Почему мы взялись за это?

Описание формата Posit

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