автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы вычислений с гарантированной точностью на платформе "Мультикор"

На правах рукописи

/Заф

ЗАХАРОВ АНДРЕЙ ВЕНИАМИНОВИЧ

□ОЭОБ8327

МЕТОДЫ ВЫЧИСЛЕНИЙ С ГАРАНТИРОВАННОЙ ТОЧНОСТЬЮ НА ПЛАТФОРМЕ «МУЛЬТИКОР»

Специальность 05 13 11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ на соискание ученой степени кандидата технических наук

Москва - 2007

003068327

Работа выполн зна в Российском университете дружбы народов

Научный руководитель

Официальные оппоненть

Ведущая организация

доктор технических наук, профессор Хачумов Вячеслав Михайлович

доктор физико-математических наук, профессор

Осипов Геннадий Семенович

кандидат технических наук, доцент Гагарин Андрей Петрович

Институт проблем управления РАН

Защита состоится « » диссертационного совета по адресу 152020, Яросл

Д 002 084 01 в Институте программных систем РАН авская область, г Переславль-Залесский, м Ботик.

С диссертацией можно ознакомиться в библиотеке ИПС РАН.

Автореферат разослан «

У» <Ха/1£4.Я 2007 г

сс

2007 г в /у часов на заседании

Ученый секретарь диссертационного совета Д 002 084.01

С.М Пономарева

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Основными производителями микропроцессорных средств в настоящее время являются зарубежные фирмы. В связи с этим важным явлением стало появление новой архитектуры - «Мультикор», перспективной отечественной разработки, способной конкурировать с зарубежными аналогами. Данная архитектура представлена серией сигнальных микроконтроллеров - в частности, микросхемами 1892ВМЗТ (МС-12) и 1892ВМ2Т (МС-24). Это однокристальные программируемые многопроцессорные «системы на кристалле» на базе 1Р-ядерной платформы, разработанной в НПЦ «Элвис». В качестве основного процессора используется ШвС-подобное ядро с архитектурой М1Р832; под его управлением работают один или более ВвР-акселераторов.

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

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

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

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

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

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

Особенностью за; ачи проектирования плавающей арифметики на платформе «Мультикор» язляется наличие нестандартного формата расширенной точности, отличающегося от стандартного способа представления плавающих чисел: дополнительный код для представления мантиссы и широкий диапазон порядка, записанного без снещения.

В настоящее время теречисленные выше проблемы являются актуальными и находятся в стадии решшия не только для платформы «Мультикор», но и для других ВвР-платформ.

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

Основной целью ркботы является разработка эффективных реализаций подпрограмм гарантированной точности для очкой на новой целевой платформе «Мультикор». данной цели выделяются следующие направления

базовых математических вычислений с плавающей т

Для достижения исследований.

1.

2.

3.

4.

щионных методов для реализации алгебраических

вычисления

Исследование итер функций.

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

Разработка ассемблерных подпрограмм в фор** Переход от кода к ф

реализаций базовых арифметических Латах расширенной и двойной точности. 5. Переход от кода к ф эрмальному доказательству гарантированной точности возвращаемого резу.1гьтата для всех построенных реализаций. Методы исследования

Для проведения исс: едований были использованы: методы математического анализа;

методы численного шализа для исследования погрешностей;

• георетико-числовые методы для тестирования и для доказательства корректности;

• методы дискретной математики для доказательства условных веток вычислений при их реализации при помощи условно исполняемых инструкций;

• методы анализа программного кода. Научная новизна

В диссертационной работе разработаны методы вычислений с гарантированной точностью на новой платформе «Мультикор», в том числе:

- получены характеристики реализации плавающей арифметики в формате двойной точности стандарта ГЕЕЕ-754;

- исследованы таблично-алгоритмические реализации элементарных функций в нестандартном формате расширенной точности и реализации базовых арифметических подпрограмм в том же формате;

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

Практическая значимость

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

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

Метод редукции аргумента в формате двойной точности, основанный на СОБШ1С-алгоритмах, может быть полезен в системах с ограничениями по объему доступной памяти.

Базовые подпрограммы двойной точности реализованы и внедрены на стадии разработки специализированного математического обеспечения в НПЦ «Элвис» для платформы «Мультикор» в виде библиотеки НЬеИр. Получен соответствующий акт о внедрении результатов.

Полученные результаты используются в курсе «Математические основы обработки сигналов» в части изучения сигнальных процессоров и их математического обеспечения в НОУ Институт программных систем -Университет города Переславля. Направление исследований отражено в г/б теме ИПС РАН «Перспективные алгоритмы и структуры вычислительных устройств для задач обработки изображений, распознавания образов и управления объектами» в части разработки перспективных алгоритмов. Апробация

Основные результаты работы докладывались и обсуждались на следующих научных конференциях:

• Конференция «Авиация и космонавтика-2003», ноябрь 2003, МАИ, г. Москва.

• 3-й расширенный семинар «Использование методов искусственного интеллекта и высокопроизводительных вычислений в аэрокосмических исследованиях», ноябрь 2003, г. Переславль-Залесский, ИПС РАН.

• Конференция «Программные системы: теория и приложения», май 2004, г. Переславль-Залесский, ИПС РАН.

• XLI всероссийская конференция по проблемам математики, информатики, физики и химии в секции «Программные системы», 18-22 апреля 2005, РУДН, г. Москва.

• XLII всероссийская конференция по проблемам математики, информатики, физики и химии в секции «Программные системы», 17-21 апреля 2006, РУДН, г. Москва.

Структура и объем работ!.1

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Общий объем основного текста диссертации -118 страниц, список литературы содержит 62 наименования. В работе 7 рисунков и 29 таблиц. По теме диссертации опубликовано 6 печатных работ.

