Graph500

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:24, 10 января 2019.

Graph500 – рейтинг демонстрации скоростных возможностей суперкомпьютеров, оценивающий их мощность по критерию Data intensive. Анонс проекта состоялся на International Supercomputing Conference в июне 2010 как замену Top500, первый список опубликован на ACM/IEEE Supercomputing Conference в ноябре 2010. Рейтинг обновляется каждые полгода. Основной метрикой в рейтинге является GTEPS (10^9 пройденных дуг в секунду).

Также существует разновидность рейтинга Green Graph 500, в котором системы оцениваются по критерию производительности на ватт потребления электроэнергии. Этот вариант был создан по аналогии с Green 500, который использует данные Top500. В настоящий момент рейтинг Graph 500 не используется по причине того, что данная программа устарела.

Необходимость нового рейтинга

Изначально суперкомпьютеры, как известно, создавались для решения вычислительных задач: моделирования физических процессов, инженерных расчетов, баллистики, криптоанализа и т. п., для которых характерна хорошая пространственно-временная локализация данных в памяти, что позволяет эффективно использовать быструю кэш-память процессоров. Для оценки производительности суперкомпьютеров при выполнении такого класса задач (Сache Friendly, СF) хорошо подходит тест Linpack, положенный в основу списка Top500, в 36-й версии которого впервые оказался китайский суперкомпьютер Tianhe-1A c пиковой производительностью 4,702 PFLOPS.

Критика теста Linpack [Источник 1], применяемого для составления рейтингового списка, который приобретает все больше политическое значение, звучала достаточно давно и предлагались разные методики более объективной оценки суперкомпьютеров, например оценочный тестовый набор HPC Challenge. Однако такой популярности, как Top500, ни одна оценка до сих пор не получила в силу сложности тестовых программ и трудности восприятия широкой общественностью. В то же время все большую важность для экономик развитых стран и систем обеспечения национальной безопасности стали приобретать задачи, отличные от CF-класса, новые типы вычислительных задач и приложения обработки больших пулов информации: анализ социальных сетей, выявление заданных и характерных ситуаций (в том числе и террористических угроз) посредством анализа накопленных в неструктурированных базах графового типа оперативно получаемых данных и т. п. Такие задачи сначала называли DIS (Data Intensive System), а сегодня рассматривают их более широко, добавляя еще и затраты на обработку входных/выходных потоков данных — DIC (Data Intensive Computing).

Специфика задач DIC-класса

Для задач DIC-класса характерны: работа с наборами данных, объем которых значительно превышает память вычислительного узла современного суперкомпьютера (до нескольких петабайтов); высокая интенсивность выполнения операций над данными по отношению к вычислительным операциям; высокая непредсказуемость нерегулярно разбросанных по памяти адресов данных; возможность сильного распараллеливания с использованием взаимодействующих друг с другом процессов. Поэтому средств и приемов оптимального выполнения CF-задач для DIC-задач недостаточно, хотя попытки их применения встречаются. Например, по нашему мнению, за редким исключением не имеет смысла использовать различные ускорители на программируемых логических матрицах (FPGA). Как следствие, базовые характеристики суперкомпьютеров, подходящих для решения DIC-задач, должны быть иными, например очень важна способность быстрой передачи вычислений к данным на удаленных узлах посредством аппаратно поддержанного механизма удаленного вызова процедур. Метрики быстродействия также иные, например более адекватны единицы GUPS, определяемые на тесте RandomAccess. Однако эти важные для профессиональной оценки характеристики относятся к архитектурному уровню и явно не связаны с приложениями, поэтому не годятся для составления воспринимаемого общественностью рейтингового списка.

Многие DIC-задачи сводятся к типовым алгоритмам на графах: поиск кратчайшего пути между заданными вершинами; поиск вхождения графа заданного вида в другой граф; поиск вширь и вглубь на графах — задачи BFS (breadth-first search) и DFS (depth-first search); нахождение вершин, через которые проходит наибольшее количество кратчайших путей, — задача BWC (Betweenness Centrality), и др. Некоторые прикладные задачи естественным образом приводятся к задачам на графах, а другие сводятся к графовым. Например, задача BWC может непосредственно использоваться в приложениях реального времени в электроэнергетике для определения наиболее ответственных участков сети и анализа непредвиденных ситуаций, а также в графах, моделирующих в финансовой области зависимости стоимости акций друг от друга. Другой пример — использование графов, моделирующих взаимодействие белков, где требуется находить небольшие графы, изоморфные заданным, чтобы определять свойства и моделировать молекулярные процессы в клетках. В инициативную группу Graph500 входят Cray, SGI, Intel, IBM, AMD, nVidia, Oracle, LexisNexis и др. Кроме того, в группу входят три национальные лаборатории Министерства энергетики США и лаборатория по созданию оружия в Великобритании, три правительственные организации — Национальный научный фонд США, Пентагон и Агентство перспективных оборонных исследований (DARPA), а также 11 университетов и суперкомпьютерных центров.

