Введение к работе
Актуальность темы исследования. В современных вычислительных устройствах практически достигнут предел роста тактовой частоты. Это повлекло за собой качественные изменения в направлении развития вычислительной техники. Рост производительности вычислительных систем достигается в настоящее время, прежде всего, путём увеличения количества исполнительных устройств. На таких системах для достижения наибольшего быстродействия необходима организация вычислений с учётом возможности распараллеливания решаемой задачи.
Для пользователей широко доступны два типа параллельных вычислительных устройств: многоядерные центральные процессоры и графические процессоры. Эти типы вычислительных устройств поддерживают многопотоковые вычисления.
Одним из широко распространённых в различных областях науки и техники классов задач, для решения которых используются многопотоковые вычисления, являются задачи вычислительной геометрии. Особенностью алгоритмов решения таких задач является их чувствительность к ошибкам округления, как при задании входных данных, так и внутри самого алгоритма. В то же время, практически во всех реализациях атгоритмов вычислительной геометрии вещественные числа представляются в формате с плавающей запятой. При выполнении арифметических операций над числами, представленными в таком формате, возникают ошибки округления. Вследствие этого возможно получение результатов, качественно отличающихся от истинных. Подобные ситуации назовём вычислительными аномалиями.
Таким образом, задача организации многопотоковых вычислений с исключением вычислительных аномалий является актуальной.
Целью работы является разработка методов и программных средств организации вычислений с исключением вычислительных аномалий для многоядерных центральных процессоров и для графических процессоров. Основные задачи
Исследовать механизм возникновения вычислительных аномалий и методы их исключения.
Разработать методику определения подверженности реализаций алгоритма вычислительным аномалиям.
Разработать методы организации вычислений с исключением вычислительных аномалий для многоядерных центральных процессоров и для графических процессоров.
Реализовать разработанные методы в виде инструментальных средств организации вычислений.
Объект исследования; многопотоковые вычислительные архитектуры и
организация на них решения задач вычислительной геометрии. ^
4 Предмет исследования: принципы обеспечения достоверности вычислений для параллельных вычислительных архитектур на примере решения задач вычислительной геометрии.
Методы исследования. При выполнении работы применяются методы теории параллельного программирования, вычислительной математики, теории алгоритмов, натурный эксперимент.
Научная новизна определяется получением следующих результатов:
Предложен понятийный аппарат, необходимый для разработки методов исключения вычислительных аномалий, в частности, формализовано понятие «вычислительная аномалия».
Разработан алгоритм определения достоверности результатов вычислений.
3 Ря.зпяботана методика оппеделекия подверженности реализации алгоритма вычислительным аномалиям. На её основе разработан метод тестирования реализаций алгоритмов обнаружения столкновений.
Определена область эффективного применения вычислений с ослаблением влияния ошибок округления с целью исключения вычислительных аномалий (как для многоядерных центральных процессоров, так и для графических процессоров).
Разработаны методы организации вычислений с ослаблением влияния ошибок округления для многоядерных центральных процессоров и графических процессоров. Разработанные методы реализованы в виде программных средств для многоядерных центральных процессоров архитектуры х86 и графических процессоров архитектуры Nvidia CUDA.
Достоверность результатов диссертационной работы подтверждается совпадением предсказанных теоретически результатов, с результатами эксперимента и сопоставлением с результатами, опубликованными в научной литературе.
Практическая значимость работы состоит в следующем:
Экспериментально подтверждена возможность исключения вычислительных аномалий в алгоритмах вычислительной геометрии.
Разработаны методы и программные средства организации вычислений с исключением вычислительных аномалий для многоядерных центральных процессоров архитектуры х86 и графических процессоров архитектуры Nvidia CUDA.
Экспериментально подтверждена возможность генерации данных, для которых в реализациях алгоритмов вычислительной геометрии, использующих вычисления с плавающей запятой, возникает вычислительная аномалия.
Исследования, представленные в данной диссертационной работе, поддержаны следующими грантами:
Проект 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
Четвёртая Международная конференция «Параллельные вычисления и проблемы управления» РАСО!2008. Москва, 27-29 октября 2008 г., ИЛУ РАН
Международная научно-техническая конференция «Информационные средства и технологии». Москва, 16-18 октября 2007 г., МЭИ (ТУ)
Международная научно-техническая конференция «Информационные средства и технологии». Москва, 21-23 октября 2008 г., МЭИ (ТУ)
XVII Международная научно-техническая конференция «Информационные
средства и технологии». Москва, 20-22 октября 2008 г., МЭИ (ТУ)
Тринадцатая Международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» Москва, 2007 г., МЭИ (ТУ)
Публикации. Результаты данной работы отражены в 8 печатных публикациях.
Структура и объём диссертационной работы. Диссертационная работа состоит из введения, четырёх глав, библиографического списка и четырёх приложений. Она изложена на 118 страницах, основного машинописного текста, содержит 16 рисунков, 13 таблиц, включает библиографию из 45 наименований. Общий объем диссертации равен 159 страницам.
