Организация многопотоковой обработки данных с исключением аномалий при решении задач вычислительной геометрии

• Автор: Орлов, Дмитрий Александрович
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 161 с.

1. ПРОБЛЕМА ВЫЧИСЛИТЕЛЬНЫХ АНОМАЛИЙ В ЗАДАЧАХ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ.

1.1. Особенности задач вычислительной геометрии

1.2. Числа с плавающей запятой как источник ошибок округления

1.2.1. Стандарт

1.2.2. Недостатки вычислений с использованием формата чисел с плавающей занятой.

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

1.3.1. Пример возникновения вычислительной аномалии

1.3.2. Пример получения результата, противоречащего законам геометрии Евклида

1.4. Способы снижения влияния ошибок округления на результаты алгоритмов.

1.5. Вычисления повышенной точности

1.6. Существующие реализации вычислений повышенной точности

1.7. Постановка задачи исследования
2. РАЗРАБОТКА И ОБОСНОВАНИЕ ПРИНЦИПОВ ИСКЛЮЧЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ АНОМАЛИЙ
2.1. Анализ причин возникновения вычислительных аномалий.
2.1.1. Определения и допущения, необходимые для исследования причин возникновения вычислительных аномалий
2.1.2. Формализация понятия вычислительная аномалия
2.1.3. Понятие топологической целостности данных.
2.2. Исследование существующих реализаций алгоритмов вычислительной геометрии на подверженность вычислительным аномалиям на примере библиотек обнаружения столкновений.
2.2.1. Разработка методики тестирования алгоритмов вычислительной геометрии на подверженность вычислительным аномалиям
2.2.2. Обоснование выбора исследуемой задачи.
2.2.3. Применение разработанной методики для алгоритмов обнаружения столкновений .
2.2.4. Эксперимент по проверке библиотек обнаружения столкновений на подверженность вычислительным аномалиям
2.3. Методы исключения вычислительных аномалий путм изменения типа вычислений.
2.3.1. Определения
2.3.2. Подходы к реализации вычислений с ослаблением влияния ошибок округления .
2.3.3. Оценка скорости вычислений с ослаблением влияния ошибок округления
2.4. Разработка метода оценки достоверности результата вычислений
2.4.1. Постановка задачи разработай.
2.4.2. Разработка алгоритмов вычислений с автовалидацией
2.4.3. Разработка алгоритма оценки достоверности результата.
2.5. Уточнение исследуемого класса задач.
2.5.1. Оценка необходимой мкости памяти для представления результата вычислений с исключением ошибок округления
2.5.2. Область эффективного применения разработанных алгоритмов.
Выводы.
3. РАЗРАБОТКА МЕТОДОВ ОРГАНИЗАЦИИ МНОГОПОТОКОВЫХ ВЫЧИСЛЕНИЙ С ОСЛАБЛЕНИЕМ ВЛИЯНИЯ ОШИБОК ОКРУГЛЕНИЯ
3.1. Анализ возможных подходов к организации многопотоковых вычислений с ослаблением влияния ошибок округления
3.2. Организация вычислений с ослаблением влияния ошибок округления на многоядерных СРЦ.
3.2.1. Основные особенности организации вычислений с ослаблением влияния ошибок округления.
3.2.2. Представление графа истории вычислений.
3.2.3. Абстракция алгоритмов вычислений с ослаблением влияния ошибок округления
3.2.4. Выбор способа представления данных и реализации вычислений с исключением ошибок округления
3.2.5. Особенности организации вычислений с ослаблением влияния ошибок округления на многоядерных СРП
3.3. Организация вычислений с ослаблением влияния ошибок округления на СР
3.3.1. Схема организации вычислений с ослаблением влияния ошибок округления на вРи
3.3.2. Особенности реализации вычислений с исключением ошибок округления на ОР1 .
3.4. Реализация вычислений в знакоразрядной системе счисления
3.4.1. Понятие знакоразрядной системы счисления.
3.4.2. Особенности реализации арифметических операций в знакоразрядной системе счисления
3.5. Реализация вычислений в многомодульной системе
3.5.1. Понятие модулярной арифметики
3.5.2. Особенности реализации арифметических операций над числами, представленными в многомодульной системе.
3.5.3. Алгоритм определения знака числа, представленного в многомодульной системе счисления
Выводы.
4. ЭКСПЕРИМЕНТАЛЬНАЯ РЕАЛИЗАЦИЯ СРЕДСТВ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ С ОСЛАБЛЕНИЕМ ВЛИЯНИЯ ОШИБОК ОКРУГЛЕНИЯ ДЛЯ ПАРАЛЛЕЛЬНЫХ АРХИТЕКТУР.
4.1. Разработка средств организации вычислений с ослаблением влияния ошибок округления для многоядерных СРи архитектуры х
4.1.1. Постановка задачи разработки
4.1.2. Разработка структуры классов библиотеки.
4.1.3. Применение библиотеки вычислений с ослаблением влияния ошибок округления для реализации алгоритмов вычислительной геометрии на примере тестовых задач.
4.2. Разработка средств организации вычислений с ослаблением влияния ошибок округления для СРи архитектуры СВЛ
4.2.1. Особенности аппаратного устройства С1ЮА
4.2.2. Программная модель С1ЮЛ и расширения языка С.
4.2.3. Реализация средств организации вычислений с ослаблением влияния ошибок округления для СРи архитектуры С1ЮА.
4.2.4 Особенности реализации необходимых типов вычислений для СР архитектуры С1ЮА
4.2.5 Исследования скорости вычислений с исключением ошибок округления на РИ архитектуры С1ЮА
4.3. Внедрение в учебный процесс постановка лабораторной работы
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЕ 1. ОПИСАНИЯ КЛАССОВ БИБЛИОТЕКИ ИСКЛЮЧЕНИЯ
ВЫЧИСЛИТЕЛЬНЫХ АНОМАЛИЙ, РАЗРАБОТАННОЙ ДЛЯ АРХИТЕКТУРЫ
ПРИЛОЖЕНИЕ 2. ОПИСАНИЯ КЛАССОВ БИБЛИОТЕКИ ИСКЛЮЧЕНИЯ
ВЫЧИСЛИТЕЛЬНЫХ АНОМАЛИЙ, РАЗРАБОТАННОЙ ДЛЯ АРХИТЕКТУРЫ ИУЮЛ
ПРИЛОЖЕНИЕ 3. АЛГОРИТМЫ ТЕСТОВЫХ ЗАДАЧ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ
ПРИЛОЖЕНИЕ 4. ОПИСАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ ПО КУРСУ
КОМПЬЮ ТЕРНЫЕ ТЕХНОЛОГИИ В НАУКЕ И ОБРАЗОВАНИИ
ВВЕДЕНИЕ


