Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

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

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

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Шаповалов Олег Владимирович. Методы и средства сокращения времени реализации параллельных программ для многопроцессорных вычислительных систем с общей памятью: диссертация ... кандидата Технических наук: 05.13.11 / Шаповалов Олег Владимирович;[Место защиты: Южный федеральный университет].- Ростов-на-Дону, 2016

Содержание к диссертации

Введение

1. Обзор средств разработки параллельных программ для систем с общей памятью 15

1.1. Особенности разработки параллельных программ для систем с общей памятью 15

1.2. Технологии параллельного программирования для систем с общей памятью 16

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

1.3.2. Отладка параллельных программ 19

1.3.3. Зависимости по данным 20

1.3.4. Тестирование корректности и производительности

1.3.5 Балансировка нагрузки 22

1.3.6 Выбор технологии параллельного программирования 22

1.4. Обзор инструментов разработки параллельных программ для систем с общей

памятью 24

1.4.1. Среда программирования SMP superscalar 24

1.4.2. Интерфейс Performance API 25

1.4.3. Инструмент для анализа и оптимизации двоичных кодов MAQAO 28

1.4.4. Инструмент анализа производительности Periscope 30

1.4.5. Инструментальная утилита OPARI2 31

1.4.6. Профилировщик Scalasca 32

1.5. Обзор автоматических и автоматизированных систем для создания параллельных программ 33

1.5.1. Среда разработки параллельных программ DVM-система 33

1.5.2. Среда автоматической разработки параллельных программ OpenTS 35

1.5.3. Система программирования mpC 38

1.5.4. Среда для автоматизации разработки MPI программ PARUS 41

1.5.5. Оптимизирующая распараллеливающая система 43

1.6. Метрики и законы параллельного программирования 46

1.6.1. Базовые метрики параллельного программирования 46

1.6.2. Закон Амдала 47

1.6.3. Закон Густавсона-Барсиса 48

1.6.4. Закон Сан-Ная 49

1.6.5. Метрика Карп-Флатта 50

1.6.6. Метрика изоэффективности 50

1.7. Выводы 51

2. Разработка методов и алгоритмов выбора технологии параллельного программирования для систем с общей памятью 54

2.1. Метрика реальной эффективности 54

2.2. Метод выбора технологии параллельного программирования 54

2.3. Алгоритм классификации циклов 60

2.4. Выводы 68

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

3.1. Структура библиотеки 71

3.2. Шаблоны распараллеливания 73

3.3. Реализация шаблона «разделяй и властвуй» 76

3.3.1. Пример распараллеливания для шаблона «разделяй и властвуй» 78

3.4. Реализация шаблона, основанного на задачах 81

3.4.1. Пример распараллеливания для шаблона, основанного на задачах 86

3.5. Выводы 88

4. Применение библиотеки для разработки параллельных программ 91

4.1. Распараллеливание пакета многотельной динамики ФРУНД 91

4.2. Моделирование динамики электронного потока 95

4.3 Распараллеливание решения прямой задачи электростатики 99

4.4. Разработка ядра геометрического моделирования 103

4.4.1. Построение тела по траектории 104

4.4.2. Операция деформации тел 107

4.4.3. Верификация топологии и геометрии моделей 108

4.4.4. Операция построения тела по набору сечений 110

4.4.5. Построение дискового сглаживания 114

4.4.6. Выводы по распараллеливанию ядра геометрического моделирования 117

4.5. Выводы 119

Заключение 121

Список использованных источников 123

Приложение а. Акты внедрения результатов диссертации

Введение к работе

Актуальность работы. В настоящее время суперкомпьютерные вычисления играют все большую роль в самых разных областях науки. Прогнозирование погоды, моделирование физических, химических, биологических и других процессов немыслимы без суперкомпьютеров. При этом многие вычислительные задачи наиболее эффективно решаются с помощью многопроцессорных вычислительных систем с общей памятью (SMP - Symmetric Multiprocessing). Популярность систем с общей памятью подтверждается ростом и развитием количества стандартов и технологий (OpenMP, C++ AMP, TBB, OpenCL, Cilk Plus и др.), ориентированных на параллельное программирование таких систем. Разные технологии обладают разными особенностями и характеристиками.

