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

• Орлов, Дмитрий Александрович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Орлов, Дмитрий Александрович

ВВЕДЕНИЕ.

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 раз.

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

Список литературы диссертационного исследования кандидат технических наук Орлов, Дмитрий Александрович, 2010 год

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