Введение

 

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

 

1. Исследование существующих форматов представления чисел с плавающей запятой и их особенностей

 

         В настоящее время одним из перспективных научных направлений в области вычислительной техники является проектирование специализированных процессорных устройств с малым энергопотреблением. При внедрении новых архитектур появляется необходимость наращивания объема системного программного обеспечения, важную часть которого составляют математические библиотеки, включающие в себя операции с плавающей запятой. При этом основной проблемой является то, что арифметика с плавающей запятой должна обладать свойствами математической корректности. На аппаратном уровне данная проблема может быть решена путем соответствия стандартам вычислений с плавающей запятой. В свете вышеизложенного представляются актуальными задачи проектирования, разработки и реализации базовых математических алгоритмов нижнего уровня, например, элементарных арифметических функций для встраиваемой процессорной системы. На начальном этапе проектирования должна быть решена важнейшая задача, связанная с обеспечением корректности вычислений, т. е. получения результата с гарантированной точностью. Решение такой задачи можно разбить на два этапа: 1-й этап — модификация форматов представления вещественных чисел (корректность представления данных); 2-й этап — введение дополнительных методов контроля точности для стандартных вычислительных алгоритмов (коррекция вычислений). В данной работе показана реализация 1-го этапа, в ходе которой предлагается уход от традиционного (бинарного) представления вещественных чисел в ЭВМ в сторону постбинарного. При таком представлении чисел с плавающей запятой предложен ряд модифицированных форматов [2, 3, 5], способных представлять не только вещественные числа как таковые, а и их совокупности в виде обыкновенных дробей (пара чисел — числитель и знаменатель) и интервалов (пара чисел — границы интервала). Для последующей проверки алгоритмов арифметических и логических операций над постбинарными числами возникла необходимость разработки программной модели соответствующих форматов. При этом аппарат ввода чисел должен быть настолько гибким, чтобы имелась возможность представления сколь угодно точного отображения множества всех действительных чисел, т. е. преобразование входное число х → постбинарный формат (pbinary[x]) и pbinary[x] → выходное число y должно быть максимально точным и стремиться к равенству х = y. В результате поиска программных продуктов, работающих с числами произвольной длины, было выявлено следующее: все программные модели представления чисел двоичной системе счисления (в частности, вещественных чисел) имеют ограничения на количество знаков после запятой и невозможность представления входных чисел и результатов в экспоненциальном виде. На фоне остальных приложений существенно выделяется бесплатная программа IEEE754 v.1.0 [4], которая способна выполнять преобразования вещественных чисел в формат одинарной или двойной точности стандарта IEEE-754 в обоих направлениях. Программа отображает абсолютно точные значения десятичных или двоичных чисел, может представлять исходные числа и результаты преобразования в экспоненциальном виде и позволяет вводить исходное десятичное число до 1074 значащих цифр в простом или экспоненциальном виде. Данный программный продукт был выбран в качестве прототипа к построению представленной далее модели преобразования десятичного вещественного числа произвольной точности в постбинарные форматы различной точности.

 

2. Исследование способов представления вещественных чисел и разработка преобразователя мантиссы числа

 

         В работе [4] был предложен ряд способов для преодоления проблем, связанных с ограничением разрядности чисел, поскольку использование при вычислениях разрядности, существенно превышающей стандартную, является одним из способов получения правильных результатов. Все эти способы в совокупности позволяют в процессе вычислений выполнять следующие операции: – увеличение (или выравнивание) разрядности во избежание переполнения порядка результата и выполнения корректных вычислений; – выполнение так называемого отложенного деления, когда отдельно вычисляются числитель и знаменатель, а деление производится на последнем шаге вычисления; – использование интервальных вычислений.

 