(СОДЕРЖАНИЕ РАБОТЫ

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

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

вычислений с плавающей вычислительных norpeini

терминология стандарта на изложены основы табличнс функций.

Возможность реализации встраиваемых системах

данного класса относится серия сигнальных микрокс

вычисления с двоичной плавающей точкой 1ЕЕЕ-754 и -алгоритмических методов вычислений элементарных

сложных математических вычислении на небольшим энергопотреблением и сокращенной

системой команд - относительно новая область исследований. К архитектурам л «Мультикор» - новая перспективная отечественная нтроллеров. Микросхемы данной серии (1892ВМЗТ (МС-12) и 1892ВМ2Т (МС-24)), - это однокристальные программируемые многопроцессорные «системы на кристалле». Область их применения включает в себя локацию и гидроакустику, связь, сигнальную обработку, системы

промышленного контроля, методов, обработку звука

системы управления с использованием адаптивных и изображений, а также высокоточную обработку данных для малогабаритных и встраиваемых систем. В качестве основного процессора используется ШБС-подобное ядро с архитектурой М1Р832; под его управлением работают один или более БвР-акселераторов. Система инструкций БЭР-ядра ориентирована Н1 высокопроизводительную параллельную обработку данных. Типичным для такой обработки является объединение нескольких независимых инструкций в одну параллельно исполняющуюся связку, в рамках которой может исполнятьс г до двух вычислительных операций в сочетании с :ами данных. Кроме того, поддерживается условное золяет сократить количество программных ветвлений. Подробная характеристика архитектуры «Мультикор» приводится в разделе 1.2.

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

одной или двумя пересыш исполнение команд, что поз

плавающей точкой. Данное

представление позволяет расширить динамическии

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

основном они взяты в трактовке, предлагаемой в тексте стандарта 1ЕЕЕ-754 на двоичную арифметику с плавающей точкой.

Проблема в том, что многие методы вычислений, ориентированные на классическую вещественную арифметику, могут выдавать несостоятельные результаты в арифметике плавающей. Причина заключается в накоплении ошибок округления в результате выполнения арифметических операций в форматах с плавающей точкой. Точный анализ распространения ошибок округления невозможен без знания того, какими свойствами обладает используемая реализация плавающей арифметики. В разделе 1.4 приводятся основные модели, используемые при доказательстве высокоуровневых вычислительных алгоритмов - арифметика с (1 + е) -свойством, арифметика с верно округленным результатом и арифметика, обладающая свойством корректного округления. Определение: арифметика с плавающей точкой обладает (1 +г)-свойством, если для любых представимых чисел а,Ье 1{0) и операции °е{+,-,х,/}, за исключением разве что Ь = 0 при ° = /, найдется такое в, что /1(а°Ь) = (ааЬ)-(\ + е), причем |с| < /?'"'.

Определение: пусть для любых a,b<zRpJ и °б{+,-,х,/}, за исключением разве что Ъ = 0 при о - /, с = а°Ь в точности. Пусть также х,у - два соседних числа с плавающей точкой того же знака, что и с, такие, что |х|<|с|<|_у|. Плавающая арифметика является верной, если /1(а°Ь) = х, если с = х, и результат }1(а°Ь) является одним из чисел х или у в противном случае.

Определение: арифметика с плавающей точкой обладает свойством коррекгного округления, если она верная, и если А(а°Ь) = х, если |с-д:| < |е-у\ и /1(а°Ь) = у, если |с-.у|<|с-х|.

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

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

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

Пусть /(х) - реализуемая функция, вычисляемая в области хе1. Обычный таблично-алгоритмический метод определяется набором (множеством) точек ске.1, к -1,2, . , N и таблицей приближенных значений Тк = /(ск). Для любого хе! вычисление f{x) осуществляется в три этапа

1. Редукция аргумента: выбрать по данному х соответствующую точку

2.

ск (как правиле некоторое преобр Аппроксимация: обязательно) р(г

, это ближайшая к х точка). Затем применяется азование г = Я(х,ск). Как правило, Я(х>ск) = х-ск

вычисление p(r) ~ f{r). Очень часто (хотя и не - полином.

3. Восстановление: i зависимости от преобразования R и значений f(ck) и /(г) вычисляв! ся обратное преобразование S, такое, что fix) = S(f{ck),f(r))« S(f(ck),p(r))« S(Tk,p(r)) Применение свойств арифметики с гарантированной точностью, соответствующей стандарту IEEE-754, широко и разнообразно - адаптивные алгоритмы вычисления геометрических предикатов, подпрограммы линейной алгебры, высокоточные реализации элементарных функций. Примеры можно найти в разделе 1.6.

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

Определение: числа с плавающей точкой в формате расширенной точности - числа

вида х = т-2"31 ={т,е\, соотношениям -231 < т < 23'

где т, е - целые числа, удовлетворяющие -1, -2"+1<е<215-1.

В разделе 23 описывается реализация базовых арифметических операций формате расширенной точности. Пусть х = {д, .у, },

сложения и вычитания в

у - {b,s2} - конечные числi в формате расширенной точности, причем s, > s2,

сг = s, - s2, е = s, (выход с и

нструкции СМРЕ).

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

1 2 asrl(a,b,b{) lsll(r,b,u2) sub(er,32, г)

«Наивный» алгоритм должен быть дополнен п знакового переполнения

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

1) Случай возможного переполнения (операнды одного знака и 0 < <т < 32): 15 тактов.

2) Случай возникновения ненормализованного результата (операнды разных знаков и 2 < <т 5 32): 14 тактов.