Во второй главе проводится исследование механизмов возникновения вычислительных аномалий, экспериментально обосновывается необходимость исключения вычислительных аномалий, вводится необходимый понятийный аппарат, разрабатываются принципы организации вычислений с ослаблением влияния ошибок округления, определяется область эффективного применения вычислений с ослаблением влияния ошибок округления и проводится уточнение исследуемого класса задач. Третья глава посвящена разработке методов организации многопоточных вычислений с исключением вычислительных аномалий для многоядерных СРи и для 7Р. Четвртая глава посвящена разработке средств организации многопоточных вычислений с исключением вычислительных аномалий для многоядерных СР и для ОРи на примере совместимых СР и СгРС архитектуры СийА что необходимо для экспериментального подтверждения разработанных алгоритмов. Проводится экспериментальное исследование разработанных средств. Проект 2. Развитие научного потенциала высшей школы годы мероприятие 2. Проведение фундаментальных исследований в области естественных, технических и гуманитарных наук. Научнометодическое обеспечение развития инфраструктуры вузовской науки раздел 2. Проведение фундаментальных исследований в области естественных, технических и гуманитарных наук подраздел 2. Проведение фундаментальных исследований в области технических наук Государственный контракт П Программные модели и системы планирования распределнных вычислений. Информатика, Математика в рамках мероприятия 1. Программы, выполняемому в рамках мероприятия 1. Проведение научных исследований научными группами под руководством докторов наук, мероприятия 1. Проведение научных исследований научными группами под руководством докторов наук и кандидатов наук направления 1 Стимулирование закрепления молодежи в сфере науки, образования и высоких технологий федеральной целевой программы Научные и научнопедагогические кадры инновационной России на годы. Грант НШ9 Планирование масштабных вычислений и управление ресурсами распределенных вычислительных сред. Совет по грантам Президента Российской Федерации на право получения средств для государственной поддержки ведущих научных школ Российской Федерации. Государственный контракт . Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования федеральной целевой научнотехнической про1раммы Исследования и разработки по приоритетным направлениям развития науки и техники на годы. Вычислительная геометрия раздел дискретной математики, в котором рассматриваются алгоритмы решения геометрических задач 8, 9. Примеры решаемых задач построение триангуляции, построение выпуклой оболочки, булевы операции над тврдыми телами, определение взаимного расположения геометрических объектов. Вычислительная геометрия активно использует как методы теории графов, так и методы аналитической геометрии. Алгоритмы решения задач вычислительной геометрии используются в компьютерной графике как статической , так и реального времени тренажрные системы, компьютерные шры, геоинформационных системах, компьютерном зрении, численном моделировании. При реализации алгоритмов вычислительной геометрии необходимо учитывать особенности вычислительного устройства, на котором будут запущены алгоритмы, прежде всего, особенности представления чисел. Чаще всего в существующих вычислительных системах числа представляются в формате с плавающей запятой. Это означает, что в большинстве случаев, как числа, так и результаты операций над ними не могут быть представлены точно, что является причиной появления ошибок округления. В некоторых случаях эти ошибки приводят к серьзному искажению результата и даже к зацикливанию алгоритма 1. Отличие алгоритмов вычислительной геометрии от прочих алгоритмов дискретной математики состоит в том, что числовые данные например, координаты точек задают топологическую информацию, т. Это прежде всего, информация об ориентации троек точек для двумерного пространства или четврок для трхмерного.