Разработки в области параллельного программирования для многопроцессорных вычислительных систем с общей памятью ведутся и в нашей стране. В ИПМ им. М.В. Келдыша РАН разрабатывают DVM-систему, которая может использоваться при распараллеливании программ для систем с общей и распределенной памятью; в МГУ ведется работа над средой автоматической разработки параллельных программ OpenTS, которая работает с общей памятью; на кафедре алгебры и дискретной математики института математики, механики и компьютерных наук им. И.И. Воровича ЮФУ под руководством Б.Я. Штейнберга разрабатывают Оптимизирующую распараллеливающую систему, которая автоматизирует процесс разработки программ для систем с общей и распределенной памятью. Но указанные разработки не учитывают, что в зависимости от текущего контекста программы для одного и того же участка программного кода эффективными могут быть разные технологии параллельного программирования. Критерием эффективности распараллеливания является время решения прикладной задачи при тех же требованиях к аппаратному и программному обеспечению. Поскольку эффективность применения технологий зависит от характеристик решаемой задачи, возникает проблема выбора технологии распараллеливания при решении конкретной прикладной задачи.

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

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

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

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

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

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

Для достижения указанной цели необходимо решить следующие задачи исследования:

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

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

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

провести анализ эффективности разработанных инструментов и моделей при решении прикладных задач.

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

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

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

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

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

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

Положения, выдвигаемые для защиты:

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

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

Результаты, выдвигаемые для защиты:

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

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

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

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

Практическая значимость и внедрение. Применение библиотеки параллельных шаблонов Parallel Technology Library (PTL) позволило добиться сокращения времени решения прикладных задач на системах с общей памятью от 5 до 20 процентов. В частности, при решении задач электростатики время работы

было сокращено на 5%, при решении задачи теплопроводности в пакете инженерного анализа ФРУНД (формирование и решение уравнений нелинейной динамики) – 7% (подтверждается актом о внедрении), а при решении ряда задач сплайновой геометрии в проекте российского геометрического ядра (НИОКР «Разработка библиотеки алгоритмов генерации базовых тел, построения тел по сечениям, по сетке направляющих кривых и проверки корректности модели для ядра 3-мерного моделирования», договор № 152М-2- ВЛГ-12/1 от 02.04.2012 г.) среднее сокращение времени работы составило 10%, а максимальное на отдельных задачах – до 20% (подтверждается актом о внедрении).

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

Разработанная программная библиотека внедрена в учебный процесс для проведения лабораторного практикума по курсу «Параллельное программирования» на кафедре ЭВМ и систем ВолгГТУ, что подтверждается актом о внедрении.

Апробация результатов работы. Основные положения и материалы диссертационной работы докладывались и обсуждались на международных, всероссийских и региональных научно-технических конференциях: Облачные вычисления. Образование. Исследования. Разработки. - Москва, ИСП РАН; VII всерос. межвуз. конф. мол. уч. – Санкт-Петербург, ИТМО; Высокопроизводительные параллельные вычисления на кластерных системах (HPC-2010) – Пермь, ПГТУ; Параллельные вычислительные технологии (ПаВТ’2011) – Москва, МГУ; Информационные технологии в образовании, технике и медицине 2009 – Волгоград, ВолгГТУ; Научный сервис в сети интернет – 2011, 2012, 2013 – Абрау-Дюрсо; IMSD 2010 – Finland, Lappeenranta.

Результаты диссертационной работы были частично использованы при проведении мастер-классов по параллельному программированию на международной конференции ПАВТ-2015 в Уральском федеральном университете и на международной Летней Суперкомпьютерной Академии в МГУ в 2015 г.

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