3) Случай возможной потери значащих цифр (операнды разных знаков и О < а < 1): 11 тактов.

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

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

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

Step 1,2

т

Step 3,4

& X

¡mul

п—

ties _J_

sub

3—

tub

| mul

Aim гT^

T-T" s eiea

i I I i

nms Si i

>0-

mul

ei

|tub ' |

\mul

«<42

mul -T"i— ut us —i—I_

scale

ТГ ФФОЗ шигиз . 1 ' ■ 1_u

tub 'ill

чн&чз .' ' ■_

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

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

{?Г2Ч-6,?Г3} = ?-(1 + ^).где -2-8° -2"93 <е4 <2^+2^. Данной точности достаточно для корректного округления. Базовый вариант подпрограммы деления исполняется за 88 тактов. Заметим, что с каждой итерацией сложность промежуточных вычислений возрастает из-за необходимости сохранения результатов в виде нескольких слов: 1-я и 2-я итерация занимают по 5 тактов, 3-я -16 тактов и 4-я - 24 такта.

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

Step 1,2

m

Step

n

J._

mui

Hn-

Z1ZS

I mid

—ГТ wtws THR

r1--1

sub

тгяЛ -

s—I scale

T

Step 4

I mul

H Г"

ztzs

TT

|'mu? ' I

sub I

Vt-

WIW2 П J_I_l_

mul

i1 , i i_

] scale

I mul

GtOzQi cfeos о о i ■ ' ' ' sub

4-1-

-Z! OlG¡ _1_l_i_

гпи!

gigs

J—I sede

zijs gigs —gigs

i i ,

<ий

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

Пусть х = ¿Г31 или х = - мантисса аргумента, масштабированная в зависимости от четности поэядка. В соответствующем утверждении показано, что на четвертой итерации мант теса результата представлена в виде г;19 г? = • (1 + е,) „ где 1 < Т Полученная оценке погрешности немного больше минимального возможного расстояния меяду результатом операции и точной серединой между двумя соседними значениям и с плавающей точкой. Однако, используя теоретико-числовые методы, можно перебрать все такие возможные случаи и проверить их корректность путем непосредственного вычисления (подраздел 2.5.2).

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

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

Исследование таблично-алгоритмических методов вычисления элементарных трансцендентных функций в разделе 2.6 проведено на примере

результате аргумент предет такие, что 8-N + 7 = [8 • х], г

приближения Р(г) =

2'-1

функции у-2х. Для редукции используется 8 точек разбиения Ьу = ] -2' 0=0...7) с табулированными значениями мантисс г] = {Т,'30УХТ^61 (]')}. В

авлен в виде х = № + 7-2 3 +г, где N, ] - целые,

= R-2~

- редуцированный аргумент.

Аппроксимация осуществляется при помощи полинома наилучшего

+ S,

арргпх 9

\SapprJ<2~

■+2^+2-

на интервале

2~4 < г < 2м . При целочисленном вычислении полинома нужно учитывать ошибки округления._

1 Целочисленная аппроксимация по схеме Горнера на ИБР-ядре целевой платформы =с„

2 Рог) = И-1 /О 1 (¡0

3 {

4 -> {и,,,и>2} а + с1, -> г

5

6 вЖг/^.С,)-^,

7 }

В общем случае аппроксимирующий полином задан своими масштабированными коэффициентами с1 = С] • 2'1>. Обозначим точное значение,

полученное s

на j-м шаге схемы Горнера, как

Пусть

+ • Т"'" , где - целочисленная мантисса, - накопленная

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

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

Stf.pi ячр з

т с *

Reduction

4-1-1—

N I s

R SI i)

_l_L_

Г I

wiws

Steps d'j)t

t— scots

ГТ"

R

l r-1-

add knyi

CfsJ

I

S(j*l) __1_

T-!—

UIIW2

J_

—| scale

Ш1 сапу

WiW2 Ch(ojCt(c)

¡add I Чг-

PiPs К

I mut_

TSfiJ—I I PIPB

71Г .

mul i—i—--1

PiPs L

mul r-r-

rifij

CO)-1 add

H-i

teak

T

ад-

hths

mim ВДЭД hths

add

ис!с!

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

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

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

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

подпрограмм необходим представленными в фор» 1ЕЕЕ-754 (разрядность -1023 2 Е< 1022). Все чу главе третьей показан возвращающие корректне

системы инструкций DSP-ядра целевой архитектуры. Для реализации выбран

режим округления

знаком и работа с нечис разделе 3.2.

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

ближайшему числу. Реализована обработка

денормализованных чисел, обработка бесконечностей, нулевых значений со

новыми данными. Базовые определения приводятся в

;тавлена реализация операции сложения и вычитания в j ости. Масштабирование и сложение (вычитание) ле требует строгого доказательства. Достаточно лишь каждой ветке вычислений результат умещается в выбранном нами представлении и к нему применяется корректный алгоритм округления в зависимости от параметра денормализации. После выполнения последовательностей малптабирования и сложения (вычитания) точный результат представлен в гиде 2е ■ {и^щ^и^и^16}. В зависимости от параметра денормализации мантиаы применяются три варианта правила точного округления.

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

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

архитектуры для частично разрядов

го ускорения распространения переноса от младших

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