Руководителем проекта Graph500 является Ричард Мерфи. Он занимается компьютерными архитектурами в Национальной лаборатории Sandia министерства энергетики США, возглавляя одну из групп разработчиков, включенных в исполнители новой программы UHPC (инициированная DARPA программа «вездесущих» высокопроизводительных вычислений Ubiquitous High Performance Computing). Кстати, задачи на графах, причем в более сложном варианте, когда они еще и динамически изменяются, – одно из основных приложений, которое должно успешно решаться на создаваемых в рамках этой программы суперкомпьютерах с революционной архитектурой. Таким образом, за Graph500 стоят серьезные ведомства, и к этому рейтингу стоит относиться соответственно.

Методика Graph500

Тест, используемый для формирования списка Graph500, включает два ядра. Сначала генератор создает граф в виде списка дуг, затем первое ядро порождает его внутреннее представление, которое используется впоследствии вторым ядром, выполняющим алгоритм поиска вширь в графе, – решается задача BFS.

Тест Graph500 имеет два параметра: SCALE и edgefactor; первый задает общее количество (N) вершин графа, которое равно 2SCALE, а второй определяет количество дуг (M) в графе, равное edgefactor*N. По умолчанию edgefactor = 16.


Графы, используемые в приложениях и моделирующие реальный мир (например, социальные сети), имеют большое количество вершин и малое число соседей либо небольшое количество вершин и много соседей. Число вершин, имеющих k соседей, обозначаемое P(k), в таких графах убывает в соответствии с законом P(k) = ck-a (как правило, 2 < a < 3). В таких графах содержится небольшое количество вершин, имеющих настолько большое количество связей, что именно это обеспечивает высокую среднюю связность графа. Такие вершины называются «хабами» (hub). Хабы с разным количеством связей образуют некоторую иерархическую структуру, в которой связность вершин-хабов с переходом на более высокий уровень увеличивается. На рисунке приведен пример сгенерированного в Graph500 графа, в котором цветом и размером вершин обозначено количество соседей у каждой вершины; чем больше вершина и темнее оттенок цвета (используется цветовая модель HSL), тем больше у нее соседей. Знание таких особенностей графов может быть важно при оптимизации теста Graph500.

При генерации графов в Graph500 используется генератор Кронекера, очень похожий на генератор графов типа Recursive MATrix (R-MAT), который в процессе работы использует матрицу смежности создаваемого графа. При добавлении каждой дуги матрица смежности NхN рекурсивно дробится до тех пор, пока не будет получена матрица из одного элемента — это и есть выбранная дуга. Такой процесс повторяется M раз. Матрица на каждом шаге такого рекурсивного процесса дробится на четыре равные части: A, B, C и D. Для каждой из этих частей изначально задана вероятность, с которой происходит выбор именно ее при добавлении новой дуги. По умолчанию вероятности выбора частей матрицы равны: P(A) = 0,57; P(B) = 0,19; P(C) = 0,19; P(D) = 1-(A+B+C) = 0,05.

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

Aлгоритм BFS, выполняемый вторым ядром, для заданного графа и заданной вершины r находит все вершины, расположенные от нее на расстоянии в одну дугу, две дуги и т. д. Особенностью алгоритма является то, что он не должен анализировать вершины, отстоящие от вершины r на расстоянии s+1 до тех пор, пока не проанализирует все вершины, отстоящие от вершины r на расстоянии s дуг. Повторно вершины графа не рассматриваются. В результате работы алгоритма BFS получается дерево, корнем которого является исходная вершина r, а узлы этого дерева — множества вершин графа, находящихся на таком расстоянии от r, которое соответствует уровню этого узла в дереве.

Производительность алгоритма BFS измеряется количеством пройденных дуг графа в секунду (Traversed Edges Per Second, TEPS). Используются обозначения ME/c и GE/c – миллионы и миллиарды пройденных дуг в секунду соответственно.