Публикации. По теме диссертации опубликовано 10 печатных работ, в том числе 5 публикаций в журналах, рекомендованных ВАК, 1 публикация в журнале, проиндексированном Scopus, и 2 публикации в иностранных источниках, получено 1 свидетельство об официальной регистрации программы для ЭВМ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 137 страниц, в том числе 33 рисунка, 16 таблиц и список литературы из 89 наименований.

Тестирование корректности и производительности

К наиболее известным и эффективным технологиям параллельного программирования для систем с общей памятью, стоит отнести OpenMP, TBB, Cilk Plus, Boost Threads и PPL.

OpenMP реализует модель, в которой основной поток выполнения программы создает набор потоков с последующим разделением задачи между ними. Если количество процессоров в вычислительной системе больше одного, то потоки будут выполняться параллельно. Основной конструкцией для распараллеливания является прагма компилятора, которая является комментарием при компиляции в последовательном режиме. Важным преимуществом данной технологии является простота перехода от параллельного программного кода к последовательному. Управление количеством создаваемых потоков осуществляется или самой программой с помощью вызова библиотечных функций, или с помощью переменных окружения. OpenMP позволяет создавать потоки (директива parallel); распределять работу между потоками (директивы DO/for и section); управлять работой с разделяемыми данными (выражения shared и private); синхронизировать обращения к данным потоков (директивы critical, atomic и barrier). Intel Threading Building Blocks (TBB) — библиотека высокоуровневых шаблонов, упрощающая работы с базовыми реализациями потоков, такими как Windows threads или POSIX Threads. Использование TBB позволяет работать с графом зависимостей задач, который может быть задан программистом, строиться автоматически или автоматически модифицироваться в зависимости от алгоритма и заданного графа задач. С помощью этого подхода осуществляется программирование параллельных алгоритмов на высоком уровне с минимальной зависимостью от архитектуры вычислительной системы.

Среди шаблонов классов и функций библиотеки TBB можно выделить: параллельные алгоритмы: scan, while, for, do, pipeline, sort, reduce; потокобезопасные контейнеры: хеш-таблица, вектор, очередь; распределители памяти; механизмы синхронизации доступа к разделяемым данным.

Intel Cilk Plus является расширением языка С++ для простого создания параллельных программ для систем с общей памятью. Для описания параллелизма Cilk Plus использует 3 ключевых слова: cilk_for – для распараллеливания циклов с фиксированным числом итераций, cilk_spawn – для выполнения операции в отдельном потоке, выполняющемся параллельно с основным и cilk_sync – для синхронизации всех параллельных потоков, запущенных с помощью функции cilk_spawn. Также Intel Cilk Plus включает в себя набор шаблонов (reducers) – «преобразователей данных», которые позволяют программисту распараллеливать типовые ситуации, не беспокоясь за корректность работы с разделяемыми данными.

Третьим важным моментом в Cilk Plus является возможность векторизации кода. Для этого есть 2 варианта: использование прагмы #simd, позволяющей векторизовать вычисления в цикле и использование особой нотации массивов, позволяющей векторизовать отдельные операции над элементами массивов.

Boost.Thread – это библиотека, позволяющая работать с потоками. Также она позволяет синхронизировать доступ к разделяемым данным. Библиотека Boost.Thread помимо стандартных с C++11 функций работы с потоками, такими как создание, выполнение потоков и т.д., предоставляет ряд дополнительных возможностей, таких как отмена выполнения потока, специальные примитивы синхронизации и др.

Библиотека параллельных шаблонов Parallel Patterns Library (PPL) предоставляет простую модель разработки параллельных программ. PPL поднимает уровень абстракции параллельного кода, предоставляя программисту возможность использования базовых, потокобезопасных алгоритмов и структур данных в параллельном режиме. К основным возможностям PPL относятся: параллелизм задач – механизм, который является надстройкой над потоком задач Windows для выполнения единиц работы (задач) в параллельном режиме; набор параллельных алгоритмов – распараллеленные алгоритмы решения типовых задач; параллельные потокобезопасные объекты и контейнеры.

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

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