1 тем/(Mj, v, >->{/>,/, > 0 ,ACt

2 mul(u2,v2) {й4р4} 0 ,AC0

3 macl(l,hA) {АС^ЛСо)

4 iiiac/(«,,Vj) —> {ACt,AC0}

5 macl(ys,u2) -> {ACUAC0}

6 macl :{ACtAC0} {р2рг}

7 8 asrl(3\,p2,tmp) aM(lt,p2,p2) adcl(tmp,p\,pi)

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

Т, _ г -8 „-40 -72 _-104 >

Р = \Р\ Рг Рг Pi }

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

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

(1) В формате одинарной точности найти Т(у), такое, что

Т(у)-у = \ + е,\а\<2-70

(2) Масштабировать операнды: Y> = T(y)-x, d = Т(у)■ у

(3) Выбрать 19 бит

ов частного усечением частичного остатка:

qJ = |^219 • wj, скорректировать w(j +1) = 219 • w(j)-q}-d

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

Пусть и = {щ2"и25 знаменателя. Можно noi

мантисса частного представлена в виде — = ——, где w = {w, "w^'w^1},

v 1 + е

гседовательно, sign{e) = signbit{dx).

} - мантисса числителя, v = {V, ^ } - мантисса азать, что после предварительного масштабирования

Итерации по основан: Ь = 2" no

1 For j = l to 3 do

2 {

3 {qjh,qJ} = w,

4 add({qjh,qjl},{Q,

5 лгй/е[г]({и', w2 w3})

6 (1 ,г2,гг}

7 subifarj^w^w. }) {wtw2w3}

8 scale[T]({QiQ2}) IQ&}

9 ;

Утверждение: после тре этапа — = {0Г250,~57} +

х итераций последовательности инструкций второго

К-Г'1, где |д|<1 + 2~:

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

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

е=шг20а"52}-

Базовый вариант и

яолнения подпрограммы деления в формате двойной

точности занимает 120 тактов. В случае возникновения денормализованного

результата (обрабатываем! умножения) мы получим

>го тем же фрагментом кода, что и для подпрограммы время выполнения от 132 до 138 тактов. Обработка денормализованных операндов существенно замедляет подпрограмму, а именно: обработка (нормализация, коррекция порядка) одного денормализованного операнда занимает до 22 тактов, таким образом, если и делимое и делитель не являются нормализованными, их обработка требует около 30% времени I арианта. Прибавляя возможность возникновения ьтата, получаем наихудшее время исполнения порядка случаи (результат не является конечным, результат в

исполнения базового денормализованного резул 180 тактов. Тривиальные

точности нулевой) обрабатываются за время от 27 до 39 тактов. В памяти

программ PRAM подпрог формате двойной точност 1000 до 1300 тактов, обраб выполнения до 1500-1600 п актов.

Заметим, что разработанный алгоритм арифметики одинарной точюсти может быть расширен на случай целочисленного

рамма деления занимает 316 слов. Деление чисел в а на ведущем ядре целевой архитектуры занимает от отка денормализованных операндов увеличивает время

деления с использованием

деления (взятия остатка) или использован в подпрограммах вычисления других алгебраических функций (I/х, 4х, Ул]х2 + у2). В частности, реализация квадратного корня с завершающим делением позволяет ускорить классический последовательный вариант в 3.5 раза.

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

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

Пусть 1р[А = {к"30"V2"7} = Ш + 2-'). Ьт[Л = {н,"30~V2''} = 1оё(1 -2"').

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

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

№-11<=}) { ¡/(г!>0) {{м>?°-'ч>-262->} <- Ьр[Я; а=а + 1;} ¡/(г1<0) ¡Чи'1-3!к,№"62--'} <- 1т[Л; а=а - 1;} .чса1е _ гщЫЦ + 10] н'262^ } -> К20^52^4} ™6(К2Ч5Ч84}, К2 Ч5Ч84}) я"*?*?} } МРУЬ{а,у]) -» {у,у2}

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

8

+ ^+ сг, • ), а результат ехр(Х) = ехр(г) ■ у.

.м

Здесь у = {у?у?} = 1[(\ + су^2~'), /^г,20^84}, где 1е(-2'й;+2->) -

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

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

вычислительных алгорит плавающей арифметики.

В разделе 4.3 разрядности корректен пр свойством верного округл Пусть р - основа!-разрядность используемс

лов, построенных на основе реализованной в работе

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

:ие системы счисления используемой арифметики, р -й арифметики. Тогда для динамического (времени выполнения) определеши основания используемой арифметики могут быть использованы два цикла £ 0-\¥Н1ЬЕ.

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

1 W = One;

2 Do{

3 W= W+W;

4 Y= W+One,

5 Z-Y—W,

6 Y = Z- One,

7 } whi!e(MinusOne + Fa BS(Y) < Zero);

8 У = One;

9 Do{

10 Radix =W+ Y;

11 Y=Y+Y,

12 Radix - Radix - 7-

13 } while (Radix -= Zero)

В соответствующих цикла ulp(W) = р, а при

утверждениях показано, что после выхода из первого условии ulp{W) = р, после выхода из второго цикла значение переменной Rad.x равняется основанию используемой арифметики р. Заметим, что в арифметике, обладающей лишь (1 + г)-свойством, данные утверждения невозможно доказать, а в обычной вещественной арифметике они и вовсе не являются истиннь ми - оба цикла были бы бесконечными.

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

Метод определения параметров С/, = ulp(X), если X > 1.0, и U2= ulp(X), если X < 1.0, основанный на использовании бесконечных периодических дробей описывается в подразделе 4.3.2. Доказаны утверждения по двум циклам.

В ажной составляю и

стратегия округления и,

зщей плавающей арифметики является выбранная как следствие, корректность использования битов округления в базовых арифметических операциях. В разделе 4.4 показана корректность алгоритма определения двух возможных стратегий округления -корректное округление в стиле IEEE-754 и случай округления усечением Утверждение: В случае к орректного округления величины X, У, Z, Т, StickyBit необходимо равны нулю, а величина Y1 в точности 0 5 В случае округления усечением величины X, Z, UtickyBit при сложении с U2 необходимо дают нулевое значение; величины Т и У должны быть строго меньше нуля, а величина Y1 строго меньше 0 5.

В случае', когда плавающая арифметика реализует корректное округление, тестируется корректность использования вспомогательной величины остатка (Sticky Bit). Анализу соответствующего фрагмента посвящен раздел 4.5.

Утверждение в случае корректного использования остатка (sticky bit) значение величины StickyBit = 1, в противном случае StickyBit = О

В заключении сформулированы основные результаты диссертационной работы.

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

Основные результаты

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

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

3) Показано, что для вычисления элементарных трансцендентных функций в расширенном формате на DSP-ядре хорошо подходят таблично-алгоритмические методы. Выведенные в работе формулы для оценки погрешностей целочисленной аппроксимации у = 2х могут бьггь использованы для других элементарных функций (иногда при условии их незначительной модификации).

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

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

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

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

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

8) Основные резуль- ■ математического «Мультикор» в вид