Рейтинг Graph500 составляется с учетом сначала размера графа, а затем развиваемой в процессе поиска вширь производительности. Существует шесть диапазонов размеров графов, соответствующих значениям параметра SCALE: toy, mini, small, medium, large и huge. Объем данных для toy соответствует примерно 1010 байт (17 Гбайт, SCALE=26), mini — 1011 байт (140 Гбайт, SCALE=29) и т. д., объем данных для huge составляет 1,1 Пбайт (SCALE=42). При SCALЕ=30 количество вершин графа около миллиарда, а самый большой граф при SCALE=42 – четыре триллиона узлов. [Источник 2]

По словам Мерфи, планируется создать версию Graph500 для включения в тесты SPEC и планируется включение в тест дополнительных ядер.

Реализация

Дистрибутив Graph500 включает две последовательные реализации на языке Си, версию на языке высокого уровня GNU Octave, параллельную версию с использованием OpenMP, две параллельные версии для Cray XMT (одна базовая, другая оптимизированная), а также две MPI-версии (одна базовая, с использованием функций двустороннего взаимодействия, другая написана с использованием функций одностороннего взаимодействия нового стандарта MPI 2.0).

Базовая версия для Cray XMT похожа на OpenMP-реализацию с использованием формата CRS (Compress Row Storage) для хранения строк разреженной матрицы смежности, соответствующих вершинам графа. Кроме того, для синхронизации тредов используются теговые биты ячеек памяти и атомарные операции. Cray XMT обладает уникальной возможностью работы с памятью разных вычислительных узлов через единое виртуальное адресное пространство – общую память, это и позволяет использовать OpenMP.

В оптимизированной версии для Cray XMT очередной список достижимых вершин следующего уровня (уровень s+1), который в конечном итоге размещается в общей памяти, формируется в два этапа. Сначала формируются фрагменты этого списка в локальной памяти вычислительных узлов. Затем эти фрагменты включаются в список вершин следующего уровня, находящийся в общей памяти. Суть оптимизации в том, что при добавлении очередного фрагмента счетчик достижимых вершин увеличивается на количество вершин во фрагменте, а не на единицу, если бы каждую достижимую вершину добавляли в отдельности. Это позволяет избежать узкого места, связанного с ожиданием выполнения атомарной операции увеличения счетчика.

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

Характерно, что в реализациях теста Graph500 сразу используется множество средств и стилей программирования, что отражает одну из сторон современной проблематики решения DIC-задач. Для получения результата можно использовать одну из реализаций, но при этом поощряется создание собственных версий. Использование стандартной версии помечается в списке как Reference, использование своей – Optimized.

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

Архитектура

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

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

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

Модель связи процессор / память не улучшится без значительных инвестиций. Это можно увидеть в современных системах памяти, которые поддерживают большую пропускную способность, но уменьшают емкость (на ядро) и уменьшают количество независимых каналов. Ключевые архитектурные методы, включая кеширование, неисполнение или невыполнение, прогнозирование ветвлений и предикаты, были разработаны для того, чтобы процессоры могли справиться с защитой памяти. Современные архитектуры демонстрируют повышенные возможности для структурированного доступа к памяти (как видно из графических процессоров), памяти блокнота для использования высокоскоростных локальных операций и хорошо написанных коммуникаций. Все они предназначены для устранения различий между вычислительными возможностями и коммуникационными каналами, но неясно, будут ли они существенно влиять на проблемы крупномасштабных данных, на примере ядер Graph500.[Источник 4]


Источники

  1. ОБНОВЛЕН GRAPH 500 — РЕЙТИНГ-ОРИЕНТИР В МИРЕ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ // Data 24/7 [2014]. URL: https://data247.ru/2013/11/25/obnovlen-graph-500-rejting-orientir-v-mire-vysokoproizvoditelnyx-vychislenij/ (Дата обращения: 10.01.2019).
  2. Graph500. URL: https://graph500.org/ (Дата обращения: 10.01.2019).
  3. Graph500: адекватный рейтинг // Открытые Системы [1992–2018]. Дата изменения: 08.02.2011. URL: https://www.osp.ru/os/2011/01/13006961/ (Дата обращения: 23.12.2018).
  4. Introducing the graph 500 // ResearchGate [2018]. Дата изменения: 29.01.2010. URL: https://www.researchgate.net/publication/255240580_Introducing_the_graph_500 (Дата обращения: 23.12.2018).