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

Создать новую статью

01.10.2009 13:00


Аннотация

В статье рассказывается о работе над проектом «Система упорядочивания и планирования шагов в библиотеке параллельного программирования Intel® Concurrent Collections». Суть его состояла в том, чтобы выстроить в оптимальном порядке шаги, на которые разбивается задача для выполнения в системе Intel® Concurrent Collections, для обеспечения максимальной эффективности использования вычислительных ресурсов. В результате проведенной работы были получены умопомрачительные результаты!

Введение

Организаторами Летней школы было предложено около 10 задач для исследований, из которых я выбрал задачу № 3 с пугающим названием «Система упорядочивания и планирования шагов в библиотеке параллельного программирования Intel® Concurrent Collections». Над проектом мы работали группой из 3 человек: Николай Алемасов, Александр Макеев и я. Руководители работы: Николай Куртов, Илья Черный.

Библиотека параллельного программирования Intel® Concurrent Collections for C++ является инструментом, облегчающим написание параллельных программ. Для того чтобы использовать данную библиотеку, мы должны разбить задачу на последовательность шагов, указать связи между шагами по данным, или по порядку запуска, передать библиотеке список шагов, исходные данные и подать команду выполнения! Библиотека сама распределит шаги по потокам, и обеспечит их нужными данными. Но все дело в том, что в библиотеке нет средства, позволяющего оптимизировать очередность выполнения шагов. Из-за этого в некоторых достаточно сложных алгоритмах (таких как разложение Холецкого, или алгоритм сжатия Dedup) вычислительные ресурсы используются неэффективно, так как некоторые шаги, исходные данные для которых еще не готовы, вынуждены ожидать данных, тем самым бесполезно загружая процессор. Таким образом, нашей задачей в рамках летней школы было обеспечить упорядочивание шагов выполнения, для повышения эффективности данной библиотеки.

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

После торжественного открытия школы нам не терпелось поскорее приняться за работу. Но сначала необходимо было разобраться с особенностями библиотеки Intel® Concurrent Collections for C++. Наш основной руководитель - Николай Куртов - предоставил нам необходимые материалы и примеры для подробного изучения особенностей самой библиотеки и ее использования. После более детального знакомства с заданием мы сформулировали список задач, которые предполагалось решить во время Летней школы:

  1. Проанализировать граф зависимостей шагов
  2. Произвести статическое планирование выполнения шагов
  3. Произвести анализ времени выполнения различных статических расписаний
  4. Разработать модуль on-line планировщика шагов

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

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

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

  1. раннее (позднее) время начала выполнения подзадачи - то время, которое показывает, в какие промежутки времени требуется запустить подзадачу на исполнение, чтобы она не задержала выполнение всей задачи;
  2. раннее (позднее) время окончания подзадачи - то время, которое показывает, до каких моментов времени требуется завершить выполнение подзадачи, чтобы она не задержала выполнение всей задачи;
  3. резерв времени - количество времени, на которое подзадача может быть задержана, не влияя на время выполнения всей задачи.

Данные параметры получаются обходом сети «в ширину», при котором сначала рассматриваются все текущие потомки. Для получения времен начала обход осуществляется от общего корня сети. Чтобы получить времена окончания, обход идет от общего листа. Если сеть не имеет общего корня или общего листа, то такие вершины легко добавить, не изменяя результатов расчетов. Раннее время начала для текущей подзадачи определяется суммой максимального раннего времени начала среди всех предков и веса дуги, ведущей от этого предка. Позднее время начала определяется как минимальная разность позднего времени начала среди всех потомков и веса дуги, ведущей от него.

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

Использование ярусной параллельной формы графа. Для исходной сети зависимостей подзадач можно построить и расписание параллельного исполнения подзадач. Такое расписание можно назвать ярусно-параллельной формой представления сети. В этом случае каждая строка расписания называется ярусом и допускает параллельное исполнение подзадач в рамках одного яруса.

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

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

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

Наибольшую производительность показал алгоритм с использованием ярусной параллельной формы графа, при использовании которого мы на 1 ядре получили производительность как на 8 ядрах без применения упорядочивания шагов! Вот такие вот результаты!

Во время нашей работы над задачей происходило много забавных вещей, например мы несколько раз перестраивали структуру репозитория, из-за чего иногда возникали некоторые неурядицы с объединением старых и новых версий программ. В некоторые дни для повышения работоспособности наш руководитель – Николай – даже баловал нас шоколадками. А уже под конец школы мы случайно обнаружили возможность использования потоко-небезопасных классов STL в многопоточном приложении, которая заключалась в том, что сначала нужно заполнить объект std::map, а затем обращаться к его элементам.

Развивающая часть

Совместно с работой над задачей во время летней школы мы прослушали ряд лекций, посвященных различным аспектам программирования, высокопроизводительных вычислений и общепрофессиональным навыкам. Но, к сожалению, у нас было очень мало времени для закрепления полученных знаний на практике. Тем не менее, во время практических занятий мы успели написать небольшое приложение для кластера с использованием MPI (и оно даже заработало!), решить задачу с использованием сетей Петри, научились распределять роли в команде а также научились профессионально проводить презентации.

Также мы побывали на экскурсии в центре высокопроизводительных вычислений, в котором нам прочитали очень познавательную лекцию об истории развития суперкомпьютерного центра в Академгородке. В центре мы посетили помещения, в котором расположены современные высокопроизводительные кластеры НКС-160 и НКС-30Т, мощностью 1 и 4,8 ТФлопс.

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

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

Очень хочется упомянуть о самом Академгородке. Городок находится в лесу, поэтому там приятно пройтись по улице (которая на самом деле скорее лес), все расположено близко, и до любого места Академгородка можно легко добраться пешком. В лесу там можно даже увидеть белок, а голуби совсем не боятся людей!

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

Об авторе

Скачков Даниил является студентом факультета инженерной педагогики и информатики Алтайского Государственного Технического Университета им. И. И. Ползунова, специальность - программное обеспечение вычислительной техники и автоматизированных систем. После того, как увидел объявление о проведении Летней школы Intel, заполнил и отправил анкету, выполнил тестовое задание, заключавшееся в решении задачи о нахождении критических путей в графе, прошел телефонное собеседование и был приглашен участвовать в стажировке. Летняя школа проходила в Новосибирске.