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

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

Орлов Дмитрий Александрович

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

Специальность 05.13.15 - Вычислительные машины, комплексы и компьютерные сети

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

•С

Москва-2010 Ггх (0 '

по

л

004604545

Работа выполнена на кафедре Вычислительных машин, систем и сетей Московского энергетического института (технического университета).

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

доктор технических наук, профессор, Дзегеленок Игорь Игоревич Официальные оппоненты:

доктор технических наук, профессор, Кораблин Юрий Прокофьевич кандидат технических наук, доцент, Лешихина Ирина Евгеньевна

Ведущая организация: ГОУВПО Московский государственный университет приборостроения и информатики

Защита состоится «25» июня 2010 г. в 18 час. 00 мин. на заседании диссертационного совета Д 212.157.16 при Московском энергетическом институте (техническом университете) по адресу: 111250, г. Москва, ул. Красноказарменная, д.!3 (ауд. М-510).

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (технического университета).

Отзывы в двух экземплярах, заверенные печатью организации, просьба направлять по адресу: 111250, г. Москва, Красноказарменная ул. д. 14, Ученый совет МЭИ (ТУ).

Автореферат разослан «24 » мая 2010. Ученый секретарь

диссертационного совета Д 212.157.16

к. т. н., доцент Чернов С.А.

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

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

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

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

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

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

1. Исследовать механизм возникновения вычислительных аномалий и методы их исключения.

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

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

4. Реализовать разработанные методы в виде инструментальных средств организации вычислений.

Объект исследования; многопотоковые вычислительные архитектуры и

организация на них решения задач вычислительной геометрии.

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

Методы исследования. При выполнении работы применяются методы теории параллельного программирования, вычислительной математики, теории алгоритмов, натурный эксперимент.

Научная новизна определяется получением следующих результатов:

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

2. Разработан алгоритм определения достоверности результатов вычислений.

3 Разработана методика определения подверженности реализации алгоритма вычислительным аномалиям. На её основе разработан метод тестирования реализаций алгоритмов обнаружения столкновений.

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

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

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

Практическая значимость работы состоит в следующем:

1. Экспериментально подтверждена возможность исключения вычислительных аномалий в алгоритмах вычислительной геометрии.

2. Разработаны методы и программные средства организации вычислений с исключением вычислительных аномалий для многоядерных центральных процессоров архитектуры х86 и графических процессоров архитектуры Nvidia CUDA.

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

Исследования, представленные в данной диссертационной работе, поддержаны следующими грантами:

• Проект 2.1.2/6718 "Стратегии организации и поддержки крупномасштабных вычислений в распределенных средах" аналитической ведомственной целевой программы "Развитие научного потенциала высшей школы (20092010 годы)" мероприятие: 2. "Проведение фундаментальных исследований в области естественных, технических и гуманитарных наук. Научно-методическое обеспечение развития инфраструктуры вузовской науки" раздел: 2.1. "Проведение фундаментальных исследований в области естественных, технических и гуманитарных наук" подраздел: 2.1.2. "Проведение фундаментальных исследований в области технических наук"

• Государственный контракт П2227 "Программные модели и системы планирования распределённых вычислений". "Проведение поисковых научно-исследовательских работ по направлениям: "Механика", "Информатика", "Математика" в рамках мероприятия 1.2.1 Программы", пыпппняемгиму п пямтгяу меппппнятиа 1 2 1 "Ппгудрдриир НЕУЧНЫХ

.....-j - г---------- ---г---1--------- --------------^ ------J -

исследований научными группами под руководством докторов наук", мероприятия 1.2 "Проведение научных исследований научными группами под руководством докторов наук и кандидатов наук" направления 1 "Стимулирование закрепления молодежи в сфере науки, образования и высоких технологий" федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009 - 2013 годы.

• Грант НШ-7239.2010.9 "Планирование масштабных вычислений и управление ресурсами распределенных вычислительных сред". Совет по грантам Президента Российской Федерации на право получения средств для государственной поддержки ведущих научных школ Российской Федерации.

• Государственный контракт 02.442.11.7546 по приоритетным направлениям, выполняемых в рамках программного мероприятия 1.9 "Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования" федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы.

• Грант Президента РФ для молодых кандидатов наук: МК-65190.2010.9

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

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

International Conference on dependability of Computer Systems DepCOS -RELCOMEX 2008. Szklarska Poreba, Poland, 25 - 29 June 2008

International Conference on dependability of Computer Systems DepCOS -RELCOMEX 2009. Brunow, Poland, 30 June - 2 July 2009

Четвёртая Международная конференция «Параллельные вычисления и проблемы управления» РАСО!2008. Москва, 27-29 октября 2008 г., ИПУ РАН

XV Международная научно-техническая конференция «Информационные средства и технологии». Москва, 16-18 октября 2007 г., МЭИ (ТУ)

XVI Международная научно-техническая конференция «Информационные средства и технологии». Москва, 21-23 октября 2008 г., МЭИ (ТУ)

XVII Международная научно-техническая конференция «Информационные средства и технологии». Москва, 20-22 октября 2008 г., МЭИ (ТУ)

Тринадцатая Международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» Москва, 2007 г., МЭИ (ТУ)

Публикации. Результаты данной работы отражены в 8 печатных публикациях.

Структура и объём диссертационной работы. Диссертационная работа состоит из введения, четырёх глав, библиографического списка и четырёх приложений. Она изложена на 118 страницах, основного машинописного текста, содержит 16 рисунков, 13 таблиц, включает библиографию из 45 наименований. Общий объем диссертации равен 159 страницам.

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

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

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

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

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

- некорректное (нереалистичное) поведение движущихся объектов виртуальной реальности;

- явные дефекты изображения (артефакты), такие, как:

- разрывы в полигональных сетках трёхмерных моделей и ландшафтов;

- исчезновение объектов, или наоборот, появление нежелательных

объектов, вследствие неправильного определения их видимости; - дрожание анимации и другие;

- неверное определение наличия столкновений объектов.

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

- в общем случае, любое действительное число представляется с погрешностью;

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

- не всегда выполняются свойства арифметических операций (например, свойство ассоциативности операции сложения);

- наблюдается явление существенной потери значимости при вычитании двух близких чисел;

- наряду с обычным переполнением, возможно ещё и антипереполненис, то есть обнуление мантиссы при округлении результата, близкого к нулю;

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

Основными способами снижения влияния ошибок округления на результаты алгоритмов вычислительной геометрии, являются:

1) расширение разрядной сетки чисел;

