WWW.DISSERS.RU

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

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

Pages:     | 1 | 2 || 4 |

2

3

4

5

6

7

8

Утверждение: последовательность инструкций MULT возвращает мантиссу результата произведения двух чисел с плавающей точкой в виде.

Базовый вариант исполнения подпрограммы умножения чисел в формате двойной точности (все операнды конечные и нормализованные, результат конечный и нормализованный) занимает 56 тактов. Выполнение последовательностей, соответствующих случаям, когда входные операнды конечные и нормализованные, занимает от 55 до 68 тактов. В противном случае мы проходим либо через обработку операндов, не являющихся конечными, либо через обработку денормализованных операндов. Варианты с обработкой операндов, не являющихся конечными, занимают от 20 до 31 такта, на обработку денормализованного результата требуется от 22 до 28 тактов, что составляет около 50% времени выполнения базового варианта. Таким образом, общее время выполнения умножения может варьироваться от 20 до 96 тактов. В памяти программ PRAM подпрограмма умножения занимает 335 слов. Выполнение соответствующих подпрограмм на ведущем ядре занимает от 400 до 450 тактов, поддержка денормализованных операндов увеличивает время выполнения до 550 тактов.

Для деления исследованы алгоритмы с последовательной сходимостью, так как они дают наиболее плотный код. Кроме того, итерационные методы с квадратичной сходимостью требуют чересчур высоких затрат на промежуточные вычисления. В разделе 3.5 рассмотрены три варианта последовательных алгоритмов: обычное деление без восстановления остатка, SRT-алгоритм деления по основанию 4 с использованием множества цифр с минимальной избыточностью и алгоритм по большому основанию с предварительным масштабированием. В первых двух вариантах время вычисления мантиссы частного составило порядка 450 тактов. В то же время одной из особенностей DSP-ядра является наличие аппаратно реализованных операций с плавающей точкой в формате одинарной точности, что можно использовать для быстрого предварительного масштабирования. В результате был разработан алгоритм деления по большому основанию, занимающий порядка 70 тактов:

  1. В формате одинарной точности найти, такое, что
    ,
  2. Масштабировать операнды:
    ,
  3. Выбрать 19 битов частного усечением частичного остатка:, скорректировать

Благодаря предварительному масштабированию (2) при корректировании частичного остатка можно избежать полного умножения на 96-битное число.

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

Итерации по основанию

1

For to 3 do

2

{

3

4

5

6

7

8

9

}

Утверждение: после трех итераций последовательности инструкций второго этапа, где.

Данная схема допускает возможность эффективно совместить ее отдельные элементы (13 тактов на итерацию).

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

Базовый вариант исполнения подпрограммы деления в формате двойной точности занимает 120 тактов. В случае возникновения денормализованного результата (обрабатываемого тем же фрагментом кода, что и для подпрограммы умножения) мы получим время выполнения от 132 до 138 тактов. Обработка денормализованных операндов существенно замедляет подпрограмму, а именно: обработка (нормализация, коррекция порядка) одного денормализованного операнда занимает до 22 тактов, таким образом, если и делимое и делитель не являются нормализованными, их обработка требует около 30% времени исполнения базового варианта. Прибавляя возможность возникновения денормализованного результата, получаем наихудшее время исполнения порядка 180 тактов. Тривиальные случаи (результат не является конечным, результат в точности нулевой) обрабатываются за время от 27 до 39 тактов. В памяти программ PRAM подпрограмма деления занимает 316 слов. Деление чисел в формате двойной точности на ведущем ядре целевой архитектуры занимает от 1000 до 1300 тактов, обработка денормализованных операндов увеличивает время выполнения до 1500-1600 тактов.

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

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

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

Пусть,.

Рассмотрим редукцию аргумента экспоненциальной функции.

Одна итерация редукции аргумента

экспоненциальной функции

if(s -11<= j)

{

if( z1>0) {; a=a + 1;}

if( z1<0) {; a=a - 1;}

}

После выполнения восьми итераций аргумент представлен в виде суммы, а результат.

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

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

В разделе 4.3 показано, что алгоритм определения основания и разрядности корректен при условии того, что используемая арифметика обладает свойством верного округления.

Пусть - основание системы счисления используемой арифметики, - разрядность используемой арифметики. Тогда для динамического (времени выполнения) определения основания используемой арифметики могут быть использованы два цикла DO-WHILE.

Алгоритм определения основания

1

W = One;

2

Do{

3

W = W+W;

4

Y = W + One;

5

Z = Y – W;

6

Y = Z – One;

7

} while(MinusOne + FABS(Y) < Zero);

8

Y = One;

9

Do{

10

Radix = W + Y;

11

Y = Y + Y;

12

Radix = Radix – W;

13

} while(Radix == Zero);

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

В третьем цикле определяется разрядность мантиссы. Показано, что в случае верного округления результатов после выхода из цикла значение переменной Precision равняется разрядности используемой арифметики.

Метод определения параметров, если, и, если, основанный на использовании бесконечных периодических дробей описывается в подразделе 4.3.2. Доказаны утверждения по двум циклам.

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

Pages:     | 1 | 2 || 4 |






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