3. Программная модель постбинарных форматов

 

         В современных вычислительных устройствах для представления действительных (вещественных) чисел используются форматы, соответствующие стандарту IEEE754-2008, которые состоят из полей знака, порядка и мантиссы числа. Такая же структура сохранена и в постбинарных форматах, однако поле мантиссы претерпело модификацию, выделив незначительное количество разрядов на поле идентификатора [3, 5]. Программная модель PBinary является преобразователем исходного десятичного числа в двоичное, «упакованное» в постбинарных форматах. PBinary реализован на языке Java и занимает около 300 КБ дискового пространства. Создание модели PBinary в виде Java-приложения было обосновано, во-первых, кроссплатформенностью, и, во-вторых, повышенным быстродействием выполнения элементарных математических операций. Интерфейс программы PBinary представлен на рис. 4.1, исходный текст программы представлен в приложении Б. В поле ввода данных формируется исходное десятичное число, которое может вводиться с клавиатуры или загружаться из текстового файла. Переключатели «число», «дробь» и «интервал» позволяют представлять входные данные в виде одного числа, числителя и знаменателя дроби или границ интервала. Флажок «тетракод» позволяет отображать значения полей форматов в тетракоде, где каждая пара двоичных бит представляет значение тетрита t∈{0, 1, A, M} [8] следующим образом: 00 для «А», 01 для «0», 10 для «1» и 11 для «М». Цифровой счетчик показывает количество значащих цифр исходного числа (в простом или экспоненциальном виде) которое будет учитываться при дальнейшем преобразовании (по умолчанию — 1024 цифры). Кнопки «Старт» и «Сбросить в 0» позволяют начать преобразование или обнулить полученные ранее результаты. Результаты всех выполняемых моделью PBinary преобразований записываются в информационные поля группы вкладок «pbinary32–pbinary256». Названия вкладок «pbinary32–pbinary256» повторяют названия соответствующих постбинарных форматов различной точности. Тело каждой вкладки содержит следующие информационные поля: 1. Значения полей числа. Данное поле содержит информацию о структуре формата (рис. 2), названия и значения его полей (используется 2 с/с и 16 с/с), принадлежности числа к стандартному множеству (± нормализованное, ± денормализованное, ± ∞, не число (NaN)) и выбранном способе округления (в меню «Опции») при формировании значений полей формата (к нулю (без округления), к ближайшему целому, к +∞ и к -∞). Данное поле отображает результат преобразования х → pbinary[x].

 

 

         Полученное значение можно отобразить в простом (рис. 3, а) и экспоненциальном (рис. 3, б) виде. Стоит отметить, что такие точные вычисления микропроцессор производить не способен, поэтому PBinary не использует математические возможности микропроцессора, а имитирует математические расчеты выполняемые вручную. Данное поле отображает результат преобразования pbinary[x] → y .
         Погрешность. В этом поле вычисляется абсолютная погрешность представления исходного числа в постбинарном формате. Значение погрешности позволяет оценить точность представления исходного числа и выбрать оптимальную точность (от 32 до 256 двоичных разрядов) для его хранения. Данное поле показывает, насколько верно равенство х = y.

 

 

         В поле статуса окна программы выводится информация о времени преобразования, которое определяет временной интервал с момента нажатия на кнопку «Старт» и до заполнения всех информационных полей. Следует отметить, что при проведении многочисленных экспериментов с различными входными числами (и с различным количеством значащих цифр в числе) в пределах показателя экспоненты -1000...1000, время преобразования ни разу не превысило 15-секундный рубеж.

 

Рисунок 3.3 — Вывод точного значения числа в 10 с/с, полученного из формата pbinary128, в простом (а) и экспоненциальном (б) виде

         Основу модели PBinary составляют функции реверсивного преобразования чисел десятичной и двоичной систем счисления. Известные алгоритмы таких преобразований в данной концепции неприменимы, поскольку 1) исходное десятичное дробное число невозможно точно представить ни в одном из стандартных вещественных форматов, т. к. десятичная дробь x₁₀ записывается в виде строки цифр a_k (0 ≤ a_k ≤ 9) c количеством n разрядов целой части и m разрядов дробной части числа . (1) По умолчанию исходная десятичная дробь может быть представлена значением n + m = 1024, однако эту сумму можно увеличить до 10 000. Такие числа в регистрах современных микропроцессоров непредставимы. 2) при преобразовании десятичной дроби в двоичную возникает необходимость представления рационального числа х10 в х2 в виде линейной комбинации (в большинстве случаев бесконечной) степеней числа 2: , (2) где bk и ck — цифры целой части и дробной части (bk, ck ∈ {0, 1}), n — число разрядов целой части. При больших значениях n (например, в формате pbinary256 длина мантиссы равно 219 разрядам) не представляется возможным загрузить такое число в регистры современного микропроцессора. Для преодоления возникшей ситуации было принято решение хранить все числовые значения в строковых форматах и разработать собственные алгоритмы, имитирующие для преобразования 2↔10 с/с сложение, вычитание, умножение и деление «в столбик» строковых чисел. При этом каждая двоичная и десятичная цифра, знаки «+», «–», «,» и «е» являются символами системы Юникод. Данный подход позволил представить числа в виде строк большой длины (до 4 ГБ (для платформы Java), где каждый символ строки равен двум байтам), т. е. фактически модель PBinary в состоянии учитывать до 2∙109 значащих цифр входного числа. Все операции, происходящие после начала преобразования (нажатие кнопки «Старт») можно разбить на несколько этапов (рис. 4.1):