2) использование проверки чисел на равенство с заданной точностью;

3) изменение порядка операций над числами;

4) использование заранее известной информации о расположении геометрических объектов;

5) отдельная обработка вырожденных и близких к ним случаев;

6) предварительная обработка геометрических данных.

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

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

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

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

- вычисления с исключением ошибок округления.

Существующие средства исключения вычислительных аномалий:

- библиотеки вычислений повышенной точности (МРП<)\

- библиотеки, ориентированные на работу с геометрическими данными

XV Международная научно-техническая конференция «Информационные средства и технологии». Москва, 16-18 октября 2007 г., МЭИ (ТУ)

XVI Международная научно-техническая конференция «Информационные средства и технологии». Москва, 21-23 октября 2008 г., МЭИ (ТУ)

XVII Международная научно-техническая конференция «Информационные средства и технологии». Москва, 20-22 октября 2008 г., МЭИ (ТУ)

Тринадцатая Международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» Москва, 2007 г., МЭИ (ТУ)

Публикации. Результаты данной работы отражены в 8 печатных публикациях.

Структура и объём диссертационной работы. Диссертационная работа состоит из введения, четырёх глав, библиографического списка и четырёх приложений. Она изложена на 118 страницах, основного машинописного текста, содержит 16 рисунков, 13 таблиц, включает библиографию из 45 наименований. Общий объем диссертации равен 159 страницам.

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

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

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

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

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

- некорректное (нереалистичное) поведение движущихся объектов виртуальной реальности;

- явные дефекты изображения (артефакты), такие, как:

- разрывы в полигональных сетках трёхмерных моделей и ландшафтов;