аты внедрены при разработке специализированного обеспечения в НПЦ «Элвис» для платформы стандартных библиотек ассемблерных подпрограмм.

:д;е

Опубликованные работы по теме диссертации

1. Захаров A.B., Хачумов В.М. Разрядно-параллельные вычисления в системах реального времени // Математика, информатика: теория и практика. Сб. трудов, посвященный 10-летию Университета г. Переславля. / Под ред. А.К.Айламазяна. - Переславль-Залесский: Издательство «Университет города Переславля», 2003, с. 97-104.

2. Захаров A.B. Разрядно-параллельные вычислительные схемы для тригонометрических преобразований II Труды 3-го расширенного семинара «Использование методов искусственного интеллекта и высокопроизводительных вычислений в аэрокосмических исследованиях». - Переславль-Залесский: Издательство «Феникс», 2003, с. 167-173.

3. Захаров A.B., Хачумов В.М. Алгоритмы CORDIC. Современное состояние и перспективы. // Программные системы: теория и приложения, М : Физматлит, 2004, с. 353-372.

4. Захаров A.B. Обзор поддержки плавающей точки в формате расширенной точности на платформе «Мультикор». // Труды XLII всероссийской сонференции по проблемам математики, информатики, физики и химик. - М.: Издательство РУДН, 2006, с. 46-66.

5. Амелькин С.А., Захаров A.B., Хачумов В.М. Обобщенное расстояние Евклида-Махал; шобиса и его свойства. // Информационные технологии и вычислительные системы, № 4,2006, с. 40-44.

6. Бурдаев М.Н., Виноградов А.Н., Заднепровский В.Ф., Захаров A.B., Куршев Е.П., Хачумов В.М. Комплекс программно-инструментальных средств для создания интеллектуальных систем контроля и управления объектами аэ »космического назначения. // Авиакосмическое приборостроение, №8,2006, с. 24-33.

Личный вклад автора в совместных работах:

В работе [1] автору принадлежит исследование возможности разрядно-параллельного представления CORDIC-алгоритмов.

В работе [3] автору принадлежит классификация CORDIC-алгоритмов и исследование погрешностей вычисления тригонометрических функций.

В работе [5] автору принадлежит экспериментальная расчетная часть работы, выполненная на платформе «Мультикор».

В работе [6] автору принадлежит раздел, посвященный разработке математического обеспечения для встраиваемых систем контроля и диагностики на базе сигнальных микроконтроллеров «Мультикор».

Подписано в печать 11.04.2007 г. Исполнено 12.04.2007 г. Печать трафаретная.

Заказ № 288 Тираж: 100 экз.

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (495) 975-78-56 www.autoreferat.ru

ВВЕДЕНИЕ.

ГЛАВА 1. Арифметика чисел с плавающей точкой.

1.1. Введение.

1.2. Платформа «Мультикор».

1.2.1. Система инструкций.

1.2.2. Ассемблер DSP.

1.2.3. Системные особенности.

1.3. Стандарт IEEE-754.

1.4. Модели плавающих арифметик.

1.4.1. Определения.

1.4.2. Доказательство реализаций.

1.5. Элементарные функции.

1.6. Применение.

1.7. Выводы.

ГЛАВА 2. Формат расширенной точности.

2.1. Введение.

2.2. Базовые определения.

2.3. Сложение (вычитание).

2.4. Деление.

2.5. Операция извлечения квадратного корня.

2.5.1. Выбор начального приближения.

2.5.2. Трудные для округления случаи.

2.5.3. Алгоритм SQRT.

2.6. Элементарные функции.

2.7. Выводы.

ГЛАВА 3. Формат двойной точности.

3.1. Введение.

3.2. Базовые определения.

3.3. Сложение (вычитание).

3.4. Умножение.

3.5. Деление.

3.5.1. Деление без восстановления остатка.

3.5.2. Деление SRT по основанию 4.

3.5.3. Деление с большим основанием.

3.6. Элементарные функции.

3.6.1. CORDIC-алгоритмы.

3.6.2. Алгоритмы редукции.

3.7. Выводы.

ГЛАВА 4. Применение гарантированной точности.

4.1. Введение.

4.2. Тестовый пакет Paranoia.

4.3. Анализ основания и разрядности.

4.3.1. Целочисленный алгоритм.

4.3.2. Бесконечные периодические дроби.

4.4. Корректность округления.

4.5. Корректность использования остатка.

4.6. Выводы.

Актуальность темы.

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

