авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 | 3 |

Методы вычислений с гарантированной точностью на платформе мультикор

-- [ Страница 1 ] --

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

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

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

Специальность 05.13.11

Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

на соискание ученой степени

кандидата технических наук

Москва - 2007

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

Научный руководитель доктор технических наук, профессор Хачумов Вячеслав Михайлович
Официальные оппоненты    доктор физико-математических наук, профессор Осипов Геннадий Семенович кандидат технических наук, доцент Гагарин Андрей Петрович
Ведущая организация    Институт проблем управления РАН    

Защита состоится 18 мая 2007 г. в 14 часов 00 минут на заседании диссертационного совета Д.002.084.01 в Институте программных систем РАН

по адресу: 152020, Ярославская область, г. Переславль-Залесский, м. Ботик.

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

Автореферат разослан 14 апреля 2007 г.

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

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

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

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

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

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

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





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

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

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

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

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

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

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

Цели и задачи работы

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

Для достижения данной цели выделяются следующие направления исследований.

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

Методы исследования

Для проведения исследований были использованы:

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

Научная новизна

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

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

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

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

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

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

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

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

Апробация

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

  • Конференция «Авиация и космонавтика-2003», ноябрь 2003, МАИ, г. Москва.
  • 3-й расширенный семинар «Использование методов искусственного интеллекта и высокопроизводительных вычислений в аэрокосмических исследованиях», ноябрь 2003, г. Переславль-Залесский, ИПС РАН.
  • Конференция «Программные системы: теория и приложения», май 2004, г. Переславль-Залесский, ИПС РАН.
  • XLI всероссийская конференция по проблемам математики, информатики, физики и химии в секции «Программные системы», 18-22 апреля 2005, РУДН, г. Москва.
  • XLII всероссийская конференция по проблемам математики, информатики, физики и химии в секции «Программные системы», 17-21 апреля 2006, РУДН, г. Москва.

Структура и объем работы

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

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

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

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

Возможность реализации сложных математических вычислений на встраиваемых системах с небольшим энергопотреблением и сокращенной системой команд - относительно новая область исследований. К архитектурам данного класса относится и «Мультикор» - новая перспективная отечественная серия сигнальных микроконтроллеров. Микросхемы данной серии (1892ВМ3Т (MC-12) и 1892ВМ2Т (MC-24)), - это однокристальные программируемые многопроцессорные «системы на кристалле». Область их применения включает в себя локацию и гидроакустику, связь, сигнальную обработку, системы промышленного контроля, системы управления с использованием адаптивных методов, обработку звука и изображений, а также высокоточную обработку данных для малогабаритных и встраиваемых систем. В качестве основного процессора используется RISC-подобное ядро с архитектурой MIPS32; под его управлением работают один или более DSP-акселераторов. Система инструкций DSP-ядра ориентирована на высокопроизводительную параллельную обработку данных. Типичным для такой обработки является объединение нескольких независимых инструкций в одну параллельно исполняющуюся связку, в рамках которой может исполняться до двух вычислительных операций в сочетании с одной или двумя пересылками данных. Кроме того, поддерживается условное исполнение команд, что позволяет сократить количество программных ветвлений. Подробная характеристика архитектуры «Мультикор» приводится в разделе 1.2.

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

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

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

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

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

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

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

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

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

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

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



Pages:   || 2 | 3 |
 



Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

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