- исчезновение объектов, или наоборот, появление нежелательных

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

Если вычисленное значение аргумента X имеет оценку ошибки округления ЛАГ, такую, что выполняется следующее неравенство:

X'-АХйХ<Х' + АХ

(то есть истинное значение аргумента содержится в интервале X' ± АХ), то можно ввести понятие «недостоверный результат вычисления функции».

Недостоверный результат вычисления функции Дх) - это значение /{X) для вычисленного значения аргумента X', имеющего оценку ошибки округления АХ (удовлетворяющую условию X' -АХ<,Х <Х' + АХ), такую, что в интервал X' ± ДА' входит хотя бы один разрыв функции Дх).

Очевидно, что если /ГУ) является качественно неверным результатом, то оно будет являться недостоверным результатом. Поэтому справедливо следующее утверждение: отсутствие недостоверных результатов в процессе вычисления алгоритма означает отсутствие качественно неверных результатов.

Исходя из введённых выше допущений, понятие вычислительная аномалия определено как возникновение одной из следующих ситуаций:

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

- зацикливание реализации алгоритма.

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

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

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

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

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

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

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

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

nmriiartrrrt лтштглттатгтгя л ттттопптлтаа чоттгттлтт Ти г» тттх т>т ттттж/"» ттлтттхгт r> tinvтгтлнаттв»*

ULIl -mV<liVlUL/l Ь> iUlliUUlUUfVU ^Ull'llVIli l^VilUl ±JUX H1W1V1U1/1 W XlVlUUU IVIUIV1U

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

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

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

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

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

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

В данной работе в качестве вычислений с автовалидацией применены интервальные вычисления. Рассмотрено два способа представления числового интервала: представление границами и представление парой «число - оценка погрешности». Для второго варианта представления предложены формулы оценки погрешности арифметических операций, выполняемых на центральном процессоре архитектуры х86, при условии, что и число, и оценка его погрешности представлены числами с плавающей запятой. Указанные формулы представлены в таблице 1. В таблице 1 введены следующие обозначения: результат операции, подчёркнутой снизу, округляется с недостатком, результат операции, подчёркнутой сверху, округляется с избытком, а, Ъ - аргументы

и

операций. Да, АЬ - оценки погрешности для а и 6 соответственно. РЕ -значение флага неточного результата сопроцессора х87 (0, если при выполнении операции округление не произошло, иначе 1), с1 - вес младшего разряда мантиссы результата соответствующей операции.

Таблица 1

Оценки погрешности для арифметических операций

Операция Оценка погрешности

а+Ь Аа+АЬ+РЕ^/г)

а-Ь

а-Ь \а{АЬ+\Ь\-Аа+Аа-АЬ+РЕ^72)

-!-, а~2.Аа а Аа7<\а\Ц^а)^РЕ(с172)

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

- при выполнении операции деления или при определении знака числа интервал аргумента содержит число 0;

- при выполнении сравнения двух чисел пересечение их интервалов не пусто,

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

Рассмотрено два способа реализации обновления результата вычислений:

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

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

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

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

(а Ъ\

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

Рис 2. Граф истории вычислений для алгоритма вычисления определителя матрицы второго порядка

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

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

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

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

2) Создание двух тестовых реализаций алгоритма для выбранного частного случая исследуемой задачи: с использованием вычислений с плавающей запятой (реализация Л/) и с использованием вычислений с исключением ошибок округления (реализация Л^). Реализация Е/ необходима для оценки ошибок округления, т.к. оценивая ошибки округления, возникающие в реализации/?^ мы получаем косвенную оценку ошибок округления, возникающих в реализации ЯТ- Реализация Ке обладает следующим свойством: для всех наборов из множества наборов входных данных реализации результат реализации ЯЕ совпадает с истинным результатом алгоритма.

вычислений и указатели на аргументы этой операции;

- количество ссылок на данную вершину графа истории вычислений;

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

Условием запуска алгоритма обновления результата является получение недостоверного результата. Словесное описание алгоритма обновления результата операции:

1) если первый аргумент операции не требует обновления, перейти к п. 3;

2) выполнить обновление первого аргумента операции;