Основными производителями микропроцессорных средств в настоящее время являются зарубежные фирмы. В связи с этим важным явлением стало появление новой архитектуры - «Мультикор», перспективной отечественной разработки, способной конкурировать с зарубежными. Данная архитектура представлена серией сигнальных микроконтроллеров - в частности, микросхемами 1892ВМЗТ (МС-12) и 1892ВМ2Т (МС-24) [multicore]. Это однокристальные программируемые многопроцессорные «системы на кристалле» на базе IP-ядерной платформы, разработанной в НПЦ «Элвис». В качестве основного процессора используется RISC-подобное ядро с архитектурой MIPS32 [mips]; под его управлением работают один или более DSP-акселераторов.

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

Арифметические операции с плавающей точкой образуют базис для построения на их основе очень большого количества вычислительных алгоритмов, которые должны учитывать особенности архитектуры. К ним относятся алгоритмы линейной алгебры [Li02], подпрограммы для вычисления корней полиномов и более сложных функций и т.п. [БибердорфО!]. Кроме этого, отметим, что центральным аспектом для всех платформ является наличие реализаций различных элементарных функций, таких как тригонометрические или экпоненциально-логарифмические. Заметим, что в последние годы наблюдается тенденция к отходу от аппаратных реализаций таких функций в сторону программных [Harrison99a, GreerOl]. Благодаря этому обеспечивается гибкость в процессе разработки, снижается стоимость и увеличивается открытость архитектуры в целом.

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

Важным условием их применимости является то, что арифметика с плавающей точкой должна удовлетворять некоторым требованиям, обладать свойствами математической корректности. На аппаратном уровне эта проблема решается разработчиками путем соответствия стандартам на вычисления с плавающей точкой [GuyOO, GuyOl, Russinoff98]. Стандарт, взятый как абстрактная модель, обладает необходимыми свойствами, и они довольно хорошо изучены. Однако возникает проблема верификации того, действительно ли построенная реализация соответствует этому стандарту, в части обеспечения гарантированной точности. Под гарантированной точностью здесь понимается то, что результат выполнения любой базовой арифметической операции однозначно определен, и, следовательно, на любой платформе с этой арифметикой мы получим одни и те же результаты.

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

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

В настоящее время перечисленные выше проблемы являются актуальными и находятся в стадии решения не только для платформы «Мультикор», но и для других DSP-платформ [Bertin04, Iordache03].

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

Цель диссертационной работы.

Основной целью диссертационной работы является построение эффективных реализаций базовых математических подпрограмм гарантированной точности для обработки данных с плавающей точкой на новой целевой платформе «Мультикор».

Для достижения данной цели в диссертационной работе поставлены и решены следующие основные задачи:

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

2. Исследование таблично-алгоритмических методов вычисления элементарных трансцендентных функций.

3. Разбиение возможных значений аргументов на подобласти, существенно отличающиеся по своей обработке (подпрограммы сложения и вычитания).

4. Разработка ассемблерных реализаций базовых арифметических подпрограмм в форматах расширенной и двойной точности.

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

Научная новизна работы.

В диссертационной работе разработаны методы вычислений с гарантированной точностью на новой платформе «Мультикор», в их числе:

• получены характеристики реализации базовых арифметических подпрограмм в формате двойной точности стандарта IEEE-754;

• исследованы таблично-алгоритмические реализации элементарных функций в нестандартном формате расширенной точности и реализации базовых арифметических подпрограмм в том же формате;

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

Практическая значимость работы.

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

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

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

Использование результатов работы.

Практически все базовые подпрограммы реализованы и внедрены на стадии разработки специализированного математического обеспечения в НПЦ «Элвис» для платформы «Мультикор». Получен соответствующий акт о внедрении результатов.

Полученные результаты используются в курсе «Математические основы обработки сигналов» в части применения сигнальных процессоров и их математического обеспечения в НОУ Институт программных систем -Университет города Переславля.

Апробация работы.

Основные результаты диссертационной работы докладывались и обсуждались на научных семинарах кафедры информационных технологий факультета физико-математических наук Российского университета дружбы народов и на следующих конференциях: "Авиация и космонавтика-2003" (ноябрь 2003, МАИ, г. Москва), "Программные системы и приложения" (май 2004, г. Переславль-Залесский, ИПС РАН), XLI и XLII всероссийских конференциях по проблемам математики, информатики, физики и химии в секции «Программные системы» (апрель 2005,2006 г., РУДН, г. Москва).

Структура и объем диссертации.

Диссертационная работа состоит из введения, четырех глав, заключения и приложения. Во введении обосновывается актуальность темы диссертационной работы, сформулированы основные цели и задачи исследования, его научная новизна и практическая значимость. Первая глава диссертации посвящена обзору литературы по вычислениям с плавающей точкой. Здесь описываются основные подходу к анализу погрешностей, обсуждаются различные оценки гарантированности результатов. Кроме того, описываются существенные черты вычислительной платформы «Мультикор» и приводятся данные по двум архитектурам аналогичного класса для сравнительного анализа [Bertin04, Iordache03], Вторая глава посвящена исследованию вопросов реализации арифметических подпрограмм с гарантированным результатом в нестандартном формате расширенной точности [ЗахаровОб]. В этой главе получены доказательства корректности пяти базовых арифметических операций. Кроме того, исследована реализуемость таблично-алгоритмических способов вычисления элементарных функций [Tang91] на целевой платформе. В третьей главе диссертации анализируется построение библиотеки арифметических подпрограмм в формате двойной точности. Показано, что возвращаемый результат соответствует стандарту IEEE-754 на вычисления с двоичной плавающей точкой [ieee754]. Рассматриваются способы реализации элементарных алгебраических функций с быстрым предварительным масштабированием. В главе четвертой приведены примеры того, как реализация арифметики гарантированной точности позволяет доказывать утверждения относительно высокоуровневых алгоритмов. В заключении сформулированы