Рисунок 4.1 - Этапы работы преобразователя
(4 кадра, длительностью 2 с., 7 повторений, размер — 62 КБ.)

Этап 1. Инкапсуляция входных данных. Если входное строковое число представлено в нормализованном виде, то оно приводится к простому виду, состоящему из цифр, знакового символа («+» или «–») и разделителя «,». Символ знака определяет знаковый разряд форматов, а модуль числа разбивается на две части, представляющих строковый эквивалент целой и дробной части исходного числа. Этап 2. Получение двоичного числа и заполнение полей постбинарных форматов («упаковка» числа). Функция преобразования 10↔2 с/с реализует два алгоритма, которые выполняют преобразование целой и дробной части строкового числа. На этом этапе дробная часть двоичного числа может оказаться бесконечной, аналогичной (2). В этом случае вычисление происходит до количества двоичных разрядов, необходимых для корректного заполнения мантиссы старшего формата (в данном случае pbinary256). Если происходит преобразование исходного рационального числа, которое можно представить в виде (где q и m — целые числа), то такое число обладает конечной записью в двоичной системе счисления: , (3) где и представляют двоичные записи соответственно частного и остатка от деления q на 2m. Если значение n + m окажется меньше разрядности мантиссы большего постбинарного формата (в данном случае pbinary256), недостающие разряды заполняются незначащими нулями. Полученные части уже двоичного числа вновь собираются в дробный формат и нормализуются. Для каждого формата pbinary рассчитываются значения порядка со смещением, отрабатывается механизм установленного округления мантиссы. Полученные значения записываются в соответствующие поля форматов. Этап 3. «Распаковка» числа из форматов для получения точного значения. Из значений полей каждого постбинарного формата формируется точное двоичное число в нормальном виде. Для этого к значению мантиссы со знаком добавляется старшая «1» (если число принадлежит к области нормализованных чисел), вычисляется значение экспоненты без смещения, определяя тем самым положение запятой, делящей поле мантиссы на целую и дробную части. Далее полученное в нормальном виде двоичное число преобразовывается в точное десятичное. Оба этих числа можно отобразить в соответствующем информационном поле (рис. 3) в нормальном и экспоненциальном виде. Этап 4. Вычисление погрешности представления. Абсолютная погрешность представления чисел Δ представляет собой разность между исходным десятичным числом x и полученным точным десятичным числом y из полей форматов после преобразования: Δ = x – y. Значение Δ выводится отдельно для каждого формата и позволяет судить об эффективности использования постбинарных форматов различной точности для заданного числа. Поскольку модель PBinary не работает с числами, а только с их строковыми эквивалентами, то описанные выше математические операции также проводятся со строковыми типами данных. В таких случаях каждый символ строки представляет цифру определенного разряда числа, и реализация всех математических алгоритмов сводится к имитации работы однобитных сумматора и делителя. Для исследования временных характеристик преобразователя, выбран ряд чисел, которые подавались на вход программы. Принцип проверки времени выполнения программы был основан на замере системного времени в момент нажатия кнопки «старт», до окончания всех преобразований. Результаты исследования представлены на рис. 4.2, где по оси ординат указано время выполнения программы в миллисекундах, а по оси абсцисс — значение экспоненты для каждого числа. Тестирование проводилось на компьютере со следующими параметрами: CPU: Celeron M 1.6 GHz, RAM: 1024 MB, HDD: SATA 80026 MB.