3) если операция унарная, перейти к п. 6

4) если второй аргумент операции не требует обновления, перейти к п. 6

5) выполнить обновление второго аргумента операции;

6) выполнить операцию при помощи вычислений с исключением ошибок

графа

истории вычислении.

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

Схема организации вычислений на многоядерных центральных процессорах представлена на рис. 3.

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

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

Архитектура графических процессоров имеет ряд ограничений по

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

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

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

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

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

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

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

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

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

- приближённое значение числа и оценку ошибки округления, т.е. объект вычислений с автовалидацией;

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

- код операции, результат которой хранится в данной вершине графа истории

вычислений и указатели на аргументы этой операции;

- количество ссылок на данную вершину графа истории вычислений;

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

Условием запуска алгоритма обновления результата является получение недостоверного результата. Словесное описание алгоритма обновления результата операции:

1) если первый аргумент операции не требует обновления, перейти к п. 3;

2) выполнить обновление первого аргумента операции;

3) если операция унарная, перейти к п. 6

4) если второй аргумент операции не требует обновления, перейти к п. 6

5) выполнить обновление второго аргумента операции;

6) выполнить операцию при помощи вычислений с исключением ошибок

лтт< 'утто тт ттгг улан г ттт тпт "лупипгтт л лЛпп^отт ттчп а» ттг г»о»1тттУ1тта гг»п Дл о * 1и1 А и и х ши^ш^и ил» 1 ч/ 1

истории вычислений.

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

Схема организации вычислений на многоядерных центральных процессорах представлена на рис. 3.

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

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

Архитектура графических процессоров имеет ряд ограничений по

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

гпло^11'1 '.члттI»1 тлI.' хэ.^огп ттттст пг»ттт. 1 тгIгст ктаи гтттгч^и-лггч нгтлто

- <. ~ - - г-----~ ------г- .....- > ~~ ж ■. ~ . -------

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

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

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

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

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

1) представление числа в знакоразрядной системе счисления;

2) представление числа в многомодульной системе счисления.

Схема организации вычислений с поразрядным параллелизмом показана на рис 5.

RAM GPU threads

С загрузка значения переменной из памяти

) преобразование переменной

/ ч вычисления (каждый поток выполняет один и тот же код)