Заключение

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

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

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

Строгое доказательство корректности возвращаемых результатов позволяет применять техники программного расширения точности.

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

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

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

Алгоритм деления с предварительным масштабированием в формате одинарной точности позволяет наиболее полно использовать особенности ядра ЦОС целевой платформы и может с успехом применяться для вычисления любых алгебраических функций.

Предложенная в работе модификация таблично-алгоритмических методов реализации элементарных функций в формате двойной точности на основе CORDIC-алгоритмов позволяет сократить количество используемых для редукции констант.

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

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

1. Амелькин. Амелькин С.А., Захаров А.В., Хачумов В.М. Обобщенное расстояние Евклида-Махаланобиса и его свойства. // Информационные технологии и вычислительные системы. №4,2006, с.40-44.

2. Байков75.: Байков В. Д., Смолов В.Б. Аппаратурная реализация элементарных функций в ЦВМ. Ленинград: Издательство ЛГУ, 1975.

3. Бибердорф01.: Бибердорф Э.А., Попова Н.И. Решение линейных систем с гарантированной оценкой точности результатов. Часть первая. Институт ядерной физики им. Г. И. Будкера СО РАН, Новосибирск, 2001.

4. Ершов04.: Ершов А.Г., Кашеварова Т.П. Интервальная математическая библиотека, основанная на разложениях в ряды Чебышева и Тейлора. Сборник трудов Международной Конференции по Вычислительной Математике, с. 201-209, 2004.

5. Захаров04.: Захаров А.В., Хачумов В.М. Алгоритмы CORDIC. Современное состояние и перспективы. Программные системы: теория и приложения, М.: Физматлит, май 2004, с. 353-372.

6. ЗахаровОб.: Захаров А.В. Обзор поддержки плавающей точки в формате расширенной точности на платформе «Мультикор». // Труды XLII всероссийскойконференции по проблемам математики, информатики, физики и химии. М.: Издательство РУДН, 2006, с. 46-66.

7. Каханер98.: Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение.: Пер. с англ. М.: Мир, 1998. - 575 с.

8. ТаненбаумОб.: Таненбаум Э. Архитектура компьютера. 4-е издание. СПб.: Питер, 2006.-699 с.

9. УорренОЗ.: Уоррен Г. Алгоритмические трюки для программистов.: Пер. с англ. -М.: Издательский дом «Вильяме», 2003. 288 с.

10. Bertin04.: Bertin С. et al. A floating-point library for integer processors. Tech. report #5268, July 2004.

11. Boldo03.: Boldo S., Daumas M. A simple test qualifying the accuracy of Horner's rule for polynomials. Tech. report #4707,38 p., Jan. 2003.

12. Cornea98.: Cornea-Hasegan M. Proving the IEEE correctness of iterative floating-point square root, divide and remainder algorithms. Intel Technology Journal, 1998-Q2:1-11,1998.

13. Darcy98.: Darcy J.D., Kahan W. How java's floating-point hurts everyone everywhere. ACM 1998 workshop on java for high-performance computing, Stanford, 1998.

14. Daumas04.: Daumas M., Boldo S. Properties of two's complement floating-point notations International Journal on Software Tools for Technology Transfer, Vol. 5, issue 2, March 2004.

15. Daumas02.: Daumas M., Boldo S. Necessary and sufficient conditions for exact floating point operations. Tech. report #4644.18p. Nov. 2002.

16. Defour04.: Defour D., Hanrot G., Lefevre V., Muller J.-M., Revol N. and Zimmermann P. Proposal for a Standardization of Mathematical Function Implementation in FloatingPoint Arithmetic. Research Report 5406, INRIA, 2004.

17. DefourOl.: Defour D., Kornerup P., Muller J.-M., Revol N. A new range reduction algorithm, Technical report #4267, 2001.

18. Ercegovac99.: Ercegovac M., Imbert L., Matula D., Muller J.-M., Wei G. Improving Goldschmidt division, square root and square root reciprocal. Tech. report #3753. Sept.1999.

19. Goldberg91.: Goldberg D. What every computer scientist should know about floatingpoint arithmetic. ACM Computing Surveys, 23(1): 5-47, March 1991.

20. Graca06.: Graca G. Da, Defour D. Implementation of float-float operators on graphics hardware. Proc. of 7th conference on Real Numbers and Computers, RNC7, Nancy, France, July 2006.

21. GreerOl.: Greer В., Harrison J., Henry G., Li W., Tang P.T.P. Scientific computing on the Itanium TM processor. Proc. Of the 2001 ACM/IEEE conference on Supercomputing, 2001.

22. GuyOO.: Guy E., Wolfgang P. On the design of IEEE-754 compliant floating point units. IEEE Transactions on computers, Vol.49, issue 5, pp. 398-413, May 2000.

23. GuyOl.: Guy E., Seidel P.-M. On the design of fast IEEE floating-point adders. In proc.th

24. Of the 15 International Symposium on Computer Arithmetic, 2001.

25. HarrisonOO.: Harrison J. Formal verification of IA-64 division algorithms. Proc. Of the 13th International Conference on Theorem Proving in higher order logics, 2000.

26. Harrison99.: Harrison J. A machine-checked theory of theory of floating-pointarithmetic. In Y. Bertot, G. Dower, A. Hirschowitz, C. Paulin, and L. Thery, editors,th

27. Theorem proving in higher order logics: 12 international conference, p. 113-130, Nice, France, Sept. 1999, Springer-Verlag.

28. Harrison03.: Harrison J. Formal verification of square root algorithms. Formal methods in system design, vol.22, issue 2, pp. 143-153, March 2003.