После алгоритмической оптимизации решается задача оптимизации последовательного кода. Эта задача не отличается от оптимизации обычных последовательных задач, за исключением большего влияния на общую скорость программы. Например, если доля последовательного кода составляла 0,1, а после оптимизации – 0,05, то максимальное ускорение, которое можно достигнуть, возросло с 10 до 20 раз. Для последовательной программы такая оптимизация дала бы прирост скорости работы 5%.

Хотя сам процесс оптимизации не отличается от оптимизации обычных последовательных задач, инструменты для анализа производительности параллельных программ имеют свои особенности [7, 47]. В первую очередь они должны корректно работать с многопоточными или многопроцессными программами, а также поддерживать работу с различными сопроцессорами и ускорителями. К наиболее известным таким инструментам можно отнести KCachegrind, Marmot/MUST, PAPI, Periscope, Scalasca, TAU, Vampir/VampirTrace. Отдельно выделяют инструменты, работающие с графическими процессорами, такие как TAU performance system, Vampir, PAPI.

Метод выбора технологии параллельного программирования

Схема преобразования программы для использования нескольких технологий распараллеливания показана на рисунке 2.6. Программист с помощью теоретических исследований или по данным профилирования определяет циклы и другие участки программы, время работы которых можно сократить за счет распараллеливания, и помечает их с помощью специальных конструкций. Для каждого цикла программист определяет набор технологий, с помощью которых будет проводиться распараллеливание. Для технологий OpenMP, TBB, Cilk Plus, Boost Threads и PPL распараллеливание автоматизировано, для других технологий распараллеливание остается задачей пользователя. За счет автоматизации распараллеливания для вышеперечисленных технологий, а также за счет автоматизации сравнения технологий сокращается время разработки параллельной программы. Анализ времени выполнения для разных технологий был также автоматизирован.

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

Был разработан алгоритм, позволяющий сократить время выполнения программы путем выбора технологии распараллеливания на этапе выполнения программы. Математически можно представить эту задачу в следующей формулировке: где g(Nj, NumTech) - время работы цикла с количеством итераций Nj с использованием технологии распараллеливания, обозначенной номером NumTechj, i = l..m– список вызовов данного цикла во время выполнения распараллеливаемой программы (как правило, неизвестен до запуска программы), NumTechj є [0, n — 1] - переменная, обозначающая используемую технологию распараллеливания, данный параметр может варьироваться, п - общее число используемых технологий распараллеливания. Целью представленной задачей оптимизации является минимизация времени работы программы за счет оптимального выбора технологии распараллеливания (номера NumTech) для каждого запуска распараллеленного цикла. Задача сводится к нахождению зависимости N - NumTech, что является задачей классификации. Если количество технологий параллельного программирования больше двух, то данная задача является задачей многоклассовой классификации. Для повышения качества работы классификатора данные текущего запуска распараллеленного кода сразу же необходимо добавлять в статистику для использования при классификации последующих запусков распараллеленного кода. Таким образом, необходимо разработать алгоритм адаптивной классификации. Номер технологии распараллеливания будет являться функцией от количества итераций запускаемого цикла и данных статистики: NumTecht = NumTech(Ni, Н), (2.4) где Nj - количество итераций цикла, Н - статистические данные по ранним запускам распараллеливаемого кода. Статистические данные представляют собой тройки «количество итераций цикла»-«номер технологии»-«время работы», в таблице 2.1 показан пример статистических данных.

Среди известных алгоритмов классификации нет такого, который бы полностью подходил для решения поставленной задачи. Наиболее близкие задачи решают следующие алгоритмы: алгоритм ближайших соседей [5], который относится к простым метрическим классификаторам (объект для классификации классифицируется так же, как и ближайшие к нему объекты из набора обучения); а также множественная логит-регрессия [6], которая обобщает логистическую регрессию на случай наличия нескольких классов для классификации (происходит аппроксимация данных с помощью логистической кривой).

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

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

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

