WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 | 4 |

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

Определение: арифметика с плавающей точкой обладает -свойством, если для любых представимых чисел и операции, за исключением разве что при, найдется такое, что, причем.

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

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

Любая арифметика, соответствующая стандарту IEEE-754 является верной, более того, корректно округленной. Таким образом, полностью реализованный стандарт является наилучшим решением, однако в силу специфики целевой платформы (ограниченность по памяти, ориентированность на целочисленные алгоритмы при обработке сигналов) целесообразно выделить и реализовать некоторое его функциональное подмножество, гарантирующее высокоточную обработку чисел в формате расширенной и двойной точности.

Целевая платформа не имеет альтернативных реализаций, поэтому для оценки в данной главе приводятся данные по двум архитектурам того же класса.

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

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

  1. Редукция аргумента: выбрать по данному соответствующую точку (как правило, это ближайшая к точка). Затем применяется некоторое преобразование. Как правило,
  2. Аппроксимация: вычисление. Очень часто (хотя и не обязательно) - полином.
  3. Восстановление: в зависимости от преобразования и значений и вычисляется обратное преобразование, такое, что

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

DSP-ядро целевой архитектуры обладает аппаратно реализованными возможностями по обработке чисел с плавающей точкой в формате одинарной точности (24 бита мантиссы и 8 бит порядка). Известно, что в ряде случаев накопление ошибок округления при вычислениях в данном формате приводит к потере точности, неприемлемой для некоторых прикладных приложений, например, систем глобального позиционирования. Поэтому в систему команд DSP-ядра введены специальные инструкции, позволяющие преобразовывать данные в нестандартный формат расширенной точности, в котором под мантиссу отводится 32-битное дробное число, а под порядок – 16-битное целое. Работа с числами, представленными в этом формате, должна быть реализована программно. В главе второй обсуждаются построенные реализации базовых арифметических операций в формате расширенной точности. Для того чтобы свободно оперировать с этим форматом, в разделе 2.2 даются базовые определения.

Определение: числа с плавающей точкой в формате расширенной точности - числа вида, где, - целые числа, удовлетворяющие соотношениям,.

В разделе 2.3 описывается реализация базовых арифметических операций сложения и вычитания в формате расширенной точности. Пусть, - конечные числа в формате расширенной точности, причем,, (выход с инструкции CMPE).

«Наивный» алгоритм сложения

1

2

«Наивный» алгоритм сложения, заключающийся в сдвиге и сложении, должен быть дополнен последовательностями, учитывающими возможность знакового переполнения мантиссы, возникновения ненормализованного результата и потери значащих разрядов. С этой целью в зависимости от знаков операндов и параметра сдвига используется три последовательности инструкций, гарантированно возвращающих корректно округленный результат:

  1. Случай возможного переполнения (операнды одного знака и ): 15 тактов.
  2. Случай возникновения ненормализованного результата (операнды разных знаков и ): 14 тактов.
  3. Случай возможной потери значащих цифр (операнды разных знаков и ): 11 тактов.

В случае, когда параметр, для корректного округления достаточно вернуть старший (больший по модулю) операнд. Для корректного округления используется последовательность инструкций Round (6 тактов). Максимальное время исполнения подпрограмм сложения (вычитания) составляет 33 (40) тактов.

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

В разделе 2.4 описывается реализация операции деления в формате расширенной точности.

Рис. 1: Функциональная схема деления чисел в формате расширенной точности.

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

, где.

Данной точности достаточно для корректного округления. Базовый вариант подпрограммы деления исполняется за 88 тактов. Заметим, что с каждой итерацией сложность промежуточных вычислений возрастает из-за необходимости сохранения результатов в виде нескольких слов: 1-я и 2-я итерация занимают по 5 тактов, 3-я – 16 тактов и 4-я – 24 такта.

В разделе 2.5 описывается реализация операции извлечения квадратного корня в формате расширенной точности.

Рис. 2: Функциональная схема извлечения квадратного корня в формате расширенной точности.

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

, где.

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

Базовый вариант подпрограммы вычисления квадратного корня исполняется за 62 такта, 1-я и 2-я итерации занимают по 5 тактов, 3-я и 4-я – по 11 и 16 тактов.

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

Исследование таблично-алгоритмических методов вычисления элементарных трансцендентных функций в разделе 2.6 проведено на примере функции. Для редукции используется 8 точек разбиения (j=0…7) с табулированными значениями мантисс. В результате аргумент представлен в виде, где, - целые, такие, что, - редуцированный аргумент.

Аппроксимация осуществляется при помощи полинома наилучшего приближения, на интервале. При целочисленном вычислении полинома нужно учитывать ошибки округления.

Целочисленная аппроксимация по схеме Горнера

на DSP-ядре целевой платформы

1

2

For to 1 do

3

{

4

5

6

7

}

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

Здесь - погрешность сдвига, в случае сложения с переносом (строка 6) равная 0.5,.

Рис. 3: Функциональная схема таблично-алгоритмической реализации функции.

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

Заметим, что выведенные в работе формулы для оценки погрешностей целочисленного варианта схемы Горнера могут быть использованы и для других функций (иногда при условии их незначительной модификации).

Существует огромное количество разнообразных вычислительных методов для решения задач линейной алгебры, интерполяции, нахождения корней полиномов и т.д., реализованных в виде стандартных свободно доступных библиотек. Во многих случаях для корректной работы соответствующих подпрограмм необходима возможность производить вычисления с числами, представленными в формате двойной точности в соответствии со стандартом IEEE-754 (разрядность 53 бита, порядок принимает значения из множества ). Все число занимает восемь байт в памяти или в регистрах. В главе третьей показано, как реализовать подпрограммы, гарантированно возвращающие корректно округленный результат в данном формате, в рамках системы инструкций DSP-ядра целевой архитектуры. Для реализации выбран режим округления к ближайшему числу. Реализована обработка денормализованных чисел, обработка бесконечностей, нулевых значений со знаком и работа с нечисловыми данными. Базовые определения приводятся в разделе 3.2.

В разделе 3.3 представлена реализация операций сложения и вычитания в формате двойной точности. Масштабирование и сложение (вычитание) многобайтовых величин не требует строгого доказательства. Достаточно лишь удостовериться, что в каждой ветке вычислений результат умещается в выбранном нами представлении и к нему применяется корректный алгоритм округления в зависимости от параметра денормализации. После выполнения последовательностей масштабирования и сложения (вычитания) точный результат представлен в виде. В зависимости от параметра денормализации мантиссы применяются три варианта правила точного округления.

Базовый вариант выполнения подпрограммы может занимать от 38 до 68 тактов. В случае появления денормализованного результата из конечных нормализованных операндов обработка может занимать от 57 до 76 тактов. Обработка ровно одного денормализованного операнда (второй операнд нормализованный и конечный) занимает до 28 тактов. Обработка тех случаев, когда оба операнда являются ненормализованными, довольно проста и занимает 32 или 35 тактов, в зависимости от знаков операндов. Работа с бесконечностями и нечисловыми данными занимает от 20 до 24 тактов. В памяти программ PRAM подпрограмма сложения (вычитания) занимает 372 слова. Не вдаваясь в подробное рассмотрение различных вариантов аналогичных подпрограмм для ведущего ядра целевой архитектуры, отметим, что базовые варианты выполняются за 250-300 тактов, а обработка денормализованных чисел увеличивает время выполнения до 400-450 тактов.

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


Умножение мантисс в формате двойной точности

(последовательность инструкций MULT)

1

Pages:     | 1 || 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»