( сравнение ипи определение знака

запись результата в память

у ' 1

Рис. 5. Схема организации вычислений с поразрядным параллелизмом

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

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

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

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

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

тчлпалллмлп «nrmn Ä л>гп ТТ г» ^т»йтт»т/м»<л»>л ll^Vl^WW^/VU ittiHA VJKIVJIJ'IV» l

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6. Реализованы алгоритмы оценки достоверности результата вычислений.

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

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

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

10.Создана экспериментальная программная реализация алгоритмов вычислений с ослаблением влияния ошибок округления для многоядерных центральных процессоров архитектуры х8б.

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

20 ^ СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Орлов, Д.А. Вычислительные аспекты построения распределеннь. систем виртуальной реальности [Текст] / И.И. Дзегелено.

B.Ю.Харитонов, Д.А. Орлов // Вестник Московского энергетическог института. - 2008. - №5. - С. 27-32. - М.: Издательский дом МЭИ, 2008.

2. Orlov, D.A. On opportunity of application of modular arithmetic for accurac improvement in positioning of virtual reality moving objects [Text] D.A. Orlov // Proceedings of International Conference on dependability о Computer Systems DepCOS - RELCOMEX 2008. Szklarska Poreba, Polan 25 - 29 June 2008. - pp. 414 - 421. - IEEE Computer Society, Los Alamito CA, USA, 2008.

3. Orlov, D.A. Application of computations with calculation error exclusion fo

/.nmnnMlnn л ГТо«|1 /ПА л. т Н О.^ллл/ИпМ л

wllipuiuuvu gwuulwu j UtgVllUUlU ^ i ^AIJ / LfiU. Vil WV II 1 lUW^UUl^O U

International Conference on dependability of Computer Systems DepCOS RELCOMEX 2009. Brunow, Poland, 30 June - 2 July 2009. - pp. 290 - 295. IEEE Computer Society, Los Alamitos, CA, USA, 2009.

4. Орлов, Д.А. Подход к организации распределенных вычислений дл согласованной визуализации движущихся объектов под управление удаленных пользователей [Текст] / И.И. Дзегеленок, В.Ю. Харитоно Д.А. Орлов // Труды четвёртой Международной конференцш «Параллельные вычисления и проблемы управления» РАСО'2008 Москва, 27-29 октября 2008 г. - С. 867-883. - М.: Институт пробле управления им. В.А. Трапезникова РАН, 2008. - 1570 с.

5. Орлов, Д.А. Повышение точности позиционирования движущихс объектов виртуальной реальности [Текст] / Д.А. Орлов // Труд международной научно-технической конференции «Информационны средства и технологии» Москва, 16-18 октября 2007 г. В 3 кн. Кн. 2.

C. 199-203. - М.: Полиграфический центр МЭИ (ТУ), 2007.

6. Орлов, Д.А. Применение вычислений с исключением ошибок округлен для реализации алгоритмов вычислительной геометрии [Текст] Д.А. Орлов // Труды XVI международной научно-техническо! конференции «Информационные средства и технологии». Москва, 21-2 октября 2008 г. В 3 кн. Кн. 2. - С. 147-150 - М.: Издательский дом МЭИ 2008.

7. Орлов, Д.А. Тестирование библиотек определения столкновений [Текст / Д.А. Орлов // Труды XVII международной научно-техническо конференции «Информационные средства и технологии». 20-22 октябр 2008 г. В 3 кн. Кн. 2. - С. 237-241. - М.: Издательский дом МЭИ, 2008.

8. Орлов, Д. А. Библиотека, реализующая вычисления в числах представленных в знакоразрядной форме [Текст] / Д.А. Орлов Ш.А. Оцоков // Радиоэлектроника, электротехника и энергетика Тринадцатая Междунар. науч.-техн. конф. студентов и аспирантов: Тез докл. В 3 кн. Кн. 1. - С. 415-416. - М.: Издательский дом МЭИ, 2007.

Подписано в печать ¿loí-Юг. Зак. fJtO Тир. (ОС П.л. г, Ад' Полиграфический центр МЭИ (ТУ) Красноказарменная ул.,д.13

ВВЕДЕНИЕ.

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

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

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

1.2.1. Стандарт /£££754.

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. Организация вычислений с ослаблением влияния ошибок округления на многоядерных CPU.

3.2.1. Основные особенности организации вычислений с ослаблением влияния ошибок округления.

3.2.2. Представление графа истории вычислений.

3.2.3. Абстракция алгоритмов вычислений с ослаблением влияния ошибок округления

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

3.2.5. Особенности организации вычислений с ослаблением влияния ошибок округления на многоядерных CPU.

3.3. Организация вычислений с ослаблением влияния ошибок округления на GPU.

3.3.1. Схема организации вычислений с ослаблением влияния ошибок округления на GPU.

3.3.2. Особенности реализации вычислений с исключением ошибок округления на GPU

3.4. Реализация вычислений в знакоразрядной системе счисления.

3.4.1. Понятие знакоразрядной системы счисления.

3.4.2. Особенности реализации арифметических операций в знакоразрядной системе счисления.

3.5. Реализация вычислений в многомодульной системе.

3.5.1. Понятие модулярной арифметики.

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

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

Выводы.

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

4.1. Разработка средств организации вычислений с ослаблением влияния ошибок округления для многоядерных CPU архитектуры х86.

4.1.1. Постановка задачи разработки.

4.1.2. Разработка структуры классов библиотеки.

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

4.2. Разработка средств организации вычислений с ослаблением влияния ошибок округления для GPU архитектуры CUDA.

4.2.1. Особенности аппаратного устройства CUDA.

4.2.2. Программная модель CUDA и расширения языка С++.

4.2.3. Реализация средств организации вычислений с ослаблением влияния ошибок округления для GPU архитектуры CUDA.

4.2.4 Особенности реализации необходимых типов вычислений для GPU архитектуры CUDA.

4.2.5 Исследования скорости вычислений с исключением ошибок округления на GPU архитектуры CUDA.

4.3. Внедрение в учебный процесс: постановка лабораторной работы.

Выводы.

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

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

- многоядерные центральные процессоры (CPU);

- графические процессоры (GPU).

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

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

Многоядерные процессоры являются симметричными мультипро1{ессоралт (SMP), следовательно, имеют организацию MIMD (multiple instructions, multiple data — множество потоков команд, множество потоков данных). Из многоядерных процессоров наиболее распространены процессоры, ядра которых имеют архитектуру л:86.

Графические процессоры (GPU) имеют организацию, схожую с SIMD {single instructions, multiple data — один поток команд, множество потоков данных), поскольку предназначаются, прежде всего, для визуализации трёхмерных сцен. Задача визуализации трёхмерных сцен обладает высоким параллелизмом по данным, поскольку для вычисления цвета для всех пикселей используется один и тот же алгоритм.

С развитием GPU появилась возможность использовать их и для других задач. Применение GPU для решения задач, непосредственно с компьютерной графикой не связанных, получило название GP GPU (General Purpose computation on GPU) — вычисления общего назначения на графических процессорах.

Так как GPU имеют организацию, схожую с SIMD, потоки, выполняющиеся на GPU, имеют один и тот же код, что позволяет GPU выполнять одновременно значительно большее количество потоков, чем CPU. Из графических процессоров с поддержкой GP GPU наиболее динамично развиваются GPU, имеющие архитектуру CUDA (Compute Unified Device Architecture - архитектура унифицированного вычислительного устройства).

Одним из классов задач, для решения которых широко применяются многопоточные вычисления, являются задачи вычислительной геометрии. Алгоритмы решения задач вычислительной геометрии находят широкое применение в различных областях науки и техники: в компьютерной графике (как статической — CAD, так и реального времени — тренажёрные системы, системы виртуальной реальности, компьютерные игры); для построения геометрических моделей объектов в CAD; в геоинформационных системах; в задачах машинного зрения («computer vision);

- в численном моделировании (в частности, при построении геометрических сеток для решения задачи одним из численных методов).

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

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

- некорректное (нереалистичное) поведение движущихся объектов виртуальной реальности;

- явные дефекты изображения (артефакты), такие, как:

- разрывы в полигональных сетках трёхмерных моделей и ландшафтов;

- исчезновение, или наоборот, появление нежелательных объектов, вследствие неправильного определения их видимости;

- дрожание анимации и другие [2];

- неверное определение наличия столкновений объектов.

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

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

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

В связи с этим, особого внимания заслуживает метод, состоящий в изменении способа представления чисел таким образом, что для любых значений аргументов (представимых в таком формате), возможно точное представление результатов арифметических операций. Такой тип вычислений назовём вычислениями с исключением ошибок округления [3 — 6]. Примерами подобных вычислений могут служить вычисления в рациональных числах и символьные вычисления. Однако вычисления с исключением ошибок округления требуют значительно большего времени и ёмкости памяти, по сравнению с вычислениями с плавающей запятой.

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

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

Таким образом, задача разработки методов и средств организации многопоточных вычислений с исключением вычислительных аномалий является актуальной. Разработку таких методов необходимо провести как для многоядерных центральных процессоров, так и для графических процессоров, поскольку эти типы вычислительных устройств распространены наиболее широко. Разработку средств организации многопоточных вычислений с исключением вычислительных аномалий целесообразно проводить на примере многоядерных процессоров, ядра которых имеют архитектуру х86, и графических процессорах, имеющих архитектуру CUD А, как наиболее широко используемые [7].

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

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

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

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

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

Конкретно, новыми результатами являются:

- понятийный аппарат, необходимый для разработки методов исключения вычислительных аномалий, в частности, формализация понятия «вычислительная аномалия»;

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

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

- определение области эффективного применения вычислений с исключением ошибок округления и вычислений' с ослаблением влияния ошибок округления для исключения вычислительных аномалий;

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

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

- Экспериментальное подтверждение возможности исключения вычислительных аномалий в алгоритмах вычислительной геометрии.

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

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

Диссертационная работа состоит из четырёх глав:

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

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

Третья глава посвящена разработке методов организации многопоточных вычислений с исключением вычислительных аномалий для многоядерных CPU и для GPU,

Четвёртая глава посвящена разработке средств организации многопоточных вычислений с исключением вычислительных аномалий для многоядерных CPU и для GPU на примере х86-совместимых CPU и GPU архитектуры CUDA (что необходимо для экспериментального подтверждения разработанных алгоритмов). Проводится экспериментальное исследование разработанных средств.

Диссертационные исследования были поддержаны следующими грантами:

- Проект 2.1.2/6718 "Стратегии организации и поддержки крупномасштабных вычислений в распределенных средах" аналитической ведомственной целевой программы "Развитие научного потенциала высшей школы (20092010 годы)" мероприятие: 2. "Проведение фундаментальных исследований в области естественных, технических и гуманитарных наук. Научно-методическое обеспечение развития инфраструктуры вузовской науки" раздел: 2.1. "Проведение фундаментальных исследований в области естественных, технических и гуманитарных наук" подраздел: 2.1.2. "Проведение фундаментальных исследований в области технических наук"

- Государственный контракт П2227 "Программные модели и системы планирования распределённых вычислений". "Проведение поисковых научно-исследовательских работ по направлениям: "Механика", "Информатика", "Математика" в рамках мероприятия 1.2.1 Программы", выполняемому в рамках мероприятия 1.2.1 "Проведение научных исследований научными группами под руководством докторов наук", мероприятия 1.2 "Проведение научных исследований научными группами под руководством докторов наук и кандидатов наук" направления 1 "Стимулирование закрепления молодежи в сфере науки, образования и высоких технологий" федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009 - 2013 годы.

- Грант НШ-7239.2010.9 "Планирование масштабных вычислений и управление ресурсами распределенных вычислительных сред". Совет по грантам Президента Российской Федерации на право получения средств для государственной поддержки ведущих научных школ Российской Федерации.

- Государственный контракт 02.442.11.7546 по приоритетным направлениям, выполняемых в рамках программного мероприятия 1.9 "Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования" федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы.

- Грант Президента РФ для молодых кандидатов наук: МК-65190.2010.9

Выводы

1) Разработанные средства организации вычислений с ослаблением влияния ошибок округления для многоядерных CP U дают возможность исключать вычислительные аномалии только за счёт изменения типа числовых данных в исходном коде алгоритма, без других модификаций исходного кода алгоритма;

2) Разработанные средства организации вычислений с ослаблением влияния ошибок округления для GPU позволяют исключить вычислительные аномалии при вычислении предикатов. Для этого необходимы легко осуществимые модификации исходного кода программы, определённые в параграфе 4.2.3;

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. L. Kettner, К. Mehlhorn, S. Pion, S. Schirra, and C. Yap Classroom Examples of Robustness Problems in Geometric Computations // ESA, LNCS. 2004. Vol. 3221. P. 702—713 http://www.mpi-inf.mpg.de/~kettner/pub/nonrobustcgta06.pdf

2. David H. Eberly 3D Game Engine Design Morgann-Kaufmann Publishers, 2004

3. Грегори P., Кришнамурти E. Безошибочные вычисления. Методы и приложения: Пер. с англ. М.: Мир, 1988 - 208 е., ил.

4. Дзегелёнок И.И., Оцоков Ш.А. Экспериментальное исследование модели безошибочных вычислений на ПМК-сети КУРС 2000 // Сб. трудов международной научной конференции «Информационные средства и технологии» М.:МЭИ (ТУ), 2003 г. с. 103-106.

5. Орлов Д.А., Оцоков Ш.А. О возможности применения «безошибочных» вычислений для решения задачи Коши // Сб. трудов Междунар. Науч-техн. Конф. «Информационные средства и технологии» Том 2, М.:МЭИ (ТУ), 2006г. с. 207-210

6. Орлов Д.А., Дзегеленок И.И., Харитонов В.Ю. Вычислительные аспекты построения распределенных систем виртуальной реальности // Вестник Московского Энергетического института, №5, 2008 г. — М.: Издательский дом МЭИ, 2008 С. 27-32.

7. Боресков А. В., Харламов А. А. Основы работы с технологией CUDA. -М.: ДМК Пресс, 2010 г. 232 стр.

8. Роджерс Д. Алгоритмические основы машинной графики, 1989

9. Е.А. Никулин Компьютерная геометрия и алгоритмы машинной графики

10. Мейсон By, Джеки Нейдер, Том Девис, Дейв Шрайнер. OpenGL. Официальное руководство программиста: Пер. с англ. СПб: ООО «ДиаСофтЮп», 2002 -592 е., ил.11. Стандарт IEEE 754-1985

11. Зубков С.В. Assembler для DOS, Windows и Unix. М.: ДМК, 1999. -640 е., ил.13. Стандарт IEEE 754-2008

12. Nicholas J. Higham Accuracy and Stability of Numerical Algorithms // Society for Industrial and Applied Mathematics, 1996

13. David Goldberg What Every Computer Scientist Should Know About Floating-Point Arithmetic // ACM Computing Surveys, 23(3):413-413, September 1991.

14. NVIDIA CUDA Programming Guide Version 3.0, Nvidia Corporation, 2010

15. Synergistic Processor Unit Instruction Set Architecture Version 1.2, IBM Systems and Technology Group, 2007

16. Peter Freese Solving Accuracy Problems in Large World Coordinates // «Game Programming Gems 4», Charles River Media, 2004, c. 157-170

17. Christer Ericson Real-Time Collision Detection, The Morgan Kaufmann, 2005

18. Les A. Piegl Knowledge-guided Computation for Robust CAD // Computer-Aided Design & Applications. 2005.Vol.2. No.5 .p.685-695.

19. Сайт разработчиков библиотеки MPFR www.mpfr.org

20. К. A. Wahid, V. S. Dimitrov and G. A. Jullien Error-Free Arithmetic for Discrete Wavelet Transforms using Algebraic Integers // Proceedings of the 16th IEEE Symposium on Computer Arithmetic (ARITH-16'03), Page: 238, 2003

21. Kurt Melhorn, Stefan Naher LEDA A Platform for Combinatorial and Geometric Computing, http://www.mpi-inf.mpg.de/%7Emehlhorn/LEDAbook.html

22. Сайт разработчиков библиотеки LEDA http://www.algorithmic-solutions.com/leda/index.htm

23. CGAL Computational Geometry Algorithms Library, www.cgal.org

24. ESOLID Library for Exact Solid Modeling http://research.cs.tamu.edu/keyser/geom/esolid/

25. Wild Magic Real-Time 3D Graphics Engine, www.geometrictools.com

26. Kokichi Sugihara Robust Geometric Computation Based on Topological Consistency

27. David Conger Physics Modeling For Game Developers, 2004

28. Сайт библиотеки SOLID http://www.dtecta.com/

29. Сайт библиотеки ColDet http://www.photoneffect.com/coldet/

30. Сайт библиотеки OPCODE http://www.codercorner.com/Opcode.htm

31. Сайт библиотеки COLLIDE http://www.cs.unc.edu/~geom/collide/index.shtml

32. Библиотека интервальных вычислений Boost.Interval http://www.boost.org/doc/libs/l370/libs/numeric/interval/doc/interval.htm

33. Скворцов А.В. Триангуляция Делоне и её применение

34. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн Алгоритмы. Построение и анализ. Издание 2-е // М.: Вильяме, 2007 г., 1296 стр.

35. Б. Страуструп Язык программирования С++, 3-е изд./Пер. с англ. СПб; М.: «Невский Диалект» - Издательство «БИНОМ», 1999г. - 991с., ил.

36. Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес Приёмы объектно-ориентированного проектирования. Паттерны проектирования // СПб: Питер, 2007 г., 366 стр.

37. Эндрюс Г.Р. Основы многопоточного, параллельного и распределённого программирования.: Пер. с англ. М.: Издательский дом «Вильяме», 2003. - 512с.: ил. - Парал. тит. англ.

38. Cyril Briquet Introduction to Convex Hull Applications