Расчет вероятностей осуществляется согласно следующим принципам: при отсутствии статистических данных вероятности выбора разных технологий распараллеливания одинаковы и равны 1/n; - чем больше время работы с указанной технологией, тем меньше вероятность ее выбора (берутся статистические данные для данной технологии с наиболее близким размером цикла), при известной сложности алгоритма в О нотации время будет пересчитываться на единицу сложности; - степень влияния статистических данных разных технологий различна и зависит от расстояния от запрашиваемого размера цикла N до размера цикла в —R2 статистических данных, вероятность пропорциональна величине е к, где R = к - относительное расстояние между требуемым размером цикла и размером N цикла в ближайших статистических данных; - для более равномерного набора статистики по времени работы разных технологий (особенно это важно при малом количестве статистики) используется критерий количества статистических данных: чем больше статистических данных у данной технологии, тем меньше вероятность ее выбора. Исходя из описания, получим:

Реализация шаблона «разделяй и властвуй»

Под шаблоном «разделяй и властвуй» в данном случае понимается шаблон, когда поток программы, осуществляющий последовательное выполнение, расщепляется на несколько, и порожденные потоки вместе с главным выполняют параллельно некоторую задачу (чаще всего описываемую циклом), а затем соединяются снова в один поток. Объектом распараллеливания в данном случае является цикл for с фиксированным числом итераций. Пользователь создает на основе тела цикла обертку над функцией, подходящую по формату для одного из двух возможных вариантов: std::function void (int) (интерфейс IAloneFunction) или std::function double (int, int) (интерфейс IManyFunction). Первый вариант используется для технологий параллельного программирования, которые впрямую или косвенно создают свои обертки над телом циклом, чтобы выполнять разные итерации цикла параллельно (Intel TBB, OpenMP, Boost Threads, Cilk Plus, PPL и т.д.). В том случае, когда архитектура многопроцессорной системы не позволяет использовать перечисленные технологии (графические ускорители, Xeon Phi, ПЛИС), или пользователь хочет сам организовать распределение витков цикла по процессорам, используется интерфейс IManyFunction. Пользователю необходимо произвести распараллеливание всего цикла и замерить время работы цикла. Поскольку разные технологии параллельного программирования используют свой синтаксис для описания параллелизма в программе, был проведен обзор реализаций распараллеливания циклов в основных технологиях достижения параллелизма для систем с общей памятью (табл. 3.1).

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

В качестве примера использования шаблона «разделяй и властвуй» рассмотрим задачу распараллеливания умножения квадратных матриц с использованием технологий CUDA и PPL [8, 35].

Пример 1. Реализация умножения на видеокарте Для добавления этой реализации к сравнению с другими технологиями распараллеливания, необходимо создать функцию, которая измерит время данной реализации, это показано в примере 2. Далее добавляются технологии распараллеливания для систем с общей памятью, и отдельный список технологии, распараллеливающие диапазон итераций. Также необходимо добавить обработчик для цикла, для этого необходимо указать файла для сохранения данных о запусках. Затем запустить умножение матриц, а для технологий для систем с общей памятью создать лямбда-функцию для выполнения i-той итерации цикла. Также необходимо указать диапазон итераций. Для более точной работы алгоритма классификации необходимо указать сложность алгоритма в О-нотации, в данном случае для умножения матриц она составляет 0(N3). // для расчета умножения матриц на графическом процессоре создается //обертка, которая вызывает необходимые функции и измеряет время auto gpuMul = [amas,hmas,resmas](int st, int fin) - double {

Эффективность работы алгоритма классификации будет выше при большем количестве запусков распараллеленного цикла. При условии отсутствия статистики, алгоритм адаптивной классификации сначала будет выполнять распараллеливание с разными технологиями (в данном случае, последовательный запуск, технологии PPL и CUDA), независимо от остальных параметров. Также можно определить критерий, когда обучение будет завершено: это произойдет, когда будут определены границы эффективной работы все технологий (в данном случае, до размера цикла около 600 будет эффективно использование технологии PPL, больше – технологии CUDA).

