Система упорядочивания и планирования исполнения шагов в библиотеке параллельного программирования Intel® Concurrent Collections (проектный аспект)

Предисловие

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

По причине собственного убеждения в том, что работу нельзя сдавать пока есть возможность сделать ее лучше, был упущен шанс первой публикации по проекту «Система упорядочивания и планирования шагов в библиотеке параллельного программирования Intel® Concurrent Collections». Поэтому описания алгоритмов будут сокращены, что позволит уделить больше внимания организации работы в нашей команде. За более подробным описанием алгоритмов рассмотренных в работе можно обратиться к статье Данила Михайловича Скачкова[1].

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

Введение

Работа относится к области многопоточного программирования с использованием асинхронной модели взаимодействия потоков. Проект был нацелен на увеличение производительности библиотеки параллельного программирования Intel® Concurrent Collections.

Intel® Concurrent Collections (CnC)

Библиотека Intel® Concurrent Collections позволяет упростить процесс создания многопоточного приложения. Основная идея заключается в разделении программного кода на слабо зависимые блоки (шаги) и выполнении их в нескольких потоках. Между шагами могут быть зависимости двух видов. Во-первых, это зависимости по событиям (тэгам), так каждый шаг после завершения может установить ряд тэгов и шаги, подписанные на них, будут добавлены в очередь исполнения. Один шаг может быть подписан на коллекцию тэгов, тогда он будет вызван при срабатывании каждого из них. Второй тип зависимостей – это зависимости по данным. Если очередь исполнения дошла до шага, данные для которого еще не готовы, то происходит его перемещение в конец очереди (перезапуск). Таким образом, библиотека разрешает все зависимости между шагами и старается исполнять их параллельно, что сильно упрощает процесс создания многопоточного приложения.

Проблемы текущей реализации

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

Цели и задачи проекта

Основная цель проекта – увеличить производительность многопоточного приложения CnC на основе предварительного сбора информации о его внутренних зависимостях.

Для достижения этой цели были поставлены следующие задачи:

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

Второстепенной целью стояло наметить путь будущей он-лайн планировки (без необходимости производить профилирующий запуск).

Тесты

В качестве основного теста использовалось приложение, реализующее алгоритм разложения Холецкого[2]. Приложение запускалось с одними и теми же параметрами но с разным ограничением на количество используемых ядер (от 1 до 8, для каждого примененного алгоритма).

Основная часть

Организация работы

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

Фактические роли участников проекта (на взгляд автора), были следующими:

Илья Сергеевич Черный – роль заказчика, руководителя проекта со стороны клиента.

Команда исполнителей:

Николай Владимирович Куртов – роль эксперта предметной области и руководителя проекта со стороны исполнителя.

Данил Михайлович Скачков – роль разработчика и ответственного за профилирование многопоточных приложений.

Николай Александрович Алемасов - роль разработчика и ответственного за алгоритмы планирования и запуска расписаний.

Александр Владимирович Макеев - роль разработчика и ответственного за выделение интерфейсов ввода/вывода и интеграцию со сторонними приложениями.

Отчетность

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

Инфраструктура

В качестве среды разработки была выбрана Microsoft® Visual Studio. Потому что, во-первых, с этой средой все члены команды были в достаточной мере знакомы. Во-вторых, в ней уже было разработано тестовое приложение (преобразование Холецкого), а работа с разными средами разработки или перенос проекта в другую среду мог вызвать временные затраты, чего в рамках школы нужно было категорически избегать.

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

Коммуникация с руководителями проекта происходила по средствам электронной почты, с использованием специально заведенных на сервисе gmail.com служебных e-mail-ов. Служебные email-ы были заведены по шаблону ss.<Name>.<Surname>@gmail.com (ss – Summer School).

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

Ход работы

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

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

Рис.1. Схема зависимостей между задачами через выделенные интерфейсы

Задачи разделились на следующие группы:

Профилировка и построение направленного графа шагов

Профилировка состояла в замере временных интервалов и идентификации шагов. Для этого использовались временные метки библиотеки TBB[3]

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

Алгоритмы планирования и их применение к тестовому приложению

Некоторые из существующих алгоритмов планирования были изучены и реализованы как отдельные классы, зависящие от графа шагов. В них вошли алгоритмы, использующие: метод сетевого планирования[4] и построение ярусно-параллельной формы графа[5].

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

Отображение графа шагов и диаграммы загруженности ядер

Для визуализации промежуточных и результирующих данных было решено использовать стороннее программное обеспечение. Все данные, нуждающиеся в визуализации, могли быть представлены в виде графов, поэтому выбранное приложение это open-source визуализатор графа. В качестве такового было выбрано приложение Tulip[6], как наиболее простое по формату представления данных и управлению просмотром графа.

Диаграмма загрузки ядер была получена из результатов профилировки, т.е. временных периодов выполнения шагов. За основу бралась диаграмма Ганта[7], где в качестве рядов использовались потоки исполнения (каждый на отдельном ядре). Информация о том, в каком конкретно потоке исполнился шаг не собиралась, но диаграмма формировалась по простому принципу: если в потоке n во время t начинает исполняться шаг, значит во всех потоках m, где m < n уже исполняются шаги. Это позволило визуально наблюдать bottle-neck-и и участки плотной загрузки потоков.

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

Результаты работы и выводы

В таблице 1 приведены численные результаты применения алгоритмов планирования.

None - без алгоритма планирования

DDC - использование динамического подсчета ссылок

NPM - использование метода сетевого планирования

PLF - использование ярусно-параллельной формы графа

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

Времена выполнения многопоточного приложения

Табл.1. Численные результаты

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

Из следующей таблицы видно, что алгоритм PLF использует все 8 ядер, в то время, как алгоритм NPM использует только 6 (из-за особенностей алгоритма не удалось загрузить все 8 ядер). Но даже, если сравнить 8-ядерный запуск NPM и 6-ядерный запуск PLF - по-прежнему будет лидировать PLF.

Диаграммы загруженности ядер

Табл.2. Диаграммы загруженности ядер

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

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

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

Возвращаясь к проектному аспекту работы:

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

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

Решение о документировании программного решения было принято с задержкой – ближе к концу Летней школы, что повлияло на малую долю документированного кода (~20-30%). Однако, командой был получен практический опыт написания документаций через приложение doxygen.

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

Ссылки

  1. Система упорядочивания и планирования шагов в библиотеке параллельного программирования Intel® Concurrent Collections, Даниил Скачков - /ru-ru/articles/sistema-yporjadochivanija-shagov-intel-concurrent-collections
  2. Разложение Холецкого - http://alglib.sources.ru/matrixops/symmetric/cholesky.php
  3. Библиотека параллельного программирования Threading Building Blocks - /ru-ru/intel-tbb/
  4. Метод сетевого планирования - http://works.tarefer.ru/100/100052/index.html
  5. Ярусно-параллельная форма графа - http://ru.wikipedia.org/wiki/Ярусно-параллельная_форма_графа
  6. Tulip software - http://tulip.labri.fr/
  7. Диаграмма Ганта – http://ru.wikipedia.org/wiki/Диаграмма_Ганта

Об авторе

Александр Владимирович Макеев магистрант второго курса Физического Факультета НГУ, специальность – Физико-Техническая Информатика. Принимал участие в таких мероприятиях Intel, как «Школа Лидеров Инновационных IT-проектов» 2008 года, «Зимняя школа-стажировка» 2009 года и «Летняя школа-стажировка» 2009 года.

For more complete information about compiler optimizations, see our Optimization Notice.