Содержание к диссертации
Введение
ГЛАВА 1. Арифметика чисел с плавающей точкой 10
1.1. Введение 10
1.2. Платформа «Мультикор» 10
1.2.1- Система инструкций 11
1.2.2. Ассемблер DSP 13
1.2.3. Системные особенности , 16
1.3. Стандарт IEEE-754 16
1.4. Модели плавающих арифметик 22
1.4.1. Определения 22
1.4.2. Доказательство реализаций, 26
1.5. Элементарные функции 29
1.6. Применение 32
1.7. Выводы 34
ГЛАВА 2. Формат расширенной точности 35
2.1. Введение 35
2.2. Базовые определения 35
2.3. Сложение (вычитание) 38
2.4. Деление 45
2.5. Операция извлечения квадратного корня 48
2.5.1. Выбор начального приближения 48
2.5.2. Трудные для округления случаи 49
2.5.3. Алгоритм SQRT 51
2.6. Элементарные функции 55
2.7. Выводы 59
ГЛАВА 3. Формат двойной точности 61
3.1. Введение 61
3.2. Базовые определения 62
3.3. Сложение (вычитание) , 64
3.4. Умножение 75
3.5. Деление 79
3.5.1. Деление без восстановления остатка 79
3.5.2. Деление SRT по основанию 4 80
3.5.3. Деление с большим основанием 81
3.6. Элементарные функции 87
3.6.1. CORDIC-алгоритмы 87
3.6.2. Алгоритмы редукции 89
3.7. Выводы 91
ГЛАВА 4. Применение гарантированной точности 93
4.1. Введение 93
4.2. Тестовый пакет Paranoia 93
4.3. Анализ основания и разрядности .. 94
4.3.1. Целочисленный алгоритм 94
4.3.2. Бесконечные периодические дроби 98
4.4. Корректность округления 101
4.5. Корректность использования остатка 104
4.6. Выводы 107
Заключение 108
Литература
- Система инструкций
- Операция извлечения квадратного корня
- Сложение (вычитание)
- Анализ основания и разрядности
Введение к работе
В настоящее время одним из перспективных научных направлений в области вычислительной техники является проектирование так называемых встраиваемых систем - специализированных микропроцессорных устройств с малым энергопотреблением- Архитектура подобных устройств становится все более сложной, может включать в себя несколько вычислительных ядер на одном кристалле и по своим функциональным возможностям приближается к процессорам общего назначения [ТаненбаумОб].
Основными производителями микропроцессорных средств в настоящее время являются зарубежные фирмы. В связи с этим важным явлением стало появление новой архитектуры - «Мультикор», перспективной отечественной разработки, способной конкурировать с зарубежными. Данная архитектура представлена серией сигнальных микроконтроллеров - в частности, микросхемами ВМЗТ (МС- ) и ВМ2Т (МС- ) [multicore]. Это однокристальные программируемые многопроцессорные «системы на кристалле» на базе IP-ядерной платформы, разработанной в НПЦ «Элвис». В качестве основного процессора используется RISC-подобное ядро с архитектурой MIPS [mips]; под его управлением работают один или более DSP-акселераторов.
Одной из проблем, возникающих при внедрении новых архитектур, является необходимость наращивания объема доступного системного программного обеспечения для данной архитектуры, важную часть которого составляют библиотеки базовых математических подпрограмм, включающих в себя арифметические операции над операндами в формате с плавающей точкой и элементарные функции. В полной мере это относится к различным архитектурам цифровой обработки сигналов (ЦОС, DSP), реализация арифметических подпрограмм для которых недостаточно широко изучена.
Арифметические операции с плавающей точкой образуют базис для построения на их основе очень большого количества вычислительных алгоритмов, которые должны учитывать особенности архитектуры. К ним относятся алгоритмы линейной алгебры [Li ], подпрограммы для вычисления корней полиномов и более сложных функций и т.п. [БибердорфОІ]. Кроме этого, отметим, что центральным аспектом для всех платформ является наличие реализаций различных элементарных функций, таких как тригонометрические или экпоненциально-логарифмические. Заметим, что в последние годы наблюдается тенденция к отходу от аппаратных реализаций таких функций в сторону программных [Harrison a, GreerOl]. Благодаря этому обеспечивается гибкость в процессе разработки, снижается стоимость и увеличивается открытость архитектуры в целом.
Основной проблемой, возникающей при переносе существующего математического обеспечения на новые платформы, является проблема корректности используемой арифметики. Дело в том, что каждая конкретная реализация арифметики с плавающей точкой имеет свои уникальные особенности, которые задают ограничения и определяют возможности построения платформенно-ориентированных версий часто используемых математических подпрограмм.
Важным условием их применимости является то, что арифметика с плавающей точкой должна удовлетворять некоторым требованиям, обладать свойствами математической корректности. На аппаратном уровне эта проблема решается разработчиками путем соответствия стандартам на вычисления с плавающей точкой [GuyOO, GuyOl, Russinofr ]. Стандарт, взятый как абстрактная модель, обладает необходимыми свойствами, и они довольно хорошо изучены. Однако возникает проблема верификации того, действительно ли построенная реализация соответствует этому стандарту, в части обеспечения гарантированной точности. Под гарантированной точностью здесь понимается то, что результат выполнения любой базовой арифметической операции однозначно определен, и, следовательно, на любой платформе с этой арифметикой мы получим одни и те же результаты.
Еще одним фактором является принцип распределенной обработки данных в гетерогенных структурах, образованных множеством микропроцессорных устройств. В этом случае крайне желательно, чтобы арифметика различных узлов таких сетей обладала сходными свойствами, как с математической точки зрения, так и с точки зрения времени обработки - требование инвариантности арифметики. К примеру, базовые арифметические операции реализованы над одними и теми же множествами операндов и скорость обработки одинаковых множеств не слишком отличается на разных машинах. В этом случае не происходит эффекта, при котором один узел с медленной арифметикой задерживает остальные, более быстрые.
Особенностью задачи проектирования плавающей арифметики на платформе «Мультикор» является наличие нестандартного формата расширенной точности, отличающегося от стандартного способа представления плавающих чисел: дополнительный код для представления мантиссы и широкий диапазон порядка, записанного без смещения.
В настоящее время перечисленные выше проблемы являются актуальными и находятся в стадии решения не только для платформы «Мультикор», но и для других DSP-платформ [Bertin , Iordache ].
В свете вышеизложенного представляются актуальными задачи проектирования, разработки, реализации и верификации базовых математических алгоритмов нижнего уровня, таких как арифметические и элементарные функции, для встраиваемых микропроцессорных систем. Важнейшей задачей является обеспечение корректности вычислений, т.е. получение результата с гарантированной точностью. Этим вопросам и посвящена настоящая работа.
Цель диссертационной работы.
Основной целью диссертационной работы является построение эффективных реализаций базовых математических подпрограмм гарантированной точности для обработки данных с плавающей точкой на новой целевой платформе «Мультикор».
Для достижения данной цели в диссертационной работе поставлены и решены следующие основные задачи:
1. Исследование итерационных методов для реализации алгебраических функций (деление, квадратный корень).
2. Исследование таблично-алгоритмических методов вычисления элементарных трансцендентных функций.
3. Разбиение возможных значений аргументов на подобласти, существенно отличающиеся по своей обработке (подпрограммы сложения и вычитания).
4. Разработка ассемблерных реализаций базовых арифметических подпрограмм в форматах расширенной и двойной точности.
5. Переход от кода к формальному доказательству гарантированной точности возвращаемого результата для всех построенных реализаций.
Научная новизна работы.
В диссертационной работе разработаны методы вычислений с гарантированной точностью на новой платформе «Мультикор», в их числе:
• получены характеристики реализации базовых арифметических подпрограмм в формате двойной точности стандарта IEEE- ;
• исследованы таблично-алгоритмические реализации элементарных функций в нестандартном формате расширенной точности и реализации базовых арифметических подпрограмм в том же формате;
• предложен новый метод редукции аргумента с минимальным количеством используемых констант и метод деления с предварительным масштабированием в формате одинарной точности.
Практическая значимость работы.
Представленные в работе теоремы о корректности предложенных реализаций базовых арифметических операций могут быть использованы при разработке, переносе и анализе вычислительных алгоритмов с плавающей точкой.
Последовательные алгоритмы для реализации элементарных алгебраических функций в формате двойной точности с предварительным масштабированием могут быть использованы на любых архитектурах, поддерживающих аппаратно арифметику одинарной точности.
Комбинированный метод вычисления элементарных функций в формате двойной точности может быть полезен в системах с ограничениями по объему доступной памяти. Использование результатов работы.
Практически все базовые подпрограммы реализованы и внедрены на стадии разработки специализированного математического обеспечения в НПЦ «Элвис» для платформы «Мультикор». Получен соответствующий акт о внедрении результатов.
Полученные результаты используются в курсе «Математические основы обработки сигналов» в части применения сигнальных процессоров и их математического обеспечения в НОУ Институт программных систем -Университет города Переславля.
Апробация работы.
Основные результаты диссертационной работы докладывались и обсуждались на научных семинарах кафедры информационных технологий факультета физико-математических наук Российского университета дружбы народов и на следующих конференциях: "Авиация и космонавтика- " (ноябрь , МАИ, г. Москва), "Программные системы и приложения" (май , г. Переелавль-Залесский, ИПС РАН), XLI и XLII всероссийских конференциях по проблемам математики, информатики, физики и химии в секции «Программные системы» (апрель , г., РУДН, г. Москва).
Структура и объем диссертации.
Диссертационная работа состоит из введения, четырех глав, заключения и приложения. Во введении обосновывается актуальность темы диссертационной работы, сформулированы основные цели и задачи исследования, его научная новизна и практическая значимость. Первая глава диссертации посвящена обзору литературы по вычислениям с плавающей точкой. Здесь описываются основные подходу к анализу погрешностей, обсуждаются различные оценки гарантированности результатов. Кроме того, описываются существенные черты вычислительной платформы «Мультикор» и приводятся данные по двум архитектурам аналогичного класса для сравнительного анализа [Bertin , Iordache ]. Вторая глава посвящена исследованию вопросов реализации арифметических подпрограмм с гарантированным результатом в нестандартном формате расширенной точности [ЗахаровОб]. В этой главе получены доказательства корректности пяти базовых арифметических операций. Кроме того, исследована реализуемость таблично-алгоритмических способов вычисления элементарных функций [Tang ] на целевой платформе. В третьей главе диссертации анализируется построение библиотеки арифметических подпрограмм в формате двойной точности. Показано, что возвращаемый результат соответствует стандарту IEEE- на вычисления с двоичной плавающей точкой [ieee ]. Рассматриваются способы реализации элементарных алгебраических функций с быстрым предварительным масштабированием. В главе четвертой приведены примеры того, как реализация арифметики гарантированной точности позволяет доказывать утверждения относительно высокоуровневых алгоритмов. В заключении сформулированы основные результаты, полученные в диссертационной работе. В конце работы помещен список рисунков, приведенных в диссертации, а также список цитируемой литературы.
Система инструкций
Микросхемы серии сигнальных микроконтроллеров «Мультикор» [multicore] - в частности, микросхемы 1892ВМЗТ (МС-12) и 1892ВМ2Т (МС-24), - это однокристальные программируемые многопроцессорные «системы на кристалле» на базе IP-ядерной платформы, разработанной в НПЦ «Элвис», Область применения включает в себя локацию и гидроакустику, связь, сигнальную обработку, системы промышленного контроля, системы управления с использованием адаптивных методов, мультимедийную обработку звука и изображений, а также высокоточную обработку данных для малогабаритных и встраиваемых систем.
В качестве основного процессора используется RISC-подобное ядро с архитектурой MIPS32 [mips]; под его управлением работают один или более DSP-акселераторов. Перечислим коротко основные архитектурные особенности DSP-ядра. DSP-ядро имеет гарвардскую архитектуру с внутренним параллелизмом по потокам обрабатываемых данных (так называемая SlMD-архитектура). Второй уровень распараллеливания определяется возможностью исполнения в течение одного командного такта нескольких операций (подробнее об этом ниже). Функционирует под управлением RISC-ядра и расширяет его возможности по обработке сигналов. 1.2.1 Система инструкций
Система инструкций DSP-адра ориентирована на высокопроизводительную параллельную обработку данных. Типичным для такой обработки является объединение нескольких независимых инструкций в одну параллельно исполняющуюся связку [ТаненбаумОб]. В рамках одной такой связки может быть исполнено до двух вычислительных операций в сочетании с одной или двумя пересылками данных. Кроме того, поддерживается условное исполнение команд. Необычным является наличие у DSP-ядра устройства для выполнения операций с плавающей точкой в формате одинарной точности.
В рамках одной инструкции может быть выполнено до двух вычислительных операций и до двух пересылок. Количество одновременно исполняемых операций и их тип определяют формат инструкции, то есть размер и структуру кода. Всего различают восемь форматов с некоторыми вариациями.
Параллельное выполнение двух вычислительных операций возможно только в том случае, когда они исполняются на разных операционных устройствах. В зависимости от исполняющего устройства их можно разделить на два типа. К первому типу относятся операции, исполняемые при помощи арифметического (AU - Arithmetic Unit) или логического устройства (LU - Logic Unit), ко второму - операции, исполняемые при помощи умножителя-сдвигателя (MS - Multiply-Shift).
Кодов условий являются логическими функциями признаков вычислительных операций. Данные признаки формируются в статусном регистре.
Статусный регистр CCR предназначен для хранения признаков результатов вычислительных операций и содержит два поля признаков, основное {Ev,U,N,Z,V,C} и дополнительное {Evm,Um,Nm,Zm,Vm, Cm}. На основе основного поля формируются условия исполнения команд. Правила формирования признаков следующие:
1. При исполнении одной операции первого типа (AU,LU,FASU) ее признаки помещаются только в основное поле.
2. При исполнении одной операции второго типа (MS,SH,FMU) ее признаки помещаются в оба поля.
3. При одновременном выполнении двух вычислительных операций признаки, формируемые операцией первого типа, поступают в основное поле, признаки, формируемые операцией второго типа, - в дополнительное поле. 4. В тех случаях, когда операция первого типа заполняет только часть признаков основного поля, оставшиеся признаки формируются операцией второго типа.
Так как нам необходимо будет доказывать реализацию полученных алгоритмов, возникает проблема нотации. Для этого будут использоваться как ассемблерные листинги, так и некоторый псевдокод. Для начала приведем сведения по ассемблеру для DSP-ядра, необходимых для чтения этих листингов.
Текст программы для DSP-ядра состоит из последовательности инструкций. В теле одной инструкции может выполняться несколько команд (операций).
Команда (операция) - часть инструкции, определяющая действие того или иного операционного устройства DSP-ядра. При этом каждая инструкция должна быть расположена на отдельной строке.
Инструкция может содержать следующие поля: 1. Поле метки - поле задания символического имени. 2. Поле первой операции - в данном поле может содержаться команда DSP-ядра в мнемонической записи, директива ассемблера или вызов макрооперации 3. Поле аргументов первой операции - данное поле содержит набор аргументов, необходимых для первой операции. Аргументами могут являться регистры RF, регистры AGU, управляющие регистры и выражения. 4. Поле второй операции - вторая команда DSP-ядра (задается в соответствии с форматом 8).
Операция извлечения квадратного корня
В качестве особенности доказательства реализации отметим тот факт, что полученная нами оценка погрешности немного больше минимального возможного расстояния между результатом операции и точной серединой между двумя соседними значениями с плавающей точкой. Однако, используя теоретико-числовые методы, мы можем легко перебрать все такие возможные случаи и проверить их корректность путем непосредственного вычисления.
Рассмотрим числа вида c = (2ia + к + \/2)-2\ где = 0...2зс-1 - точные середины интервалов между двумя соседними числами с плавающей точкой в расширенном формате. Очевидно, что если с = 4х, где д: - число в формате расширенной точности, то с3 = X.
С другой стороны, с2 = (230 + к + \/2)2-22е 62. Обозначим (2 + к + \12)2=М. Тогда М = 260 + (2І] + \)-к + (2т + к2 +1/4), следовательно, расстояние между старшим значащим битом и младшим значащим битом много больше 31 и число вида М -22""62 не может быть представлено в формате расширенной точности. Далее рассмотрим два варианта.
Случай первый. 2"" Ы 2й1. Тогда М 22"а = (М 24") - 2гс" . Ближайшее число в формате расширенной точности может быть записано, как (т-2 3])-24, следовательно, М = 2i0-m + S + \/4 = 2}0-(230+F)+S+\/4, где F = 0...230-l. Упрощая, переходим к уравнению относительно целых чисел: к2 + 2м к + к + 230 = 2я F + S, что равносильно решению к2 + к = S(mod 230).
Случай второй. 20, М 262. Тогда M-22i 62 = (М-2 )-22 . Ближайшее число в формате расширенной точности может быть записано, как (m-2"!)-2 , следовательно, М = 23 -m + +l/4 = 231 -(23" + F) + S + \I4, где F = 0...230-\. Упрощая, переходим к уравнению относительно целых чисел: А:2+231- + А + 230 = 260 + 2Э- + ,чторавносильно решению 2+ + 230- 0(mod231).
Оба уравнения квадратные, следовательно, имеют не более двух корней. Подставляя различные целые значения параметра 5, мы переберем все возможные решения, что даст пам все значения наиболее близкие к точной середине интервалов и трудные для округления. Дальнейшие детали метода можно найти в работе [Согпеа98],
Для доказательства осталось проверить все случаи, трудные для округления, удовлетворяющие 7 и удостовериться, что алгоритм возвращает и для них корректно округленный результат.
Базовый вариант подпрограммы вычисления квадратного корня исполняется за 62 такта. 2.6. Элементарные функции
Вопрос о степени корректности различных реализаций элементарных функций до сих пор остается открытым. Стандарт IEEE-754 не определяет, каким требованиям они должны удовлетворять, по разным причинам. Одной из них является TMD - "table-maker dilemma", которая заключается в следующем: в общем случае неизвестно, какая именно точность потребуется для корректного (в том же смысле, что и базовые арифметические операции) округления результата вычислений. Отметим, что существует несколько способов решения этой проблемы, все они довольно обременительны как в плане скорости, так и в плане требуемой памяти, поэтому мы ограничимся исследованием того, насколько хорошо реализуемы таблично-алгоритмические методы [Tang91] на целевой платформе, В первую очередь нас будет интересовать гарантированная оценка погрешности результата, во вторую очередь - оценка времени исполнения.
Более подробную информацию по таблично-алгоритмическим методам для некоторых функций можно найти в работах [Tang89, Tang90, Tang92]. Информацию о работе с погрешностями при вычислениях по схеме Горнера можно найти в [Boldo02, ВоШоОЗ], вопросы нахождения наилучшего аппроксимирующего полинома затронуты в [МиПегОЗ].
Рассмотрим реализацию функции возведения двойки в степень - у = V. На первом этапе аргумент представляется в виде суммы: х = N + j/8 + r Здесь N, j - целые числа, причем / = 0...7, г - число с плавающей точкой в формате расширенной точности. Тогда 2,,% Т = {T Tf} + {hf%bl} + {mfmf } + Sh+ $я + Sr Г + Sp 2j! Строки 16-17; 2jl$ ={u;i.if} + S, S 2 il +2-" + 2 b0
Строка 18: Погрешность округления составляет не более половины единицы младшего разряда, следовательно, результирующая погрешность, измеряемая в ulps, составит не более чем и 2" + 2"9 0.502 nips, что и требовалось показать.
Заметим, что другие элементарные функции реализуются аналогичным способом. Иногда может потребоваться незначительная модификация формул для расчета погрешностей при вычислениях по схеме Горнера. Примером могут служить тригонометрические функции синус и косинус, аппроксимирующие полиномы для которых имеют вид Р(г2) . 2.7. Выводы
Наиболее оптимальным по скорости вариантом реализации сложения (вычитания) в формате расширенной точности является разбиение всех возможных случаев взаимного расположения операндов на четыре подмножества так, как показано в данной главе. В этом случае соответствующие последовательности инструкций эффективно используют возможности, предоставляемые DSP-ядром целевой архитектуры, такие, например, как условное исполнение в зависимости от признаков, формируемых вычислительными операциями.
Исследование итерационных алгоритмов с квадратичной сходимостью для вычисления алгебраических функций (на примерах деления и квадратного корня) показывает, что их использование для расширенного формата является оправданным по скоростным характеристикам. Нужно отметить, что с каждой итерацией сложность реализации (масштабирование, объем используемых регистров) и доказательства корректности возрастает. Поэтому для форматов большей разрядности целесообразно использовать последовательные алгоритмы.
Показано, что для вычисления элементарных трансцендентных функций в расширенном формате на DSP-ядре хорошо подходят таблично-алгоритмические методы. Выведенные в работе формулы для оценки погрешностей целочисленного варианта схемы Горнера (на примере функции у = 2") могут быть использованы и для других функций (иногда при условии их незначительной модификации).
Таким образом, в данной главе решена проблема вычислений в нестандартном формате расширенной точности, используемого на целевой платформе «Мультикор». Реализованы базовые математические подпрограммы, возвращающие результат с гарантированной точностью, что доказано в соответствующих утверждениях.
Сложение (вычитание)
Алгоритм обрабатывает ситуацию появления ненормализованной мантиссы, то есть, случай, когда 0.5 {и"20н2""2г/ 84г/4""ь} 1.0. В результате выполнения инструкций 1-3 имеем s = Т -{s s. s s }, где .у, = щ , s2 = иг + b (учитывается в инструкциях 6-7), s3 =иъ, sA = 2 и4.
В зависимости от признаков, формируемых инструкцией 4, получим следующие варианты округления:
Пусть и, 2JI. Тогда CARRY = 0, ZERO = 0, из чего следует, что последовательность инструкций 5-6 не выполняется, следовательно, возвращаемый результат равен 5 = 2е {щ2йи 52 +6}-2е {щ20и252} (1 + є), где относительная погрешность є = Sf{u 20u 2} 2 53 =0.5-ulp(.s), что и требуется по стандарту,
Далее, пусть иъ 2А. Тогда CARRY = \, ZERO = 0, из чего следует, что инструкции 5-6 не выполняются, следовательно, (,,-20-521 ,-20-52, . п-52 s = T- {и?и? + 8} = Г {u;10uf} - (1 + е). S = {щ щ]6}-2 52 -2 53 и относительная погрешность є = S/{u 20U2 n} -2"53 = -0.5 ulp(s), что и требуется по стандарту. Наконец, пусть щ = 231. Тогда CARRY = 1, ZERO = 1, и инструкция 5 выполняется. Заметим, ч і о после выполнения инструкции 5 ZERO = 1 тогда и только тогда, когда и4 = 0. В этом случае CARRY = Ъ и реализуется правило точного округления (к четному). В противном случае результат аналогичен предыдущему варианту.
Таким образом, мы показали, что во всех возможных случаях округление происходит корректно. Алгоритм округления нормализованного результата NORM: addl(2i] ,и3,и3) orlq(uitu4,S) lsrl.eq(\,u2,b) adcl(0,u2,u2) adcl{0,uvux) Лемма: Если результат сложения (вычитания) двух чисел с плавающей точкой представлен в нормализованном виде s = 2С -{щ щ и и 6}, то последовательность инструкций NORM возвращает мантиссу корректно округленного результата в формате двойной точности в виде {щ2йи22}. Относительная погрешность = S/{w 20wJ52} -2 я - -0.5-и/р(.?), что и требуется по стандарту. Таким образом, мы показали, что во всех возможных случаях округление происходит корректно.
Подпрограмма сложения (вычитания) в формате двойной точности обладает наиболее разветвленной структурой. Во-первых, две ветки по сложению или вычитанию мантисс, во-вторых, различные варианты их выравнивания -четыре варианта в случае сложения и шесть вариантов в случае вычитания. Все это можно определить, как базовые варианты исполнения подпрограммы.
Вариант исполнения, когда происходит потеря значащих разрядов, обозначенная, как Cancellation, целесообразно рассмотреть отдельно.
Таким образом, базовый вариант может занимать от 38 до 68 тактов. В случае появления денормализованного результата из конечных нормализованных операндов обработка может занимать от 57 до 76 тактов. Обработка ровно одного денормализованного операнда (второй операнд нормализованный и конечный) занимает до 28 тактов.
Обработка тех случаев, когда оба операнда являются ненормализованными, довольно проста и занимает 32 или 35 тактов, в зависимости от знаков операндов. Работа с бесконечностями и не-числами занимает от 20 до 24 тактов.
Реализация подпрограммы вычитания чисел в формате двойной точности опирается на тот факт, что арифметика, определяемая стандартом ГЕЕЕ-754 обладает следующим свойством: о(х у) = х{-у) для всех возможных операндов, а операция унарного минуса замкнута, то есть величина z--y принадлежит множеству представимых чисел с плавающей точкой тогда и только тогда, когда величина у сама принадлежит множеству чисел с плавающей точкой. Поэтому подпрограмма вычитания реализована в виде пролога к подпрограмме сложения и представляет собой 9-тактовую последовательность инструкций, манипулирующих со знаком и стековой структурой.
В памяти программ PRAM подпрограмма сложения (вычитания) занимает 372 слова.
Не вдаваясь в подробное рассмотрение различных вариантов аналогичных подпрограмм для ведущего ядра целевой архитектуры, отметим, что базовые варианты выполняются за 250-300 тактов, а обработка денормализованных чисел увеличивает время выполнения до 400-450 тактов. 3.4. Умножение
Из всех арифметических операций умножение, возможно, является самой простой, во всяком случае, в плане доказательства его корректности. Ключевые особенности реализации - представление операндов в виде слов со знаком для более простого выражения результата (с учетом того, что мы имеем только умножение со знаком, но не его беззнаковый вариант) и использование инструкции MACL (умножение с накоплением) целевой архитектуры для частичного ускорения распространения переноса от младших разрядов,
Анализ основания и разрядности
В представленной работе проведено исследование комплекса вопросов, связанных с проектированием и реализацией базовых математических подпрограмм на новой целевой платформе «Мультикор».
В результате работы были получены как реализации базовых подпрограмм для работы с плавающей точкой в формате расширенной точности, так и доказательства их корректности. Данный формат является специфическим для целевой платформы и используется в тех случаях, когда аппаратно реализованная арифметика одинарной точности оказывается недостаточной.
Сложение и вычитание чисел, представленных в данном формате, доказываются тремя утверждениями с использованием леммы об округлении, деление и квадратный корень - по одному утверждению на каждую операцию. Кроме того, исследована возможность реализации таблично-алгоритмических методов вычисления элементарных трансцендентных функций со строгой оценкой погрешности результата на примере функции возведения двойки в степень. Другие трансцендентные функции реализуются аналогично.
Строгое доказательство корректности возвращаемых результатов позволяет применять техники программного расширения точности.
Полученные в работе характеристики базовых арифметических подпрограмм могут быть использованы при решении того, какая именно реализация арифметики необходима для решения конкретного класса задач.
Также в работе исследованы вопросы реализации на целевой платформе стандартного формата двойной точности на вычисления с двоичной плавающей точкой. Возможность работы в данном формате позволяет использовать большое количество свободного программного обеспечения для приложений;, требующих высокоточной обработки данных. Реализация оформлена в виде библиотеки, получен соответствующий акт о внедрении.
Доказательства корректности алгоритмов сложения (вычитания) и умножения базируются на соответствующих утверждениях о правиле точного округления. Доказательство предложенного алгоритма деления включает в себя три леммы - о предварительном масштабировании с использованием арифметики одинарной точности, доказательство одной итерации деления по большому основанию и утверждение о корректности округления.
Алгоритм деления с предварительным масштабированием в формате одинарной точности позволяет наиболее полно использовать особенности ядра ЦОС целевой платформы и может с успехом применяться для вычисления любых алгебраических функций.
Предложенная в работе модификация таблично-алгоритмических методов реализации элементарных функций в формате двойной точности на основе CORDIC-алгоритмов позволяет сократить количество используемых для редукции констант.
Все полученные результаты сравнимы с результатами для архитектур аналогичного класса.
На примерах показано, как гарантированность результата выполнения базовых арифметических операций может быть использована для анализа и доказательства корректности высокоуровневых алгоритмов с плавающей точкой.
1. [Амелькин] Амелькин С.А., Захаров А.В., Хачумов В.М. Обобщенное расстояние Евклида-Махаланобиса и его свойства. // Информационные технологии и вычислительные системы. №4, 2006, с.40-44.
2. [Байков75]: Байков В. Д., Смолов В.Б. Аппаратурная реализация элементарных функций в ЦВМ. -Ленинград: Издательство ЛГУ, 1975.
3. [БибердорфОІ]: Бибердорф Э.А., Попова Н.И. Решение линейных систем с гарантированной оценкой точности результатов. Часть первая. Институт ядерной физики им. Г. И. Будкера СО РАН, Новосибирск, 2001.
4. [БурдаевОб]: М.Н. Бурдаев, А.Н. Виноградов, В.Ф. Заднепровский, А.В. Захаров, Е.П. Куршев, В.М. Хачумов, Институт программных систем РАН. Комплекс программно-инструментальных средств для создания интеллектуальных систем контроля и управления объектами аэрокосмического назначения. Авиакосмическое приборостроение, №8, 2006, с. 24-33.
5. [Ершов04]: Ершов А.Г., Кашеварова Т.П. Интервальная математическая библиотека, основанная на разложениях в ряды Чебышева и Тейлора. Сборник трудов Международной Конференции по Вычислительной Математике, с. 201-209, 2004.
6. [ЗахаровОЗ]: Захаров А.В., Хачумов В.М. Разрядно-параллельные вычисления в системах реальною времени // Математика, информатика: теория и практика. Сб. трудов, посвященный 10-летию Университета г. Переславля, под ред. Айламазяна А.К., издательство «Университет города Переславля», 2003, с. 97-104.
7. [ЗахаровОЗа]: Захаров А.В. Разрядно-параллельные вычислительные схемы для тригонометрических преобразований. Труды 3-го расширенного семинара «Использование методов искусственного интеллекта и высокопроизводительных вычислений в аэрокосмических исследованиях», М., Физматлит, 2003, с. 167-173.
8. [Захаров04]: Захаров А.В., Хачумов В.М. Алгоритмы CORDIC. Современное состояние и перспективы. Программные системы: теория и приложения, М.: Физматлит, май 2004, с. 353-372.
9. [ЗахаровОб]: Захаров А.В. Обзор поддержки плавающей точки в формате расширенной точности на платформе «Мультикор». // Труды XLII всероссийской конференции по проблемам математики, информатики, физики и химии. - М.: Издательство РУДН, 2006, с. 46-66.
10. [Каханер98]: Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение.: Пер. с англ. - М.: Мир, 1998. - 575 с.
11. [ТаненбаумОб]: Таненбаум Э. Архитектура компьютера. 4-е издание. - СПб.: Питер, 2006. - 699 с.
12. [УорренОЗ]: Уоррен Г. Алгоритмические трюки для программистов.: Пер. с англ. -М.: Издательский дом «Вильяме», 2003. - 288 с.
13. [Bertin04]: Berlin С. et al. A floating-point library for integer processors. Tech. report #5268, July 2004.