Для параллельной реализации алгоритма, описанного направленным ациклическим графом, реализованы разные способы в зависимости от используемых технологий параллельного программирования. Для OpenMP реализация шаблона, основанного на задачах, возможна с помощью omp sections (пример 3) или omp tasks (пример 4). Эти реализации почти эквивалентны между собой, и, как правило, нет особой разницы по времени работы, какую их них использовать. Но для лучшей читаемости программного кода лучше использовать механизм задач (omp tasks). #pragma omp parallel sections { #pragma omp section {

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

В рамках проекта по созданию отечественного геометрического ядра РГК (российское геометрическое ядро), одним из основных участников которого были сотрудники ВолгГТУ (НИОКР «Разработка библиотеки алгоритмов генерации базовых тел, построения тел по сечениям, по сетке направляющих кривых и проверки корректности модели для ядра 3-мерного моделирования», договор № 152М-2- ВЛГ-12/1 от 02.04.2012 г.), одной из приоритетных задач ставилось эффективное распараллеливание используемых алгоритмов.

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

В российском геометрическом ядре модели описываются с помощью методов граничного представления (B-Rep, Boundary Representation) [68]. Параметры модели описываются с помощью геометрических объектов, а также топологии связей между геометрическими объектами (точки, кривые, поверхности). Для обеспечения высокой скорости работы пакета геометрического моделирования, а также для высокой точности расчетов используются разные виды описания геометрических объектов. Для кривых используются или аналитические типы данных (прямая, окружность, эллипс и т.д.) или NURBS-кривые (NURBS - Non-uniform rational B-spline, широко распространенный вид сплайнов, используемый для генерации и представления кривых и поверхностей [80-81]). Для описания поверхностей также используются как аналитические (плоскость, цилиндр, конус и т.д.), так и NURBS-поверхности.

Расчет сложных моделей может занимать существенное время, и далее будут рассмотрены несколько примеров распараллеливания в ядре RGK [44]. Данные методы и алгоритмы часто используются и являются базовыми для геометрического ядра.

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

Движение окружности по гладкой траектории, заданной nurbs-кривой Опишем более детально алгоритм работы генератора: 1. Для вычисления набора систем координат минимального вращения, двигающихся по траектории необходимо проанализировать длины векторов второй производной для разных участков траектории, учитывая заданные законы вращения и масштабирования. По результатам анализа вычисляются точки для построения систем координат минимального вращения, количество точек должно быть достаточно для обеспечения необходимой точности. Поскольку системы координат строятся одна за другой, данная операция не может быть распараллелена. 2. Предварительный этап для дальнейшего распараллеливания. Нужен, чтобы построение поверхностей можно было выполнить параллельно. Для этого необходимо построить контура в начальном положении для каждого ребра траектории. 3. Затем можно параллельно построить поверхности граней, интерполируя контура, движущиеся по ребру траектории. Сложность данного этапа зависит от сложности кривых в траектории и контуре, а также заданные законы вращения и масштабирования. 4. Сборка топологии результирующего тела – последовательная процедура сборки результирующего тела.

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

В результате было распараллелено построение поверхностей. В качестве технологий распараллеливания были выбраны Visual C++ 2010 OpenMP, TBB 4.1, Cilk Plus 1.05. Для распараллеливания были использован шаблон «разделяй и властвуй». Эффективность проведенного распараллеливания оценивалась с помощью стресс-тестов с использованием сложных кривых в контурах и траекториях (табл. 4.4). Сложность контуров и траекторий зависит от количества рёбер и сложности кривых в ребрах, сложность кривых определяется количеством точек контрольного полигона и степенью кривой. Сложность построения итоговых поверхностей пропорциональна сложности образующих их кривых (контуров и траекторий). Усложнение кривых контуров дает вычислительную нагрузку на иные распараллеленные циклы по сравнению с кривыми траекторий. Количество ребер также влияет на время работы. Результаты тестирования с использованием данных моделей приведены в таблице 4.5.