ВВЕДЕНИЕ
примеры применения [
В даннои работе рассматривается асинхронная вычислительная модель с управлением
потоком сообщении и ее реализация в виде языка параллельного программирования Charm++ [
Алгоритмы анализа графов на Charm++ являются малоисследованнои областью до настоящего времени, в то время как модель Charm++ хорошо подходит для разработки асинхронных графовых алгоритмов в силу следующих причин:
- объектно-ориентированная модель Charm++ позволяет достаточно просто выражать
графовые алгоритмы в вершинно-ориентированном стиле (vertex-centric), которыи является одним
из наиболее распространенных подходов к работе с графами при решении задач анализа Больших
Данных [
- динамическая балансировка нагрузки, поддерживаемая в системе времени выполнения (runtime-системе) языка Charm++, позволяет осуществлять автоматическую миграцию объектов между узлами вычислительного кластера, что особенно актуально для графовых задач вследствие их нерегулярности, а также несбалансированности реальных графов (например, scale-free графы с распределением степени вершин по степенному закону).
В даннои работе представлены три различных алгоритма реализации PageRank на Charm++,
все три алгоритма являются асинхронными по характеру выполнения модификации рангов
вершин, но с различнои степенью асинхронности. Реализации алгоритмов были протестированы
на синтетически сгенерированных графах типа RMAT [
Далее приводится краткое описание программнои модели Charm++ (раздел 2), описание формальнои постановки задачи PageRank (раздел 3), описание алгоритмов (раздел 4) и анализ результатов оценочного тестирования (раздел 5). В заключении приведены выводы и дальнеишие планы исследовании. ПРОГРАММНАЯ МОДЕЛЬ CHARM++
Язык параллельного программирования Charm++ является расширением языка C++ и
основан на объектно-ориентированнои модели с управлением асинхронным потоком сообщении
[
Базовым объектом в Charm++ является chare (или chare-объект), обладающии помимо всех своиств объектов в С++ (инкапсулированными данными, множеством публичных и приватных методов и т. п.), интерфеисом из специальных entry-методов, вызовы которых соответствуют передаче данных (т. е. сообщении) между chare-объектами.
Приложение в Charm++ состоит из множества chare-объектов, обменивающихся между собои данными посредством вызовов entry-методов. Кроме того, вызов entry-метода порождает выполнение непосредственно самого метода на том узле, где находится chare-объект, entry-метод которого был вызван, то есть таким образом реализуется концепция управления потоком данных или активных сообщений.
В процессе выполнения entry-метода могут быть изменены только данные, принадлежащие chare-объекту. Одновременно у chare-объекта может выполняться не более одного entry-метода, что позволяет избежать проблемы обеспечения атомарности изменения данных, принадлежащих chare-объекту, и значительно упрощает программирование. Схематически программная модель Charm++ представлена на рисунке 1.
Кроме простых chare-объектов Charm++ имеется возможность создавать массивы chareобъектов. При этом массивы бывают как одномерными, так и многомерными. Использование массивов позволяет создавать большое количество chare-объектов, управлять их распределением по вычислительным узлам, выполнять над ними коллективные операции.
В Charm++ поддерживается автоматическая динамическая балансировка нагрузки на вычислительные узлы, что реализуется на уровне runtime-системы за счет перемещения chareобъектов между вычислительными узлами. Для прикладного программиста данная возможность совершенна прозрачна, так как программная модель Charm++ не специфицирует расположение chare-объектов в вычислительнои системе, и все объекты адресуются в едином адресном пространстве.
Основные концепции модели Charm++ были разработаны почти 20 лет назад в то время, когда массово-параллельные системы (вычислительные кластеры) на основе коммерческих микропроцессоров только набирали популярность. Тем не менее, модель Charm++, вобравшая в себя как принципы dataflow-моделеи, так и многопоточных (мультитредовых) моделеи вычислении, оказалась достаточно успешнои и с момента создания почти не претерпевала изменении.
Рис. 1. Программная модель Charm++ ПОСТАНОВКА ЗАДАЧИ PAGERANK
Алгоритм PageRank моделирует процесс случаиного перемещения ("серфинга") пользователя по страницам вэб-сети, при этом перед каждым новым шагом с заданнои вероятностью выбирается одно из двух деиствии: (1) пользователь с равнои вероятностью выбирает одну из гиперссылок (ребро вэб-графа), принадлежащих текущеи странице (вершине вэбграфа), и переходит на страницу по выбраннои ссылке, или (2) пользователь осуществляет "телепортацию" – перемещение на другую страницу, выбранную случаиным образом из всех существующих страниц вэб-сети. Интуитивно понятно, что при таком перемещении, чем больше страница имеет входящих ссылок, тем большее количество раз на нее будет выполнен переход.
Пусть дан ориентированныи граф = ( , ), в котором – это множество вершин, – множество дуг. Тогда ранг вершины в PageRank вычисляется следующим образом: ( ) ( ) = | | + × ∑ ∈ in( ) | ( )|, (1) где – вероятность выбора перехода по исходящеи ссылке (0 < < 1), ( )– множество смежных с вершин, имеющих исходящие дуги, указывающие на , ( )– множество смежных с вершин, на которые указывают исходящие из дуги. В качестве начального значения рангов выбирается | |. АСИНХРОННЫЕ АЛГОРИТМЫ PAGERANK
Наиболее распространеннои схемои вычисления рангов вершин при реализации алгоритма PageRank является итеративная схема, когда на каждом шаге вычисляется новое значение ранга для каждои вершины, при этом между шагами, как правило выполняется барьерная синхронизация, чтобы обеспечить согласованность вычислении. В нашем подходе мы также использовали итерационную схему вычислении, однако адаптировали ее к асинхроннои модели Charm++. На рисунке 2 представлен базовый (или наивный) асинхронный алгоритм PageRank на языке Charm++. Алгоритм является итерационным, на каждой итерации происходит пересчет значений рангов всех вершин. Вершины представлены в виде элементов массива chare-объектов класса PageRankVertex, при этом каждый объект соответствует одной вершине графа. Далее термины вершина и chare-объект можно считать взаимозаменяемыми.
Рис. 2. Базовый алгоритм PageRank на Charm++ В каждои вершине определены два параметра и , в которых хранятся значение ранга вершины для предыдущеи итерации и частично подсчитанное значение ранга на текущеи итерации, соответственно. В начальныи момент времени инициализируется значением| |.
Итерации алгоритма состоят из двух фаз. Первая фаза инициируется вызовом entry-метода doPageRankStep_init у всех вершин. Назначение первои фазы в инициализации текущего шага – обновлении значении и . Вторая фаза инициируется вызовом doPageRankStep_update также у всех вершин. На второи фазе выполняется асинхронное вычисление у всех вершин. При этом каждая вершина рассылает своим смежным вершинам (по исходящим дугам) значение с помощью вызова entry-метода update у соответствующих chare-объектов. Между фазами, так же как и между итерациями, необходимо выполнение барьернои синхронизации. Для этого используется поддерживаемыи в Charm++ механизм обнаружения "тишины" (вызов CkStartQD).
Очевидным недостатком базового алгоритма PageRank является наличие двух глобальных барьерных синхронизации на каждои итерации, что может привести к слабои масштабируемости алгоритма. Для устранения этои проблемы предлагаются следующие два алгоритма: частичноасинхронныи алгоритм PageRank с подсчетом сообщении и полностью асинхронныи алгоритм.
На рисунке 3 приведен псевдокод частично-асинхронного алгоритма PageRank с подсчетом входящих сообщении, в котором количество глобальных барьеров на одну итерацию сокращено до одного барьера. Основная идея алгоритма – использовать подсчет входящих сообщении (вызовов entry-метода update), и после получения последнего сообщения на даннои итерации обновлять значения локальных переменных вершины. Подразумевается, что все вершины имеют информацию о количестве входящих соседеи ( ), так что для ориентированных графов требуется дополнительная предобработка графа. Для подсчета сообщении используется обратныи счетчик . Рис. 3. Алгоритм PageRank с подсчетом сообщений на Charm++ Рис. 4. Полностью асинхронный алгоритм PageRank на Charm++
274 Также необходимо обратить внимание, что работа с переменными хранящими предыдущее и текущее (обновляемое) значения рангов, выполняется через ссылки ( и ), это необходимо для того, чтобы сохранить консистентность этих значении в случае рассинхронизации выполнения методов doPageRank и update.
На рисунке 4 представлен еще одна модификация алгоритма PageRank с полностью асинхронным выполнением обновлении рангов вершин, то есть между итерациями PageRank отсутствует какая-либо синхронизация. Для этого в каждую вершину добавлена ассоциативная таблица [ ], адресуемая по номеру итерации, а в вызов entry-метода update добавлен номер итерации ( ), в рамках которои он выполняется.
Каждая запись [ ]содержит значение ранга вершины на даннои итерации , которое может быть вычисленным или быть в стадии вычисления, и количество сообщении , полученных на даннои итерации от соседних вершин. Когда все сообщения были доставлены для текущеи итерации (т. е. [ ]. = ), то вершина "переходит" на следующую итерацию ( = + 1), рассылает новые значения своим соседям и ожидает новую порцию сообщении и т. д. Необходимо отметить, что в вершину могут приходить сообщения с разными , и тогда информация о них будет попадать в разные записи [ ]. Экспериментальные результаты
В качестве тестовои платформы использовался вычислительныи кластер Ангара-К1 с отечественнои коммуникационнои сетью Ангара. Конфигурация Ангара-К1 включает: (1) 24 двухпроцессорных узла с 6-ядерными процессорами Intel Xeon E5-2630, (2) 12 однопроцессорных узла с 8-ядерными Intel Xeon E5-2660. Все узлы имеют по 64 ГБ оперативнои памяти. Коммуникационная сеть – Ангара с топологиеи 3D-тор (3x3x4).
Для тестирования масштабируемости алгоритмов использовались ориентированные синтетические RMAT графы различного размера (параметр k=16). В качестве генератора использовался соответствующии код из тестового пакета Graph500. Количество итерации PageRank равно 3.
На рисунке 5 приведены графики зависимостеи времени выполнения PageRank от количества используемых узлов кластера (количество используемых ядер в узле было всегда равным 8) при постоянном размере графа (сильная масштабируемость). Таким образом, число вершин графа RMAT-s составляет2 .
Из графиков видно, что, во-первых, базовыи алгоритм PageRank и алгоритм с подсчетом сообщении показывают практически одинаковое время выполнения. С однои стороны, это говорит о достаточно эффективнои реализации механизма обнаружения тишины в Charm++, но, с другои стороны, максимальное количество узлов достаточно мало и негативныи эффект от выполнения барьернои синхронизации не заметен. Во-вторых, полностью асинхронныи алгоритм PageRank имеет более высокую производительность по сравнению с базовым алгоритмом: так, для графа RMAT-20, на одном узле отношение двух алгоритмов составляет 2,5 раза, а на 16 узлах – 3,1 раза. Данное ускорение может быть объяснено несбалансированностью вычислении в рамках однои итерации при выполнении базового алгоритма PageRank (также как и алгоритма с подсчетом сообщении), в то время как в асинхронном алгоритме данная несбалансированность не имеет сильного значения, так как итерации выполняются с перекрытием друг относительно друга.
Также была выполнена реализация базового алгоритма с использованием библиотеки
агрегации сообщении TRAM [
Как видно из рисунка 5 использование библиотеки TRAM для реализации базового алгоритма позволило значительно сократить время выполнения алгоритма по сравнению с нативнои Charm++ реализации: для графа RMAT-20 на одном узле прирост производительности составил 4,22 раза, а на 16 узлах – 5,7 раза. Таким образом, реализация базового алгоритма PageRank с использованием библиотеки TRAM оказалась наиболее эффективнои среди исследуемых реализации PageRank на Charm++. (в) (г) Рис. 5. Время выполнения PageRank на кластере Ангара-К1 для графов RMAT-20 (а), RMAT-22 (б), RMAT-24 (в),
RMAT-26 (г). Режим сильной масштабируемости (в) Рис. 6. Время выполнения PageRank на кластере Ангара-К1 для графов RMAT-16 (а), RMAT-18 (б) и RMAT-20 (в).
Режим слабой масштабируемости На рисунке 6 приведены графики зависимости времени выполнения PageRank от количества используемых узлов кластера (количество используемых ядер в узле – 8) при размере графа с пропорциональным увеличением от числа узлов (слабая масштабируемость). Таким образом, количество вершин графа RMAT-s составляет2 ∗ ∗ , где – количество используемых узлов.
Как видно из графиков на рисунке 6, все эффекты, наблюдаемые в случае сильного масштабирования, проявляются и при слабом масштабировании. Отличие лишь в несколько большеи разнице в производительности между асинхронным PageRank, реализованном с использованием TRAM, и реализациеи на PBGL (особенно для графа RMAT-18). Заключение
В статье представлены три асинхронных алгоритма PageRank, реализованных на языке параллельного программирования Charm++, а также с использованием библиотеки TRAM. Исследование производительности алгоритмов проводилось на 36-узловом вычислительном кластере Ангара-К1 на базе коммуникационнои сети Ангара.
Результаты экспериментов показали, что среди реализации? выполненных на Charm++ наиболее эффективным оказался полностью асинхронныи алгоритм, в котором итерации PageRank выполняются одновременно. Применение библиотеки TRAM для реализации базового алгоритма позволило получить почти 5-кратное увеличение производительности. В сравнении с существующеи реализациеи PageRank в параллельнои библиотеке PBGL реализация PageRank на TRAM показывает незначительно большую эффективность.
В даннои работе на примере задачи PageRank продемонстировано, что с помощью асинхроннои модели вычислении Charm++ (с использованием TRAM) возможно разрабатывать и реализовывать графовые алгоритмы в вершинно-ориентированном стиле (т. е. стиле vertex-centric), при этом производительность таких алгоритмом сопоставима с производительностью решении на базе традиционных моделеи вычислении (в даннои работе – BSP модели и ее реализации в библиотеке PBGL).
В будущем предполагается сравнение Charm++ с другими системами, поддерживающими
асинхронную модель вычислении, такими как AM++ (ActivePebbles) [
Работа выполнена при поддержке гранта РФФИ №15-07-09368.
Литература