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

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

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

Pages:   || 2 | 3 |

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

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

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

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

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

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

автореферат

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

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

Москва – 2010

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

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

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

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

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

кандидат технических наук, доцент, Лешихина Ирина Евгеньевна

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

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

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

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

направлять по адресу: 111250, г. Москва, Красноказарменная ул. д. 14, Ученый

совет МЭИ (ТУ).

Автореферат разослан « » мая 2010.

Ученый секретарь

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

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

Общая характеристика работы

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

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

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





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

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

Основные задачи

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

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

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

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

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

  1. Предложен понятийный аппарат, необходимый для разработки методов исключения вычислительных аномалий, в частности, формализовано понятие «вычислительная аномалия».
  2. Разработан алгоритм определения достоверности результатов вычислений.
  3. Разработана методика определения подверженности реализации алгоритма вычислительным аномалиям. На её основе разработан метод тестирования реализаций алгоритмов обнаружения столкновений.
  4. Определена область эффективного применения вычислений с ослаблением влияния ошибок округления с целью исключения вычислительных аномалий (как для многоядерных центральных процессоров, так и для графических процессоров).
  5. Разработаны методы организации вычислений с ослаблением влияния ошибок округления для многоядерных центральных процессоров и графических процессоров. Разработанные методы реализованы в виде программных средств для многоядерных центральных процессоров архитектуры x86 и графических процессоров архитектуры Nvidia CUDA.

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

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

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

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

  • Проект 2.1.2/6718 "Стратегии организации и поддержки крупномасштабных вычислений в распределенных средах" аналитической ведомственной целевой программы "Развитие научного потенциала высшей школы (2009-2010 годы)" мероприятие: 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

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

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

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

Четвёртая Международная конференция «Параллельные вычисления и проблемы управления» PACO’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. предварительная обработка геометрических данных.

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

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

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

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

  • библиотеки вычислений повышенной точности (MPFR);
  • библиотеки, ориентированные на работу с геометрическими данными (LEDA, CGAL).

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

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

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

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

Исследован следующий механизм возникновения вычислительных аномалий. Пусть в исследуемом алгоритме необходимо вычислить значение y=f(X). Если f(x) непрерывна в точке X и в достаточно большой её окрестности, то ошибки округления оказывают незначительное влияние на результат вычисления f(X) (график слева на рис. 1). Если f(x) имеет точки разрыва вблизи точки X, то ошибки округления могут привести к результату, не имеющему ничего общего с истинным (график справа на рис. 1), то есть, к возникновению вычислительной аномалии. На рис. 1: X – истинное значение аргумента функции, X* – вычисленное значение аргумента функции, искажённое под влиянием ошибок округления.

 Влияние ошибок округления в случаях-0

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

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

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

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

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

Недостоверный результат вычисления функции f(x) – это значение f(X*) для вычисленного значения аргумента , имеющего оценку ошибки округления (удовлетворяющую условию ), такую, что в интервал входит хотя бы один разрыв функции f(x).

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

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

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

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

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

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

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



Pages:   || 2 | 3 |
 

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







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

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