29. Harrison99a.: Harrison J., Kubaska Т., Story S., and Tang P.T.P. The computation of transcendental functions on the IA-64 architecture. Intel Technology Journal, (Q4):l-7, November 1999.

30. Iordache03.: Iordache C., Tang P.T.P. An overview of floating-point support and math library on the Intel XScale Architecture. In proc. Of the 16th IEEE Symposium on computer arithmetic, pp. 122-128, June 2003.

31. Kahan05.: Kahan W. A logarithm too clever by half. Available electronically at /~wkahan/LOG 10HAF.txt.

32. КогпегирОЗ.: Kornerup P., Muller J.-M. Choosing starting values for Newton-Raphson computation of reciprocals, square-roots and square-root reciprocals. Tech. report #4687, Jan. 2003.

33. Li03.: Li R.-C., Boldo S. and Daumas D. Theorems on efficient argument reductions. Proc. Of the 16th IEEE Symposium on Computer Arithmetic, 2003.

34. Li02.: Li X.S., Demmel J.W., Bailey D.H., Henry G., et al. Design, Implementation and testing of extended and mixed precision BLAS. ACM Transaction on Mathematical Software, Vol. 28, No. 2, pp. 152-205, June 2002.

35. Markstein97.: Markstein P., Karp A.P. High precision division and square root. ACM Transactions on Mathematical Software, Vol. 23, num. 4, pp. 561-589,1997.

36. Muller03.: Muller J.-M., Brisebarre N. Finding the "truncated" polynomial that is closest to a function. Tech. report #4787, 15 pages Avr. 2003.

37. Muller05.: Muller J.-M. On the definition of ulp(x). Tech. report #5504. 16 p. Feb. 2005.43. multicore. http://multicore.ru/

38. Ng92.: K.C. Ng. Argument reduction for huge arguments: good to the last bit. Technical report, SunPro, 1992.

39. Nickmehr05.: Nickmehr H. Architectures for floating-point division. Ph.D., The university of Adelaide Australia, p. 241, Aug. 2005.

40. Oberman97.: Oberman S.F., Flynn M.J. Division algorithms and implementations. IEEE transactions on computers, 48(6): 833-854, Aug. 1997.

41. Priest91.: Priest, Douglas M. Algorithms for arbitrary precision floating point arithmetic. Proceedings of the 10th {IEEE} Symposium on Computer Arithmetic, pp. 132-144,1991.

42. Priest92.: Priest, Douglas M. On properties of floating point arithmetic: numerical stability and the cost of accurate computations. Draft of PhD Thesis, Berkeley, Nov. 1992.

43. Russinoff98.: Rusinoff, David M. A mechanically checked proof of IEEE compliance of the floating point multiplication, division, and square root algorithms of the AMD-K7 processor. LMS Journal of Computation and Mathematics, Vol. 1,1998.

44. Schulte99.: Schulte M. J., Stine J. E. Approximating elementary functions with symmetric bipartite tables. IEEE Transactions on computers, Vol. 48, No. 8, Aug. 1999.

45. Shewchuk97.: Shewchuk J. R. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18:305-363,1997.

46. Story99.: S. Story, P.T.P. Tang. New algorithms for improved transcendental functions on IA-64. Proc. 14th IEEE Symposium on Computer Arithmetic, 1999.

47. Sun.: Numerical computation guide by Sun.

48. Tang91.: Tang P.T.P. Table-Lookup algorithms for elementary functions and their error analysis. In P. Kornerup and D.W. Matula, editors, Proc. Of the 10th IEEE symposium on Computer Arithmetic, pp. 232-236, Grenoble, France, June 1991.

49. Tang89.: Tang P.T.P. Table-driven implementation of the exponential function in IEEE floating-point arithmetic. ACM Transactions on Mathematical Software, vol. 15, No. 2, pp. 144-157, June 1989.

50. Tang90.: Tang P.T.P. Table-driven implementation of the logarithm function in IEEE floating-point arithmetic. ACM Transactions on Mathematical Software, vol. 16, No. 4, pp. 378-400, Dec. 1990.

51. Tang92.: Tang P.T.P. Table-driven implementation of the expml function in IEEE floating-point arithmetic. ACM Transactions on Mathematical Software, vol. 18, No. 2, pp. 211-222, June 1992.

52. Volder59.: Voider J.E. The Cordic trigonometric computing technique. IRE Transactions on Electronic Computers. Vol. 8, pp. 330-334,1959.

53. Walther71.: Walther J.S. A unified algorithm for elementary functions. Proc. Spring Joint Computer Conference, pp. 379-385,1971.60. arm.: www.arm.com61. mips.: www.mips.com62. paranoia.: www.netlib.org/paranoia/1. Список иллюстраций

54. Рис. 1.1. Функциональная схема сложения (вычитания) чисел в формате расширенной точности: переполнение мантиссы, ненормализованная мантисса и обработка возможной потери значащих битов.

55. Рис. 1.2. Функциональная схема деления в формате расширенной точности: Step 1,2-первые две итерации, Step 3,4- третья и четвертая итерации.

56. Рис. 1.3. Функциональная схема алгоритма извлечения квадратного корня: Step 1,2-первая и вторая итерации, Step 3 третья итерация, Step 4 - переход к вычислению квадратного корня.

57. Рис. 1.4. Функциональная схема алгоритма возведения двойки в степень: Stepl редукцияаргумента, Step2 полиномиальная аппроксимация, Step3 - восстановление результата.

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

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

60. Рис. 2.3. Деление в формате двойной точности: Step 1 предварительноемасштабирование, Step 2 три итерации по основанию = 219, Step3 - округлениерезультата.