Рисунок 4.2 – Временная диаграмма преобразователя (ось ординат - длительность работи в секуднах, ось абсцисс - длина числа)

         По результатам исследования выявлено, что при небольших значениях экспоненты, время работы зависит от количества значащих цифр самого числа, а при больших значениях экспоненты разница между исходными числами не существенна. Анализируя полученные результаты можно предположить, что при отрицательных значениях экспоненты, зависимость времени от ее величины линейная, а при положительных значениях — экспоненциальная. Это явление можно объяснить следующим: при отрицательных значениях экспоненты происходит множественное выполнение операции умножения (фактически, многократное сложение), а при положительных значениях экспоненты — множественные операции деления (фактически, многократное вычитание).

         Конечным этапом работы является разработка постбинарного процессора, для реализации на ПЛИС, так как изготовление заказных БИС является очень дорогим и трудоемким. Разработана модель данного устройства на языке HDL, которая позволяет преобразовывать входное число в постбинарный формат, для последующей работы, так как данном процессоре все операции выполняются над постбинарными числами. RB0 и RB1 – буферные регистры. B2PT – преобразователь бинарных чисел в постбинарные P2BT – преобразователь постбинарных чисел в бинарные ALU – арифметико-логическое устройство (АЛУ) RFL – регистр флагов RB0 служит для ввода исходного числа. Разрядность – 64 бита. B2PT преобразовывает входное число из буфера RB0 в формат, необходимый для представления в АЛУ, определяет код формата и модификатор формата для входного числа. В RFL хранятся код и модификатор числа, его тип (бинарный или постбинарный), коды ошибки. Данные из регистра флагов используются при работе АЛУ, а также для преобразования выходных чисел. P2BT – преобразовывает выходное 128-битное число результата из АЛУ в бинарный формат, и записывает его в регистры RB0 и RB1. При этом анализируется значение поле формата числа, и если его можно представить 64 битами, то запись происходит только в регистр RB0, а RB1 заполняется нулями.

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2012 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

1. Hammer R., Hocks M., Kulisch U., Ratz D. — Numerical Toolbox for Verified Computing (Pascal-XSC Programs) Springer-Verlag Berlin Heidelberg, 1993, с.8.

2. Аноприенко А.Я., Гранковский В.А., Иваница С.В. Пример Румпа в контексте традиционных, интервальных и постбинарных вычислений // Научные труды Донецкого национального технического университета. Серия «Проблемы моделирования и автоматизации проектирования динамических систем» (МАП-2011). Выпуск 9 (179): Донецк: ДонНТУ, 2011. С. 324–343.

3. Аноприенко А.Я., Иваница С.В., Кулибаба С.В. Особенности представления постбинарных вещественных чисел в контексте интервальных вычислений и развития аппаратного обеспечения средств компьютерного моделирования // Моделирование и компьютерная графика / Материалы IV международной научно-технической конференции – 5-8 октября 2011 г. Донецк, ДонНТУ. – 2011. С. 13-19.

4. Бесплатные программы SoftElectro. Программа IEEE754 — конвертор чисел формата IEEE754 c абсолютной точностью представления результата. Электронный ресурс. Страница доступа: http://www.softelectro.ru/program.html.

5. Аноприенко А.Я., Иваница С.В. Постбинарный компьютинг и интервальные вычисления в контексте кодо-логической эволюции. — Донецк, ДонНТУ, УНИТЕХ, 2011. — 244 с.

6. Loh E., Walster G. Rump’s Example Revisited // Reliable Computing 8: 2002, p. 245–248.

7. Петров Ю.П. Обеспечение надежности и достоверности компьютерных расчетов. — СПб: БХВ-Петербург, 2008. — 160 с.

8. Аноприенко А.Я. Обобщенный кодо-логический базис в вычислительном моделировании и представлении знаний: эволюция идеи и перспективы развития // Научные труды Донецкого национального технического университета. Серия «Информатика, кибернетика и вычислительная техника» (ИКВТ-2005) выпуск 93: – Донецк: ДонНТУ, 2005. C. 289-316.

9. Аноприенко А.Я., Иваница С.В. Особенности постбинарного кодирования на примере интервального представления результатов вычислений по формуле Бэйли-Боруэйна-Плаффа // Научные труды Донецкого национального технического университета. Серия: «Информатика, кибернетика и вычислительная техника» (ИКВТ-2010). Выпуск 11 (164). – Донецк: ДонНТУ, 2010. С. 19-23.

10. Аноприенко А.Я., Иваница С.В. Интервальные вычисления и перспективы их развития в контексте кодо-логической эволюции // Научные труды Донецкого национального технического университета. Серия «Проблемы моделирования и автоматизации проектирования динамических систем» (МАП-2010). Выпуск 8 (168): Донецк: ДонНТУ, 2010. С. 150–160.

11. Moore R.E. Interval analysis. Eiiglewood Cliffs / R.E. Moore — N.J.:Prentic-e-llall, 1966.

12. Иваница С.В., Аноприенко А.Я. Особенности реализации операций тетралогики // Научные труды Донецкого национального технического университета. Серия: «Информатика, кибернетика и вычислительная техника» (ИКВТ-2011). Выпуск 13 (185). – Донецк: ДонНТУ, 2011. С. 134-140.

13. IEEE Standard for Floating-Point Arithmetic (IEEE 754) http://en.wikipedia.org/wiki/IEEE_754-2008